List of all members | Public Types | Public Member Functions | Protected Member Functions | Protected Attributes
shark::BoxConstrainedProblem< SVMProblem > Class Template Reference

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
 
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.
 
double functionValue () const
 Returns the current function value of the problem.
 
bool shrink (double)
 
void reshrink ()
 
void unshrink ()
 
void setInitialSolution (RealVector const &alpha, RealVector const &gradient)
 Define the initial solution for the iterative solver.
 
void setInitialSolution (RealVector const &alpha)
 Define the initial solution for the iterative solver.
 
void deactivateVariable (std::size_t i)
 Remove the i-th example from the problem.
 
void activateVariable (std::size_t i)
 Reactivate an previously deactivated variable.
 
void flipCoordinates (std::size_t i, std::size_t j)
 exchange two variables via the permutation
 
virtual void setLinear (std::size_t i, double newValue)
 adapts the linear part of the problem and updates the internal data structures accordingly.
 
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
 
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.

References shark::BoxConstrainedProblem< SVMProblem >::alpha(), shark::BoxConstrainedProblem< SVMProblem >::dimensions(), shark::BoxConstrainedProblem< SVMProblem >::m_gradient, shark::BoxConstrainedProblem< SVMProblem >::quadratic(), and shark::BoxConstrainedProblem< SVMProblem >::updateAlphaStatus().

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.

References shark::BoxConstrainedProblem< SVMProblem >::dimensions(), SIZE_CHECK, and shark::BoxConstrainedProblem< SVMProblem >::updateAlphaStatus().

◆ active()

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

Definition at line 165 of file BoxConstrainedProblems.h.

References shark::BoxConstrainedProblem< SVMProblem >::m_active.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::deactivateVariable(), and shark::BoxConstrainedProblem< SVMProblem >::updateSMO().

◆ alpha()

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

Definition at line 194 of file BoxConstrainedProblems.h.

References shark::BoxConstrainedProblem< SVMProblem >::m_problem.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::BoxConstrainedProblem(), shark::BoxConstrainedProblem< SVMProblem >::boxMax(), shark::BoxConstrainedProblem< SVMProblem >::boxMin(), shark::BoxConstrainedProblem< SVMProblem >::deactivateVariable(), shark::BoxConstrainedProblem< SVMProblem >::getUnpermutedAlpha(), shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), and shark::BoxConstrainedProblem< SVMProblem >::updateSMO().

◆ boxMax()

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

Definition at line 172 of file BoxConstrainedProblems.h.

References shark::BoxConstrainedProblem< SVMProblem >::alpha(), shark::AlphaDeactivated, shark::BoxConstrainedProblem< SVMProblem >::m_alphaStatus, and shark::BoxConstrainedProblem< SVMProblem >::m_problem.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), shark::BoxConstrainedProblem< SVMProblem >::updateAlphaStatus(), and shark::BoxConstrainedProblem< SVMProblem >::updateSMO().

◆ boxMin()

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

Definition at line 169 of file BoxConstrainedProblems.h.

References shark::BoxConstrainedProblem< SVMProblem >::alpha(), shark::AlphaDeactivated, shark::BoxConstrainedProblem< SVMProblem >::m_alphaStatus, and shark::BoxConstrainedProblem< SVMProblem >::m_problem.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), shark::BoxConstrainedProblem< SVMProblem >::updateAlphaStatus(), and shark::BoxConstrainedProblem< SVMProblem >::updateSMO().

◆ checkKKT()

template<class SVMProblem >
double shark::BoxConstrainedProblem< SVMProblem >::checkKKT ( ) const
inline

Definition at line 355 of file BoxConstrainedProblems.h.

References shark::BoxConstrainedProblem< SVMProblem >::dimensions(), shark::BoxConstrainedProblem< SVMProblem >::gradient(), shark::BoxConstrainedProblem< SVMProblem >::isDeactivated(), shark::BoxConstrainedProblem< SVMProblem >::isLowerBound(), and shark::BoxConstrainedProblem< SVMProblem >::isUpperBound().

◆ 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.

References shark::BoxConstrainedProblem< SVMProblem >::active(), shark::BoxConstrainedProblem< SVMProblem >::alpha(), shark::AlphaDeactivated, shark::BoxConstrainedProblem< SVMProblem >::dimensions(), shark::BoxConstrainedProblem< SVMProblem >::m_alphaStatus, shark::BoxConstrainedProblem< SVMProblem >::m_gradient, shark::BoxConstrainedProblem< SVMProblem >::m_problem, shark::BoxConstrainedProblem< SVMProblem >::quadratic(), and SIZE_CHECK.

◆ diagonal()

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

Definition at line 198 of file BoxConstrainedProblems.h.

References shark::BoxConstrainedProblem< SVMProblem >::m_problem.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::updateSMO().

