Quadratic program with box constraints. More...

#include <shark/Algorithms/QP/BoxConstrainedProblems.h>

Public Types
typedef SVMProblem::QpFloatType	QpFloatType

typedef SVMProblem::MatrixType	MatrixType

typedef MaximumGainCriterion	PreferedSelectionStrategy

Public Member Functions
	BoxConstrainedProblem (SVMProblem &problem)

std::size_t	dimensions () const

std::size_t	active () const

double	boxMin (std::size_t i) const

double	boxMax (std::size_t i) const

bool	isLowerBound (std::size_t i) const

bool	isUpperBound (std::size_t i) const

bool	isDeactivated (std::size_t i) const

MatrixType &	quadratic ()
	representation of the quadratic part of the objective function More...

double	linear (std::size_t i) const

double	alpha (std::size_t i) const

double	diagonal (std::size_t i) const

double	gradient (std::size_t i) const

std::size_t	permutation (std::size_t i) const

RealVector	getUnpermutedAlpha () const

virtual void	updateSMO (std::size_t i, std::size_t j)
	Does an update of SMO given a working set with indices i and j. More...

double	functionValue () const
	Returns the current function value of the problem. More...

bool	shrink (double)

void	reshrink ()

void	unshrink ()

void	setInitialSolution (RealVector const &alpha, RealVector const &gradient)
	Define the initial solution for the iterative solver. More...

void	setInitialSolution (RealVector const &alpha)
	Define the initial solution for the iterative solver. More...

void	deactivateVariable (std::size_t i)
	Remove the i-th example from the problem. More...

void	activateVariable (std::size_t i)
	Reactivate an previously deactivated variable. More...

void	flipCoordinates (std::size_t i, std::size_t j)
	exchange two variables via the permutation More...

virtual void	setLinear (std::size_t i, double newValue)
	adapts the linear part of the problem and updates the internal data structures accordingly. More...

double	checkKKT () const

Protected Member Functions
void	updateAlphaStatus (std::size_t i)

bool	testShrinkVariable (std::size_t a, double largestUp, double smallestDown) const

Protected Attributes
SVMProblem &	m_problem

RealVector	m_gradient
	gradient of the objective function at the current alpha More...

std::size_t	m_active

std::vector< char >	m_alphaStatus

Detailed Description

template<class SVMProblem>
class shark::BoxConstrainedProblem< SVMProblem >

Quadratic program with box constraints.

: An instance of this class represents a quadratic program of the type TODO: write documentation!

Definition at line 138 of file BoxConstrainedProblems.h.

Member Typedef Documentation

◆ MatrixType

template<class SVMProblem>

typedef SVMProblem::MatrixType shark::BoxConstrainedProblem< SVMProblem >::MatrixType

Definition at line 141 of file BoxConstrainedProblems.h.

◆ PreferedSelectionStrategy

template<class SVMProblem>

typedef MaximumGainCriterion shark::BoxConstrainedProblem< SVMProblem >::PreferedSelectionStrategy

Definition at line 142 of file BoxConstrainedProblems.h.

◆ QpFloatType

template<class SVMProblem>

typedef SVMProblem::QpFloatType shark::BoxConstrainedProblem< SVMProblem >::QpFloatType

Definition at line 140 of file BoxConstrainedProblems.h.

Constructor & Destructor Documentation

◆ BoxConstrainedProblem()

template<class SVMProblem>

shark::BoxConstrainedProblem< SVMProblem >::BoxConstrainedProblem ( SVMProblem & problem )

inline

Definition at line 145 of file BoxConstrainedProblems.h.

Member Function Documentation

◆ activateVariable()

template<class SVMProblem>

void shark::BoxConstrainedProblem< SVMProblem >::activateVariable ( std::size_t i )

inline

Reactivate an previously deactivated variable.

Definition at line 331 of file BoxConstrainedProblems.h.

◆ active()

template<class SVMProblem>

std::size_t shark::BoxConstrainedProblem< SVMProblem >::active ( ) const

inline

Definition at line 165 of file BoxConstrainedProblems.h.

◆ alpha()

template<class SVMProblem>

double shark::BoxConstrainedProblem< SVMProblem >::alpha ( std::size_t i ) const

inline

Definition at line 194 of file BoxConstrainedProblems.h.

◆ boxMax()

template<class SVMProblem>

