gtsam  4.0.0
gtsam
gtsam::ActiveSetSolver< PROBLEM, POLICY, INITSOLVER > Class Template Reference

Detailed Description

template<class PROBLEM, class POLICY, class INITSOLVER>
class gtsam::ActiveSetSolver< PROBLEM, POLICY, INITSOLVER >

This class implements the active set algorithm for solving convex Programming problems.

Template Parameters
PROBLEMType of the problem to solve, e.g. LP (linear program) or QP (quadratic program).
POLICYspecific detail policy tailored for the particular program
INITSOLVERSolver for an initial feasible solution of this problem.

Public Member Functions

 ActiveSetSolver (const PROBLEM &problem)
 Constructor.
 
std::pair< VectorValues, VectorValuesoptimize (const VectorValues &initialValues, const VectorValues &duals=VectorValues(), bool useWarmStart=false) const
 Optimize with provided initial values For this version, it is the responsibility of the caller to provide a feasible initial value, otherwise, an exception will be thrown. More...
 
std::pair< VectorValues, VectorValuesoptimize () const
 For this version the caller will not have to provide an initial value. More...
 
GaussianFactorGraph::shared_ptr buildDualGraph (const InequalityFactorGraph &workingSet, const VectorValues &delta) const
 Just for testing... More...
 
GaussianFactorGraph buildWorkingGraph (const InequalityFactorGraph &workingSet, const VectorValues &xk=VectorValues()) const
 Build a working graph of cost, equality and active inequality constraints to solve at each iteration. More...
 
State iterate (const State &state) const
 Iterate 1 step, return a new state with a new workingSet and values.
 
InequalityFactorGraph identifyActiveConstraints (const InequalityFactorGraph &inequalities, const VectorValues &initialValues, const VectorValues &duals=VectorValues(), bool useWarmStart=false) const
 Identify active constraints based on initial values.
 
int identifyLeavingConstraint (const InequalityFactorGraph &workingSet, const VectorValues &lambdas) const
 Identifies active constraints that shouldn't be active anymore.
 

Classes

struct  State
 This struct contains the state information for a single iteration. More...
 

Protected Types

typedef std::vector< std::pair< Key, Matrix > > TermsContainer
 Vector of key matrix pairs. Matrices are usually the A term for a factor.
 

Protected Member Functions

boost::tuple< double, int > computeStepSize (const InequalityFactorGraph &workingSet, const VectorValues &xk, const VectorValues &p, const double &maxAlpha) const
 Compute minimum step size alpha to move from the current point xk to the next feasible point along a direction p: x' = xk + alpha*p, where alpha \in [0,maxAlpha]. More...
 
template<typename FACTOR >
TermsContainer collectDualJacobians (Key key, const FactorGraph< FACTOR > &graph, const VariableIndex &variableIndex) const
 Finds the active constraints in the given factor graph and returns the Dual Jacobians used to build a dual factor graph.
 
JacobianFactor::shared_ptr createDualFactor (Key key, const InequalityFactorGraph &workingSet, const VectorValues &delta) const
 Creates a dual factor from the current workingSet and the key of the the variable used to created the dual factor.
 

Protected Attributes

const PROBLEM & problem_
 the particular [convex] problem to solve
 
VariableIndex equalityVariableIndex_
 
VariableIndex inequalityVariableIndex_
 
KeySet constrainedKeys_
 

Member Function Documentation

◆ buildDualGraph()

template<class PROBLEM , class POLICY , class INITSOLVER >
GaussianFactorGraph::shared_ptr gtsam::ActiveSetSolver< PROBLEM, POLICY, INITSOLVER >::buildDualGraph ( const InequalityFactorGraph workingSet,
const VectorValues delta 
) const

Just for testing...

Builds a dual graph from the current working set.

◆ buildWorkingGraph()

template<class PROBLEM , class POLICY , class INITSOLVER >
GaussianFactorGraph gtsam::ActiveSetSolver< PROBLEM, POLICY, INITSOLVER >::buildWorkingGraph ( const InequalityFactorGraph workingSet,
const VectorValues xk = VectorValues() 
) const

Build a working graph of cost, equality and active inequality constraints to solve at each iteration.

Parameters
workingSetthe collection of all cost and constrained factors
xkcurrent solution, used to build a special quadratic cost in LP
Returns
a new better solution

◆ computeStepSize()

template<class PROBLEM , class POLICY , class INITSOLVER >
boost::tuple<double, int> gtsam::ActiveSetSolver< PROBLEM, POLICY, INITSOLVER >::computeStepSize ( const InequalityFactorGraph workingSet,
const VectorValues xk,
const VectorValues p,
const double &  maxAlpha 
) const
protected

Compute minimum step size alpha to move from the current point xk to the next feasible point along a direction p: x' = xk + alpha*p, where alpha \in [0,maxAlpha].

For QP, maxAlpha = 1. For LP: maxAlpha = Inf.

Returns
a tuple of (minAlpha, closestFactorIndex) where closestFactorIndex is the closest inactive inequality constraint that blocks xk to move further and that has the minimum alpha, or (-1, maxAlpha) if there is no such inactive blocking constraint.

If there is a blocking constraint, the closest one will be added to the working set and become active in the next iteration.

◆ optimize() [1/2]

template<class PROBLEM , class POLICY , class INITSOLVER >
std::pair<VectorValues, VectorValues> gtsam::ActiveSetSolver< PROBLEM, POLICY, INITSOLVER >::optimize ( const VectorValues initialValues,
const VectorValues duals = VectorValues(),
bool  useWarmStart = false 
) const

Optimize with provided initial values For this version, it is the responsibility of the caller to provide a feasible initial value, otherwise, an exception will be thrown.

Returns
a pair of <primal, dual> solutions

◆ optimize() [2/2]

template<class PROBLEM , class POLICY , class INITSOLVER >
std::pair<VectorValues, VectorValues> gtsam::ActiveSetSolver< PROBLEM, POLICY, INITSOLVER >::optimize ( ) const

For this version the caller will not have to provide an initial value.

Returns
a pair of <primal, dual> solutions

Member Data Documentation

◆ constrainedKeys_

template<class PROBLEM , class POLICY , class INITSOLVER >
KeySet gtsam::ActiveSetSolver< PROBLEM, POLICY, INITSOLVER >::constrainedKeys_
protected

all constrained keys, will become factors in dual graphs

◆ inequalityVariableIndex_

template<class PROBLEM , class POLICY , class INITSOLVER >
VariableIndex gtsam::ActiveSetSolver< PROBLEM, POLICY, INITSOLVER >::inequalityVariableIndex_
protected

index to corresponding factors to build dual graphs


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