×

A primal-dual augmented Lagrangian penalty-interior-point filter line search algorithm. (English) Zbl 1394.49025

Summary: 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.

MSC:

49M05 Numerical methods based on necessary conditions
49M15 Newton-type methods
49M29 Numerical methods involving duality
49M37 Numerical methods based on nonlinear programming
90C06 Large-scale problems in mathematical programming
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C51 Interior-point methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armand, P; Omheni, R, A globally and quadratically convergent primal-dual augmented Lagrangian algorithm for equality constrained optimization, Optim Methods Softw, 32, 1-21, (2017) · Zbl 1365.90209 · doi:10.1080/10556788.2015.1025401
[2] Armand P, Omheni R (2017b) A mixed logarithmic barrier-augmented Lagrangian method for nonlinear optimization. J Optim Theory Appl 173:1-25 · Zbl 1370.49022
[3] Armand, P; Benoist, J; Omheni, R; Pateloup, V, Study of a primal-dual algorithm for equality constrained minimization, Comput Optim Appl, 59, 405-433, (2014) · Zbl 1304.49050 · doi:10.1007/s10589-014-9679-3
[4] Benson, H; Vanderbei, R; Shanno, D, Interior-point methods for nonconvex nonlinear programming: filter methods and merit functions, Comput Optim Appl, 23, 257-272, (2002) · Zbl 1022.90017 · doi:10.1023/A:1020533003783
[5] Benson, HY; Shanno, DF; Vanderbei, RJ; Pillo, G (ed.); Murli, A (ed.), A comparative study of large-scale nonlinear optimization algorithms, No. 82, 95-127, (2003), New York · Zbl 1066.90138 · doi:10.1007/978-1-4613-0241-4_5
[6] Benson HY, Sen A, Shanno DF (2007) Convergence analysis of an interior-point method for nonconvex nonlinear programming, Technical report · Zbl 1134.90053
[7] Boman EG (1999) Infeasibility and negative curvature in optimization, Ph.D. thesis. Stanford University · Zbl 1134.90542
[8] Büskens, C; Wassel, D; Fasano, G (ed.); Pintér, JD (ed.), The ESA NLP solver WORHP, No. 73, 85-110, (2013), New York · Zbl 1365.90007 · doi:10.1007/978-1-4614-4469-5_4
[9] Byrd, RH; Curtis, FE; Nocedal, J, Infeasibility detection and SQP methods for nonlinear optimization, SIAM J Optim, 20, 2281-2299, (2010) · Zbl 1211.90179 · doi:10.1137/080738222
[10] Chen, L; Goldfarb, D, Interior-point \(ℓ 2\)-penalty methods for nonlinear programming with strong global convergence properties, Math Program, 108, 1-36, (2006) · Zbl 1142.90498 · doi:10.1007/s10107-005-0701-5
[11] Chen L, Goldfarb D (2006b) On the fast local convergence of interior-point \(ℓ 2\)-penalty methods for nonlinear programming, Technical report. IEOR Department, Columbia University, New York · Zbl 1070.90110
[12] Chen, L; Goldfarb, D, An interior-point piecewise linear penalty method for nonlinear programming, Math Program, 128, 73-122, (2009) · Zbl 1227.49039
[13] Conn A, Gould N, Toint P (2000) Trust-region methods. SIAM, Philadelphia · Zbl 0958.65071
[14] 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 · Zbl 0761.90087
[15] Curtis, FE, A penalty-interior-point algorithm for nonlinear constrained optimization, Math Program Comput, 4, 181-209, (2012) · Zbl 1269.49045 · doi:10.1007/s12532-012-0041-4
[16] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math Program, 91, 201-213, (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[17] Fletcher R (1983) Penalty functions. Springer, Berlin, pp 87-114 · Zbl 0542.90087
[18] Fletcher, R; Boggs, PT (ed.); Byrd, RH (ed.); Schnabel, RB (ed.), An \(ℓ 1\) penalty method for nonlinear constraints, 26-40, (1985), Philadelphia · Zbl 0583.65043
[19] Fletcher, R; Leyffer, S, Nonlinear programming without a penalty function, Math Program, 91, 239-269, (2002) · Zbl 1049.90088 · doi:10.1007/s101070100244
[20] Forsgren, A; Gill, PE, Primal-dual interior methods for nonconvex nonlinear programming, SIAM J Optim, 8, 1132-1152, (1998) · Zbl 0915.90236 · doi:10.1137/S1052623496305560
[21] Forsgren, A; Gill, PE; Wright, MH, Interior methods for nonlinear optimization, SIAM Rev, 44, 525-597, (2002) · Zbl 1028.90060 · doi:10.1137/S0036144502414942
[22] Gertz, EM; Gill, PE, A primal-dual trust region algorithm for nonlinear optimization, Math Program, 100, 49-94, (2004) · Zbl 1146.90514
[23] Gill, PE; Robinson, DP, A primal-dual augmented Lagrangian, Comput Optim Appl, 51, 1-25, (2010) · Zbl 1244.90219 · doi:10.1007/s10589-010-9339-1
[24] Gill, PE; Robinson, DP, A globally convergent stabilized SQP method, SIAM J Optim, 23, 1983-2010, (2013) · Zbl 1285.49023 · doi:10.1137/120882913
[25] Gill, PE; Kungurtsev, V; Robinson, DP, A stabilized SQP method: global convergence, IMA J Numer Anal, 37, 407-443, (2017) · Zbl 1367.49003 · doi:10.1093/imanum/drw004
[26] Gill, PE; Kungurtsev, V; Robinson, DP, A stabilized SQP method: superlinear convergence, Math Program, 163, 369-410, (2017) · Zbl 1367.49003 · doi:10.1007/s10107-016-1066-7
[27] Goldfarb, D; Polyak, R; Scheinberg, K; Yuzefovich, I, A modified barrier-augmented Lagrangian method for constrained minimization, Comput Optim Appl, 14, 55-74, (1999) · Zbl 0951.90042 · doi:10.1023/A:1008705028512
[28] Gould, NIM; Toint, PL, Nonlinear programming without a penalty function or a filter, Math Program, 122, 155-196, (2010) · Zbl 1216.90069 · doi:10.1007/s10107-008-0244-7
[29] Gould NIM, Orban D, Toint PL (2005) Numerical analysis and optimization: NAO-III, Muscat, Oman, January 2014, chap. In: An interior-point \(ℓ 1\)-penalty method for nonlinear optimization. Springer, Cham, pp 117-150 · Zbl 1367.49003
[30] Gould, NIM; Loh, Y; Robinson, DP, A filter method with unified step computation for nonlinear optimization, SIAM J Optim, 24, 175-209, (2014) · Zbl 1301.49070 · doi:10.1137/130920599
[31] Gould, NIM; Loh, Y; Robinson, DP, A nonmonotone filter SQP method: local convergence and numerical results, SIAM J Optim, 25, 1885-1911, (2015) · Zbl 1326.49042 · doi:10.1137/140996677
[32] Gould, NIM; Orban, D; Toint, PL, Cutest: a constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput Optim Appl, 60, 545-557, (2015) · Zbl 1325.90004 · doi:10.1007/s10589-014-9687-3
[33] Greif, C; Moulding, E; Orban, D, Bounds on eigenvalues of matrices arising from interior-point methods, SIAM J Optim, 24, 49-83, (2014) · Zbl 1291.15008 · doi:10.1137/120890600
[34] Hogg J, Scott JA (2012) New parallel sparse direct solvers for engineering applications, Technical report. Science and Technology Facilities Council · Zbl 1028.90060
[35] Izmailov, AF; Solodov, MV, On attraction of linearly constrained Lagrangian methods and of stabilized and quasi-Newton SQP methods to critical multipliers, Math Program, 126, 231-257, (2011) · Zbl 1218.90184 · doi:10.1007/s10107-009-0279-4
[36] Izmailov, AF; Solodov, MV, Stabilized SQP revisited, Math Program, 133, 93-120, (2012) · Zbl 1245.90145 · doi:10.1007/s10107-010-0413-3
[37] Liu, X; Yuan, Y, A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization, SIAM J Optim, 21, 545-571, (2011) · Zbl 1233.90257 · doi:10.1137/080739884
[38] 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 · Zbl 1049.90004
[39] Nocedal J, Wright S (2006) Numerical optimization. Springer, Berlin · Zbl 1104.65059
[40] Nocedal, J; Wächter, A; Waltz, RA, Adaptive barrier update strategies for nonlinear interior methods, SIAM J Optim, 19, 1674-1693, (2009) · Zbl 1176.49036 · doi:10.1137/060649513
[41] Parikh, N; Boyd, S, Proximal algorithms, Found Trends Optim, 1, 127-239, (2014) · doi:10.1561/2400000003
[42] Shen, C; Zhang, LH; Liu, W, A stabilized filter SQP algorithm for nonlinear programming, J Glob Optim, 65, 677-708, (2016) · Zbl 1353.90149 · doi:10.1007/s10898-015-0400-6
[43] Tits, AL; Wächter, A; Bakhtiari, S; Urban, TJ; Lawrence, CT, A primal-dual interior-point method for nonlinear programming with strong global and local convergence properties, SIAM J Optim, 14, 173-199, (2003) · Zbl 1075.90078 · doi:10.1137/S1052623401392123
[44] Ulbrich, M; Ulbrich, S; Vicente, NL, A globally convergent primal-dual interior-point filter method for nonlinear programming, Math Program, 100, 379-410, (2003) · Zbl 1070.90110 · doi:10.1007/s10107-003-0477-4
[45] Vanderbei, RJ, LOQO: an interior point code for quadratic programming, Optim Methods Softw, 11, 451-484, (1999) · Zbl 0973.90518 · doi:10.1080/10556789908805759
[46] Vanderbei, RJ; Shanno, DF, An interior-point algorithm for nonconvex nonlinear programming, Comput Optim Appl, 13, 231-252, (1999) · Zbl 1040.90564 · doi:10.1023/A:1008677427361
[47] Wächter, A; Biegler, LT, Failure of global convergence for a class of interior point methods for nonlinear programming, Math Program, 88, 565-574, (2000) · Zbl 0963.65063 · doi:10.1007/PL00011386
[48] Wächter, A; Biegler, LT, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Math Program, 106, 25-57, (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[49] Waltz, R; Morales, J; Nocedal, J; Orban, D, An interior algorithm for nonlinear optimization that combines line search and trust region steps, Math Program, 107, 391-408, (2006) · Zbl 1134.90053 · doi:10.1007/s10107-004-0560-5
[50] Yamashita, H, A globally convergent primal-dual interior point method for constrained optimization, Optim Methods Softw, 10, 443-469, (1998) · Zbl 0946.90110 · doi:10.1080/10556789808805723
[51] Yamashita, H; Yabe, H, An interior point method with a primal-dual quadratic barrier penalty function for nonlinear optimization, SIAM J Optim, 14, 479-499, (2003) · Zbl 1072.90050 · doi:10.1137/S1052623499355533
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.