double shark::BoxConstrainedProblem< SVMProblem >::boxMax ( std::size_t i ) const

inline

Definition at line 172 of file BoxConstrainedProblems.h.

◆ boxMin()

template<class SVMProblem>

double shark::BoxConstrainedProblem< SVMProblem >::boxMin ( std::size_t i ) const

inline

Definition at line 169 of file BoxConstrainedProblems.h.

◆ checkKKT()

template<class SVMProblem>

double shark::BoxConstrainedProblem< SVMProblem >::checkKKT ( ) const

inline

Definition at line 355 of file BoxConstrainedProblems.h.

◆ deactivateVariable()

template<class SVMProblem>

void shark::BoxConstrainedProblem< SVMProblem >::deactivateVariable ( std::size_t i )

inline

Remove the i-th example from the problem.

Definition at line 320 of file BoxConstrainedProblems.h.

◆ diagonal()

template<class SVMProblem>

double shark::BoxConstrainedProblem< SVMProblem >::diagonal ( std::size_t i ) const

inline

Definition at line 198 of file BoxConstrainedProblems.h.

◆ dimensions()

template<class SVMProblem>

std::size_t shark::BoxConstrainedProblem< SVMProblem >::dimensions ( ) const

inline

Definition at line 161 of file BoxConstrainedProblems.h.

◆ flipCoordinates()

template<class SVMProblem>

void shark::BoxConstrainedProblem< SVMProblem >::flipCoordinates	(	std::size_t	i,
		std::size_t	j
	)

inline

exchange two variables via the permutation

Definition at line 337 of file BoxConstrainedProblems.h.

◆ functionValue()

template<class SVMProblem>

double shark::BoxConstrainedProblem< SVMProblem >::functionValue ( ) const

inline

Returns the current function value of the problem.

Definition at line 269 of file BoxConstrainedProblems.h.

◆ getUnpermutedAlpha()

template<class SVMProblem>

RealVector shark::BoxConstrainedProblem< SVMProblem >::getUnpermutedAlpha ( ) const

inline

Definition at line 210 of file BoxConstrainedProblems.h.

◆ gradient()

template<class SVMProblem>

double shark::BoxConstrainedProblem< SVMProblem >::gradient ( std::size_t i ) const

inline

Definition at line 202 of file BoxConstrainedProblems.h.

◆ isDeactivated()

template<class SVMProblem>

bool shark::BoxConstrainedProblem< SVMProblem >::isDeactivated ( std::size_t i ) const

inline

Definition at line 181 of file BoxConstrainedProblems.h.

◆ isLowerBound()

template<class SVMProblem>

bool shark::BoxConstrainedProblem< SVMProblem >::isLowerBound ( std::size_t i ) const

inline

Definition at line 175 of file BoxConstrainedProblems.h.

◆ isUpperBound()

template<class SVMProblem>

bool shark::BoxConstrainedProblem< SVMProblem >::isUpperBound ( std::size_t i ) const

inline

Definition at line 178 of file BoxConstrainedProblems.h.

◆ linear()

template<class SVMProblem>

double shark::BoxConstrainedProblem< SVMProblem >::linear ( std::size_t i ) const

inline

Definition at line 190 of file BoxConstrainedProblems.h.

◆ permutation()

template<class SVMProblem>

std::size_t shark::BoxConstrainedProblem< SVMProblem >::permutation ( std::size_t i ) const

inline

Definition at line 206 of file BoxConstrainedProblems.h.

◆ quadratic()

template<class SVMProblem>

MatrixType& shark::BoxConstrainedProblem< SVMProblem >::quadratic ( )

inline

representation of the quadratic part of the objective function

Definition at line 186 of file BoxConstrainedProblems.h.

◆ reshrink()

template<class SVMProblem>

void shark::BoxConstrainedProblem< SVMProblem >::reshrink ( )

inline

Definition at line 274 of file BoxConstrainedProblems.h.

◆ setInitialSolution() [1/2]

template<class SVMProblem>

void shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution	(	RealVector const &	alpha,
		RealVector const &	gradient
	)

inline

Define the initial solution for the iterative solver.

This method can be used to warm-start the solver. It requires a feasible solution (alpha) and the corresponding gradient of the dual objective function.

Definition at line 282 of file BoxConstrainedProblems.h.

◆ setInitialSolution() [2/2]

template<class SVMProblem>

void shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution ( RealVector const & alpha )

