QpBoxDecomp Class Reference

Quadratic program solver for box constrained problems. More...

#include <QuadraticProgram.h>

Inheritance diagram for QpBoxDecomp:

List of all members.

Public Member Functions

QpBoxDecomp (CachedMatrix &quadraticPart)

Constructor.

virtual ~QpBoxDecomp ()

Destructor.

void Solve (const Array< double > &linearPart, const Array< double > &boxLower, const Array< double > &boxUpper, Array< double > &solutionVector, double eps=0.001)

solve the quadratic program

void Continue (const Array< double > &boxLower, const Array< double > &boxUpper, Array< double > &solutionVector)

continue solving the quadratic program

void Continue (const Array< double > &gradientUpdate, Array< double > &solutionVector)

continue solving the quadratic program

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

Protected Member Functions

void SMO ()

SMO loop.

virtual bool SelectWorkingSet (unsigned int &i)

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

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.

double epsilon

stopping condition - solution accuracy

bool bUnshrinked

true if the problem has already been unshrinked

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

Detailed Description

Quadratic program solver for box constrained problems.

: This algorithm solves the same problem as QpSvmDecomp but without the equality constraint. For example, this problem corresponds to SVMs without bias. The same techniques are applied.

Definition at line 757 of file QuadraticProgram.h.

Constructor & Destructor Documentation

QpBoxDecomp::QpBoxDecomp ( CachedMatrix & quadraticPart )

Constructor.

Parameters:

quadratic

quadratic part of the objective function and matrix cache

Definition at line 1378 of file QuadraticProgram.cpp.

References alpha, boxMax, boxMin, diagonal, dimension, CachedMatrix::Entry(), QPMatrix::getMatrixSize(), gradient, i, linear, maxIter, permutation, and quadratic.

QpBoxDecomp::~QpBoxDecomp ( ) [virtual]

Destructor.

Definition at line 1403 of file QuadraticProgram.cpp.

Member Function Documentation

void QpBoxDecomp::Continue	(	const Array< double > &	gradientUpdate,
		Array< double > &	solutionVector
	)

continue solving the quadratic program

Parameters:

	gradientUpdate	this vector is added to the current gradient
	solutionVector	output: solution $\alpha^*$

: The Continue method assumes that a quadratic program has already been solved, such that current solution and gradient are consistent. This method allows the user to alter the linear part of the program by adding a vector to the current gradient. The method re-uses the previous solution and the kernel cache for a warm start.

Definition at line 1496 of file QuadraticProgram.cpp.

References alpha, dimension, gradient, i, permutation, SMO(), and Unshrink().

void QpBoxDecomp::Continue	(	const Array< double > &	boxLower,
		const Array< double > &	boxUpper,
		Array< double > &	solutionVector
	)

continue solving the quadratic program

Parameters:

	boxLower	vector l of lower bounds
	boxUpper	vector u of upper bounds
	solutionVector	output: solution $\alpha^*$

: The Continue method assumes that a quadratic program with strictly smaller box has already been solved. It re-uses the previous solution, the kernel cache, and the active set for a warm start.

Definition at line 1464 of file QuadraticProgram.cpp.

References alpha, boxMax, boxMin, dimension, i, permutation, Shrink(), and SMO().

void QpBoxDecomp::FlipCoordinates	(	unsigned int	i,
		unsigned int	j
	)			`[protected]`

exchange two variables via the permutation

Definition at line 1715 of file QuadraticProgram.cpp.

References alpha, boxMax, boxMin, diagonal, CachedMatrix::FlipColumnsAndRows(), gradient, linear, permutation, quadratic, and XCHG_A.

Referenced by Shrink().

bool QpBoxDecomp::isOptimal ( ) [inline]

Is the solution optimal up to the given epsilon?

Definition at line 823 of file QuadraticProgram.h.

References optimal.

SharkInt64 QpBoxDecomp::iterations ( ) [inline]

Return the number of iterations used to solve the problem.

Definition at line 817 of file QuadraticProgram.h.

References iter.

bool QpBoxDecomp::SelectWorkingSet ( unsigned int & i ) [protected, virtual]

Definition at line 1585 of file QuadraticProgram.cpp.

References active, alpha, boxMax, boxMin, epsilon, and gradient.

Referenced by SMO().

void QpBoxDecomp::setMaxIterations ( SharkInt64 maxiter = -1 ) [inline]

set the maximal number of iterations the solver is allowed to perform

Parameters:

maxiter

maximal number of iterations, -1 for infinity

Definition at line 831 of file QuadraticProgram.h.

References maxIter.

Referenced by SVM_Optimizer::optimize().

void QpBoxDecomp::Shrink ( ) [protected]

Shrink the problem.

Definition at line 1616 of file QuadraticProgram.cpp.

References active, alpha, boxMax, boxMin, bUnshrinked, CachedMatrix::CacheRowRelease(), CachedMatrix::CacheRowResize(), epsilon, FlipCoordinates(), CachedMatrix::getCacheRowSize(), gradient, quadratic, and Unshrink().

Referenced by Continue(), SMO(), Solve(), and Unshrink().

void QpBoxDecomp::SMO ( ) [protected]

SMO loop.

Definition at line 1518 of file QuadraticProgram.cpp.

References active, alpha, boxMax, boxMin, bUnshrinked, diagonal, gradient, i, iter, maxIter, optimal, quadratic, CachedMatrix::Row(), SelectWorkingSet(), Shrink(), and Unshrink().

Referenced by Continue(), and Solve().

void QpBoxDecomp::Solve	(	const Array< double > &	linearPart,
		const Array< double > &	boxLower,
		const Array< double > &	boxUpper,
		Array< double > &	solutionVector,
		double	eps = `0.001`
	)

