Template Class BoxQPTpl

Class Documentation

template<typename _Scalar>
class BoxQPTpl

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 Types

typedef BoxQPSolutionTpl<Scalar> BoxQPSolution
typedef MathBaseTpl<Scalar> MathBase
typedef MathBase::VectorXs VectorXs
typedef MathBase::MatrixXs MatrixXs

Public Functions

BoxQPTpl(const std::size_t nx, const std::size_t maxiter = 100, const Scalar th_acceptstep = Scalar(0.1), const Scalar th_grad = Scalar(1e-9), const Scalar reg = Scalar(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)

~BoxQPTpl() = default

Destroy the Projected-Newton QP solver.

const BoxQPSolution &solve(const MatrixXs &H, const VectorXs &q, const VectorXs &lb, const VectorXs &ub, const VectorXs &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

template<typename NewScalar>
BoxQPTpl<NewScalar> cast() const

Cast the BoxQP solver to a different scalar type.

It is useful for operations requiring different precision or scalar types.

Template Parameters:

NewScalar – The new scalar type to cast to.

Returns:

BoxQPTpl<NewScalar> A BoxQP solver with the new scalar type.

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.

Scalar get_th_acceptstep() const

Return the acceptance step threshold.

Scalar get_th_grad() const

Return the gradient tolerance threshold.

Scalar get_reg() const

Return the regularization value.

const std::vector<Scalar> &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 Scalar th_acceptstep)

Modify the acceptance step threshold.

void set_th_grad(const Scalar th_grad)

Modify the gradient tolerance threshold.

void set_reg(const Scalar reg)

Modify the regularization value.

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

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

Public Members

EIGEN_MAKE_ALIGNED_OPERATOR_NEW typedef _Scalar Scalar