A solver for sparse, medium-sized instances of bound constrained quadratic programs. More...
#include <qp.hh>
Detailed Description
class Kaskade::QPDirectSparse< R >
A solver for sparse, medium-sized instances of bound constrained quadratic programs.
The solver addresses problems of the form
\[ \min_x \frac{1}{2} x^T Ax + c^T x \quad \text{s.t. } x \le b, \]
where \( A \) is a positive definite sparse matrix. A direct solver is used to solve projected subproblems.
- Template Parameters
-
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 | SparseMatrix = NumaBCRSMatrix< Dune::FieldMatrix< Real, 1, 1 > > |
| using | Matrix = DynamicMatrix< Dune::FieldMatrix< double, 1, 1 > > |
Public Member Functions | |
| QPDirectSparse (SparseMatrix const &A, QPConvexificationStrategy convex=QPConvexificationStrategy::DONOTHING) | |
| Constructs the solver, providing the matrix \( A \). 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... | |
| QPDirectSparse< double > & | setMinSteps (int count) |
| defines the minimal number of steps to perform in solving. More... | |
| QPDirectSparse< 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
|
inherited |
◆ Real
| using Kaskade::QPDirectSparse< R >::Real = R |
◆ SparseMatrix
| using Kaskade::QPDirectSparse< R >::SparseMatrix = NumaBCRSMatrix<Dune::FieldMatrix<Real,1,1> > |
◆ Vector
| using Kaskade::QPDirectSparse< R >::Vector = typename Base::Vector |
Constructor & Destructor Documentation
◆ QPDirectSparse()
| Kaskade::QPDirectSparse< R >::QPDirectSparse | ( | SparseMatrix const & | A, |
| QPConvexificationStrategy | convex = QPConvexificationStrategy::DONOTHING |
||
| ) |
Constructs the solver, providing the matrix \( A \).
The argument matrix is copied internally, and is 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:
