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

Inheritance diagram for shark::SvmProblem< Problem >:

Public Types
typedef Problem::QpFloatType	QpFloatType

typedef Problem::MatrixType	MatrixType

typedef LibSVMSelectionCriterion	PreferedSelectionStrategy

Public Member Functions
	SvmProblem (Problem &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

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

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 while taking the equality constraint into account.

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

void	scaleBoxConstraints (double factor, double variableScalingFactor)
	Scales all box constraints by a constant factor and adapts the solution using a separate scaling.

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
virtual void	applyStep (std::size_t i, std::size_t j, double step)
	Update the problem by a proposed step i taking the box constraints into account.

void	updateAlphaStatus (std::size_t i)

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

Protected Attributes
Problem	m_problem

RealVector	m_gradient
	gradient of the objective function at the current alpha

std::size_t	m_active

std::vector< char >	m_alphaStatus
	Stores the status, whther alpha is on the lower or upper bound, or whether it is free.

Detailed Description

template<class Problem>
class shark::SvmProblem< Problem >

Definition at line 300 of file SvmProblems.h.

Member Typedef Documentation

◆ MatrixType

template<class Problem >

typedef Problem::MatrixType shark::SvmProblem< Problem >::MatrixType

Definition at line 303 of file SvmProblems.h.

◆ PreferedSelectionStrategy

template<class Problem >

typedef LibSVMSelectionCriterion shark::SvmProblem< Problem >::PreferedSelectionStrategy

Definition at line 304 of file SvmProblems.h.

◆ QpFloatType

template<class Problem >

typedef Problem::QpFloatType shark::SvmProblem< Problem >::QpFloatType

Definition at line 302 of file SvmProblems.h.

Constructor & Destructor Documentation

◆ SvmProblem()

template<class Problem >

shark::SvmProblem< Problem >::SvmProblem ( Problem & problem )

inline

Definition at line 306 of file SvmProblems.h.

References shark::SvmProblem< Problem >::alpha(), shark::SvmProblem< Problem >::dimensions(), shark::SvmProblem< Problem >::m_gradient, shark::SvmProblem< Problem >::quadratic(), and shark::SvmProblem< Problem >::updateAlphaStatus().

Member Function Documentation

◆ activateVariable()

template<class Problem >

void shark::SvmProblem< Problem >::activateVariable ( std::size_t i )

inline

Reactivate an previously deactivated variable.

Definition at line 503 of file SvmProblems.h.

References shark::AlphaFree, shark::SvmProblem< Problem >::dimensions(), shark::SvmProblem< Problem >::m_alphaStatus, SIZE_CHECK, and shark::SvmProblem< Problem >::updateAlphaStatus().

◆ active()

template<class Problem >

std::size_t shark::SvmProblem< Problem >::active ( ) const

inline

Definition at line 326 of file SvmProblems.h.

References shark::SvmProblem< Problem >::m_active.

Referenced by shark::SvmProblem< Problem >::applyStep(), shark::SvmProblem< Problem >::checkKKT(), and shark::SvmProblem< Problem >::updateSMO().

◆ alpha()

template<class Problem >

double shark::SvmProblem< Problem >::alpha ( std::size_t i ) const

inline

Definition at line 352 of file SvmProblems.h.

References shark::SvmProblem< Problem >::m_problem.

Referenced by shark::SvmProblem< Problem >::boxMax(), shark::SvmProblem< Problem >::boxMin(), shark::SvmProblem< Problem >::deactivateVariable(), shark::SvmProblem< Problem >::getUnpermutedAlpha(), shark::SvmProblem< Problem >::setInitialSolution(), shark::SvmProblem< Problem >::setInitialSolution(), and shark::SvmProblem< Problem >::SvmProblem().

◆ applyStep()

template<class Problem >

virtual void shark::SvmProblem< Problem >::applyStep	(	std::size_t	i,
		std::size_t	j,
		double	step
	)

inlineprotectedvirtual

Update the problem by a proposed step i taking the box constraints into account.

A step length 0<=lambda<=1 is found so that boxMin(i) <= alpha(i)+lambda*step <= boxMax(i) and boxMin(j) <= alpha(j)-lambda*step <= boxMax(j) the update is performed in a numerically stable way and the internal data structures are also updated.

Definition at line 572 of file SvmProblems.h.

References shark::SvmProblem< Problem >::active(), shark::SvmProblem< Problem >::boxMax(), shark::SvmProblem< Problem >::boxMin(), shark::SvmProblem< Problem >::m_gradient, shark::SvmProblem< Problem >::m_problem, shark::SvmProblem< Problem >::quadratic(), SIZE_CHECK, and shark::SvmProblem< Problem >::updateAlphaStatus().

Referenced by shark::SvmProblem< Problem >::deactivateVariable().

◆ boxMax()

template<class Problem >

double shark::SvmProblem< Problem >::boxMax ( std::size_t i ) const

inline

Definition at line 333 of file SvmProblems.h.

References shark::SvmProblem< Problem >::alpha(), shark::AlphaDeactivated, shark::SvmProblem< Problem >::m_alphaStatus, and shark::SvmProblem< Problem >::m_problem.

Referenced by shark::SvmProblem< Problem >::applyStep(), shark::SvmProblem< Problem >::setInitialSolution(), shark::SvmProblem< Problem >::updateAlphaStatus(), and shark::SvmProblem< Problem >::updateSMO().

◆ boxMin()

template<class Problem >

double shark::SvmProblem< Problem >::boxMin ( std::size_t i ) const

inline

Definition at line 330 of file SvmProblems.h.

References shark::SvmProblem< Problem >::alpha(), shark::AlphaDeactivated, shark::SvmProblem< Problem >::m_alphaStatus, and shark::SvmProblem< Problem >::m_problem.

Referenced by shark::SvmProblem< Problem >::applyStep(), shark::SvmProblem< Problem >::setInitialSolution(), shark::SvmProblem< Problem >::updateAlphaStatus(), and shark::SvmProblem< Problem >::updateSMO().

◆ checkKKT()

template<class Problem >

double shark::SvmProblem< Problem >::checkKKT ( ) const

inline

Definition at line 541 of file SvmProblems.h.

References shark::SvmProblem< Problem >::active(), shark::SvmProblem< Problem >::gradient(), shark::SvmProblem< Problem >::isLowerBound(), and shark::SvmProblem< Problem >::isUpperBound().

◆ deactivateVariable()

template<class Problem >

void shark::SvmProblem< Problem >::deactivateVariable ( std::size_t i )

inline

Remove the i-th example from the problem while taking the equality constraint into account.

The i-th element is first set to zero and as well as an unspecified set corrected so that the constraint is fulfilled.

Definition at line 490 of file SvmProblems.h.

References shark::SvmProblem< Problem >::alpha(), shark::AlphaDeactivated, shark::SvmProblem< Problem >::applyStep(), shark::SvmProblem< Problem >::dimensions(), shark::SvmProblem< Problem >::m_alphaStatus, and SIZE_CHECK.

◆ diagonal()

template<class Problem >

double shark::SvmProblem< Problem >::diagonal ( std::size_t i ) const

inline

Definition at line 356 of file SvmProblems.h.

References shark::SvmProblem< Problem >::m_problem.

Referenced by shark::SvmProblem< Problem >::updateSMO().

◆ dimensions()

template<class Problem >

std::size_t shark::SvmProblem< Problem >::dimensions ( ) const

inline

Definition at line 322 of file SvmProblems.h.

References shark::SvmProblem< Problem >::m_problem.

Referenced by shark::SvmProblem< Problem >::activateVariable(), shark::SvmProblem< Problem >::deactivateVariable(), shark::SvmProblem< Problem >::flipCoordinates(), shark::SvmProblem< Problem >::getUnpermutedAlpha(), shark::SvmProblem< Problem >::scaleBoxConstraints(), shark::SvmProblem< Problem >::setInitialSolution(), shark::SvmProblem< Problem >::setInitialSolution(), shark::SvmProblem< Problem >::SvmProblem(), and shark::SvmProblem< Problem >::updateAlphaStatus().

◆ flipCoordinates()

template<class Problem >

void shark::SvmProblem< Problem >::flipCoordinates	(	std::size_t	i,
		std::size_t	j
	)

inline

exchange two variables via the permutation

Definition at line 510 of file SvmProblems.h.

References shark::SvmProblem< Problem >::dimensions(), shark::SvmProblem< Problem >::m_alphaStatus, shark::SvmProblem< Problem >::m_gradient, shark::SvmProblem< Problem >::m_problem, and SIZE_CHECK.

◆ functionValue()

template<class Problem >

double shark::SvmProblem< Problem >::functionValue ( ) const

inline

Returns the current function value of the problem.

Definition at line 436 of file SvmProblems.h.

References shark::SvmProblem< Problem >::m_gradient, and shark::SvmProblem< Problem >::m_problem.

◆ getUnpermutedAlpha()

template<class Problem >

RealVector shark::SvmProblem< Problem >::getUnpermutedAlpha ( ) const

inline

Definition at line 368 of file SvmProblems.h.

References shark::SvmProblem< Problem >::alpha(), shark::SvmProblem< Problem >::dimensions(), and shark::SvmProblem< Problem >::m_problem.

◆ gradient()

template<class Problem >

double shark::SvmProblem< Problem >::gradient ( std::size_t i ) const

inline

Definition at line 360 of file SvmProblems.h.

References shark::SvmProblem< Problem >::m_gradient.

Referenced by shark::SvmProblem< Problem >::checkKKT(), shark::SvmProblem< Problem >::setInitialSolution(), shark::SvmProblem< Problem >::setInitialSolution(), shark::SvmProblem< Problem >::testShrinkVariable(), and shark::SvmProblem< Problem >::updateSMO().

◆ isLowerBound()

template<class Problem >

bool shark::SvmProblem< Problem >::isLowerBound ( std::size_t i ) const

inline

Definition at line 336 of file SvmProblems.h.

References shark::AlphaLowerBound, and shark::SvmProblem< Problem >::m_alphaStatus.

Referenced by shark::SvmProblem< Problem >::checkKKT(), and shark::SvmProblem< Problem >::testShrinkVariable().

◆ isUpperBound()

template<class Problem >

bool shark::SvmProblem< Problem >::isUpperBound ( std::size_t i ) const

inline

Definition at line 339 of file SvmProblems.h.

References shark::AlphaUpperBound, and shark::SvmProblem< Problem >::m_alphaStatus.

Referenced by shark::SvmProblem< Problem >::checkKKT(), and shark::SvmProblem< Problem >::testShrinkVariable().

◆ linear()

template<class Problem >

double shark::SvmProblem< Problem >::linear ( std::size_t i ) const

inline

Definition at line 348 of file SvmProblems.h.

References shark::SvmProblem< Problem >::m_problem.

Referenced by shark::SvmProblem< Problem >::scaleBoxConstraints(), and shark::SvmProblem< Problem >::setLinear().

◆ permutation()

template<class Problem >

std::size_t shark::SvmProblem< Problem >::permutation ( std::size_t i ) const

inline

Definition at line 364 of file SvmProblems.h.

References shark::SvmProblem< Problem >::m_problem.

Referenced by shark::SvmProblem< Problem >::setInitialSolution().

◆ quadratic()

template<class Problem >

MatrixType & shark::SvmProblem< Problem >::quadratic ( )

inline

representation of the quadratic part of the objective function

Definition at line 344 of file SvmProblems.h.

References shark::SvmProblem< Problem >::m_problem.

Referenced by shark::SvmProblem< Problem >::applyStep(), shark::SvmProblem< Problem >::SvmProblem(), and shark::SvmProblem< Problem >::updateSMO().

◆ reshrink()

template<class Problem >

void shark::SvmProblem< Problem >::reshrink ( )

inline

Definition at line 441 of file SvmProblems.h.

◆ scaleBoxConstraints()

template<class Problem >

void shark::SvmProblem< Problem >::scaleBoxConstraints	(	double	factor,
		double	variableScalingFactor
	)

inline

Scales all box constraints by a constant factor and adapts the solution using a separate scaling.

Definition at line 522 of file SvmProblems.h.

References shark::AlphaDeactivated, shark::SvmProblem< Problem >::dimensions(), shark::SvmProblem< Problem >::linear(), shark::SvmProblem< Problem >::m_alphaStatus, shark::SvmProblem< Problem >::m_gradient, shark::SvmProblem< Problem >::m_problem, and shark::SvmProblem< Problem >::updateAlphaStatus().

◆ setInitialSolution() [1/2]

template<class Problem >

void shark::SvmProblem< Problem >::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 470 of file SvmProblems.h.

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

◆ setInitialSolution() [2/2]

template<class Problem >

void shark::SvmProblem< Problem >::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 449 of file SvmProblems.h.

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

Referenced by shark::SvmProblem< Problem >::setInitialSolution().

◆ setLinear()

template<class Problem >

virtual void shark::SvmProblem< Problem >::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< SvmProblem< Problem > >.

Definition at line 535 of file SvmProblems.h.

References shark::SvmProblem< Problem >::linear(), shark::SvmProblem< Problem >::m_gradient, and shark::SvmProblem< Problem >::m_problem.

◆ shrink()

template<class Problem >

bool shark::SvmProblem< Problem >::shrink ( double )

inline

Definition at line 440 of file SvmProblems.h.

◆ testShrinkVariable()

template<class Problem >

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

inlineprotected

Definition at line 632 of file SvmProblems.h.

References shark::SvmProblem< Problem >::gradient(), shark::SvmProblem< Problem >::isLowerBound(), and shark::SvmProblem< Problem >::isUpperBound().

◆ unshrink()

template<class Problem >

void shark::SvmProblem< Problem >::unshrink ( )

inline

Definition at line 442 of file SvmProblems.h.

◆ updateAlphaStatus()

template<class Problem >

void shark::SvmProblem< Problem >::updateAlphaStatus ( std::size_t i )

inlineprotected

Definition at line 623 of file SvmProblems.h.

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

Referenced by shark::SvmProblem< Problem >::activateVariable(), shark::SvmProblem< Problem >::applyStep(), shark::SvmProblem< Problem >::scaleBoxConstraints(), shark::SvmProblem< Problem >::setInitialSolution(), shark::SvmProblem< Problem >::SvmProblem(), and shark::SvmProblem< Problem >::updateSMO().

◆ updateSMO()

template<class Problem >

void shark::SvmProblem< Problem >::updateSMO	(	std::size_t	i,
		std::size_t	j
	)

inline

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

Definition at line 376 of file SvmProblems.h.

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

Member Data Documentation

◆ m_active

template<class Problem >

std::size_t shark::SvmProblem< Problem >::m_active

protected

Definition at line 559 of file SvmProblems.h.

Referenced by shark::SvmProblem< Problem >::active().

◆ m_alphaStatus

template<class Problem >

std::vector<char> shark::SvmProblem< Problem >::m_alphaStatus

protected

Stores the status, whther alpha is on the lower or upper bound, or whether it is free.

Definition at line 562 of file SvmProblems.h.

Referenced by shark::SvmProblem< Problem >::activateVariable(), shark::SvmProblem< Problem >::boxMax(), shark::SvmProblem< Problem >::boxMin(), shark::SvmProblem< Problem >::deactivateVariable(), shark::SvmProblem< Problem >::flipCoordinates(), shark::SvmProblem< Problem >::isLowerBound(), shark::SvmProblem< Problem >::isUpperBound(), shark::SvmProblem< Problem >::scaleBoxConstraints(), and shark::SvmProblem< Problem >::updateAlphaStatus().

◆ m_gradient

template<class Problem >

RealVector shark::SvmProblem< Problem >::m_gradient

protected

gradient of the objective function at the current alpha

Definition at line 557 of file SvmProblems.h.

Referenced by shark::SvmProblem< Problem >::applyStep(), shark::SvmProblem< Problem >::flipCoordinates(), shark::SvmProblem< Problem >::functionValue(), shark::SvmProblem< Problem >::gradient(), shark::SvmProblem< Problem >::scaleBoxConstraints(), shark::SvmProblem< Problem >::setInitialSolution(), shark::SvmProblem< Problem >::setLinear(), shark::SvmProblem< Problem >::SvmProblem(), and shark::SvmProblem< Problem >::updateSMO().

◆ m_problem

template<class Problem >

Problem shark::SvmProblem< Problem >::m_problem

protected

Definition at line 554 of file SvmProblems.h.

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

include/shark/Algorithms/QP/SvmProblems.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ MatrixType

◆ PreferedSelectionStrategy

◆ QpFloatType

Constructor & Destructor Documentation

◆ SvmProblem()

Member Function Documentation

◆ activateVariable()

◆ active()

◆ alpha()

◆ applyStep()

◆ boxMax()

◆ boxMin()

◆ checkKKT()

◆ deactivateVariable()

◆ diagonal()

◆ dimensions()

◆ flipCoordinates()

◆ functionValue()

◆ getUnpermutedAlpha()

◆ gradient()

◆ isLowerBound()

◆ isUpperBound()

◆ linear()

◆ permutation()

◆ quadratic()

◆ reshrink()

◆ scaleBoxConstraints()

◆ setInitialSolution() [1/2]

◆ setInitialSolution() [2/2]

◆ setLinear()

◆ shrink()

◆ testShrinkVariable()

◆ unshrink()

◆ updateAlphaStatus()

◆ updateSMO()

Member Data Documentation

◆ m_active

◆ m_alphaStatus

◆ m_gradient

◆ m_problem