inline

Define the initial solution for the iterative solver.

This method can be used to warm-start the solver. It requires a feasible solution (alpha), for which it computes the gradient of the dual objective function. Note that this is a quadratic time operation in the number of non-zero coefficients.

Definition at line 303 of file BoxConstrainedProblems.h.

◆ setLinear()

template<class SVMProblem>

virtual void shark::BoxConstrainedProblem< SVMProblem >::setLinear	(	std::size_t	i,
		double	newValue
	)

inlinevirtual

adapts the linear part of the problem and updates the internal data structures accordingly.

Reimplemented in shark::BoxBasedShrinkingStrategy< BoxConstrainedProblem< Problem > >.

Definition at line 349 of file BoxConstrainedProblems.h.

◆ shrink()

template<class SVMProblem>

bool shark::BoxConstrainedProblem< SVMProblem >::shrink ( double )

inline

Definition at line 273 of file BoxConstrainedProblems.h.

◆ testShrinkVariable()

template<class SVMProblem>

bool shark::BoxConstrainedProblem< SVMProblem >::testShrinkVariable	(	std::size_t	a,
		double	largestUp,
		double	smallestDown
	)		const

inlineprotected

Definition at line 388 of file BoxConstrainedProblems.h.

◆ unshrink()

template<class SVMProblem>

void shark::BoxConstrainedProblem< SVMProblem >::unshrink ( )

inline

Definition at line 275 of file BoxConstrainedProblems.h.

◆ updateAlphaStatus()

template<class SVMProblem>

void shark::BoxConstrainedProblem< SVMProblem >::updateAlphaStatus ( std::size_t i )

inlineprotected

Definition at line 379 of file BoxConstrainedProblems.h.

◆ updateSMO()

template<class SVMProblem>

virtual void shark::BoxConstrainedProblem< SVMProblem >::updateSMO	(	std::size_t	i,
		std::size_t	j
	)

inlinevirtual

Does an update of SMO given a working set with indices i and j.

Reimplemented in shark::BoxBasedShrinkingStrategy< BoxConstrainedProblem< Problem > >.

Definition at line 218 of file BoxConstrainedProblems.h.

Member Data Documentation

◆ m_active

template<class SVMProblem>

std::size_t shark::BoxConstrainedProblem< SVMProblem >::m_active

protected

Definition at line 375 of file BoxConstrainedProblems.h.

◆ m_alphaStatus

template<class SVMProblem>

std::vector<char> shark::BoxConstrainedProblem< SVMProblem >::m_alphaStatus

protected

Definition at line 377 of file BoxConstrainedProblems.h.

◆ m_gradient

template<class SVMProblem>

RealVector shark::BoxConstrainedProblem< SVMProblem >::m_gradient

protected

gradient of the objective function at the current alpha

Definition at line 373 of file BoxConstrainedProblems.h.

◆ m_problem

template<class SVMProblem>

SVMProblem& shark::BoxConstrainedProblem< SVMProblem >::m_problem

protected

Definition at line 370 of file BoxConstrainedProblems.h.

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

include/shark/Algorithms/QP/BoxConstrainedProblems.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class SVMProblem> class shark::BoxConstrainedProblem< SVMProblem >

Member Typedef Documentation

◆ MatrixType

◆ PreferedSelectionStrategy

◆ QpFloatType

Constructor & Destructor Documentation

◆ BoxConstrainedProblem()

Member Function Documentation

◆ activateVariable()

◆ active()

◆ alpha()

◆ boxMax()

◆ boxMin()

◆ checkKKT()

◆ deactivateVariable()

◆ diagonal()

◆ dimensions()

◆ flipCoordinates()

◆ functionValue()

◆ getUnpermutedAlpha()

◆ gradient()

◆ isDeactivated()

◆ isLowerBound()

◆ isUpperBound()

◆ linear()

◆ permutation()

◆ quadratic()

◆ reshrink()

◆ setInitialSolution() [1/2]

◆ setInitialSolution() [2/2]

◆ setLinear()

◆ shrink()

◆ testShrinkVariable()

◆ unshrink()

◆ updateAlphaStatus()

◆ updateSMO()

Member Data Documentation

◆ m_active

◆ m_alphaStatus

◆ m_gradient

◆ m_problem

template<class SVMProblem>
class shark::BoxConstrainedProblem< SVMProblem >