Please solving this QP equation

i work on a problem that is so like a SVDD (support vector data description) a new work on SVDD is QSVDD(Quasi support vector data description) that describes more accurately lots of real data sets than SVDD.the pdf of this article is here: www.sersc.org/journals/IJSIP/vol5_no3/5.pdf

The objective of SVDD is to find a sphere or domain with minimum volume containing all or most of the data. let {Xi|i=1,2,...,n} whit d dimention be the given training data set. Let a and R denote the center and radius of the sphere, respectively.This goal is formulated as a constrained convex optimization problem :

where eta is a slack variable that allows the possibility of outliers in the training data set. The parameter C controls the trade-off between the volume and the training errors.

the method of the QSVDD is like a SVDD but the gravity center of the samples has a decisive role.they changed the mathematical model of SVDD as purposful. the goal is to give importance to gravity center of samples and incorporate this idea with SVDD method.Distance between center of sphere and samples gravity center is formulated as:

and proposed idea is formulated as a constrained optimization problem:

the parameter,B,implies the importance degree of gravity center and the parameter, C, has the same role that it has in SVDD method. Constructing the Lagrangian function with Lagrange multipliers gives:

Setting partial derivatives of R, a and ete to zero gives the constraints we can calculate the center of the sphare (a) from this formula:

substituting this constraints in constrained optimization problem give us the dual problem :

This optimization problem is equivalent to a convex quadratic problem with global minimum, when B>-1 holds. solving this problem gives a set αi.

my question is : how can i solve this convex quadratic problem with a quadprog() function in matlab ??????

A training object xi and its corresponding αi satisfy one of this three conditions :

The objects with the coefficients αi>0 are called the support vectors. The radius R of the sphere can be obtained by calculating the distance from the center of the sphere to any support vector with 0<αi<C.

i want to use the idea of QSVDD in my work but i cant solve that QP. please help me and tanks.

Answer 1

[Matt J]

Let X be the matrix whose columns are the x_i. Then, it will be something like the following,

      Q=X.'*X;
      H=2*Q;
      f=-2*B/n*sum(Q,2)+trace(Q)*(1+B);

          H=-H; f=-f; %convert maximization to minimization

      Aeq=ones(1,n);
      beq=1;

      lb(1:n)=0;
      ub(1:n)=C;

      alpha=quadprog(H,f,[],[],Aeq,beq,lb,ub);

[Hassan]

can you explain how can you estimate the H and f ? the way you get this parameters is exactly my question. thank you for your attention

[Matt J]

Ignoring the 1/(1+B) scale factor, the second order term can be factored as follows

   (sum_i alpha_i*x_i.') * (sum_j alpha_j*x_j)
      =(sum_k alpha_k*x_k).' * (sum_k alpha_k*x_k)

which is just norm( X*alpha(:) )^2 or

alpha.'*X.'*X*alpha

Therefore, the Hessian is H=2*X.'*X. The first order terms can be vectorized similarly.

[Hassan]

so by ignoring the scale factor the H and f exactly is the above answer yes??

[Matt J]

Yes, assuming I've done my math right. The scale factor doesn't matter. It doesn't change the location of the minima.

[Hassan]

thank you matt so the argument of quadprog() function should fill with H and f that you mention ?... i am beginner sorry about my questions ...

[Hassan]

sorry again are you sure about your answer? i mean the H and f is exactly is the above answer yes?

[Matt J]

Nope. Depends on how good my algebra was. I leave it to you to check that ;)

[Hassan]

sorry Matt J what is the sum(Q,2) and trace(Q)*(1+B) ? what do you mean sum(Q,2) ?

[Matt J]

These are MATLAB commands and you can find out about them from the doc() command. sum(Q,2) is the summation along the rows of the matrix Q. trace(Q) is the trace of the matrix Q (sum along the diagonal).

[Hassan]

thank you very much matt i understand ....