Crocoddyl
BoxQP Class Reference

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 BoxQPSolutionget_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 BoxQPSolutionsolve (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...
 

Detailed Description

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.

Constructor & Destructor Documentation

◆ BoxQP()

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.

Parameters
[in]nxDimension of the decision vector
[in]maxiterMaximum number of allowed iterations (default 100)
[in]th_acceptstepAcceptance step threshold (default 0.1)
[in]th_gradGradient tolerance threshold (default 1e-9)
[in]regRegularization value (default 1e-9)

Definition at line 17 of file box-qp.cpp.

Member Function Documentation

◆ solve()

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.

Parameters
[in]HHessian (dimension nx * nx)
[in]qGradient (dimension nx)
[in]lbLower bound (dimension nx)
[in]ubUpper bound (dimension nx)
[in]xinitInitial guess (dimension nx)
Returns
The solution of the problem

Definition at line 69 of file box-qp.cpp.


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