Next: Termination Criterion Up: The Decomposition Algorithm Previous: Solving the Subproblem

## Shrinking

The idea of shrinking is to remove some variables whose values have been equal to the bounds 0 or C for a long time, and that will probably not change anymore. To do this, we use the fact that minimizes the problem (3) under the constraints (4) and (5) if and only if there exists numbers , , that verify the following KKT conditions:

 (24)

 (25)

 (26)

 (27)

 (28)

 (29)

 (30)

Note that if , then the corresponding variable is equal to 0. Also, if , then the corresponding variable is equal to C. The idea is thus to search at each iteration for variables , and that verify as well as possible3 the equations (24)-(28), and to remove a variable whose value is equal to 0 if its coefficient is strictly positive (or just above a constant ) during a given number of iterations. Using the same idea, we also eliminate a variable whose value is equal to Cif its coefficient stays strictly positive for a sufficient number of iterations.

To estimate or , we start by estimating (note that if then and if then ). Noting

we have (with standing for an estimation of ) :

 (31)

Then if we have

 (32)

and if a variable stays a sufficient number of iterations at 0 (or C) with its corresponding coefficient (or ), then we remove it from the problem. Note that this can lead to an incorrect solution if or the number of iterations before removing a variable is too small. This is verified in the experimental section.

Next: Termination Criterion Up: The Decomposition Algorithm Previous: Solving the Subproblem
Journal of Machine Learning Research