qpmad

CI status	Debian package

Eigen-based, header-only C++ implementation of Goldfarb-Idnani dual active set algorithm for quadratic programming. The package is ROS compatible.

The solver is optimized for performance, for this reason some of the computations are omitted as described below. See https://github.com/asherikov/qpmad_benchmark for comparison with qpOASES and eiQuadProg.

Contents

• Links
• Features
• Dependencies
• Notes
• Documentation
• FAQ

Links =====

• Doxygen: https://asherikov.github.io/qpmad/
• GitHub: https://github.com/asherikov/qpmad

Features: =========

• Double sided inequality constraints: lb <= A*x <= ub. Such constraints can be handled in a more efficient way than lb <= A*x commonly used in other implementations of the algorithm. A can be sparse.

• Simple bounds: lb <= x <= ub.

• Lazy data initialization, e.g., perform inversion of the Cholesky factor only if some of the constraints are activated.

• Works with positive-definite problems only (add regularization if necessary).

• Performs in-place factorization of Hessian and can reuse it on subsequent iterations. Can optionally store inverted Cholesky factor in the Hessian matrix for additional performance gain.

• Does not compute value of the objective function.

• Does not compute/update Lagrange multipliers for equality constraints.

• Three types of memory allocation:

  • on demand (default);
  • on compile time using template parameters;
  • dynamic preallocation using reserve() method.

Dependencies: =============

• C++14 compatible compiler
• cmake >= 3.0
• Eigen >= 3.3.0
• Boost (for C++ tests)

Notes: ======

1. Before computing the full step length I check that the dot product of the chosen constraint with the step direction is not zero instead of checking the norm of the step direction. The former approach makes more sense since the said dot product appears later as a divisor and we can avoid computation of a useless norm.

2. I am aware that activation of simple bounds zeroes out parts of matrix ‘J’. Unfortunately, I don’t see a way to exploit this on modern hardware –

File truncated at 100 lines see the full file