Classes and methods for solving linear-quadratic programs. More...

Classes
class	Kaskade::QPBoundSolverBase< Real, Implementation >
	An iterative solver for small instances of bound constrained quadratic programs. More...

class	Kaskade::QPBoundSolver< R >
	An iterative solver for small instances of bound constrained quadratic programs. More...

class	Kaskade::QPDirectSparse< R >
	A solver for sparse, medium-sized instances of bound constrained quadratic programs. More...

class	Kaskade::QPSlackSolver< sparsity, R >
	An iterative solver for particular instances of bound constrained quadratic programs. More...

class	Kaskade::QPSolver< d, Real >
	An iterative solver for small instances of a particular class of quadratic programs. More...

class	Kaskade::QPPenalizedSolver< d, sparsity, Real >
	An iterative solver for small instances of a particular class of quadratic programs. More...

class	Kaskade::QPALSolver< d, sparsity, Real >
	An augmented Lagrangian solver for small instances of a particular class of quadratic programs. More...

class	Kaskade::MGSolverStatistics< d, Real >
	An interface for gathering multigrid solver statistics. More...

class	Kaskade::QPMultiGridBase< d, Prolongation, Smoother, CoarseSmoother, Real >
	A base class for multigrid solver for QPs. More...

class	Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >
	A multigrid solver for convex QPs. More...

Functions
template<class MatrixA , class MatrixB , class VectorX , class VectorB >
std::array< typename ScalarTraits< typename MatrixA::field_type >::Real, 4 >	Kaskade::checkKKT (MatrixA const &A, MatrixB const &B, VectorX const &c, VectorB const &b, VectorX const &x, VectorB const &lambda)
	Computes the KKT residual for approximate solutions of certain QPs. More...

template<class MatrixA , class MatrixB , class VectorX , class VectorB , class Real >
Real	Kaskade::qpLinesearch (MatrixA const &A, MatrixB const &B, Real gamma, VectorX const &c, VectorB const &b, VectorX const &dx)
	Performs linesearch for penalized QPs. More...

template<class MatrixA , class MatrixB , class VectorX , class VectorB , class Real >
Real	Kaskade::qpLinesearch (MatrixA const &A, MatrixB const &B, Real gamma, VectorX const &c, VectorB const &b, VectorX const &x, VectorX const &dx)
	Performs linesearch for penalized QPs. More...

Detailed Description

Classes and methods for solving linear-quadratic programs.

A general linear-quadratic program is of the (standard) form

\[ \min_x \frac{1}{2} x^T A x + c^T x \quad \textsf{s.t. $Bx\le b$, $Cx=0$}. \]

The classes provided here are intended for subsets of QPs with certain structure, in particular without equality constraints. There are classes intended to be used directly for solving QPs and supporting classes.

General inequalities

For general inequality constrained problems of the type

\[ \min_x \frac{1}{2} x^T A x + c^T x \quad \textsf{s.t. $Bx\le b$} \]

with positive (semi-) definite $ A $, there are two solvers:

QPSolver, which transforms the QP into its Lagrange dual problem and solves this via a projected gradient method
QPPenalizedSolver, which solves a quadratically penalized problem
QPALSolver, which uses quadratic penalization and a Rockafellar augmentation
QPMultiGrid,

Bound constraints

For bound constrained problems of the form

\[ \min_x \frac{1}{2} x^T A x + c^T x \quad \textsf{s.t. $x\le b$} \]

with positive semi-definite $ A $, there are

QPBoundSolver, realizing a projected gradient method with dense linear algebra
QPDirectSparse, a projected gradient method with sparse linear algebra

Function Documentation

◆ checkKKT()

template<class MatrixA , class MatrixB , class VectorX , class VectorB >

std::array< typename ScalarTraits< typename MatrixA::field_type >::Real, 4 > Kaskade::checkKKT	(	MatrixA const &	A,
		MatrixB const &	B,
		VectorX const &	c,
		VectorB const &	b,
		VectorX const &	x,
		VectorB const &	lambda
	)

Computes the KKT residual for approximate solutions of certain QPs.

For QPs of the form

\[ \min_x \frac{1}{2} x^T Ax + c^T x \quad \text{s.t. } Bx \le b, \]

this function computes the KKT residual and returns the values

\[ [ \|Ax + c + B^T \lambda \|, \|Bx-b\|_+ , \|\lambda\|_- , \lambda^T (b-Bx) ]. \]

◆ qpLinesearch() [1/2]

template<class MatrixA , class MatrixB , class VectorX , class VectorB , class Real >

Real Kaskade::qpLinesearch	(	MatrixA const &	A,
		MatrixB const &	B,
		Real	gamma,
		VectorX const &	c,
		VectorB const &	b,
		VectorX const &	dx
	)

Performs linesearch for penalized QPs.

For a penalized convex QP of the form

\[ \min_{\delta x} J(\delta x) = \frac{1}{2} \delta x^T A\delta x + c^T \delta x + \frac{\gamma}{2}\left\|B\delta x-b\right\|_+^2, \]

and given a search direction $ \delta x $, this computes the (unique) step size $ t \ge 0 $ minimizing $ J(t\delta x) $.

Parameters

gamma the penalty factor $ \gamma $. If gamma == std::numeric_limits<Real>::infinity() holds, strict feasibility is enforced, i.e. $ tB\delta x \le b $. However, numerical roundoff errors may prevent to take a reasonable step in that case.

This function is equivalent to qpLinesearch(MatrixA const& A, MatrixB const& B, Real gamma, VectorX const& c, VectorB const& b, VectorX const& x, VectorX const& dx) with $ x = 0 $.

Definition at line 44 of file qpLinesearch.hh.

Referenced by Kaskade::qpLinesearch().

◆ qpLinesearch() [2/2]

template<class MatrixA , class MatrixB , class VectorX , class VectorB , class Real >

Real Kaskade::qpLinesearch	(	MatrixA const &	A,
		MatrixB const &	B,
		Real	gamma,
		VectorX const &	c,
		VectorB const &	b,
		VectorX const &	x,
		VectorX const &	dx
	)

Performs linesearch for penalized QPs.

For a penalized convex QP of the form

\[ \min_{x} J(x) = \frac{1}{2} x^T A x + c^T x + \frac{\gamma}{2}\left\|B x-b\right\|_+^2, \]

and given a nonzero starting point $ x $ and a search direction $ \delta x $, this computes the (unique) step size $ t \ge 0 $ minimizing $ J(x+t\delta x) $.

Definition at line 196 of file qpLinesearch.hh.

Classes