3. LSVM (Lagrangian Support Vector Machine) Algorithm

Before stating our algorithm we define two matrices to simplify
notation as follows:

It will be understood that within the LSVM Algorithm, the single time that is computed at the outset of the algorithm, the SMW identity (1) will be used. Hence only an matrix is inverted.

The LSVM Algorithm is based directly on the Karush-Kuhn-Tucker
necessary and sufficient optimality conditions
[15, KTP 7.2.4, page 94] for the dual problem (11):

the optimality condition (12) can be written in the following equivalent form for any positive :

These optimality conditions lead to the following very simple iterative scheme which constitutes our LSVM Algorithm:

for which we will establish global linear convergence from any starting point under the easily satisfiable condition:

We impose this condition as in all our experiments, where is the parameter of our SVM formulation (7). It turns out, and this is the way that led us to this iterative scheme, that the optimality condition (14), is also the necessary and sufficient condition for the unconstrained minimum of the implicit Lagrangian [21] associated with the dual problem (11):

Setting the gradient with respect to of this convex and differentiable Lagrangian to zero gives

or equivalently:

which is equivalent to the optimality condition (14) under the assumption that is positive and not an eigenvalue of .

We establish now the global linear convergence of the iteration (15) under condition (16).

Using the Projection Theorem [1, Proposition 2.1.3] which states that the distance between any two points in is not less than the distance between their projections on any convex set (the nonnegative orthant here) in , the above equation gives:

All we need to show now is that . This follows from (16) as follows. Noting the definition (10) of and letting , , denote the nonnegative eigenvalues of , all we need is:

or equivalently:

which is satisfied under the assumption (16).

We give now a complete MATLAB [26] code of LSVM which is
capable of solving problems with millions of points using only native
MATLAB commands.
The input parameters, besides , and of (10),
which define the problem, are: itmax, the maximum number of iterations
and tol, the tolerated nonzero error in
at
termination. The quantity
bounds from above:

function [it, opt, w, gamma] = svml(A,D,nu,itmax,tol) % lsvm with SMW for min 1/2*u'*Q*u-e'*u s.t. u=>0, % Q=I/nu+H*H', H=D[A -e] % Input: A, D, nu, itmax, tol; Output: it, opt, w, gamma % [it, opt, w, gamma] = svml(A,D,nu,itmax,tol); [m,n]=size(A);alpha=1.9/nu;e=ones(m,1);H=D*[A -e];it=0; S=H*inv((speye(n+1)/nu+H'*H)); u=nu*(1-S*(H'*e));oldu=u+1; while it<itmax & norm(oldu-u)>tol z=(1+pl(((u/nu+H*(H'*u))-alpha*u)-1)); oldu=u; u=nu*(z-S*(H'*z)); it=it+1; end; opt=norm(u-oldu);w=A'*D*u;gamma=-e'*D*u; function pl = pl(x); pl = (abs(x)+x)/2;