This class implements a Box QP solver based on a Projected Newton method. More...
#include <box-qp.hpp>
Public Member Functions | |
EIGEN_MAKE_ALIGNED_OPERATOR_NEW | BoxQP (const std::size_t nx, const std::size_t maxiter=100, const double th_acceptstep=0.1, const double th_grad=1e-9, const double reg=1e-9) |
Initialize the Projected-Newton QP for bound constraints. More... | |
~BoxQP () | |
Destroy the Projected-Newton QP solver. | |
const std::vector< double > & | get_alphas () const |
Return the stack of step lengths using by the line-search procedure. | |
std::size_t | get_maxiter () const |
Return the maximum allowed number of iterations. | |
std::size_t | get_nx () const |
Return the decision vector dimension. | |
double | get_reg () const |
Return the regularization value. | |
const BoxQPSolution & | get_solution () const |
Return the stored solution. | |
double | get_th_acceptstep () const |
Return the acceptance step threshold. | |
double | get_th_grad () const |
Return the gradient tolerance threshold. | |
void | set_alphas (const std::vector< double > &alphas) |
Modify the stack of step lengths using by the line-search procedure. | |
void | set_maxiter (const std::size_t maxiter) |
Modify the maximum allowed number of iterations. | |
void | set_nx (const std::size_t nx) |
Modify the decision vector dimension. | |
void | set_reg (const double reg) |
Modify the regularization value. | |
void | set_th_acceptstep (const double th_acceptstep) |
Modify the acceptance step threshold. | |
void | set_th_grad (const double th_grad) |
Modify the gradient tolerance threshold. | |
const BoxQPSolution & | solve (const Eigen::MatrixXd &H, const Eigen::VectorXd &q, const Eigen::VectorXd &lb, const Eigen::VectorXd &ub, const Eigen::VectorXd &xinit) |
Compute the solution of bound-constrained QP based on Newton projection. More... | |
This class implements a Box QP solver based on a Projected Newton method.
We consider a box QP problem of the form:
\begin{eqnarray*} \min_{\mathbf{x}} &= \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{q}^T\mathbf{x} \\ \textrm{subject to} & \hspace{1em} \mathbf{\underline{b}} \leq \mathbf{x} \leq \mathbf{\bar{b}} \\ \end{eqnarray*}
where \(\mathbf{H}\), \(\mathbf{q}\) are the Hessian and gradient of the problem, respectively, \(\mathbf{\underline{b}}\), \(\mathbf{\bar{b}}\) are lower and upper bounds of the decision variable \(\mathbf{x}\).
The algorithm procees by iteratively identifying the active bounds, and then performing a projected Newton step in the free sub-space. The projection uses the Hessian of the free sub-space and is computed efficiently using a Cholesky decomposition. It uses a line search procedure with polynomial step length values in a backtracking fashion. The steps are checked using an Armijo condition together L2-norm gradient.
For more details about this solver, we encourage you to read the following article:
Definition at line 82 of file box-qp.hpp.
BoxQP | ( | const std::size_t | nx, |
const std::size_t | maxiter = 100 , |
||
const double | th_acceptstep = 0.1 , |
||
const double | th_grad = 1e-9 , |
||
const double | reg = 1e-9 |
||
) |
Initialize the Projected-Newton QP for bound constraints.
[in] | nx | Dimension of the decision vector |
[in] | maxiter | Maximum number of allowed iterations (default 100) |
[in] | th_acceptstep | Acceptance step threshold (default 0.1) |
[in] | th_grad | Gradient tolerance threshold (default 1e-9) |
[in] | reg | Regularization value (default 1e-9) |
Definition at line 17 of file box-qp.cpp.
const BoxQPSolution & solve | ( | const Eigen::MatrixXd & | H, |
const Eigen::VectorXd & | q, | ||
const Eigen::VectorXd & | lb, | ||
const Eigen::VectorXd & | ub, | ||
const Eigen::VectorXd & | xinit | ||
) |
Compute the solution of bound-constrained QP based on Newton projection.
[in] | H | Hessian (dimension nx * nx) |
[in] | q | Gradient (dimension nx) |
[in] | lb | Lower bound (dimension nx) |
[in] | ub | Upper bound (dimension nx) |
[in] | xinit | Initial guess (dimension nx) |
Definition at line 69 of file box-qp.cpp.