QPBSVMLib.cpp

Go to the documentation of this file.
00001 /*-----------------------------------------------------------------------
00002  *
00003  * This program is free software; you can redistribute it and/or modify
00004  * it under the terms of the GNU General Public License as published by
00005  * the Free Software Foundation; either version 3 of the License, or
00006  * (at your option) any later version.
00007  *
00008  * Library for solving QP task required for learning SVM without bias term.
00009  *
00010  * Written (W) 2006-2009 Vojtech Franc, xfrancv@cmp.felk.cvut.cz
00011  * Written (W) 2007 Soeren Sonnenburg
00012  * Copyright (C) 2006-2009 Center for Machine Perception, CTU FEL Prague
00013  * Copyright (C) 2007-2009 Fraunhofer Institute FIRST
00014  *
00015  *
00016  *  min 0.5*x'*H*x + f'*x
00017  *
00018  *  subject to  C >= x(i) >= 0 for all i
00019  *
00020  * H [dim x dim] is symmetric positive semi-definite matrix.
00021  * f [dim x 1] is an arbitrary vector.
00022  *
00023  * The precision of found solution is given by parameters 
00024  * tmax, tolabs, tolrel which define the stopping conditions:
00025  *
00026  *    t >= tmax                   ->  exit_flag = 0  Number of iterations.
00027  *    UB-LB <= tolabs             ->  exit_flag = 1  Abs. tolerance.
00028  *    UB-LB <= UB*tolrel          ->  exit_flag = 2  Relative tolerance.
00029  *
00030  * UB ... Upper bound on the optimal solution.
00031  * LB ... Lower bound on the optimal solution.
00032  * t  ... Number of iterations.
00033  * History ... Value of LB and UB wrt. number of iterations.
00034  *
00035  * 1. Generalized Gauss-Seidel methods
00036  * exitflag = qpbsvm_sca( &get_col, diag_H, f, UB, dim, tmax, 
00037  *               tolabs, tolrel, x, Nabla, &t, &History, verb )
00038  *
00039  * 2. Greedy variant - Udpate variable yielding the best improvement.
00040  * exitflag = qpbsvm_scas( &get_col, diag_H, f, UB, dim, tmax, 
00041  *               tolabs, tolrel, x, Nabla, &t, &History, verb )
00042  *
00043  * 3. Updates variable which most violates the KKT conditions
00044  * exitflag = qpbsvm_scamv( &get_col, diag_H, f, UB, dim, tmax, 
00045  *               tolabs, tolrel, tolKKT, x, Nabla, &t, &History, verb )
00046  *
00047 -------------------------------------------------------------------- */
00048 
00049 #include <math.h>
00050 #include <string.h>
00051 #include <limits.h>
00052 
00053 #include <shogun/lib/config.h>
00054 #include <shogun/io/SGIO.h>
00055 #include <shogun/mathematics/Cplex.h>
00056 #include <shogun/mathematics/Math.h>
00057 
00058 #include <shogun/classifier/svm/QPBSVMLib.h>
00059 #include <shogun/classifier/svm/pr_loqo.h>
00060 
00061 using namespace shogun;
00062 
00063 #define HISTORY_BUF 1000000
00064 
00065 #define INDEX(ROW,COL,DIM) ((COL*DIM)+ROW)
00066 
00067 CQPBSVMLib::CQPBSVMLib(void)
00068 {
00069     SG_UNSTABLE("CQPBSVMLib::CQPBSVMLib(void)", "\n");
00070 
00071     m_H=0;
00072     m_dim = 0;
00073     m_diag_H = NULL;
00074 
00075     m_f = NULL;
00076     m_UB = 0.0;
00077     m_tmax = INT_MAX;
00078     m_tolabs = 0;
00079     m_tolrel = 1e-6;
00080     m_tolKKT = 0;
00081     m_solver = QPB_SOLVER_SCA;
00082 }
00083 
00084 CQPBSVMLib::CQPBSVMLib(
00085     float64_t* H, int32_t n, float64_t* f, int32_t m, float64_t UB)
00086 : CSGObject()
00087 {
00088     ASSERT(H && n>0);
00089     m_H=H;
00090     m_dim = n;
00091     m_diag_H=NULL;
00092 
00093     m_f=f;
00094     m_UB=UB;
00095     m_tmax = INT_MAX;
00096     m_tolabs = 0;
00097     m_tolrel = 1e-6;
00098     m_tolKKT = 0;
00099     m_solver = QPB_SOLVER_SCA;
00100 }
00101 
00102 CQPBSVMLib::~CQPBSVMLib()
00103 {
00104     SG_FREE(m_diag_H);
00105 }
00106 
00107 int32_t CQPBSVMLib::solve_qp(float64_t* result, int32_t len)
00108 {
00109     int32_t status = -1;
00110     ASSERT(len==m_dim);
00111     float64_t* Nabla=SG_MALLOC(float64_t, m_dim);
00112     for (int32_t i=0; i<m_dim; i++)
00113         Nabla[i]=m_f[i];
00114 
00115     SG_FREE(m_diag_H);
00116     m_diag_H=SG_MALLOC(float64_t, m_dim);
00117 
00118     for (int32_t i=0; i<m_dim; i++)
00119         m_diag_H[i]=m_H[i*m_dim+i];
00120 
00121     float64_t* History=NULL;
00122     int32_t t;
00123     int32_t verb=0;
00124 
00125     switch (m_solver)
00126     {
00127         case QPB_SOLVER_GRADDESC:
00128             status = qpbsvm_gradient_descent(result, Nabla, &t, &History, verb );
00129             break;
00130         case QPB_SOLVER_GS:
00131             status = qpbsvm_gauss_seidel(result, Nabla, &t, &History, verb );
00132             break;
00133         case QPB_SOLVER_SCA:
00134             status = qpbsvm_sca(result, Nabla, &t, &History, verb );
00135             break;
00136         case QPB_SOLVER_SCAS:
00137             status = qpbsvm_scas(result, Nabla, &t, &History, verb );
00138             break;
00139         case QPB_SOLVER_SCAMV:
00140             status = qpbsvm_scamv(result, Nabla, &t, &History, verb );
00141             break;
00142         case QPB_SOLVER_PRLOQO:
00143             status = qpbsvm_prloqo(result, Nabla, &t, &History, verb );
00144             break;
00145 #ifdef USE_CPLEX
00146         case QPB_SOLVER_CPLEX:
00147             status = qpbsvm_cplex(result, Nabla, &t, &History, verb );
00148 #else
00149             SG_ERROR("cplex not enabled at compile time - unknow solver\n");
00150 #endif
00151             break;
00152         default:
00153             SG_ERROR("unknown solver\n");
00154             break;
00155     }
00156 
00157     SG_FREE(History);
00158     SG_FREE(Nabla);
00159     SG_FREE(m_diag_H);
00160     m_diag_H=NULL;
00161 
00162     return status;
00163 }
00164 
00165 /* --------------------------------------------------------------
00166 
00167 Usage: exitflag = qpbsvm_sca(m_UB, m_dim, m_tmax, 
00168                m_tolabs, m_tolrel, m_tolKKT, x, Nabla, &t, &History, verb )
00169 
00170 -------------------------------------------------------------- */
00171 int32_t CQPBSVMLib::qpbsvm_sca(float64_t *x,
00172             float64_t *Nabla,
00173             int32_t   *ptr_t,
00174             float64_t **ptr_History,
00175             int32_t   verb)
00176 {
00177   float64_t *History;
00178   float64_t *col_H;
00179   float64_t *tmp_ptr;
00180   float64_t x_old;
00181   float64_t delta_x;
00182   float64_t xHx;
00183   float64_t Q_P;
00184   float64_t Q_D;
00185   float64_t xf;
00186   float64_t xi_sum;
00187   int32_t History_size;
00188   int32_t t;
00189   int32_t i, j;
00190   int32_t exitflag;
00191   int32_t KKTsatisf;
00192 
00193   /* ------------------------------------------------------------ */
00194   /* Initialization                                               */
00195   /* ------------------------------------------------------------ */
00196 
00197   t = 0;
00198 
00199   History_size = (m_tmax < HISTORY_BUF ) ? m_tmax+1 : HISTORY_BUF;
00200   History=SG_MALLOC(float64_t, History_size*2);
00201   memset(History, 0, sizeof(float64_t)*History_size*2);
00202 
00203   /* compute Q_P and Q_D */
00204   xHx = 0;
00205   xf = 0;
00206   xi_sum = 0;
00207   for(i = 0; i < m_dim; i++ ) {
00208     xHx += x[i]*(Nabla[i] - m_f[i]);
00209     xf += x[i]*m_f[i];
00210     xi_sum += CMath::max(0.0,-Nabla[i]);
00211   }
00212 
00213   Q_P = 0.5*xHx + xf;
00214   Q_D = -0.5*xHx - m_UB*xi_sum;
00215   History[INDEX(0,t,2)] = Q_P;
00216   History[INDEX(1,t,2)] = Q_D;
00217 
00218   if( verb > 0 ) {
00219     SG_PRINT("%d: Q_P=%m_f, Q_D=%m_f, Q_P-Q_D=%m_f, (Q_P-Q_D)/|Q_P|=%m_f \n",
00220      t, Q_P, Q_D, Q_P-Q_D,(Q_P-Q_D)/CMath::abs(Q_P));
00221   }
00222 
00223   exitflag = -1;
00224   while( exitflag == -1 ) 
00225   {
00226     t++;     
00227  
00228     for(i = 0; i < m_dim; i++ ) {
00229       if( m_diag_H[i] > 0 ) {
00230         /* variable update */
00231         x_old = x[i];
00232         x[i] = CMath::min(m_UB,CMath::max(0.0, x[i] - Nabla[i]/m_diag_H[i]));
00233         
00234         /* update Nabla */
00235         delta_x = x[i] - x_old;
00236         if( delta_x != 0 ) {
00237           col_H = (float64_t*)get_col(i);
00238           for(j = 0; j < m_dim; j++ ) {
00239             Nabla[j] += col_H[j]*delta_x;
00240           }
00241         }   
00242 
00243       }
00244     }
00245 
00246     /* compute Q_P and Q_D */
00247     xHx = 0;
00248     xf = 0;
00249     xi_sum = 0;
00250     KKTsatisf = 1;
00251     for(i = 0; i < m_dim; i++ ) {
00252       xHx += x[i]*(Nabla[i] - m_f[i]);
00253       xf += x[i]*m_f[i];
00254       xi_sum += CMath::max(0.0,-Nabla[i]);
00255 
00256       if((x[i] > 0 && x[i] < m_UB && CMath::abs(Nabla[i]) > m_tolKKT) || 
00257          (x[i] == 0 && Nabla[i] < -m_tolKKT) ||
00258          (x[i] == m_UB && Nabla[i] > m_tolKKT)) KKTsatisf = 0;
00259     }
00260 
00261     Q_P = 0.5*xHx + xf;
00262     Q_D = -0.5*xHx - m_UB*xi_sum;
00263 
00264     /* stopping conditions */
00265     if(t >= m_tmax) exitflag = 0;
00266     else if(Q_P-Q_D <= m_tolabs) exitflag = 1;
00267     else if(Q_P-Q_D <= CMath::abs(Q_P)*m_tolrel) exitflag = 2;
00268     else if(KKTsatisf == 1) exitflag = 3;
00269 
00270     if( verb > 0 && (t % verb == 0 || t==1)) {
00271       SG_PRINT("%d: Q_P=%m_f, Q_D=%m_f, Q_P-Q_D=%m_f, (Q_P-Q_D)/|Q_P|=%m_f \n",
00272         t, Q_P, Q_D, Q_P-Q_D,(Q_P-Q_D)/CMath::abs(Q_P));
00273     }
00274 
00275     /* Store m_UB LB to History buffer */
00276     if( t < History_size ) {
00277       History[INDEX(0,t,2)] = Q_P;
00278       History[INDEX(1,t,2)] = Q_D;
00279     }
00280     else {
00281       tmp_ptr=SG_MALLOC(float64_t, (History_size+HISTORY_BUF)*2);
00282       memset(tmp_ptr, 0, sizeof(float64_t)*(History_size+HISTORY_BUF)*2);
00283 
00284       for( i = 0; i < History_size; i++ ) {
00285         tmp_ptr[INDEX(0,i,2)] = History[INDEX(0,i,2)];
00286         tmp_ptr[INDEX(1,i,2)] = History[INDEX(1,i,2)];
00287       }
00288       tmp_ptr[INDEX(0,t,2)] = Q_P;
00289       tmp_ptr[INDEX(1,t,2)] = Q_D;
00290       
00291       History_size += HISTORY_BUF;
00292       SG_FREE(History);
00293       History = tmp_ptr;
00294     }
00295   }
00296 
00297   (*ptr_t) = t;
00298   (*ptr_History) = History;
00299 
00300   SG_PRINT("QP: %f QD: %f\n", Q_P, Q_D);
00301 
00302   return( exitflag ); 
00303 }
00304 
00305 
00306 /* --------------------------------------------------------------
00307 
00308 Usage: exitflag = qpbsvm_scas(m_UB, m_dim, m_tmax, 
00309                m_tolabs, m_tolrel, m_tolKKT, x, Nabla, &t, &History, verb )
00310 
00311 -------------------------------------------------------------- */
00312 int32_t CQPBSVMLib::qpbsvm_scas(float64_t *x,
00313             float64_t *Nabla,
00314             int32_t   *ptr_t,
00315             float64_t **ptr_History,
00316             int32_t   verb)
00317 {
00318   float64_t *History;
00319   float64_t *col_H;
00320   float64_t *tmp_ptr;
00321   float64_t x_old;
00322   float64_t x_new;
00323   float64_t delta_x;
00324   float64_t max_x=CMath::INFTY;
00325   float64_t xHx;
00326   float64_t Q_P;
00327   float64_t Q_D;
00328   float64_t xf;
00329   float64_t xi_sum;
00330   float64_t max_update;
00331   float64_t curr_update;
00332   int32_t History_size;
00333   int32_t t;
00334   int32_t i, j;
00335   int32_t max_i=-1;
00336   int32_t exitflag;
00337   int32_t KKTsatisf;
00338 
00339   /* ------------------------------------------------------------ */
00340   /* Initialization                                               */
00341   /* ------------------------------------------------------------ */
00342 
00343   t = 0;
00344 
00345   History_size = (m_tmax < HISTORY_BUF ) ? m_tmax+1 : HISTORY_BUF;
00346   History=SG_MALLOC(float64_t, History_size*2);
00347   memset(History, 0, sizeof(float64_t)*History_size*2);
00348 
00349   /* compute Q_P and Q_D */
00350   xHx = 0;
00351   xf = 0;
00352   xi_sum = 0;
00353   for(i = 0; i < m_dim; i++ ) {
00354     xHx += x[i]*(Nabla[i] - m_f[i]);
00355     xf += x[i]*m_f[i];
00356     xi_sum += CMath::max(0.0,-Nabla[i]);
00357   }
00358 
00359   Q_P = 0.5*xHx + xf;
00360   Q_D = -0.5*xHx - m_UB*xi_sum;
00361   History[INDEX(0,t,2)] = Q_P;
00362   History[INDEX(1,t,2)] = Q_D;
00363 
00364   if( verb > 0 ) {
00365     SG_PRINT("%d: Q_P=%m_f, Q_D=%m_f, Q_P-Q_D=%m_f, (Q_P-Q_D)/|Q_P|=%m_f \n",
00366      t, Q_P, Q_D, Q_P-Q_D,(Q_P-Q_D)/CMath::abs(Q_P));
00367   }
00368 
00369   exitflag = -1;
00370   while( exitflag == -1 ) 
00371   {
00372     t++;     
00373 
00374     max_update = -CMath::INFTY;
00375     for(i = 0; i < m_dim; i++ ) {
00376       if( m_diag_H[i] > 0 ) { 
00377         /* variable update */
00378         x_old = x[i];
00379         x_new = CMath::min(m_UB,CMath::max(0.0, x[i] - Nabla[i]/m_diag_H[i]));
00380   
00381         curr_update = -0.5*m_diag_H[i]*(x_new*x_new-x_old*x_old) - 
00382           (Nabla[i] - m_diag_H[i]*x_old)*(x_new - x_old);
00383 
00384         if( curr_update > max_update ) {
00385           max_i = i;
00386           max_update = curr_update;
00387           max_x = x_new;
00388         }
00389       } 
00390     }                                                                                            
00391 
00392     x_old = x[max_i];
00393     x[max_i] = max_x;
00394 
00395     /* update Nabla */
00396     delta_x = max_x - x_old;
00397     if( delta_x != 0 ) {
00398       col_H = (float64_t*)get_col(max_i);
00399       for(j = 0; j < m_dim; j++ ) {
00400         Nabla[j] += col_H[j]*delta_x;
00401       }
00402     }   
00403 
00404     /* compute Q_P and Q_D */
00405     xHx = 0;
00406     xf = 0;
00407     xi_sum = 0;
00408     KKTsatisf = 1;
00409     for(i = 0; i < m_dim; i++ ) {
00410       xHx += x[i]*(Nabla[i] - m_f[i]);
00411       xf += x[i]*m_f[i];
00412       xi_sum += CMath::max(0.0,-Nabla[i]);
00413 
00414       if((x[i] > 0 && x[i] < m_UB && CMath::abs(Nabla[i]) > m_tolKKT) || 
00415          (x[i] == 0 && Nabla[i] < -m_tolKKT) ||
00416          (x[i] == m_UB && Nabla[i] > m_tolKKT)) KKTsatisf = 0;
00417     }
00418 
00419     Q_P = 0.5*xHx + xf;
00420     Q_D = -0.5*xHx - m_UB*xi_sum;
00421 
00422     /* stopping conditions */
00423     if(t >= m_tmax) exitflag = 0;
00424     else if(Q_P-Q_D <= m_tolabs) exitflag = 1;
00425     else if(Q_P-Q_D <= CMath::abs(Q_P)*m_tolrel) exitflag = 2;
00426     else if(KKTsatisf == 1) exitflag = 3;
00427 
00428     if( verb > 0 && (t % verb == 0 || t==1)) {
00429       SG_PRINT("%d: Q_P=%m_f, Q_D=%m_f, Q_P-Q_D=%m_f, (Q_P-Q_D)/|Q_P|=%m_f \n",
00430         t, Q_P, Q_D, Q_P-Q_D,(Q_P-Q_D)/CMath::abs(Q_P));
00431     }
00432 
00433     /* Store m_UB LB to History buffer */
00434     if( t < History_size ) {
00435       History[INDEX(0,t,2)] = Q_P;
00436       History[INDEX(1,t,2)] = Q_D;
00437     }
00438     else {
00439       tmp_ptr=SG_MALLOC(float64_t, (History_size+HISTORY_BUF)*2);
00440       memset(tmp_ptr, 0, (History_size+HISTORY_BUF)*2*sizeof(float64_t));
00441       for( i = 0; i < History_size; i++ ) {
00442         tmp_ptr[INDEX(0,i,2)] = History[INDEX(0,i,2)];
00443         tmp_ptr[INDEX(1,i,2)] = History[INDEX(1,i,2)];
00444       }
00445       tmp_ptr[INDEX(0,t,2)] = Q_P;
00446       tmp_ptr[INDEX(1,t,2)] = Q_D;
00447       
00448       History_size += HISTORY_BUF;
00449       SG_FREE(History);
00450       History = tmp_ptr;
00451     }
00452   }
00453 
00454   (*ptr_t) = t;
00455   (*ptr_History) = History;
00456 
00457   return( exitflag ); 
00458 }
00459 
00460 /* --------------------------------------------------------------
00461 
00462 Usage: exitflag = qpbsvm_scamv(m_UB, m_dim, m_tmax, 
00463                m_tolabs, m_tolrel, m_tolKKT, x, Nabla, &t, &History, verb )
00464 
00465 -------------------------------------------------------------- */
00466 int32_t CQPBSVMLib::qpbsvm_scamv(float64_t *x,
00467             float64_t *Nabla,
00468             int32_t   *ptr_t,
00469             float64_t **ptr_History,
00470             int32_t   verb)
00471 {
00472   float64_t *History;
00473   float64_t *col_H;
00474   float64_t delta_x;
00475   float64_t x_new;
00476   float64_t max_viol;
00477   float64_t fval;
00478   int32_t t;
00479   int32_t i;
00480   int32_t u=-1;
00481   int32_t exitflag;
00482 
00483   /* ------------------------------------------------------------ */
00484   /* Initialization                                               */
00485   /* ------------------------------------------------------------ */
00486 
00487   t = 0;
00488   exitflag = -1;
00489   while( exitflag == -1 && t <= m_tmax) 
00490   {
00491     t++;     
00492 
00493     max_viol = 0;
00494     for(i = 0; i < m_dim; i++ ) 
00495     {      
00496       if( x[i] == 0 )
00497       {
00498         if( max_viol < -Nabla[i]) { u = i; max_viol = -Nabla[i]; }
00499       }
00500       else if( x[i] > 0 && x[i] < m_UB )
00501       {
00502         if( max_viol < CMath::abs(Nabla[i]) ) { u = i; max_viol = CMath::abs(Nabla[i]); } 
00503       }
00504       else if( max_viol < Nabla[i]) { u = i; max_viol = Nabla[i]; }
00505     }
00506 
00507 /*    SG_PRINT("%d: max_viol=%m_f, u=%d\n", t, max_viol, u);*/
00508 
00509     if( max_viol <= m_tolKKT ) 
00510     {
00511       exitflag = 1;
00512     } 
00513     else
00514     {
00515       /* update */
00516       x_new = CMath::min(m_UB,CMath::max(0.0, x[u] - Nabla[u]/m_diag_H[u]));
00517 
00518       delta_x = x_new - x[u];
00519       x[u] = x_new;
00520 
00521       col_H = (float64_t*)get_col(u);
00522       for(i = 0; i < m_dim; i++ ) {
00523         Nabla[i] += col_H[i]*delta_x;
00524       }
00525     }
00526   }
00527 
00528   History=SG_MALLOC(float64_t, (t+1)*2);
00529   memset(History, 0, sizeof(float64_t)*(t+1)*2);
00530 
00531   fval = 0;
00532   for(fval = 0, i = 0; i < m_dim; i++ ) {
00533     fval += 0.5*x[i]*(Nabla[i]+m_f[i]);
00534   }
00535 
00536   History[INDEX(0,t,2)] = fval;
00537   History[INDEX(1,t,2)] = 0;
00538 
00539   (*ptr_t) = t;
00540   (*ptr_History) = History;
00541 
00542 
00543 
00544   return( exitflag ); 
00545 }
00546 
00547 /* --------------------------------------------------------------
00548 
00549 Usage: exitflag = qpbsvm_prloqo(m_UB, m_dim, m_tmax, 
00550                m_tolabs, m_tolrel, m_tolKKT, x, Nabla, &t, &History, verb )
00551 
00552 -------------------------------------------------------------- */
00553 int32_t CQPBSVMLib::qpbsvm_prloqo(float64_t *x,
00554             float64_t *Nabla,
00555             int32_t   *ptr_t,
00556             float64_t **ptr_History,
00557             int32_t   verb)
00558 {
00559     float64_t* lb=SG_MALLOC(float64_t, m_dim);
00560     float64_t* ub=SG_MALLOC(float64_t, m_dim);
00561     float64_t* primal=SG_MALLOC(float64_t, 3*m_dim);
00562     float64_t* dual=SG_MALLOC(float64_t, 1+2*m_dim);
00563     float64_t* a=SG_MALLOC(float64_t, m_dim);
00564 
00565     for (int32_t i=0; i<m_dim; i++)
00566     {
00567         a[i]=0.0;
00568         lb[i]=0;
00569         ub[i]=m_UB;
00570     }
00571 
00572     float64_t b=0;
00573 
00574     CMath::display_vector(m_f, m_dim, "m_f");
00575     int32_t result=pr_loqo(m_dim, 1, m_f, m_H, a, &b, lb, ub, primal, dual,
00576             2, 5, 1, -0.95, 10,0);
00577 
00578     SG_FREE(a);
00579     SG_FREE(lb);
00580     SG_FREE(ub);
00581     SG_FREE(primal);
00582     SG_FREE(dual);
00583 
00584     *ptr_t=0;
00585     *ptr_History=NULL;
00586     return result;
00587 }
00588 
00589 int32_t CQPBSVMLib::qpbsvm_gauss_seidel(float64_t *x,
00590             float64_t *Nabla,
00591             int32_t   *ptr_t,
00592             float64_t **ptr_History,
00593             int32_t   verb)
00594 {
00595     for (int32_t i=0; i<m_dim; i++)
00596         x[i]=CMath::random(0.0, 1.0);
00597 
00598     for (int32_t t=0; t<200; t++)
00599     {
00600         for (int32_t i=0; i<m_dim; i++)
00601         {
00602             x[i]= (-m_f[i]-(CMath::dot(x,&m_H[m_dim*i], m_dim) -
00603                         m_H[m_dim*i+i]*x[i]))/m_H[m_dim*i+i];
00604             x[i]=CMath::clamp(x[i], 0.0, 1.0);
00605         }
00606     }
00607 
00608     int32_t atbound=0;
00609     for (int32_t i=0; i<m_dim; i++)
00610     {
00611         if (x[i]==0.0 || x[i]==1.0)
00612             atbound++;
00613     }
00614     SG_PRINT("atbound:%d of %d (%2.2f%%)\n", atbound, m_dim, ((float64_t) 100.0*atbound)/m_dim);
00615     *ptr_t=0;
00616     *ptr_History=NULL;
00617     return 0;
00618 }
00619 
00620 int32_t CQPBSVMLib::qpbsvm_gradient_descent(float64_t *x,
00621             float64_t *Nabla,
00622             int32_t   *ptr_t,
00623             float64_t **ptr_History,
00624             int32_t   verb)
00625 {
00626     for (int32_t i=0; i<m_dim; i++)
00627         x[i]=CMath::random(0.0, 1.0);
00628 
00629     for (int32_t t=0; t<2000; t++)
00630     {
00631         for (int32_t i=0; i<m_dim; i++)
00632         {
00633             x[i]-=0.001*(CMath::dot(x,&m_H[m_dim*i], m_dim)+m_f[i]);
00634             x[i]=CMath::clamp(x[i], 0.0, 1.0);
00635         }
00636     }
00637 
00638     int32_t atbound=0;
00639     for (int32_t i=0; i<m_dim; i++)
00640     {
00641         if (x[i]==0.0 || x[i]==1.0)
00642             atbound++;
00643     }
00644     SG_PRINT("atbound:%d of %d (%2.2f%%)\n", atbound, m_dim, ((float64_t) 100.0*atbound)/m_dim);
00645     *ptr_t=0;
00646     *ptr_History=NULL;
00647     return 0;
00648 }
00649 
00650 #ifdef USE_CPLEX
00651 /* --------------------------------------------------------------
00652 
00653 Usage: exitflag = qpbsvm_prloqo(m_UB, m_dim, m_tmax, 
00654                m_tolabs, m_tolrel, m_tolKKT, x, Nabla, &t, &History, verb )
00655 
00656 -------------------------------------------------------------- */
00657 int32_t CQPBSVMLib::qpbsvm_cplex(float64_t *x,
00658             float64_t *Nabla,
00659             int32_t   *ptr_t,
00660             float64_t **ptr_History,
00661             int32_t   verb)
00662 {
00663     float64_t* lb=SG_MALLOC(float64_t, m_dim);
00664     float64_t* ub=SG_MALLOC(float64_t, m_dim);
00665 
00666     for (int32_t i=0; i<m_dim; i++)
00667     {
00668         lb[i]=0;
00669         ub[i]=m_UB;
00670     }
00671 
00672     CCplex cplex;
00673     cplex.init(E_QP);
00674     cplex.setup_lp(m_f, NULL, 0, m_dim, NULL, lb, ub);
00675     cplex.setup_qp(m_H, m_dim);
00676     cplex.optimize(x);
00677     cplex.cleanup();
00678 
00679     SG_FREE(lb);
00680     SG_FREE(ub);
00681 
00682     *ptr_t=0;
00683     *ptr_History=NULL;
00684     return 0;
00685 }
00686 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation