An iterative solver for particular instances of bound constrained quadratic programs. More...
#include <qp.hh>
Detailed Description
class Kaskade::QPSlackSolver< sparsity, R >
An iterative solver for particular instances of bound constrained quadratic programs.
The solver addresses problems of the form
\[ \min_x \frac{1}{2} x^T Qx + c^T x \quad \text{s.t. } x \le b, \]
where
\[ Q = \begin{bmatrix} A+\gamma B^T B & -\gamma B^T \\ -\gamma B & \gamma I \end{bmatrix}\]
is a positive definite block structured matrix. Problems of this type rarely arise on their own, mostly from a penalty or augmented Lagrangian relaxation of general QPs (see QPPenalizedSolver).
The implementation is intended to solve problems where \( A \) is small and dense , with just a couple of variables, typically less than 30.
- Template Parameters
-
structure specifies which type of linear algebra to use: - DENSE uses dense linear algebra and is intended to solve problems where \( A \) is small, with usually not more than 30 variables
- SPARSE uses sparse solvers, and is intended for problems of moderate size
Real the real field type of matrix/vector entries. Explicit instantiations are provided for float and double.
Public Types | |
| using | Real = R |
| using | Vector = typename Base::Vector |
| using | Matrix = std::conditional_t< sparsity==QPStructure::DENSE, DynamicMatrix< Entry >, NumaBCRSMatrix< Entry > > |
Public Member Functions | |
| QPSlackSolver (Matrix const &A, Matrix const &B, Real gamma, QPConvexificationStrategy convex=QPConvexificationStrategy::DONOTHING) | |
| Constructs the solver, providing the matrix \( A \) and \( B \). More... | |
| std::tuple< Vector, int > | solve (Vector const &c, Vector const &b, double tol) const |
| Solves the QP for the given right hand side vectors. More... | |
| std::tuple< Vector, int > | solve (Vector const &x, Vector const &c, Vector const &b, double tol) const |
| Solves the QP for the given right hand side vectors. More... | |
| void | gradientStep (Vector const &c, Vector const &b, Vector &x) const |
| Performs a single projected gradient step. More... | |
| QPSlackSolver< QPStructure::DENSE, double > & | setMinSteps (int count) |
| defines the minimal number of steps to perform in solving. More... | |
| QPSlackSolver< QPStructure::DENSE, double > & | setMaxSteps (int count) |
| defines the maximum allowed number of steps to perform in solving. More... | |
Protected Member Functions | |
| Vector | solveSubmatrix (std::vector< int > const &idx, Vector const &b) const |
| solves a subsystem \( \tilde A x = b \). More... | |
| virtual void | updateWithColumn (double a, int i, Vector &s) const |
| Performs the update \( s \gets s + aAe_i \), where \( e_i \) is the i-th unit vector. More... | |
Member Typedef Documentation
◆ Matrix
| using Kaskade::QPSlackSolver< sparsity, R >::Matrix = std::conditional_t<sparsity==QPStructure::DENSE, DynamicMatrix<Entry>, NumaBCRSMatrix<Entry> > |
◆ Real
| using Kaskade::QPSlackSolver< sparsity, R >::Real = R |
◆ Vector
| using Kaskade::QPSlackSolver< sparsity, R >::Vector = typename Base::Vector |
Constructor & Destructor Documentation
◆ QPSlackSolver()
| Kaskade::QPSlackSolver< sparsity, R >::QPSlackSolver | ( | Matrix const & | A, |
| Matrix const & | B, | ||
| Real | gamma, | ||
| QPConvexificationStrategy | convex = QPConvexificationStrategy::DONOTHING |
||
| ) |
Constructs the solver, providing the matrix \( A \) and \( B \).
The argument matrices are copied internally, and are not referenced later.
Throws a NonpositiveMatrixException if \( A \) is not positive definite and
- convex is QPConvexificationStrategy::DONOTHING.
- Todo:
- write a move constructor
Member Function Documentation
◆ gradientStep()
|
inherited |
Performs a single projected gradient step.
This is a generalization of a Richardson smoother with linesearch, and can be used when the QP is just a subproblem, e.g. in multigrid methods, and rather well conditioned.
◆ setMaxSteps()
|
inherited |
defines the maximum allowed number of steps to perform in solving.
The default value is 200. If the maximum iteration count is below the minimum iteration count, the number of steps performed in solving is undefined.
◆ setMinSteps()
|
inherited |
defines the minimal number of steps to perform in solving.
The default value is 0. If the minimum iteration count is set to less than the maximum iteration count, the number of steps performed is undefined.
◆ solve() [1/2]
|
inherited |
Solves the QP for the given right hand side vectors.
Solves the QP with a projected gradient method starting at the feasible point \( x = \min(0,b)\).
- Parameters
-
c the linear term of the objective b the constraints right hand side tol the tolerance for termination criterion
The iteration is terminated as soon as the projected gradient \( s \) is small, i.e. \( \|s\|_2 \le \mathsf{tol} \).
- Returns
- a tuple \( (x,iter) \) of solution vector, and iteration count
If the QP is infeasible, an InfeasibleProblemException is thrown.
◆ solve() [2/2]
|
inherited |
Solves the QP for the given right hand side vectors.
- Parameters
-
x an initial guess for the solution. If an unfeasible starting point is provided, it will be projected to the feasible set. c the linear term of the objective b the constraints right hand side tol the tolerance for termination criterion
The iteration is terminated as soon as the projected gradient \( s \) is small, i.e. \( \|s\|_2 \le \mathsf{tol} \).
- Returns
- a tuple \( (x,iter) \) of solution vector, and iteration count. If the iteration count equals the maximum iteration count (
- See also
- setMaxSteps), the returned Solution Tools vector need not satisfy the tolerance criterion.
If the QP is infeasible, an InfeasibleProblemException is thrown.
◆ solveSubmatrix()
|
protectedinherited |
solves a subsystem \( \tilde A x = b \).
This needs to be overwritten by derived classes.
For a set idx of indices, the submatrix \( \tilde A \) in Matlab notation is A(idx,idx).
- Parameters
-
idx the indices defining the submatrix b the right hand side (of the same length as the index vector)
- Returns
- the solution \( x \)
◆ updateWithColumn()
|
protectedvirtualinherited |
Performs the update \( s \gets s + aAe_i \), where \( e_i \) is the i-th unit vector.
The default implementation performs a complete matrix-vector product, which is performance-wise suboptimal. Override this for better performance.
The documentation for this class was generated from the following file:
