Abstract
Interior-point methods have been shown to be very efficient for large-scale nonlinear programming. The combination with penalty methods increases their robustness due to the regularization of the constraints caused by the penalty term. In this paper a primal–dual penalty-interior-point algorithm is proposed, that is based on an augmented Lagrangian approach with an \(\ell 2\)-exact penalty function. Global convergence is maintained by a combination of a merit function and a filter approach. Unlike the majority of filter methods, no separate feasibility restoration phase is required. The algorithm has been implemented within the solver WORHP to study different penalty and line search options and to compare its numerical performance to two other state-of-the-art nonlinear programming algorithms, the interior-point method IPOPT and the sequential quadratic programming method of WORHP.
Similar content being viewed by others
Notes
Note, that if \(\lambda _k = y_k / \rho _k\) and \(\rho _k = 1\) the step \((\varDelta x_k, \varDelta y_k, \varDelta z_k)\) equals the step \((\widetilde{\varDelta x_k}, \widetilde{\varDelta \lambda _k}, \widetilde{\varDelta y_k})\) of Chen and Goldfarb (2009).
Further information and download of WORHP on www.worhp.de.
See www.netlib.org/blas.
References
Armand P, Omheni R (2017a) A globally and quadratically convergent primal–dual augmented Lagrangian algorithm for equality constrained optimization. Optim Methods Softw 32(1):1–21
Armand P, Omheni R (2017b) A mixed logarithmic barrier-augmented Lagrangian method for nonlinear optimization. J Optim Theory Appl 173:1–25
Armand P, Benoist J, Omheni R, Pateloup V (2014) Study of a primal–dual algorithm for equality constrained minimization. Comput Optim Appl 59(3):405–433
Benson H, Vanderbei R, Shanno D (2002) Interior-point methods for nonconvex nonlinear programming: filter methods and merit functions. Comput Optim Appl 23(2):257–272
Benson HY, Shanno DF, Vanderbei RJ (2003) A comparative study of large-scale nonlinear optimization algorithms. In: Di Pillo G, Murli A (eds) High performance algorithms and software for nonlinear optimization, applied optimization, vol 82. Springer, New York, pp 95–127
Benson HY, Sen A, Shanno DF (2007) Convergence analysis of an interior-point method for nonconvex nonlinear programming, Technical report
Boman EG (1999) Infeasibility and negative curvature in optimization, Ph.D. thesis. Stanford University
Büskens C, Wassel D (2013) The ESA NLP solver WORHP. In: Fasano G, Pintér JD (eds) Modeling and optimization in space engineering, Springer optimization and its applications, vol 73. Springer, New York, pp 85–110
Byrd RH, Curtis FE, Nocedal J (2010) Infeasibility detection and SQP methods for nonlinear optimization. SIAM J Optim 20(5):2281–2299
Chen L, Goldfarb D (2006a) Interior-point \(\ell 2\)-penalty methods for nonlinear programming with strong global convergence properties. Math Program 108(1):1–36
Chen L, Goldfarb D (2006b) On the fast local convergence of interior-point \(\ell 2\)-penalty methods for nonlinear programming, Technical report. IEOR Department, Columbia University, New York
Chen L, Goldfarb D (2009) An interior-point piecewise linear penalty method for nonlinear programming. Math Program 128(1):73–122
Conn A, Gould N, Toint P (2000) Trust-region methods. SIAM, Philadelphia
Conn A, Gould G, Toint P (2013) Lancelot: a Fortran package for large-scale nonlinear optimization (Release A), Springer Series in Computational Mathematics. Springer, Berlin
Curtis FE (2012) A penalty-interior-point algorithm for nonlinear constrained optimization. Math Program Comput 4(2):181–209
Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2):201–213
Fletcher R (1983) Penalty functions. Springer, Berlin, pp 87–114
Fletcher R (1985) An \(\ell 1\) penalty method for nonlinear constraints. In: Boggs PT, Byrd RH, Schnabel RB (eds) Numerical optimization 1984. SIAM, Philadelphia, pp 26–40
Fletcher R, Leyffer S (2002) Nonlinear programming without a penalty function. Math Program 91(2):239–269
Forsgren A, Gill PE (1998) Primal–dual interior methods for nonconvex nonlinear programming. SIAM J Optim 8(4):1132–1152
Forsgren A, Gill PE, Wright MH (2002) Interior methods for nonlinear optimization. SIAM Rev 44(4):525–597
Gertz EM, Gill PE (2004) A primal–dual trust region algorithm for nonlinear optimization. Math Program 100(1):49–94
Gill PE, Robinson DP (2010) A primal–dual augmented Lagrangian. Comput Optim Appl 51(1):1–25
Gill PE, Robinson DP (2013) A globally convergent stabilized SQP method. SIAM J Optim 23(4):1983–2010
Gill PE, Kungurtsev V, Robinson DP (2017a) A stabilized SQP method: global convergence. IMA J Numer Anal 37(1):407–443
Gill PE, Kungurtsev V, Robinson DP (2017b) A stabilized SQP method: superlinear convergence. Math Program 163(1):369–410
Goldfarb D, Polyak R, Scheinberg K, Yuzefovich I (1999) A modified barrier-augmented Lagrangian method for constrained minimization. Comput Optim Appl 14(1):55–74
Gould NIM, Toint PL (2010) Nonlinear programming without a penalty function or a filter. Math Program 122(1):155–196
Gould NIM, Orban D, Toint PL (2005) Numerical analysis and optimization: NAO-III, Muscat, Oman, January 2014, chap. In: An interior-point \(\ell 1\)-penalty method for nonlinear optimization. Springer, Cham, pp 117–150
Gould NIM, Loh Y, Robinson DP (2014) A filter method with unified step computation for nonlinear optimization. SIAM J Optim 24(1):175–209
Gould NIM, Loh Y, Robinson DP (2015a) A nonmonotone filter SQP method: local convergence and numerical results. SIAM J Optim 25(3):1885–1911
Gould NIM, Orban D, Toint PL (2015b) Cutest: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Comput Optim Appl 60(3):545–557
Greif C, Moulding E, Orban D (2014) Bounds on eigenvalues of matrices arising from interior-point methods. SIAM J Optim 24(1):49–83
Hogg J, Scott JA (2012) New parallel sparse direct solvers for engineering applications, Technical report. Science and Technology Facilities Council
Izmailov AF, Solodov MV (2011) On attraction of linearly constrained Lagrangian methods and of stabilized and quasi-newton SQP methods to critical multipliers. Math Program 126(2):231–257
Izmailov AF, Solodov MV (2012) Stabilized SQP revisited. Math Program 133(1):93–120
Liu X, Yuan Y (2011) A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization. SIAM J Optim 21(2):545–571
Morales JL, Nocedal J, Waltz RA, Liu G, Goux JP (2003) Assessing the potential of interior methods for nonlinear optimization. In: Biegler LT, Heinkenschloss M, Ghattas O, van Bloemen Waanders B (eds) Large-scale PDE-constrained optimization, lecture notes in computational science and engineering, vol 30. Springer, Berlin, pp 167–183
Nocedal J, Wright S (2006) Numerical optimization. Springer, Berlin
Nocedal J, Wächter A, Waltz RA (2009) Adaptive barrier update strategies for nonlinear interior methods. SIAM J Optim 19(4):1674–1693
Parikh N, Boyd S (2014) Proximal algorithms. Found Trends Optim 1(3):127–239
Shen C, Zhang LH, Liu W (2016) A stabilized filter SQP algorithm for nonlinear programming. J Glob Optim 65(4):677–708
Tits AL, Wächter A, Bakhtiari S, Urban TJ, Lawrence CT (2003) A primal–dual interior-point method for nonlinear programming with strong global and local convergence properties. SIAM J Optim 14(1):173–199
Ulbrich M, Ulbrich S, Vicente NL (2003) A globally convergent primal–dual interior-point filter method for nonlinear programming. Math Program 100(2):379–410
Vanderbei RJ (1999) LOQO: an interior point code for quadratic programming. Optim Methods Softw 11(1–4):451–484
Vanderbei RJ, Shanno DF (1999) An interior-point algorithm for nonconvex nonlinear programming. Comput Optim Appl 13(1–3):231–252
Wächter A, Biegler LT (2000) Failure of global convergence for a class of interior point methods for nonlinear programming. Math Program 88(3):565–574
Wächter A, Biegler LT (2006) On the implementation of a primal–dual interior point filter line search algorithm for large-scale nonlinear programming. Math Program 106(1):25–57
Waltz R, Morales J, Nocedal J, Orban D (2006) An interior algorithm for nonlinear optimization that combines line search and trust region steps. Math Program 107(3):391–408
Yamashita H (1998) A globally convergent primal–dual interior point method for constrained optimization. Optim Methods Softw 10(2):443–469
Yamashita H, Yabe H (2003) An interior point method with a primal–dual quadratic barrier penalty function for nonlinear optimization. SIAM J Optim 14(2):479–499
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kuhlmann, R., Büskens, C. A primal–dual augmented Lagrangian penalty-interior-point filter line search algorithm. Math Meth Oper Res 87, 451–483 (2018). https://doi.org/10.1007/s00186-017-0625-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-017-0625-x
Keywords
- Nonlinear programming
- Constrained optimization
- Augmented Lagrangian
- Penalty-interior-point algorithm
- Primal–dual method