Skip to content

Commit

Permalink
Improved libqp GSMO solver
Browse files Browse the repository at this point in the history 
Reformatted spaces to tabs
Added checks of initial guess
  • Loading branch information
@lisitsyn
lisitsyn committed Jul 20, 2012
1 parent 2442926 commit d5d5151
Showing 1 changed file with 173 additions and 146 deletions.
319 changes: 173 additions & 146 deletions src/shogun/lib/external/libqp_gsmo.cpp
View file
Expand Up @@ -33,6 +33,8 @@
* structure [libqp_state_T]
* .QP [1x1] Primal objective value.
* .exitflag [1 x 1] Indicates which stopping condition was used:
* -3 ... initial solution vector does not satisfy equality constraint
* -2 ... initial solution vector does not satisfy bounds
* -1 ... not enough memory
* 0 ... Maximal number of iterations reached: nIter >= MaxIter.
* 4 ... Relaxed KKT conditions satisfied.
Expand Down Expand Up @@ -69,156 +71,181 @@ namespace shogun
{

libqp_state_T libqp_gsmo_solver(const float64_t* (*get_col)(uint32_t),
float64_t *diag_H,
float64_t *f,
float64_t *a,
float64_t b,
float64_t *LB,
float64_t *UB,
float64_t *x,
uint32_t n,
uint32_t MaxIter,
float64_t TolKKT,
void (*print_state)(libqp_state_T state))
{
float64_t *col_u;
float64_t *col_v;
float64_t *Nabla;
float64_t minF_up;
float64_t maxF_low;
float64_t tau;
float64_t F_i;
float64_t tau_ub, tau_lb;
uint32_t i, j;
uint32_t u=0, v=0;
libqp_state_T state;

Nabla = NULL;

/* ------------------------------------------------------------ */
/* Initialization */
/* ------------------------------------------------------------ */

/* Nabla = H*x + f is gradient*/
Nabla = (float64_t*)LIBQP_CALLOC(n, sizeof(float64_t));
if( Nabla == NULL )
{
state.exitflag=-1;
goto cleanup;
}

/* compute gradient */
for( i=0; i < n; i++ )
{
Nabla[i] += f[i];
if( x[i] != 0 ) {
col_u = (float64_t*)get_col(i);
for( j=0; j < n; j++ ) {
Nabla[j] += col_u[j]*x[i];
}
}
}

if( print_state != NULL)
{
state.QP = 0;
for(i = 0; i < n; i++ )
state.QP += 0.5*(x[i]*Nabla[i]+x[i]*f[i]);

print_state( state );
}


/* ------------------------------------------------------------ */
/* Main optimization loop */
/* ------------------------------------------------------------ */

state.nIter = 0;
state.exitflag = 100;
while( state.exitflag == 100 )
{
state.nIter ++;

/* find the most violating pair of variables */
minF_up = LIBQP_PLUS_INF;
maxF_low = -LIBQP_PLUS_INF;
for(i = 0; i < n; i++ )
{

F_i = Nabla[i]/a[i];

if(LB[i] < x[i] && x[i] < UB[i])
{ /* i is from I_0 */
if( minF_up > F_i) { minF_up = F_i; u = i; }
if( maxF_low < F_i) { maxF_low = F_i; v = i; }
}
else if((a[i] > 0 && x[i] == LB[i]) || (a[i] < 0 && x[i] == UB[i]))
{ /* i is from I_1 or I_2 */
if( minF_up > F_i) { minF_up = F_i; u = i; }
}
else if((a[i] > 0 && x[i] == UB[i]) || (a[i] < 0 && x[i] == LB[i]))
{ /* i is from I_3 or I_4 */
if( maxF_low < F_i) { maxF_low = F_i; v = i; }
}
}

/* check KKT conditions */
if( maxF_low - minF_up <= TolKKT )
state.exitflag = 4;
else
{
/* SMO update of the most violating pair */
col_u = (float64_t*)get_col(u);
col_v = (float64_t*)get_col(v);

if( a[u] > 0 )
{ tau_lb = (LB[u]-x[u])*a[u]; tau_ub = (UB[u]-x[u])*a[u]; }
else
{ tau_ub = (LB[u]-x[u])*a[u]; tau_lb = (UB[u]-x[u])*a[u]; }

if( a[v] > 0 )
{ tau_lb = LIBQP_MAX(tau_lb,(x[v]-UB[v])*a[v]); tau_ub = LIBQP_MIN(tau_ub,(x[v]-LB[v])*a[v]); }
else
{ tau_lb = LIBQP_MAX(tau_lb,(x[v]-LB[v])*a[v]); tau_ub = LIBQP_MIN(tau_ub,(x[v]-UB[v])*a[v]); }

tau = (Nabla[v]/a[v]-Nabla[u]/a[u])/
(diag_H[u]/(a[u]*a[u]) + diag_H[v]/(a[v]*a[v]) - 2*col_u[v]/(a[u]*a[v]));

tau = LIBQP_MIN(LIBQP_MAX(tau,tau_lb),tau_ub);

x[u] += tau/a[u];
x[v] -= tau/a[v];

/* update Nabla */
for(i = 0; i < n; i++ )
Nabla[i] += col_u[i]*tau/a[u] - col_v[i]*tau/a[v];

}

if( state.nIter >= MaxIter )
state.exitflag = 0;

if( print_state != NULL)
{
state.QP = 0;
for(i = 0; i < n; i++ )
state.QP += 0.5*(x[i]*Nabla[i]+x[i]*f[i]);

print_state( state );
}

}

/* compute primal objective value */
state.QP = 0;
for(i = 0; i < n; i++ )
state.QP += 0.5*(x[i]*Nabla[i]+x[i]*f[i]);
float64_t *diag_H,
float64_t *f,
float64_t *a,
float64_t b,
float64_t *LB,
float64_t *UB,
float64_t *x,
uint32_t n,
uint32_t MaxIter,
float64_t TolKKT,
void (*print_state)(libqp_state_T state))
{
float64_t *col_u;
float64_t *col_v;
float64_t *Nabla;
float64_t minF_up;
float64_t maxF_low;
float64_t tau;
float64_t F_i;
float64_t tau_ub, tau_lb;
uint32_t i, j;
uint32_t u=0, v=0;
libqp_state_T state;
float64_t atx = 0.0;

Nabla = NULL;

/* ------------------------------------------------------------ */
/* Initialization */
/* ------------------------------------------------------------ */

// check bounds of initial guess
for (i=0; i<n; i++)
{
if (x[i]>UB[i])
{
state.exitflag = -2;
goto cleanup;
}
if (x[i]<LB[i])
{
state.exitflag = -2;
goto cleanup;
}
}

// check equality constraint
for (i=0; i<n; i++)
atx += a[i]*x[i];
if (b != atx)
{
state.exitflag = -3;
goto cleanup;
}

/* Nabla = H*x + f is gradient*/
Nabla = (float64_t*)LIBQP_CALLOC(n, sizeof(float64_t));
if( Nabla == NULL )
{
state.exitflag=-1;
goto cleanup;
}

/* compute gradient */
for( i=0; i < n; i++ )
{
Nabla[i] += f[i];
if( x[i] != 0 ) {
col_u = (float64_t*)get_col(i);
for( j=0; j < n; j++ ) {
Nabla[j] += col_u[j]*x[i];
}
}
}

if( print_state != NULL)
{
state.QP = 0;
for(i = 0; i < n; i++ )
state.QP += 0.5*(x[i]*Nabla[i]+x[i]*f[i]);

print_state( state );
}


/* ------------------------------------------------------------ */
/* Main optimization loop */
/* ------------------------------------------------------------ */

state.nIter = 0;
state.exitflag = 100;
while( state.exitflag == 100 )
{
state.nIter ++;

/* find the most violating pair of variables */
minF_up = LIBQP_PLUS_INF;
maxF_low = -LIBQP_PLUS_INF;
for(i = 0; i < n; i++ )
{

F_i = Nabla[i]/a[i];

if(LB[i] < x[i] && x[i] < UB[i])
{ /* i is from I_0 */
if( minF_up > F_i) { minF_up = F_i; u = i; }
if( maxF_low < F_i) { maxF_low = F_i; v = i; }
}
else if((a[i] > 0 && x[i] == LB[i]) || (a[i] < 0 && x[i] == UB[i]))
{ /* i is from I_1 or I_2 */
if( minF_up > F_i) { minF_up = F_i; u = i; }
}
else if((a[i] > 0 && x[i] == UB[i]) || (a[i] < 0 && x[i] == LB[i]))
{ /* i is from I_3 or I_4 */
if( maxF_low < F_i) { maxF_low = F_i; v = i; }
}
}

/* check KKT conditions */
if( maxF_low - minF_up <= TolKKT )
state.exitflag = 4;
else
{
/* SMO update of the most violating pair */
col_u = (float64_t*)get_col(u);
col_v = (float64_t*)get_col(v);

if( a[u] > 0 )
{ tau_lb = (LB[u]-x[u])*a[u]; tau_ub = (UB[u]-x[u])*a[u]; }
else
{ tau_ub = (LB[u]-x[u])*a[u]; tau_lb = (UB[u]-x[u])*a[u]; }

if( a[v] > 0 )
{ tau_lb = LIBQP_MAX(tau_lb,(x[v]-UB[v])*a[v]); tau_ub = LIBQP_MIN(tau_ub,(x[v]-LB[v])*a[v]); }
else
{ tau_lb = LIBQP_MAX(tau_lb,(x[v]-LB[v])*a[v]); tau_ub = LIBQP_MIN(tau_ub,(x[v]-UB[v])*a[v]); }

tau = (Nabla[v]/a[v]-Nabla[u]/a[u])/
(diag_H[u]/(a[u]*a[u]) + diag_H[v]/(a[v]*a[v]) - 2*col_u[v]/(a[u]*a[v]));

tau = LIBQP_MIN(LIBQP_MAX(tau,tau_lb),tau_ub);

x[u] += tau/a[u];
x[v] -= tau/a[v];

/* update Nabla */
for(i = 0; i < n; i++ )
Nabla[i] += col_u[i]*tau/a[u] - col_v[i]*tau/a[v];

}

if( state.nIter >= MaxIter )
state.exitflag = 0;

if( print_state != NULL)
{
state.QP = 0;
for(i = 0; i < n; i++ )
state.QP += 0.5*(x[i]*Nabla[i]+x[i]*f[i]);

print_state( state );
}

}

/* compute primal objective value */
state.QP = 0;
for(i = 0; i < n; i++ )
state.QP += 0.5*(x[i]*Nabla[i]+x[i]*f[i]);

cleanup:

LIBQP_FREE(Nabla);
LIBQP_FREE(Nabla);

return( state );
return( state );
}

} /* shogun namespace */
Expand Down

0 comments on commit d5d5151

Please sign in to comment.