Quadratic program solver for SVMs. More...
#include <QuadraticProgram.h>
Public Member Functions | |
QpSvmDecomp (CachedMatrix &quadraticPart) | |
Constructor. | |
virtual | ~QpSvmDecomp () |
Destructor. | |
double | Solve (const Array< double > &linearPart, const Array< double > &boxLower, const Array< double > &boxUpper, Array< double > &solutionVector, double eps=0.001, double threshold=1e100) |
solve the quadratic program | |
double | ComputeInnerProduct (unsigned int index, const Array< double > &coeff) |
compute the inner product of a training example with a linear combination of the training examples | |
void | getGradient (Array< double > &grad) |
return the gradient of the objective function in the optimum | |
void | setVerbose (bool verbose=false) |
enable/disable console status output | |
void | setStrategy (const char *strategy=NULL) |
set the working set strategy parameter | |
void | setShrinking (bool shrinking=true) |
enable/disable shrinking | |
SharkInt64 | iterations () |
Return the number of iterations used to solve the problem. | |
bool | isOptimal () |
Is the solution optimal up to the given epsilon? | |
void | setMaxIterations (SharkInt64 maxiter=-1) |
set the maximal number of iterations the solver is allowed to perform | |
void | setMaxSeconds (int seconds=-1) |
set the maximal number of seconds the solver is allowed to run | |
Protected Member Functions | |
bool | MVP (unsigned int &i, unsigned int &j) |
Select the most violatig pair (MVP). | |
bool | HMG (unsigned int &i, unsigned int &j) |
Select a working set according to the hybrid maximum gain (HMG) algorithm. | |
bool | Libsvm28 (unsigned int &i, unsigned int &j) |
Select a working set according to the second order algorithm of LIBSVM 2.8. | |
virtual bool | SelectWorkingSet (unsigned int &i, unsigned int &j) |
Select a working set. | |
void | SelectWSS () |
Choose a suitable working set algorithm. | |
void | Shrink () |
Shrink the problem. | |
void | Unshrink (bool complete=false) |
Active all variables. | |
void | FlipCoordinates (unsigned int i, unsigned int j) |
exchange two variables via the permutation | |
Protected Attributes | |
unsigned int | dimension |
problem dimension | |
CachedMatrix & | quadratic |
representation of the quadratic part of the objective function | |
Array< double > | linear |
linear part of the objective function | |
Array< double > | boxMin |
box constraint lower bound, that is, minimal variable value | |
Array< double > | boxMax |
box constraint upper bound, that is, maximal variable value | |
SharkInt64 | iter |
solution statistics: number of iterations | |
bool | optimal |
is the solution found (near) optimal or has the solver stopped due to an interation or time constraint? | |
SharkInt64 | maxIter |
maximum number of iterations | |
int | maxSeconds |
maximum number of seconds | |
bool | printInfo |
should the solver print its status to the standard output? | |
const char * | WSS_Strategy |
working set selection strategy to follow | |
bool | useShrinking |
should the solver use the shrinking heuristics? | |
bool(QpSvmDecomp::* | currentWSS )(unsigned int &, unsigned int &) |
pointer to the currently used working set selection algorithm | |
unsigned int | active |
number of currently active variables | |
Array< unsigned int > | permutation |
permutation of the variables alpha, gradient, etc. | |
Array< double > | diagonal |
diagonal matrix entries The diagonal array is of fixed size and not subject to shrinking. | |
Array< double > | gradient |
gradient of the objective function The gradient array is of fixed size and not subject to shrinking. | |
Array< double > | alpha |
Solution candidate. | |
bool | bFirst |
indicator of the first decomposition iteration | |
unsigned int | old_i |
first component of the previous working set | |
unsigned int | old_j |
second component of the previous working set | |
double | epsilon |
stopping condition - solution accuracy | |
bool | bUnshrinked |
true if the problem has already been unshrinked |
Quadratic program solver for SVMs.
Definition at line 526 of file QuadraticProgram.h.
QpSvmDecomp::QpSvmDecomp | ( | CachedMatrix & | quadraticPart | ) |
Constructor.
quadratic | quadratic part of the objective function and matrix cache |
Definition at line 729 of file QuadraticProgram.cpp.
References alpha, boxMax, boxMin, diagonal, dimension, CachedMatrix::Entry(), QPMatrix::getMatrixSize(), gradient, i, linear, maxIter, maxSeconds, permutation, printInfo, quadratic, useShrinking, and WSS_Strategy.
QpSvmDecomp::~QpSvmDecomp | ( | ) | [virtual] |
Destructor.
Definition at line 758 of file QuadraticProgram.cpp.
double QpSvmDecomp::ComputeInnerProduct | ( | unsigned int | index, | |
const Array< double > & | coeff | |||
) |
compute the inner product of a training example with a linear combination of the training examples
index | index of the training example | |
coeff | list of coefficients of the training examples |
Definition at line 921 of file QuadraticProgram.cpp.
References dimension, CachedMatrix::Entry(), CachedMatrix::getCacheRowSize(), i, permutation, quadratic, and CachedMatrix::Row().
Referenced by LOO::error().
void QpSvmDecomp::FlipCoordinates | ( | unsigned int | i, | |
unsigned int | j | |||
) | [protected] |
exchange two variables via the permutation
Definition at line 1350 of file QuadraticProgram.cpp.
References alpha, boxMax, boxMin, diagonal, CachedMatrix::FlipColumnsAndRows(), gradient, linear, old_i, old_j, permutation, quadratic, and XCHG_A.
Referenced by Shrink(), and Unshrink().
void QpSvmDecomp::getGradient | ( | Array< double > & | grad | ) |
return the gradient of the objective function in the optimum
grad | gradient of the objective function |
Definition at line 949 of file QuadraticProgram.cpp.
References dimension, gradient, i, and permutation.
Referenced by LOO::ComputeB(), and SVM_Optimizer::optimize().
bool QpSvmDecomp::HMG | ( | unsigned int & | i, | |
unsigned int & | j | |||
) | [protected] |
Select a working set according to the hybrid maximum gain (HMG) algorithm.
i | first working set component | |
j | second working set component |
Definition at line 986 of file QuadraticProgram.cpp.
References active, alpha, bFirst, boxMax, boxMin, diagonal, epsilon, gradient, Libsvm28(), old_i, old_j, printInfo, quadratic, and CachedMatrix::Row().
Referenced by SelectWSS().
bool QpSvmDecomp::isOptimal | ( | ) | [inline] |
Is the solution optimal up to the given epsilon?
Definition at line 609 of file QuadraticProgram.h.
References optimal.
Referenced by SpanBound1::error(), SpanBound::error(), LOO::error(), SpanBound1::errorDerivative(), and RadiusMargin::solveProblems().
SharkInt64 QpSvmDecomp::iterations | ( | ) | [inline] |
Return the number of iterations used to solve the problem.
Definition at line 603 of file QuadraticProgram.h.
References iter.
Referenced by SpanBound::error(), LOO::error(), and RadiusMargin::solveProblems().
bool QpSvmDecomp::Libsvm28 | ( | unsigned int & | i, | |
unsigned int & | j | |||
) | [protected] |
Select a working set according to the second order algorithm of LIBSVM 2.8.
i | first working set component | |
j | second working set component |
Definition at line 1107 of file QuadraticProgram.cpp.
References active, alpha, boxMax, boxMin, diagonal, epsilon, gradient, quadratic, and CachedMatrix::Row().
Referenced by HMG(), and SelectWSS().
bool QpSvmDecomp::MVP | ( | unsigned int & | i, | |
unsigned int & | j | |||
) | [protected] |
Select the most violatig pair (MVP).
i | first working set component | |
j | second working set component |
Definition at line 956 of file QuadraticProgram.cpp.
References active, alpha, boxMax, boxMin, epsilon, and gradient.
Referenced by SelectWSS().
bool QpSvmDecomp::SelectWorkingSet | ( | unsigned int & | i, | |
unsigned int & | j | |||
) | [protected, virtual] |
Select a working set.
i | first working set component | |
j | second working set component |
Definition at line 1158 of file QuadraticProgram.cpp.
References currentWSS, old_i, and old_j.
Referenced by Solve().
void QpSvmDecomp::SelectWSS | ( | ) | [protected] |
Choose a suitable working set algorithm.
Definition at line 1168 of file QuadraticProgram.cpp.
References active, currentWSS, CachedMatrix::getMaxCacheSize(), HMG(), Libsvm28(), MVP(), quadratic, and WSS_Strategy.
void QpSvmDecomp::setMaxIterations | ( | SharkInt64 | maxiter = -1 |
) | [inline] |
set the maximal number of iterations the solver is allowed to perform
maxiter | maximal number of iterations, -1 for infinity |
Definition at line 617 of file QuadraticProgram.h.
References maxIter.
Referenced by LOO::error(), SVM_Optimizer::optimize(), and RadiusMargin::solveProblems().
void QpSvmDecomp::setMaxSeconds | ( | int | seconds = -1 |
) | [inline] |
set the maximal number of seconds the solver is allowed to run
seconds | maximal number of seconds, -1 for infinity |
Definition at line 625 of file QuadraticProgram.h.
References maxSeconds.
Referenced by SVM_Optimizer::optimize().
void QpSvmDecomp::setShrinking | ( | bool | shrinking = true |
) | [inline] |
enable/disable shrinking
Definition at line 597 of file QuadraticProgram.h.
References useShrinking.
void QpSvmDecomp::setStrategy | ( | const char * | strategy = NULL |
) | [inline] |
set the working set strategy parameter
Definition at line 591 of file QuadraticProgram.h.
References WSS_Strategy.
void QpSvmDecomp::setVerbose | ( | bool | verbose = false |
) | [inline] |
enable/disable console status output
Definition at line 585 of file QuadraticProgram.h.
References printInfo.
Referenced by SVM_Optimizer::optimize().
void QpSvmDecomp::Shrink | ( | ) | [protected] |
Shrink the problem.
Definition at line 1197 of file QuadraticProgram.cpp.
References active, alpha, boxMax, boxMin, bUnshrinked, CachedMatrix::CacheRowRelease(), CachedMatrix::CacheRowResize(), epsilon, FlipCoordinates(), CachedMatrix::getCacheRowSize(), gradient, old_i, old_j, printInfo, quadratic, SelectWSS(), and Unshrink().
Referenced by Solve().
double QpSvmDecomp::Solve | ( | const Array< double > & | linearPart, | |
const Array< double > & | boxLower, | |||
const Array< double > & | boxUpper, | |||
Array< double > & | solutionVector, | |||
double | eps = 0.001 , |
|||
double | threshold = 1e100 | |||
) |
solve the quadratic program
linearPart | linear part v of the target function | |
boxLower | vector l of lower bounds | |
boxUpper | vector u of upper bounds | |
solutionVector | input: initial feasible vector ; output: solution | |
eps | solution accuracy, in terms of the maximum KKT violation | |
threshold | threshold to use for the objective value stopping criterion |
Definition at line 763 of file QuadraticProgram.cpp.
References active, alpha, bFirst, boxMax, boxMin, bUnshrinked, diagonal, dimension, epsilon, gradient, i, iter, linear, maxIter, maxSeconds, optimal, permutation, printInfo, quadratic, CachedMatrix::Row(), SelectWorkingSet(), SelectWSS(), Shrink(), Unshrink(), and useShrinking.
Referenced by SpanBound::error(), LOO::error(), SVM_Optimizer::optimize(), and RadiusMargin::solveProblems().
void QpSvmDecomp::Unshrink | ( | bool | complete = false |
) | [protected] |
unsigned int QpSvmDecomp::active [protected] |
number of currently active variables
Definition at line 673 of file QuadraticProgram.h.
Referenced by HMG(), Libsvm28(), MVP(), SelectWSS(), Shrink(), Solve(), and Unshrink().
Array<double> QpSvmDecomp::alpha [protected] |
Solution candidate.
Definition at line 687 of file QuadraticProgram.h.
Referenced by FlipCoordinates(), HMG(), Libsvm28(), MVP(), QpSvmDecomp(), Shrink(), Solve(), and Unshrink().
bool QpSvmDecomp::bFirst [protected] |
indicator of the first decomposition iteration
Definition at line 690 of file QuadraticProgram.h.
Array<double> QpSvmDecomp::boxMax [protected] |
box constraint upper bound, that is, maximal variable value
Definition at line 644 of file QuadraticProgram.h.
Referenced by FlipCoordinates(), HMG(), Libsvm28(), MVP(), QpSvmDecomp(), Shrink(), Solve(), and Unshrink().
Array<double> QpSvmDecomp::boxMin [protected] |
box constraint lower bound, that is, minimal variable value
Definition at line 641 of file QuadraticProgram.h.
Referenced by FlipCoordinates(), HMG(), Libsvm28(), MVP(), QpSvmDecomp(), Shrink(), Solve(), and Unshrink().
bool QpSvmDecomp::bUnshrinked [protected] |
true if the problem has already been unshrinked
Definition at line 741 of file QuadraticProgram.h.
bool(QpSvmDecomp::* QpSvmDecomp::currentWSS)(unsigned int &, unsigned int &) [protected] |
pointer to the currently used working set selection algorithm
Referenced by SelectWorkingSet(), and SelectWSS().
Array<double> QpSvmDecomp::diagonal [protected] |
diagonal matrix entries The diagonal array is of fixed size and not subject to shrinking.
Definition at line 680 of file QuadraticProgram.h.
Referenced by FlipCoordinates(), HMG(), Libsvm28(), QpSvmDecomp(), and Solve().
unsigned int QpSvmDecomp::dimension [protected] |
problem dimension
Definition at line 632 of file QuadraticProgram.h.
Referenced by ComputeInnerProduct(), getGradient(), QpSvmDecomp(), Solve(), and Unshrink().
double QpSvmDecomp::epsilon [protected] |
stopping condition - solution accuracy
Definition at line 699 of file QuadraticProgram.h.
Referenced by HMG(), Libsvm28(), MVP(), Shrink(), and Solve().
Array<double> QpSvmDecomp::gradient [protected] |
gradient of the objective function The gradient array is of fixed size and not subject to shrinking.
Definition at line 684 of file QuadraticProgram.h.
Referenced by FlipCoordinates(), getGradient(), HMG(), Libsvm28(), MVP(), QpSvmDecomp(), Shrink(), Solve(), and Unshrink().
SharkInt64 QpSvmDecomp::iter [protected] |
solution statistics: number of iterations
Definition at line 647 of file QuadraticProgram.h.
Referenced by iterations(), and Solve().
Array<double> QpSvmDecomp::linear [protected] |
linear part of the objective function
Definition at line 638 of file QuadraticProgram.h.
Referenced by FlipCoordinates(), QpSvmDecomp(), Solve(), and Unshrink().
SharkInt64 QpSvmDecomp::maxIter [protected] |
maximum number of iterations
Definition at line 655 of file QuadraticProgram.h.
Referenced by QpSvmDecomp(), setMaxIterations(), and Solve().
int QpSvmDecomp::maxSeconds [protected] |
maximum number of seconds
Definition at line 658 of file QuadraticProgram.h.
Referenced by QpSvmDecomp(), setMaxSeconds(), and Solve().
unsigned int QpSvmDecomp::old_i [protected] |
first component of the previous working set
Definition at line 693 of file QuadraticProgram.h.
Referenced by FlipCoordinates(), HMG(), SelectWorkingSet(), Shrink(), and Unshrink().
unsigned int QpSvmDecomp::old_j [protected] |
second component of the previous working set
Definition at line 696 of file QuadraticProgram.h.
Referenced by FlipCoordinates(), HMG(), SelectWorkingSet(), Shrink(), and Unshrink().
bool QpSvmDecomp::optimal [protected] |
is the solution found (near) optimal or has the solver stopped due to an interation or time constraint?
Definition at line 652 of file QuadraticProgram.h.
Referenced by isOptimal(), and Solve().
Array<unsigned int> QpSvmDecomp::permutation [protected] |
permutation of the variables alpha, gradient, etc.
Definition at line 676 of file QuadraticProgram.h.
Referenced by ComputeInnerProduct(), FlipCoordinates(), getGradient(), QpSvmDecomp(), and Solve().
bool QpSvmDecomp::printInfo [protected] |
should the solver print its status to the standard output?
Definition at line 661 of file QuadraticProgram.h.
Referenced by HMG(), QpSvmDecomp(), setVerbose(), Shrink(), Solve(), and Unshrink().
CachedMatrix& QpSvmDecomp::quadratic [protected] |
representation of the quadratic part of the objective function
Definition at line 635 of file QuadraticProgram.h.
Referenced by ComputeInnerProduct(), FlipCoordinates(), HMG(), Libsvm28(), QpSvmDecomp(), SelectWSS(), Shrink(), Solve(), and Unshrink().
bool QpSvmDecomp::useShrinking [protected] |
should the solver use the shrinking heuristics?
Definition at line 667 of file QuadraticProgram.h.
Referenced by QpSvmDecomp(), setShrinking(), and Solve().
const char* QpSvmDecomp::WSS_Strategy [protected] |
working set selection strategy to follow
Definition at line 664 of file QuadraticProgram.h.
Referenced by QpSvmDecomp(), SelectWSS(), and setStrategy().