×

Methods for convex and general quadratic programming. (English) Zbl 1317.90225

Summary: Computational methods are considered for finding a point that satisfies the second-order necessary conditions for a general (possibly nonconvex) quadratic program (QP). The first part of the paper considers the formulation and analysis of an active-set method for a generic QP with both equality and inequality constraints. The method uses a search direction that is the solution of an equality-constrained subproblem involving a “working set” of linearly independent constraints. The method is a reformulation of a method for general QP first proposed by R. Fletcher [J. Inst. Math. Appl. 7, 76–91 (1971; Zbl 0226.90036)], and modified subsequently by N. I. M. Gould [IMA J. Numer. Anal. 11, No. 3, 299–234 (1991; Zbl 0727.65055)]. The reformulation facilitates a simpler analysis and has the benefit that the algorithm reduces to a variant of the simplex method when the QP is a linear program. The search direction is computed from a KKT system formed from the QP Hessian and the gradients of the working-set constraints. It is shown that, under certain circumstances, the solution of this KKT system may be updated using a simple recurrence relation, thereby giving a significant reduction in the number of KKT systems that need to be solved. The second part of the paper focuses on the solution of QP problems with constraints in so-called standard form. We describe how the constituent KKT systems are solved, and discuss how an initial basis is defined. Numerical results are presented for all QPs in the CUTEst test collection.

MSC:

90C20 Quadratic programming
90C06 Large-scale problems in mathematical programming
65K05 Numerical mathematical programming methods
90C25 Convex programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amestoy, P.R., Duff, I.S., L’Excellent, J.-Y., Koster, J.: A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J. Matrix Anal. Appl. 23(1), 15-41 (2001). (electronic) · Zbl 0992.65018
[2] Ashcraft, C., Grimes, R.: SPOOLES: an object-oriented sparse matrix library. In: Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing 1999 (San Antonio, TX), p. 10. SIAM, Philadelphia (1999) · Zbl 0637.90078
[3] Bartlett, R.A., Biegler, L.T.: QPSchur: a dual, active-set, Schur-complement method for large-scale and structured convex quadratic programming. Optim. Eng. 7(1), 5-32 (2006) · Zbl 1167.90615
[4] Best, MJ; Fischer, H. (ed.); Riedmüller, B. (ed.); Schäffler, S. (ed.), An algorithm for the solution of the parametric quadratic programming problem, 57-76 (1996), Heidelberg · Zbl 0906.65064
[5] Bisschop, J., Meeraus, A.: Matrix augmentation and partitioning in the updating of the basis inverse. Math. Progr. 13, 241-254 (1977) · Zbl 0372.90083
[6] Borwein, J.M.: Necessary and sufficient conditions for quadratic minimality. Numer. Funct. Anal. Optim. 5, 127-140 (1982) · Zbl 0507.90091
[7] Bunch, J.R., Kaufman, L.: A computational method for the indefinite quadratic programming problem. Linear Algebra Appl. 34, 341-370 (1980) · Zbl 0473.65036
[8] Contesse, L.B.: Une caractérisation complète des minima locaux en programmation quadratique. Numer. Math. 34, 315-332 (1980) · Zbl 0422.90061
[9] Cottle, R.W., Habetler, G.J., Lemke, C.E.: On classes of copositive matrices. Linear Algebra Appl. 3, 295-310 (1970) · Zbl 0196.05602
[10] Davis, T.A.: Algorithm 832: UMFPACK V4.3—an unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30(2), 196-199 (2004) · Zbl 1072.65037
[11] Davis, T.A.: A column pre-ordering strategy for the unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30(2), 167-195 (2004) · Zbl 1072.65036
[12] Davis, T.A., Duff, I.S.: An unsymmetric-pattern multifrontal method for sparse \[LU\] LU factorization. SIAM J. Matrix Anal. Appl. 18(1), 140-158 (1997) · Zbl 0884.65021
[13] Davis, T.A., Duff, I.S.: A combined unifrontal/multifrontal method for unsymmetric sparse matrices. ACM Trans. Math. Softw. 25(1), 1-20 (1999) · Zbl 0962.65027
[14] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with COPS. Technical Memorandum ANL/MCS-TM-246. Argonne National Laboratory, Argonne (2000) · Zbl 0992.65018
[15] Duff, I.S.: MA57—a code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Softw. 30(2), 118-144 (2004) · Zbl 1070.65525
[16] Duff, I.S., Reid, J.K.: The multifrontal solution of indefinite sparse symmetric linear equations. ACM Trans. Math. Softw. 9, 302-325 (1983) · Zbl 0515.65022
[17] Eldersveld, S.K., Saunders, M.A.: A block-LU update for large-scale linear programming. SIAM J. Matrix Anal. Appl. 13, 191-201 (1992) · Zbl 0753.65050
[18] Ferreau, H.J.: An Online Active Set Strategy for Fast Solution of Parametric Quadratic Programs with Applications to Predictive Engine Control. Ph.D. thesis, University of Heidelberg (2006) · Zbl 1210.90176
[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
[20] Fletcher, R.: A general quadratic programming algorithm. J. Inst. Math. Appl. 7, 76-91 (1971) · Zbl 0226.90036
[21] Forsgren, A., Gill, P.E., Murray, W.: On the identification of local minimizers in inertia-controlling methods for quadratic programming. SIAM J. Matrix Anal. Appl. 12, 730-746 (1991) · Zbl 0737.65047
[22] Friedlander, M.P., Leyffer, S.: Global and finite termination of a two-phase augmented Lagrangian filter method for general quadratic programs. SIAM J. Sci. Comput. 30(4), 1706-1729 (2008) · Zbl 1179.65065
[23] Gill, P.E.: Recent developments in numerically stable methods for linear programming. IMA Bull. 10, 180-186 (1973)
[24] Gill, P.E., Gould, N.I.M., Murray, W., Saunders, M.A., Wright, M.H.: A weighted Gram-Schmidt method for convex quadratic programming. Math. Program. 30, 176-195 (1984) · Zbl 0545.90080
[25] Gill, P.E., Murray, W.: Numerically stable methods for quadratic programming. Math. Program. 14, 349-372 (1978) · Zbl 0374.90054
[26] Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM Rev. 47, 99-131 (2005) · Zbl 1210.90176
[27] Gill, P.E., Murray, W., Saunders, M.A.: User’s Guide for SQOPT Version 7: Software for Large-Scale Linear and Quadratic Programming. Numerical Analysis Report 06-1, Department of Mathematics, University of California, San Diego, La Jolla (2006) · Zbl 0584.90069
[28] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: Sparse matrix methods in optimization. SIAM J. Sci. Stat. Comput. 5(3), 562-589 (1984) · Zbl 0559.65042
[29] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: Maintaining \[LU\] LU factors of a general sparse matrix. Linear Algebra Appl. 88(89), 239-270 (1987) · Zbl 0618.65019
[30] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: A practical anti-cycling procedure for linearly constrained optimization. Math. Progr. 45, 437-474 (1989) · Zbl 0688.90038
[31] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: A Schur-complement method for sparse quadratic programming. In: Cox, M.G., Hammarling, S.J. (eds.) Reliable Numerical Computation. pp. 113-138. Oxford University Press, Oxford (1990) · Zbl 0725.65060
[32] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: Inertia-controlling methods for general quadratic programming. SIAM Rev. 33(1), 1-36 (1991) · Zbl 0734.90062
[33] Gill, P.E., Murray, W., Wright, M.H.: Numerical Linear Algebra and Optimization, vol. 1. Addison-Wesley Publishing Company, Redwood City (1991) · Zbl 0714.65063
[34] Gill, P.E., Wong, E.: Sequential quadratic programming methods. In: Lee, J., Leyffer, S. (eds) Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and its Applications, vol. 154, pp. 147-224. Springer, New York (2012). doi:10.1007/978-1-4614-1927-3_6 · Zbl 1242.90297
[35] Goldfarb, D., Idnani, A.: A numerically stable dual method for solving strictly convex quadratic programs. Math. Progr. 27(1), 1-33 (1983) · Zbl 0537.90081
[36] Gould, N.I.M.: On practical conditions for the existence and uniqueness of solutions to the general equality quadratic programming problem. Math. Progr. 32, 90-99 (1985) · Zbl 0591.90068
[37] Gould, N.I.M.: An algorithm for large-scale quadratic programming. IMA J. Numer. Anal. 11(3), 299-324 (1991) · Zbl 0727.65055
[38] Gould, N.I.M., Orban, D., Toint, P.L.: GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization. ACM Trans. Math. Softw. 29(4), 353-372 (2003) · Zbl 1068.90525
[39] Gould, N.I.M., Orban, D., Toint, P.L.: CUTEst: a constrained and unconstrained testing environment with safe threads. Technical report, Rutherford Appleton Laboratory, Chilton, England (2013) · Zbl 1325.90004
[40] Gould, N.I.M., Toint, P.L.: An iterative working-set method for large-scale nonconvex quadratic programming. Appl. Numer. Math. 43(1-2), 109-128 (2002). 19th Dundee Biennial Conference on Numerical Analysis (2001) · Zbl 1012.65054
[41] Gould, N.I.M., Toint, P.L.: Numerical methods for large-scale non-convex quadratic programming. In: Trends in industrial and applied mathematics (Amritsar, 2001). Appl. Optim., vol. 72, pp. 149-179. Kluwer Academic Publications, Dordrecht (2002) · Zbl 0644.90067
[42] Hall, J.A.J., McKinnon, K.I.M.: The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling. Technical Report MS 96-010, Department of Mathematics and Statistics, University of Edinburgh (1996) · Zbl 1146.90473
[43] Hogg, J.D., Scott, J.A.: \[{\rm HSL\_MA97}\] HSL_MA97: a bit-compatible multifrontal code for sparse symmetric systems. Technical report, Rutherford Appleton Laboratory, Oxon (2011)
[44] HSL: A collection of Fortran codes for large-scale scientific computation. http://www.hsl.rl.ac.uk (2013) · Zbl 0278.90043
[45] Huynh, H.M.: A Large-Scale Quadratic Programming Solver Based on Block-LU Updates of the KKT System. Ph.D. thesis, Program in Scientific Computing and Computational Mathematics, Stanford University, Stanford (2008) · Zbl 1284.93100
[46] Maes, C.M.: A Regularized Active-Set Method for Sparse Convex Quadratic Programming. Ph.D. thesis, Institute for Computational and Mathematical Engineering, Stanford University, Stanford (2010) · Zbl 0992.65018
[47] Majthay, A.: Optimality conditions for quadratic programming. Math. Progr. 1, 359-365 (1971) · Zbl 0246.90038
[48] Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Progr. 39, 117-129 (1987) · Zbl 0637.90078
[49] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer-Verlag, New York (1999) · Zbl 0930.65067
[50] Pardalos, P.M., Schnitger, G.: Checking local optimality in constrained quadratic programming is NP-hard. Oper. Res. Lett. 7(1), 33-35 (1988) · Zbl 0644.90067
[51] Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1(1), 15-22 (1991) · Zbl 0755.90065
[52] Powell, M.J.D.: On the quadratic programming algorithm of Goldfarb and Idnani. Math. Progr. Stud. 25, 46-61 (1985) · Zbl 0584.90069
[53] Ruiz, D.: A scaling algorithm to equilibrate both row and column norms in matrices. Report RAL-TR-2001-034, Rutherford Appleton Laboratory, Oxon (2001)
[54] Saunders. M.A.: LUMOD: Updating a dense square factorization LC = U. http://www.stanford.edu/group/SOL/software/lumod.html
[55] Schenk, O., Gärtner, K.: Solving unsymmetric sparse systems of linear equations with PARDISO. In: Computational Science-ICCS 2002, Part II (Amsterdam). Lecture Notes in Computer Science, vol. 2330, pp. 355-363. Springer, Berlin (2002) · Zbl 1062.65035
[56] Tomlin, J.A.: On pricing and backward transformation in linear programming. Math. Progr. 6, 42-47 (1974) · Zbl 0278.90043
[57] Wong, E.: Active-Set Methods for Quadratic Programming. Ph.D. thesis, Department of Mathematics, University of California San Diego, La Jolla (2011) · Zbl 0884.65021
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.