◆ dimensions()

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

Definition at line 161 of file BoxConstrainedProblems.h.

References shark::BoxConstrainedProblem< SVMProblem >::m_problem.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::activateVariable(), shark::BoxConstrainedProblem< SVMProblem >::BoxConstrainedProblem(), shark::BoxConstrainedProblem< SVMProblem >::checkKKT(), shark::BoxConstrainedProblem< SVMProblem >::deactivateVariable(), shark::BoxConstrainedProblem< SVMProblem >::flipCoordinates(), shark::BoxConstrainedProblem< SVMProblem >::getUnpermutedAlpha(), shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), and shark::BoxConstrainedProblem< SVMProblem >::updateAlphaStatus().

◆ 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.

References shark::BoxConstrainedProblem< SVMProblem >::dimensions(), shark::BoxConstrainedProblem< SVMProblem >::m_alphaStatus, shark::BoxConstrainedProblem< SVMProblem >::m_gradient, shark::BoxConstrainedProblem< SVMProblem >::m_problem, and SIZE_CHECK.

◆ 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.

References shark::BoxConstrainedProblem< SVMProblem >::m_gradient, and shark::BoxConstrainedProblem< SVMProblem >::m_problem.

◆ getUnpermutedAlpha()

template<class SVMProblem >
RealVector shark::BoxConstrainedProblem< SVMProblem >::getUnpermutedAlpha ( ) const
inline

Definition at line 210 of file BoxConstrainedProblems.h.

References shark::BoxConstrainedProblem< SVMProblem >::alpha(), shark::BoxConstrainedProblem< SVMProblem >::dimensions(), and shark::BoxConstrainedProblem< SVMProblem >::m_problem.

◆ gradient()

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

Definition at line 202 of file BoxConstrainedProblems.h.

References shark::BoxConstrainedProblem< SVMProblem >::m_gradient.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::checkKKT(), shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), shark::BoxConstrainedProblem< SVMProblem >::testShrinkVariable(), and shark::BoxConstrainedProblem< SVMProblem >::updateSMO().

◆ isDeactivated()

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

Definition at line 181 of file BoxConstrainedProblems.h.

References shark::BoxConstrainedProblem< SVMProblem >::isLowerBound(), and shark::BoxConstrainedProblem< SVMProblem >::isUpperBound().

Referenced by shark::BoxConstrainedProblem< SVMProblem >::checkKKT().

◆ isLowerBound()

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

Definition at line 175 of file BoxConstrainedProblems.h.

References shark::AlphaLowerBound, and shark::BoxConstrainedProblem< SVMProblem >::m_alphaStatus.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::checkKKT(), shark::BoxConstrainedProblem< SVMProblem >::isDeactivated(), and shark::BoxConstrainedProblem< SVMProblem >::testShrinkVariable().

◆ isUpperBound()

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

Definition at line 178 of file BoxConstrainedProblems.h.

References shark::AlphaUpperBound, and shark::BoxConstrainedProblem< SVMProblem >::m_alphaStatus.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::checkKKT(), shark::BoxConstrainedProblem< SVMProblem >::isDeactivated(), and shark::BoxConstrainedProblem< SVMProblem >::testShrinkVariable().

◆ linear()

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

Definition at line 190 of file BoxConstrainedProblems.h.

References shark::BoxConstrainedProblem< SVMProblem >::m_problem.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::setLinear().

◆ 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.

References shark::BoxConstrainedProblem< SVMProblem >::m_problem.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution().

◆ 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.

References shark::BoxConstrainedProblem< SVMProblem >::m_problem.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::BoxConstrainedProblem(), shark::BoxConstrainedProblem< SVMProblem >::deactivateVariable(), and shark::BoxConstrainedProblem< SVMProblem >::updateSMO().

◆ 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)
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.

References shark::BoxConstrainedProblem< SVMProblem >::alpha(), shark::BoxConstrainedProblem< SVMProblem >::dimensions(), shark::BoxConstrainedProblem< SVMProblem >::gradient(), shark::BoxConstrainedProblem< SVMProblem >::m_problem, shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), and SIZE_CHECK.

