QPSchur

QPSchur: A dual, active-set, Schur-complement method for large-scale and structured convex quadratic programming We describe an active-set, dual-feasible Schur-complement method for quadratic programming (QP) with positive definite Hessians. The formulation of the QP being solved is general and flexible, and is appropriate for many different application areas. Moreover, the specialized structure of the QP is abstracted away behind a fixed KKT matrix called $K_{o}$ and other problem matrices, which naturally leads to an object-oriented software implementation. Updates to the working set of active inequality constraints are facilitated using a dense Schur complement, which we expect to remain small. Here, the dual Schur complement method requires the projected Hessian to be positive definite for every working set considered by the algorithm. Therefore, this method is not appropriate for all QPs. While the Schur complement approach to linear algebra is very flexible with respect to allowing exploitation of problem structure, it is not as numerically stable as approaches using a QR factorization. However, we show that the use of fixed-precision iterative refinement helps to dramatically improve the numerical stability of this Schur complement algorithm. The use of the object-oriented QP solver implementation is demonstrated on two different application areas with specializations in each area; large-scale model predictive control (MPC) and reduced-space successive quadratic programming (with several different representations for the reduced Hessian). These results demonstrate that the QP solver can exploit application-specific structure in a computationally efficient and fairly robust manner as compared to other QP solver implementations.


References in zbMATH (referenced in 13 articles , 1 standard article )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Curtis, Frank E.; Han, Zheng: Globally convergent primal-dual active-set methods with inexact subproblem solves (2016)
  2. Forsgren, Anders; Gill, Philip E.; Wong, Elizabeth: Primal and dual active-set methods for convex quadratic programming (2016)
  3. Gill, Philip E.; Wong, Elizabeth: Methods for convex and general quadratic programming (2015)
  4. Johnson, Travis C.; Kirches, Christian; Wächter, Andreas: An active-set method for quadratic programming based on sequential hot-starts (2015)
  5. Tian, Da Gang: An exterior point polynomial-time algorithm for convex quadratic programming (2015)
  6. Ferreau, Hans Joachim; Kirches, Christian; Potschka, Andreas; Bock, Hans Georg; Diehl, Moritz: qpOASES: a parametric active-set algorithm for quadratic programming (2014)
  7. Pirnay, Hans; López-Negrete, Rodrigo; Biegler, Lorenz T.: Optimal sensitivity based on IPOPT (2012)
  8. Kirches, Christian; Bock, Hans Georg; Schlöder, Johannes P.; Sager, Sebastian: Block-structured quadratic programming for the direct multiple shooting method for optimal control (2011)
  9. Kirches, Christian; Bock, Hans Georg; Schlöder, Johannes P.; Sager, Sebastian: A factorization with update procedures for a KKT matrix arising in direct optimal control (2011)
  10. Patrinos, Panagiotis; Sopasakis, Pantelis; Sarimveis, Haralambos: A global piecewise smooth Newton method for fast large-scale model predictive control (2011)
  11. Brahmi, Belkacem; Bibi, Mohand Ouamer: Dual support method for solving convex quadratic programs (2010)
  12. Fabien, Brian C.: Parameter optimization using the $L_\infty $ exact penalty function and strictly convex quadratic programming problems (2008)
  13. Bartlett, Roscoe A.; Biegler, Lorenz T.: QPSchur: A dual, active-set, Schur-complement method for large-scale and structured convex quadratic programming (2006)