Software & Data Downloads — PQP

Parallel Quadratic Programming for solving problems involving convex optimization.

An iterative multiplicative algorithm is proposed for the fast solution of quadratic programming (QP) problems that arise in the real-time implementation of Model Predictive Control (MPC). The proposed algorithm—Parallel Quadratic Programming (PQP)—is amenable to fine-grained parallelization. Conditions on the convergence of the PQP algorithm are given and proved. Due to its extreme simplicity, even serial implementations offer considerable speed advantages. To demonstrate, PQP is applied to several simulation examples, including a stand-alone QP problem and two MPC examples. When implemented in MATLAB using single-thread computations, numerical simulations of PQP demonstrate a 5 - 10x speed-up compared to the MATLAB active-set based QP solver quadprog. A parallel implementation would offer a further speed-up, linear in the number of parallel processors.

    •  Di Cairano, S., Brand, M., "On a Multiplicative Update Dual Optimization Algorithm for Constrained Linear MPC", IEEE Conference on Decision and Control (CDC), December 2013.
      BibTeX TR2013-108 PDF Software
      • @inproceedings{DiCairano2013dec2,
      • author = {{Di Cairano}, S. and Brand, M.},
      • title = {On a Multiplicative Update Dual Optimization Algorithm for Constrained Linear MPC},
      • booktitle = {IEEE Conference on Decision and Control (CDC)},
      • year = 2013,
      • month = dec,
      • url = {https://www.merl.com/publications/TR2013-108}
      • }
    •  Di Cairano, S., Brand, M., Bortoff, S.A., "Projection-free Parallel Quadratic Programming for Linear Model predictive Control", International Journal of Control, July 2013.
      BibTeX TR2013-059 PDF Software
      • @article{DiCairano2013jul,
      • author = {{Di Cairano}, S. and Brand, M. and Bortoff, S.A.},
      • title = {Projection-free Parallel Quadratic Programming for Linear Model predictive Control},
      • journal = {International Journal of Control},
      • year = 2013,
      • month = jul,
      • url = {https://www.merl.com/publications/TR2013-059}
      • }
    •  Brand, M., Chen, D., "Parallel Quadratic Programming for Image Processing", IEEE International Conference on Image Processing (ICIP), DOI: 10.1109/​ICIP.2011.6116089, September 2011, pp. 2261-2264.
      BibTeX TR2011-064 PDF Software
      • @inproceedings{Brand2011sep,
      • author = {Brand, M. and Chen, D.},
      • title = {Parallel Quadratic Programming for Image Processing},
      • booktitle = {IEEE International Conference on Image Processing (ICIP)},
      • year = 2011,
      • pages = {2261--2264},
      • month = sep,
      • doi = {10.1109/ICIP.2011.6116089},
      • url = {https://www.merl.com/publications/TR2011-064}
      • }
    •  Brand, M., Shilpiekandula, V., Bortoff, S.A., "A Parallel Quadratic Programming Algorithm for Model Predictive Control", World Congress of the International Federation of Automatic Control (IFAC), August 2011, vol. 18.
      BibTeX TR2011-056 PDF Software
      • @inproceedings{Brand2011aug,
      • author = {Brand, M. and Shilpiekandula, V. and Bortoff, S.A.},
      • title = {A Parallel Quadratic Programming Algorithm for Model Predictive Control},
      • booktitle = {World Congress of the International Federation of Automatic Control (IFAC)},
      • year = 2011,
      • volume = 18,
      • month = aug,
      • url = {https://www.merl.com/publications/TR2011-056}
      • }

    Access software at https://github.com/merlresearch/PQP.