Abstract
This paper presents an active-set algorithm for large-scale optimization that occupies the middle ground between sequential quadratic programming and sequential linear-quadratic programming methods. It consists of two phases. The algorithm first minimizes a piecewise linear approximation of the Lagrangian, subject to a linearization of the constraints, to determine a working set. Then, an equality constrained subproblem based on this working set and using second derivative information is solved in order to promote fast convergence. A study of the local and global convergence properties of the algorithm highlights the importance of the placement of the interpolation points that determine the piecewise linear model of the Lagrangian.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Allgower E.L., Georg K.: Piecewise linear methods for nonlinear equations and optimization. J. Comput. Appl. Math. 124(1–2), 245–261 (2000)
Bartels R.H., Conn A.R., Sinclair J.W.: Minimization techniques for piecewise differentiable functions—the L1 solution to an overdetermined linear system. SIAM J. Numer. Anal. 15, 224–241 (1978)
Byrd R.H., Gould N.I.M., Nocedal J., Waltz R.A.: An algorithm for nonlinear optimization using linear programming and equality constrained subproblems. Math. Program. Ser. B 100(1), 27–48 (2004)
Byrd R.H., Gould N.I.M., Nocedal J., Waltz R.A.: On the convergence of successive linear-quadratic programming algorithms. SIAM J. Optim. 16(2), 471–489 (2006)
Byrd R.H., Nocedal J., Schnabel R.: Representations of quasi-newton matrices and their use in limited memory methods. Math. Program. 63(4), 129–156 (1994)
Byrd R.H., Nocedal J., Waltz R.A.: Steering exact penalty methods. Optim. Methods Softw. 23(2), 197–213 (2008)
Byrd, R.H., Nocedal, J., López-Calva, G.: A Line Search Exact Penalty Method Using Steering Rules. Technical Report, Optimization Center, Northwestern University (2009)
Byrd, R.H., Nocedal, J., Waltz, R.A., Wu, Y.: On the Implementation of a Method for Nonlinear Programming Based on Piecewise Linear Models. Technical Report, Optimization Center, Northwestern University (2011). Posted on Optimization Online
Byrd R.H., Waltz R.A.: An active-set algorithm for nonlinear programming using parametric linear programming. Optim. Methods Softw. 26(1), 47–66 (2011)
Celis M.R., Dennis J.E., Tapia R.A.: A trust region strategy for nonlinear equality constrained optimization. In: Boggs, P.T., Byrd, R.H., Schnabel, R.B. (eds) Numerical Optimization 1984, SIAM, Philadelphia (1985)
Chen L., Goldfarb D.: An interior-point piecewise linear penalty method for nonlinear programming. Math. Program. 128(1–2), 73–122 (2011)
Chin C.M., Fletcher R.: On the global convergence of an SLP-filter algorithm that takes EQP steps. Math. Program. Ser. A 96(1), 161–177 (2003)
Conn A.R., Gould N.I.M., Toint Ph.: Trust-Region Methods MPS-SIAM Series on Optimization. SIAM, Philadelphia (2000)
Dantzig G.B.: Recent advances in linear programming. Manag. Sci. 2, 131–144 (1956)
Fletcher R., Leyffer S.: Nonlinear programming without a penalty function. Math. Program. 91, 239–269 (2002)
Fletcher R., Sainz de la Maza E.: Nonlinear programming and nonsmooth optimization by successive linear programming. Math. Program. 43(3), 235–256 (1989)
Friedlander, M.P., Gould, N.I.M., Leyffer, S., Munson, T.S.: A Filter Active-Set Trust-Region Method. Technical Report Preprint ANL/MCS-P1456-097, Argonne National Laboratory (2007)
Gill P.E., Murray W., Saunders M.A.: SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM J. Optim. 12, 979–1006 (2002)
Gould, N.I.M., Robinson, D.P.: A Second Derivative SQP Method: Global Convergence. Technical Report NA-08/18, Oxford University Computing Laboratory (2008, Nov) [to appear in SIAM J. Optim.]
Gould, N.I.M., Robinson, D.P.: A Second Derivative SQP Method: Local Convergence. Technical Report NA-08/21, Oxford University Computing Laboratory (2008, Dec) [to appear in SIAM J. Optim.]
Hadley G.: Nonlinear and Dynamic Programming. Addison-Wesley, Reading (1964)
Morales, J.L., Nocedal, J., Wu, Y.: A Sequential Quadratic Programming Algorithm with an Additional Equality Constrained Phase. Technical Report OTC-05, Northwestern University (2008) [to appear in IMA J. Numer. Anal.]
Nocedal J., Wright S.J.: Numerical Optimization. Springer Series in Operations Research. Springer, Berlin (1999)
Oberlin C., Wright S.J.: Active constraint identification in nonlinear programming. SIAM J. Optim. 17, 577–605 (2006)
Powell M.J.D., Yuan Y.: A trust region algorithm for equality constrained optimization. Math. Program. 49(2), 189–213 (1990)
Waltz, R.A.: Algorithms for Large-Scale Nonlinear Optimization. PhD thesis, Department of Electrical and Computer Engineering, Northwestern University, Evanston (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
Richard H. Byrd was supported by National Science Foundation grant CMMI 0728190 and Department of Energy grant DE-SC0001774. Jorge Nocedal and Yuchen Wu were supported by Department of Energy grant DE-FG02-87ER25047-A004 and National Science Foundation grant DMS-0810213. Richard A. Waltz was supported by National Science Foundation grant CMMI 0728036.
Rights and permissions
About this article
Cite this article
Byrd, R.H., Nocedal, J., Waltz, R.A. et al. On the use of piecewise linear models in nonlinear programming. Math. Program. 137, 289–324 (2013). https://doi.org/10.1007/s10107-011-0492-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-011-0492-9