×

qpOASES: a parametric active-set algorithm for quadratic programming. (English) Zbl 1302.90146

Summary: Many practical applications lead to optimization problems that can either be stated as quadratic programming (QP) problems or require the solution of QP problems on a lower algorithmic level. One relatively recent approach to solve QP problems are parametric active-set methods that are based on tracing the solution along a linear homotopy between a QP problem with known solution and the QP problem to be solved. This approach seems to make them particularly suited for applications where a-priori information can be used to speed-up the QP solution or where high solution accuracy is required. In this paper we describe the open-source C++ software package qpOASES, which implements a parametric active-set method in a reliable and efficient way. Numerical tests show that qpOASES can outperform other popular academic and commercial QP solvers on small- to medium-scale convex test examples of the Maros-Mészáros QP collection. Moreover, various interfaces to third-party software packages make it easy to use, even on embedded computer hardware. Finally, we describe how qpOASES can be used to compute critical points of nonconvex QP problems.

MSC:

90C20 Quadratic programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Croz, J.D., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide, 3rd edn. SIAM, Philadelphia, PA (1999) · Zbl 0934.65030
[2] Ängeby, J., Huschenbett, M., Alberer, D.: Automotive Model Predictive Control, MIMO Model Predictive Control for Integral Gas Engines. In: Lecture Notes in Control and Information Sciences, vol. 402, pp. 257-272, Springer, Berlin (2010) · Zbl 1222.93067
[3] Arnold, E., Neupert, J., Sawodny, O., Schneider, K.: Trajectory tracking for boom cranes based on nonlinear control and optimal trajectory generation. In: IEEE International Conference on Control Applications, pp. 1444-1449 (2007). doi:10.1109/CCA.2007.4389439 · Zbl 1284.93100
[4] Bartels, R., Golub, G.: The simplex method for linear programming using LU decomposition. Commun. ACM 12(5), 266-268 (1969) · Zbl 0181.19104 · doi:10.1145/362946.362974
[5] Bartlett, R., Biegler, L.: QPSchur: a dual, active set, Schur complement method for large-scale and structured convex quadratic programming algorithm. Optim. Eng. 7, 5-32 (2006) · Zbl 1167.90615 · doi:10.1007/s11081-006-6588-z
[6] Benzi, M., Golub, G., Liesen, J.: Numerical solution of saddle-point problems. Acta Numerica 14, 1-137 (2005) · Zbl 1115.65034 · doi:10.1017/S0962492904000212
[7] Best, M.: An Algorithm for the Solution of the Parametric Quadratic Programming Problem. In: Applied Mathematics and Parallel Computing, pp. 57-76. Physica, Heidelberg (1996) · Zbl 0906.65064
[8] Blackford, L.S., Demmel, J., Dongarra, J., Duff, I.: An updated set of basic linear algebra subprograms (BLAS). ACM Trans. Math. Softw. 28, 135-151 (2002) · Zbl 1070.65520 · doi:10.1145/567806.567807
[9] Bock, H., Plitt, K.: A multiple shooting algorithm for direct solution of optimal control problems. In: Proceedings 9th IFAC World Congress, pp. 242-247. Pergamon Press, Budapest (1984) · Zbl 1167.90615
[10] Contesse, L.: Une charactérisation complète des minima locaux en programmation quadratique. Numerische Mathematik 34, 315-332 (1980) · Zbl 0422.90061 · doi:10.1007/BF01396705
[11] Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963) · Zbl 0108.33103
[12] Diehl, M., Ferreau, H.J., Haverbeke, N.: Nonlinear model predictive control, Efficient Numerical Methods for Nonlinear MPC and Moving Horizon Estimation. In: Lecture Notes in Control and Information Sciences, vol. 384, pp. 391-417. Springer, Berlin (2009) · Zbl 1195.93038
[13] Eaton, J.W.: GNU Octave Manual. Network Theory Limited (2002)
[14] Ferreau, H.J.: An Online Active Set Strategy for Fast Solution of Parametric Quadratic Programs with Applications to Predictive Engine Control. Master’s thesis, University of Heidelberg (2006) · Zbl 0537.90081
[15] Ferreau, H.J., et al.: qpOASES User’s Manual. http://www.qpOASES.org (2007-2014) · Zbl 0727.65055
[16] Ferreau, H.J.: Model predictive control algorithms for applications with millisecond timescales. PhD thesis, KU Leuven (2011)
[17] Ferreau, H.J., Diehl, M.: Online QP Benchmark Collection. http://www.qpOASES.org/onlineQP (2006-2008)
[18] Ferreau, H.J., Ortner, P., Langthaler, P., del Re, L., Diehl, M.: Predictive control of a real-world diesel engine using an extended online active set strategy. Annu. Rev. Control 31(2), 293-301 (2007) · doi:10.1016/j.arcontrol.2007.09.001
[19] Ferreau, H.J., Bock, H.G., Diehl, M.: An online active set strategy to overcome the limitations of explicit MPC. Int. J. Robust Nonlinear Control 18(8), 816-830 (2008) · Zbl 1284.93100 · doi:10.1002/rnc.1251
[20] Fletcher, R.: Practical Methods of Optimization, 2nd edn. Wiley, Chichester (1987) · Zbl 0905.65002
[21] Fletcher, R.: Approximation Theory and Optimization, Dense factors of sparse matrices. In: Tributes to M.J.D. Powell, pp. 145-166. Cambridge University Press, Cambridge (1997) · Zbl 1031.65043
[22] Fletcher, R.: Stable reduced Hessian updates for indefinite quadratic programming. Numerical Analysis Report NA/187, Department of Mathematics and Computer Science, University of Dundee, Dundee DD1 4HN, Scotland, UK (1999) · Zbl 0964.65065
[23] Fletcher, R., Matthews, S.: Stable modification of explicit LU factors for simplex updates. Math. Progr. 30(3), 267-284 (1984) · Zbl 0574.65057 · doi:10.1007/BF02591933
[24] Gertz, E., Wright, S.: Object-oriented software for quadratic programming. ACM Trans. Math. Softw. 29(1), 58-81 (2003) · Zbl 1068.90586 · doi:10.1145/641876.641880
[25] Gill, P., Golub, G., Murray, W., Saunders, M.A.: Methods for modifying matrix factorizations. Math. Comput. 28(126), 505-535 (1974) · Zbl 0289.65021 · doi:10.1090/S0025-5718-1974-0343558-6
[26] Gill, P., Murray, W., Saunders, M., Wright, M.: Procedures for optimization problems with a mixture of bounds and general linear constraints. ACM Trans. Math. Softw. 10(3), 282-298 (1984) · Zbl 0562.90079 · doi:10.1145/1271.1276
[27] Gill, P., Murray, W., Saunders, M., Wright, M.: Maintaining LU factors of a general sparse matrix. Linear Algebra Appl. 88(89), 239-270 (1987) · Zbl 0618.65019 · doi:10.1016/0024-3795(87)90112-1
[28] Goldfarb, D., Idnani, A.: A numerically stable dual method for solving strictly convex quadratic programs. Math. Progr. 27, 1-33 (1983) · Zbl 0537.90081 · doi:10.1007/BF02591962
[29] Gould, N.: An algorithm for large-scale quadratic programming. IMA J. Numer. Anal. 11(3), 299-324 (1991) · Zbl 0727.65055 · doi:10.1093/imanum/11.3.299
[30] Gould, N., Toint, P.: A quadratic programming bibliography. Tech. Rep. 2000-1, Rutherford Appleton Laboratory, Computational Science and Engineering Department (2010) · Zbl 1216.90069
[31] Gould, N., Toint, P.: A quadratic programming page. http://www.numerical.rl.ac.uk/qp/qp.html (2012) · Zbl 1235.90118
[32] Gould, N., Orban, D., Toint, P.: CUTEr testing environment for optimization and linear algebra solvers. http://cuter.rl.ac.uk/cuter-www/, (2002)
[33] Harris, P.: Pivot selection methods of the DEVEXLP code. Math. Progr. 5, 1-29 (1973) · Zbl 0261.90031 · doi:10.1007/BF01580108
[34] van Heesch, D.: Doxygen homepage (1997-2011). http://www.doxygen.org · Zbl 0358.90053
[35] Houska, B., Ferreau, H.J., Diehl, M.: ACADO Toolkit—an open source framework for automatic control and dynamic optimization. Optim. Control Appl. Methods 32(3), 298-312 (2011) · Zbl 1218.49002 · doi:10.1002/oca.939
[36] Huynh, H.: A large-scale quadratic programming solver based on block-LU updates of the KKT system. PhD thesis, Stanford University (2008) · Zbl 0422.90061
[37] IBM Corp: IBM ILOG CPLEX V12.1, User’s Manual for CPLEX (2009)
[38] Inc TM: Real-Time Workshop for Use with SIMULINK, User’s Guide (1999)
[39] Karmarkar, N.: A new polynomial time algorithm for linear programming. Combinatorica 4, 373-395 (1984) · Zbl 0557.90065 · doi:10.1007/BF02579150
[40] Kirches, C., Bock, H., Schlöder, J., Sager, S.: A factorization with update procedures for a KKT matrix arising in direct optimal control. Math. Progr. Comput. 3(4), 319-348 (2011) · Zbl 1276.90046 · doi:10.1007/s12532-011-0030-z
[41] Kostina, E.: The long step rule in the bounded-variable dual simplex method: numerical experiments. Math. Methods Oper. Res. 55(3), 413-429 (2002) · Zbl 1031.90010 · doi:10.1007/s001860200188
[42] Leineweber, D., Bauer, I., Schäfer, A., Bock, H., Schlöder, J.: An efficient multiple shooting based reduced SQP strategy for large-scale dynamic process optimization (parts I and II). Comput. Chem. Eng. 27, 157-174 (2003) · doi:10.1016/S0098-1354(02)00158-8
[43] Löfberg, J.: YALMIP: A toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004). http://users.isy.liu.se/johanl/yalmip
[44] Maros, I., Meszaros, C.: A repository of convex quadratic programming problems. Optim. Methods Softw. 11, 431-449 (1999) · Zbl 0973.90520 · doi:10.1080/10556789908805768
[45] Murty, K.: Some NP-complete problems in quadratic and nonlinear programming. Math. Progr. 39, 117-129 (1987) · Zbl 0637.90078 · doi:10.1007/BF02592948
[46] Nesterov, Y.: Introductory lectures on convex optimization: a basic course. In: Applied Optimization, vol. 87. Kluwer Academic Publishers, Dordrecht (2003) · Zbl 1086.90045
[47] Nesterov, Y., Nemirovski, A.: Interior-point Polynomial Algorithms in Convex Programming. In: Society for Industrial Mathematics (1994)
[48] Nocedal, J., Wright, S.: Springer series in operations research and financial engineering. In: Numerical Optimization, 2nd edn. Springer, Berlin (2006) · Zbl 0637.90078
[49] Rauter, G., von Zitzewitz, J., Duschau-Wicke, A., Vallery, H., Riener, R.: A tendon-based parallel robot applied to motor learning in sports. In: Proceedings of the IEEE International Conference on Biomedical Robotics and Biomechatronics 2010, Japan (2010)
[50] Rockafellar, R.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877-898 (1976) · Zbl 0358.90053 · doi:10.1137/0314056
[51] Sager, S.: Lange Schritte im Dualen Simplex-Algorithmus. Master’s thesis, Universität Heidelberg (2001) · Zbl 0103.37603
[52] Scilab Consortium: Scilab: The free software for numerical computation. Scilab Consortium, Digiteo, Paris, France (2011). http://www.scilab.org · Zbl 0181.19104
[53] Takács, G., Rohal’-Ilkiv, B.: Predictive vibration control: efficient constrained MPC vibration control for lightly damped mechanical systems. Springer, Berlin (2012) · Zbl 1253.93005 · doi:10.1007/978-1-4471-2333-0
[54] Van den Broeck, L.: Time optimal control of mechatronic systems through embedded optimization. PhD thesis, KU Leuven (2011)
[55] Wang, X.: Resolution of Ties in Parametric Quadratic Programming. Master’s thesis, University of Waterloo, Ontario, Canada (2004)
[56] Wilkinson, J.: The Algebraic Eigenvalue Problem. Clarendon Press, Oxford (1965) · Zbl 0258.65037
[57] Wills, A., Bates, D., Fleming, A., Ninness, B., Moheimani, S.: Application of MPC to an active structure using sampling rates up to 25kHz. In: 44th IEEE Conference on Decision and Control and European Control Conference ECC’05, Seville (2005)
[58] Wolfe, P.: The simplex method for quadratic programming. Econometrica 27, 382-398 (1959) · Zbl 0103.37603 · doi:10.2307/1909468
[59] Wright, S.: Primal-Dual Interior-Point Methods. SIAM Publications, Philadelphia (1997) · Zbl 0863.65031 · doi:10.1137/1.9781611971453
[60] Wunderling, R.: Paralleler und Objektorientierter Simplex-Algorithmus. PhD thesis, Konrad-Zuse-Zentrum Berlin (1996) · Zbl 0871.65048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.