solve the quadratic program

Parameters:

	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 $\alpha$ ; output: solution $\alpha^*$
	eps	solution accuracy, in terms of the maximum KKT violation

Definition at line 1408 of file QuadraticProgram.cpp.

References active, alpha, boxMax, boxMin, dimension, epsilon, gradient, i, linear, permutation, quadratic, CachedMatrix::Row(), Shrink(), and SMO().

Referenced by SVM_Optimizer::optimize().

void QpBoxDecomp::Unshrink ( bool complete = false ) [protected]

Active all variables.

Definition at line 1692 of file QuadraticProgram.cpp.

References active, alpha, dimension, gradient, i, linear, quadratic, CachedMatrix::Row(), and Shrink().

Referenced by Continue(), Shrink(), and SMO().

Member Data Documentation

unsigned int QpBoxDecomp::active [protected]

number of currently active variables

Definition at line 856 of file QuadraticProgram.h.

Referenced by SelectWorkingSet(), Shrink(), SMO(), Solve(), and Unshrink().

Array<double> QpBoxDecomp::alpha [protected]

Solution candidate.

Definition at line 870 of file QuadraticProgram.h.

Referenced by Continue(), FlipCoordinates(), QpBoxDecomp(), SelectWorkingSet(), Shrink(), SMO(), Solve(), and Unshrink().

Array<double> QpBoxDecomp::boxMax [protected]

box constraint upper bound, that is, maximal variable value

Definition at line 853 of file QuadraticProgram.h.

Referenced by Continue(), FlipCoordinates(), QpBoxDecomp(), SelectWorkingSet(), Shrink(), SMO(), and Solve().

Array<double> QpBoxDecomp::boxMin [protected]

box constraint lower bound, that is, minimal variable value

Definition at line 850 of file QuadraticProgram.h.

Referenced by Continue(), FlipCoordinates(), QpBoxDecomp(), SelectWorkingSet(), Shrink(), SMO(), and Solve().

bool QpBoxDecomp::bUnshrinked [protected]

true if the problem has already been unshrinked

Definition at line 884 of file QuadraticProgram.h.

Referenced by Shrink(), and SMO().

Array<double> QpBoxDecomp::diagonal [protected]

diagonal matrix entries The diagonal array is of fixed size and not subject to shrinking.

Definition at line 863 of file QuadraticProgram.h.

Referenced by FlipCoordinates(), QpBoxDecomp(), and SMO().

unsigned int QpBoxDecomp::dimension [protected]

problem dimension

Definition at line 841 of file QuadraticProgram.h.

Referenced by Continue(), QpBoxDecomp(), Solve(), and Unshrink().

double QpBoxDecomp::epsilon [protected]

stopping condition - solution accuracy

Definition at line 873 of file QuadraticProgram.h.

Referenced by SelectWorkingSet(), Shrink(), and Solve().

Array<double> QpBoxDecomp::gradient [protected]

gradient of the objective function The gradient array is of fixed size and not subject to shrinking.

Definition at line 867 of file QuadraticProgram.h.

Referenced by Continue(), FlipCoordinates(), QpBoxDecomp(), SelectWorkingSet(), Shrink(), SMO(), Solve(), and Unshrink().

SharkInt64 QpBoxDecomp::iter [protected]

solution statistics: number of iterations

Definition at line 887 of file QuadraticProgram.h.

Referenced by iterations(), and SMO().

Array<double> QpBoxDecomp::linear [protected]

linear part of the objective function

Definition at line 847 of file QuadraticProgram.h.

Referenced by FlipCoordinates(), QpBoxDecomp(), Solve(), and Unshrink().

SharkInt64 QpBoxDecomp::maxIter [protected]

maximum number of iterations

Definition at line 895 of file QuadraticProgram.h.

Referenced by QpBoxDecomp(), setMaxIterations(), and SMO().

bool QpBoxDecomp::optimal [protected]

is the solution found (near) optimal or has the solver stopped due to an interation or time constraint?

Definition at line 892 of file QuadraticProgram.h.

Referenced by isOptimal(), and SMO().

Array<unsigned int> QpBoxDecomp::permutation [protected]

permutation of the variables alpha, gradient, etc.

Definition at line 859 of file QuadraticProgram.h.

Referenced by Continue(), FlipCoordinates(), QpBoxDecomp(), and Solve().

CachedMatrix& QpBoxDecomp::quadratic [protected]

representation of the quadratic part of the objective function

Definition at line 844 of file QuadraticProgram.h.

Referenced by FlipCoordinates(), QpBoxDecomp(), Shrink(), SMO(), Solve(), and Unshrink().

The documentation for this class was generated from the following files:


Public Member Functions
	QpBoxDecomp (CachedMatrix &quadraticPart)
	Constructor.
virtual	~QpBoxDecomp ()
	Destructor.
void	Solve (const Array< double > &linearPart, const Array< double > &boxLower, const Array< double > &boxUpper, Array< double > &solutionVector, double eps=0.001)
	solve the quadratic program
void	Continue (const Array< double > &boxLower, const Array< double > &boxUpper, Array< double > &solutionVector)
	continue solving the quadratic program
void	Continue (const Array< double > &gradientUpdate, Array< double > &solutionVector)
	continue solving the quadratic program
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
Protected Member Functions
void	SMO ()
	SMO loop.
virtual bool	SelectWorkingSet (unsigned int &i)
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
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.
double	epsilon
	stopping condition - solution accuracy
bool	bUnshrinked
	true if the problem has already been unshrinked
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