We propose to select a new set of q variables such that the overall criterion will be optimized. In order to select such a working set, we use the same idea as Joachims : simply search for the optimal gradient-descent direction p which is feasible and which has only q non-null components. The variables corresponding to these components are chosen to be the new working set .
We thus need to minimize:
Since we are searching for an optimal descent direction, which is a direction where the scalar product with the gradient is the smallest, we want indeed to minimize (6). The conditions (7) and (8) are necessary to ensure the feasibility of the obtained direction. The condition (9) is there only to ensure that the problem has a solution. Finally, (10) is imposed because we are searching for a direction with only q non-null components.
Note that the derivative of
can be easily computed:
In order to solve this problem, it thus suffices to consider
Since we are searching for exactly q variables, the must be distinct. We could have to reduce q if one variable is selected twice.
Proof: Let us go back to the minimization
problem of the function
In the case where 2l = q = 2r, it is easy to see that the minimum is obtained for zi = -1 if and zi = 1 if : if for instance zi0 is augmented by for a , then one needs to compensate by another zj to maintain (12). Since we want to minimize (11), the best thing to do, knowing that the are sorted in reverse order and keeping in mind the constraint (13), is to modify zq and thus to fix . Equation (11) is then augmented by , which is a positive value because the are sorted and thus we get out of the minimum.
In the case where
2l > q = 2r, suppose we found a
which is a solution
of (11). Let us denote
the q indices of
the components of
z which are non-null. Using the same
argument as in the previous paragraph, it is clear that
In other words, if
z is a solution of our problem, then
we necessarily have
Considering again the order
of the ,
it becomes evident that we have to take
Our new working set is then composed of the q variables corresponding to the indices ci (where an index corresponds to and an index ci > l corresponds to ).