◆ setInitialSolution() [2/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.

References shark::BoxConstrainedProblem< SVMProblem >::alpha(), shark::BoxConstrainedProblem< SVMProblem >::boxMax(), shark::BoxConstrainedProblem< SVMProblem >::boxMin(), shark::BoxConstrainedProblem< SVMProblem >::dimensions(), shark::BoxConstrainedProblem< SVMProblem >::gradient(), shark::BoxConstrainedProblem< SVMProblem >::m_gradient, shark::BoxConstrainedProblem< SVMProblem >::m_problem, shark::BoxConstrainedProblem< SVMProblem >::permutation(), SHARK_ASSERT, SIZE_CHECK, and shark::BoxConstrainedProblem< SVMProblem >::updateAlphaStatus().

Referenced by shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution().

◆ 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.

References shark::BoxConstrainedProblem< SVMProblem >::linear(), shark::BoxConstrainedProblem< SVMProblem >::m_gradient, and shark::BoxConstrainedProblem< SVMProblem >::m_problem.

◆ 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.

References shark::BoxConstrainedProblem< SVMProblem >::gradient(), shark::BoxConstrainedProblem< SVMProblem >::isLowerBound(), and shark::BoxConstrainedProblem< SVMProblem >::isUpperBound().

◆ 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.

References shark::AlphaFree, shark::AlphaLowerBound, shark::AlphaUpperBound, shark::BoxConstrainedProblem< SVMProblem >::boxMax(), shark::BoxConstrainedProblem< SVMProblem >::boxMin(), shark::BoxConstrainedProblem< SVMProblem >::dimensions(), shark::BoxConstrainedProblem< SVMProblem >::m_alphaStatus, shark::BoxConstrainedProblem< SVMProblem >::m_problem, and SIZE_CHECK.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::activateVariable(), shark::BoxConstrainedProblem< SVMProblem >::BoxConstrainedProblem(), shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), and shark::BoxConstrainedProblem< SVMProblem >::updateSMO().

◆ 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.

References shark::BoxConstrainedProblem< SVMProblem >::active(), shark::BoxConstrainedProblem< SVMProblem >::alpha(), shark::BoxConstrainedProblem< SVMProblem >::boxMax(), shark::BoxConstrainedProblem< SVMProblem >::boxMin(), shark::BoxConstrainedProblem< SVMProblem >::diagonal(), shark::BoxConstrainedProblem< SVMProblem >::gradient(), shark::BoxConstrainedProblem< SVMProblem >::m_gradient, shark::BoxConstrainedProblem< SVMProblem >::m_problem, shark::BoxConstrainedProblem< SVMProblem >::quadratic(), SIZE_CHECK, and shark::BoxConstrainedProblem< SVMProblem >::updateAlphaStatus().

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.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::active().

◆ m_alphaStatus

template<class SVMProblem >
std::vector<char> shark::BoxConstrainedProblem< SVMProblem >::m_alphaStatus
protected

Definition at line 377 of file BoxConstrainedProblems.h.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::boxMax(), shark::BoxConstrainedProblem< SVMProblem >::boxMin(), shark::BoxConstrainedProblem< SVMProblem >::deactivateVariable(), shark::BoxConstrainedProblem< SVMProblem >::flipCoordinates(), shark::BoxConstrainedProblem< SVMProblem >::isLowerBound(), shark::BoxConstrainedProblem< SVMProblem >::isUpperBound(), and shark::BoxConstrainedProblem< SVMProblem >::updateAlphaStatus().

◆ 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.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::BoxConstrainedProblem(), shark::BoxConstrainedProblem< SVMProblem >::deactivateVariable(), shark::BoxConstrainedProblem< SVMProblem >::flipCoordinates(), shark::BoxConstrainedProblem< SVMProblem >::functionValue(), shark::BoxConstrainedProblem< SVMProblem >::gradient(), shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), shark::BoxConstrainedProblem< SVMProblem >::setLinear(), and shark::BoxConstrainedProblem< SVMProblem >::updateSMO().

◆ m_problem

template<class SVMProblem >
SVMProblem& shark::BoxConstrainedProblem< SVMProblem >::m_problem
protected

Definition at line 370 of file BoxConstrainedProblems.h.

Referenced by shark::BoxConstrainedProblem< SVMProblem >::alpha(), shark::BoxConstrainedProblem< SVMProblem >::boxMax(), shark::BoxConstrainedProblem< SVMProblem >::boxMin(), shark::BoxConstrainedProblem< SVMProblem >::deactivateVariable(), shark::BoxConstrainedProblem< SVMProblem >::diagonal(), shark::BoxConstrainedProblem< SVMProblem >::dimensions(), shark::BoxConstrainedProblem< SVMProblem >::flipCoordinates(), shark::BoxConstrainedProblem< SVMProblem >::functionValue(), shark::BoxConstrainedProblem< SVMProblem >::getUnpermutedAlpha(), shark::BoxConstrainedProblem< SVMProblem >::linear(), shark::BoxConstrainedProblem< SVMProblem >::permutation(), shark::BoxConstrainedProblem< SVMProblem >::quadratic(), shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), shark::BoxConstrainedProblem< SVMProblem >::setInitialSolution(), shark::BoxConstrainedProblem< SVMProblem >::setLinear(), shark::BoxConstrainedProblem< SVMProblem >::updateAlphaStatus(), and shark::BoxConstrainedProblem< SVMProblem >::updateSMO().

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