×

zbMATH — the first resource for mathematics

PAL-Hom method for QP and an application to LP. (English) Zbl 1414.90224
Summary: In this paper, a proximal augmented Lagrangian homotopy (PAL-Hom) method for solving convex quadratic programming problems is proposed. This method takes the proximal augmented Lagrangian method as the outer iteration. To solve the proximal augmented Lagrangian subproblems, a homotopy method is presented as the inner iteration. The homotopy method tracks the piecewise-linear solution path of a parametric quadratic programming problem whose start problem takes an approximate solution as its solution and the target problem is the subproblem to be solved. To improve the performance of the homotopy method, the accelerated proximal gradient method is used to obtain a fairly good approximate solution that implies a good prediction of the optimal active set. Moreover, a sorting technique for the Cholesky factor update as well as an \(\varepsilon \)-relaxation technique for checking primal-dual feasibility and correcting the active sets are presented to improve the efficiency and robustness of the homotopy method. Simultaneously, a proximal-point-based AL-Hom method which is shown to converge in finite number of steps, is applied to linear programming. Numerical experiments on randomly generated problems and the problems from the CUTEr and Netlib test collections, support vector machines (SVMs) and contact problems of elasticity demonstrate that PAL-Hom is faster than the active-set methods and the parametric active set methods and is competitive to the interior-point methods and the specialized algorithms designed for specific models (e.g., sequential minimal optimization method for SVMs).
MSC:
90C05 Linear programming
90C20 Quadratic programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Averick, B.M., Carter, R.G., Xue, G.L., Moré, J.J.: The minpack-2 test problem collection. Technical Report, Argonne National Lab., IL, USA (1992)
[2] Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[3] Best, M.J.: An algorithm for the solution of the parametric quadratic programming problem. CORR 82-14, Department of Combinatorics and Optimization, University of Waterloo, Canada (1982)
[4] Best, M.J.: An Algorithm for the Solution of the Parametric Quadratic Programming Problem. Springer, Berlin (1996) · Zbl 0906.65064
[5] Bongartz, I.; Conn, AR; Gould, N.; Toint, PL, Cute: constrained and unconstrained testing environment, ACM Trans. Math. Softw. (TOMS), 21, 123-160, (1995) · Zbl 0886.65058
[6] Buys, J.D.: Dual Algorithms for Constrained Optimization Problems. Brondder-Offset, Rotterdam (1972)
[7] Chang, C.C., Lin, C.J.: LIBSVM: A library for support vector machines. ACM Trans. Intell. Syst. Technol. 2,( 27): 1-27 (2011). http://www.csie.ntu.edu.tw/ cjlin/libsvm
[8] Conn, AR; Gould, NIM; Toint, PL, A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds, SIAM J. Numer. Anal., 28, 545-572, (1991) · Zbl 0724.65067
[9] Conn, A.R., Gould, N.I.M., Toint, P.L.: LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization (Release A). Springer, Berlin (2013) · Zbl 0761.90087
[10] Cornuejols, G., Tütüncü, R.: Optimization Methods in Finance. Cambridge University Press, Cambridge (2006) · Zbl 1117.91031
[11] Dostál, Z.; Friedlander, A.; Santos, SA, Augmented Lagrangians with adaptive precision control for quadratic programming with simple bounds and equality constraints, SIAM J. Optim., 13, 1120-1140, (2003) · Zbl 1043.65076
[12] Dostál, Z.; Gomes, FAM; Santos, SA, Duality-based domain decomposition with natural coarse-space for variational inequalities, J. Comput. Appl. Math., 126, 397-415, (2000) · Zbl 0970.65074
[13] Dostál, Z.; Gomes, FAM; Santos, SA, Solution of contact problems by feti domain decomposition with natural coarse space projections, Comput. Methods Appl. Mech. Eng., 190, 1611-1627, (2000) · Zbl 1005.74064
[14] Fan, RE; Chen, PH; Lin, CJ, Working set selection using second order information for training support vector machines, J. Mach. Learn. Res., 6, 1889-1918, (2005) · Zbl 1222.68198
[15] Ferreau, H.J.: An Online Active Set Strategy for Fast Solution of Parametric Quadratic Programs with Applications to Predictive Engine Control. University of Heidelberg, Heidelberg (2006)
[16] Ferreau, HJ; Bock, HG; Diehl, M., An online active set strategy to overcome the limitations of explicit MPC, Int. J. Robust Nonlinear Control, 18, 816-830, (2008) · Zbl 1284.93100
[17] Ferreau, HJ; Kirches, C.; Potschka, A.; Bock, HG; Diehl, M., qpOASES: a parametric active-set algorithm for quadratic programming, Math. Progr. Comput., 6, 327-363, (2014) · Zbl 1302.90146
[18] Fletcher, R., A general quadratic programming algorithm, IMA J. Numer. Anal., 7, 76-91, (1971) · Zbl 0226.90036
[19] Fletcher, R., Stable reduced hessian updates for indefinite quadratic programming, Math. Progr., 87, 251-264, (2000) · Zbl 0964.65065
[20] Forsgren, A., E, P.G., Wong, E.: Primal and dual active-set methods for convex quadratic programming. Math. Progr. 159(1-2), 469-508 (2016) · Zbl 1346.90652
[21] Gay, DM, Electronic mail distribution of linear programming test problems, Math. Progr. Soc. COAL Newsl., 13, 10-12, (1985)
[22] Gill, P.E., Murray, W., Saunders, M.A.: User’s Guide for Qpopt 1.0: A Fortran Package for Quadratic Programming, Technical Report SOL 95-4, Systems Optimization Laboratory, Dept. Operations Research, Stanford University (1995)
[23] Gill, P.E., Murray, W., Saunders, M.A.: User’s Guide for Snopt Version 7: Software for Large-scale Linear and Quadratic Programming. Report NA 05-2, Department of Mathematics, University of California, San Diego (2008)
[24] Gill, PE; Murray, W.; Saunders, MA; Tomlin, JA; Wright, MH, On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, Math. Progr., 36, 183-209, (1986) · Zbl 0624.90062
[25] Gill, PE; Wong, E., Methods for convex and general quadratic programming, Math. Progr. Comput., 7, 71-112, (2015) · Zbl 1317.90225
[26] Gould, NI, An algorithm for large-scale quadratic programming, IMA J. Numer. Anal., 11, 299-324, (1991) · Zbl 0727.65055
[27] Hager, W.W., c. Zhang, H.: A new active set algorithm for box constrained optimization. SIAM J. Optim. 17(2), 526-557 (2006) · Zbl 1165.90570
[28] Hestenes, MR, Multiplier and gradient methods, J. Optim. Theory Appl., 4, 303-320, (1969) · Zbl 0174.20705
[29] Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: Proceedings of the sixteenth Annual ACM Symposium onTheory of Computing, pp. 302-311. ACM (1984) · Zbl 0557.90065
[30] Lichman, M.: UCI machine learning repository (2013). http://archive.ics.uci.edu/ml
[31] Lin, CJ; Moré, JJ, Newton’s method for large bound-constrained optimization problems, SIAM J. Optim., 9, 1100-1127, (1999) · Zbl 0957.65064
[32] Mangasarian, OL, Iterative solution of linear programs, SIAM J. Numer. Anal., 18, 606-614, (1981) · Zbl 0471.65033
[33] Mangasarian, OL; Meyer, RR, Nonlinear perturbation of linear programs, SIAM J. Control Optim., 17, 745-752, (1979) · Zbl 0432.90047
[34] Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 575-601, (1992) · Zbl 0773.90047
[35] Nesterov, Y., Smooth minimization of non-smooth functions, Math. Progr., 103, 127-152, (2005) · Zbl 1079.90102
[36] Nesterov, Y., et al.: Gradient methods for minimizing composite objective function. In: Technical report, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain (2007)
[37] Osuna, E., Freund, R., Girosi, F.: An improved training algorithm for support vector machines. In: Proceedings of the VII IEEE Workshop Neural Networks for Signal Processing, pp. 276-285. IEEE (1997)
[38] Powell, MJD; Fletcher, R. (ed.), A method for nonlinear constraints in minimization problems, 283-298, (1969), London
[39] Ritter, K.: On Parametric Linear and Quadratic Programming Problems. Technical Report, DTIC Document (1981) · Zbl 0535.90086
[40] Ritter, K.; Meyer, M., A method for solving nonlinear maximum-problems depending on parameters, Nav. Res. Logist. (NRL), 14, 147-162, (1967) · Zbl 0149.38101
[41] Rockafellar, RT, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1, 97-116, (1976) · Zbl 0402.90076
[42] Sra, S., Nowozin, S., Wright, S.J.: Optimization for Machine Learning. MIT Press, Cambridge (2012)
[43] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Progr., 106, 25-57, (2006) · Zbl 1134.90542
[44] Wright, SJ, Implementing proximal point methods for linear programming, J. Optim. Theory Appl., 65, 531-554, (1990) · Zbl 0676.90042
[45] Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997) · Zbl 0863.65031
[46] Yuan, YX, Analysis on a superlinearly convergent augmented Lagrangian method, Acta Math. Sin. Engl. Ser., 30, 1-10, (2014) · Zbl 1292.90287
[47] Zhang, Y., Solving large-scale linear programs by interior-point methods under the matlab environment, Optim. Methods Softw., 10, 1-31, (1998) · Zbl 0916.90208
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.