How to understand the quadratic programming of the inter loop in CPMMC(cutting plane maximum margin clustering) code

Here is the code of the following paper[1], I see that the CCCP_MMC_dual.m is to update the omega/xi/b, can anyone understand the parameters in this 'quadprog' function and why this code decomposites the omega into a product of 'x_mat' and 'XQP'? PS: the objective function is :

    % In this function, we solve the non-convex optimization         problem
    % encountered in the Maximum Margin Clustering via CCCP
    % Input:
    %   omega_0:    initial value for omega
    %   b_0:        initial value for b
    %   xi_0:       initial value for xi
%   C:          regularization parameter in the objective function, soft
%               constraint
%   W:          set of constraints, matrix
%   l:          bound on the label bias
%   MyData:     data set, each sample corresponds to a vector in MyData
%
% Call:     [omega,b,xi] = CCCP_MMC_dual(omega_0,b_0,xi_0,C,epsilon,W,l,MyData)
%
% Author: Bin Zhao
% Created on: 10 July, 2007
% Last updated on : 13 Nov, 2007

function [omega,b,xi] =   CCCP_MMC_dual(omega_0,b_0,xi_0,C,W,l,MyData)

 % Step 1: initialzation
   [nConstraint nData] = size(W); 
   [nDim temp] = size(omega_0); 
   omegaOld = omega_0; 
   bOld = b_0; 
   xiOld = xi_0; 
   fValOld = 0.5 * omegaOld' * omegaOld + C * xiOld; 

   flagQuit = 0;
   perQuit = 0.01; 
% perQuit controls the total step of the CCCP iteration

 iter = 0;
 c_k = mean(W,2);
 s_k = zeros(nConstraint,1);
 z_k = zeros(nDim,nConstraint);
 x_k = sum(MyData,2);
% XOld = rand(nConstraint + 2,1);

% Step 2: CCCP iteration % We solve the QP problem in its dual form, which will be much faster than directly solving the primal problem

while (flagQuit == 0)
  iter = iter + 1;

    temp_z_k = zeros(nDim,nData);
    temp_s_k = zeros(nData,1);
    for iData = 1:nData
        temp_s_k(iData) = sign(omegaOld'*MyData(:,iData)+bOld);
        temp_z_k(:,iData) = temp_s_k(iData) * MyData(:,iData);
    end;

    s_k = W * temp_s_k / nData;
    z_k = temp_z_k * W' / nData;

    x_mat = [z_k,-x_k,x_k];
    HQP = x_mat' * x_mat;
    fQP = [-c_k;l;l];

    AQP = [ones(1,nConstraint),0,0];
    bQP = C;

    Aeq = [-s_k',nData,-nData];
    beq = 0;

    LB = zeros(nConstraint+2,1);
    UB = [inf*ones(1,nConstraint+2)]';

    ops.LargeScale = 'off';
    [XQP,fVal,exitFlag] = quadprog(HQP,fQP,AQP,bQP,Aeq,beq,LB,UB,[],ops);

    omegaOld = x_mat * XQP;
    xiOld = (-fVal - 0.5 * omegaOld' * omegaOld) / C;
    SV_index = find(XQP(1:nConstraint)>0);
    bOld = (c_k(SV_index(1)) - xiOld - omegaOld' * z_k(:,SV_index(1))) / s_k(SV_index(1));

    fVal = 0.5 * omegaOld' * omegaOld + C * xiOld;

    if(fValOld - fVal >= 0 & fValOld - fVal < perQuit * fValOld)
        flagQuit = 1;
    else
        fValOld = fVal;
    end;
end;

omega = omegaOld;
b = bOld;
xi = xiOld;

Reference: [1] Bin Zhao, Fei Wang, Changshui Zhang. Efficient Maximum Margin Clustering Via Cutting Plane Algorithm. The 8th SIAM International Conference on Data Mining (SDM 08). Hyatt Regency Hotel, Atlanta, Georgia. 2008. pp. 751-762. (ORAL)

Answer 1

[Qingqing Zheng]

Finally I get it after scanning the svm. The same as svm, setting dual variable, the objective function can be reformulated into quadratic programming.

Answer 2

[Draga Cvetinovic]

Hi, I was about to try to implement the algorithm described in " Efficient Maximum Margin Clustering Via Cutting Plane Algorithm". Thanks for the clarification about quadprog function. I was wondering if you would have any idea as to what would be the best way to test the implementation of this algorithm (e.g. which data set to use and what should be the expected output) ? Also, could you point me to the original source of this function as I haven't found it anywhere else on the Internet? I know a lot of time has passed, but would really appreciate any suggestion or/and help... Thank you!