Class BoxQP

Class Documentation

class BoxQP

This class implements a Box QP solver based on a Projected Newton method.

We consider a box QP problem of the form:

\[\begin{split}\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*}\end{split}\]
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:

Public 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.

Parameters:

  • nx – [in] Dimension of the decision vector

  • maxiter – [in] Maximum number of allowed iterations (default 100)

  • th_acceptstep – [in] Acceptance step threshold (default 0.1)

  • th_grad – [in] Gradient tolerance threshold (default 1e-9)

  • reg – [in] Regularization value (default 1e-9)

~BoxQP()

Destroy the Projected-Newton QP solver.

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:

  • H – [in] Hessian (dimension nx * nx)

  • q – [in] Gradient (dimension nx)

  • lb – [in] Lower bound (dimension nx)

  • ub – [in] Upper bound (dimension nx)

  • xinit – [in] Initial guess (dimension nx)

Returns:

The solution of the problem

const BoxQPSolution &get_solution() const

Return the stored solution.

std::size_t get_nx() const

Return the decision vector dimension.

std::size_t get_maxiter() const

Return the maximum allowed number of iterations.

double get_th_acceptstep() const

Return the acceptance step threshold.

double get_th_grad() const

Return the gradient tolerance threshold.

double get_reg() const

Return the regularization value.

const std::vector<double> &get_alphas() const

Return the stack of step lengths using by the line-search procedure.

void set_nx(const std::size_t nx)

Modify the decision vector dimension.

void set_maxiter(const std::size_t maxiter)

Modify the maximum allowed number of iterations.

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.

void set_reg(const double reg)

Modify the regularization value.

void set_alphas(const std::vector<double> &alphas)

Modify the stack of step lengths using by the line-search procedure.