zbMATH — the first resource for mathematics

A mixed logarithmic barrier-augmented Lagrangian method for nonlinear optimization. (English) Zbl 1370.49022
Summary: We present a primal-dual algorithm for solving a constrained optimization problem. This method is based on a Newtonian method applied to a sequence of perturbed KKT systems. These systems follow from a reformulation of the initial problem under the form of a sequence of penalized problems, by introducing an augmented Lagrangian for handling the equality constraints and a log-barrier penalty for the inequalities. We detail the updating rules for monitoring the different parameters (Lagrange multiplier estimate, quadratic penalty and log-barrier parameter), in order to get strong global convergence properties. We show that one advantage of this approach is that it introduces a natural regularization of the linear system to solve at each iteration, for the solution of a problem with a rank deficient Jacobian of constraints. The numerical experiments show the good practical performances of the proposed method especially for degenerate problems.

49M15 Newton-type methods
65K05 Numerical mathematical programming methods
90C06 Large-scale problems in mathematical programming
90C30 Nonlinear programming
90C51 Interior-point methods
Full Text: DOI
[1] Wächter, A; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57, (2006) · Zbl 1134.90542
[2] Gill, PE; Murray, W; Saunders, MA, SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM Rev., 47, 99-131, (2005) · Zbl 1210.90176
[3] Byrd, RH; Gilbert, JC; Nocedal, J, A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89, 149-185, (2000) · Zbl 1033.90152
[4] Shanno, D.F., Vanderbei, R.J.: Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods. Math. Program. 87(2, Ser. B), 303-316 (2000). Studies in algorithmic optimization · Zbl 1054.90091
[5] Birgin, E.G., Martínez, J.M.: Practical Augmented Lagrangian Methods for Constrained Optimization. Fundamental of Algorithms. SIAM Publications, Philadelphia (2014) · Zbl 1339.90312
[6] Conn, A.R., Gould, N.I.M., Toint, P.L.: LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization (Release A), Springer Series in Computational Mathematics, vol. 17. Springer, Berlin (1992) · Zbl 0761.90087
[7] Kočvara, M; Stingl, M, Pennon: a code for convex nonlinear and semidefinite programming, Optim. Methods Softw., 18, 317-333, (2003) · Zbl 1037.90003
[8] 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
[9] Armand, P; Omheni, R, A globally and quadratically convergent primal-dual augmented Lagrangian algorithm for equality constrained optimization, Optim. Methods Softw., 31, 1-21, (2017) · Zbl 1365.90209
[10] Chen, L; Goldfarb, D, Interior-point \(l_2\)-penalty methods for nonlinear programming with strong global convergence properties, Math. Program., 108, 1-36, (2006) · Zbl 1142.90498
[11] Gill, PE; Robinson, DP, A primal-dual augmented Lagrangian, Comput. Optim. Appl., 51, 1-25, (2012) · Zbl 1244.90219
[12] Gill, PE; Robinson, DP, A globally convergent stabilized SQP method, SIAM J. Optim., 23, 1983-2010, (2013) · Zbl 1285.49023
[13] Omheni, R.: Méthodes primales-duales régularisées pour l’optimisation non linéaire avec contraintes. Ph.D. thesis, University of Limoges, France (2014)
[14] 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
[15] Armand, P; Benoist, J; Orban, D, From global to local convergence of interior methods for nonlinear optimization, Optim. Methods Softw., 28, 1051-1080, (2013) · Zbl 1278.90254
[16] 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
[17] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006)
[18] Armand, P; Benoist, J, Uniform boundedness of the inverse of a Jacobian matrix arising in regularized interior-point methods, Math. Program., 137, 587-592, (2013) · Zbl 1260.49058
[19] Forsgren, A; Gill, PE; Wright, MH, Interior methods for nonlinear optimization, SIAM Rev., 44, 525-597, (2002) · Zbl 1028.90060
[20] Friedlander, MP; Orban, D, A primal-dual regularized interior-point method for convex quadratic programs, Math. Program. Comput., 4, 71-107, (2012) · Zbl 1279.90193
[21] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2000) · Zbl 0958.65071
[22] Armand, P; Benoist, J; Orban, D, Dynamic updates of the barrier parameter in primal-dual methods for nonlinear programming, Comput. Optim. Appl., 41, 1-25, (2008) · Zbl 1180.90305
[23] Ulbrich, M; Ulbrich, S; Vicente, LN, A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. Program., 100, 379-410, (2004) · Zbl 1070.90110
[24] Wächter, A; Biegler, LT, Line search filter methods for nonlinear programming: local convergence, SIAM J. Optim., 16, 32-48, (2005) · Zbl 1115.90056
[25] Hock, W., Schittkowski, K.: Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, vol. 187. Springer, Berlin (1981) · Zbl 0452.90038
[26] Schittkowski, K. (ed.): More Test Examples for Nonlinear Programming Codes. Springer, New York (1987) · Zbl 0658.90060
[27] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[28] Duff, IS, Ma57—a code for the solution of sparse symmetric definite and indefinite systems, ACM Trans. Math. Softw., 30, 118-144, (2004) · Zbl 1070.65525
[29] Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming, 2nd edn. Brooks/Cole, Pacific Grove (2002) · Zbl 0701.90062
[30] Wright, SJ, An algorithm for degenerate nonlinear programming with rapid local convergence, SIAM J. Optim., 15, 673-696, (2005) · Zbl 1077.90067
[31] Gould, N.I.M., Orban, D., Toint, P.L.: CUTEr and SifDec: A constrained and unconstrained testing environment, revisited. Tech. rep, CERFACS, Toulouse, France (2001) · Zbl 1068.90526
[32] Dolan, E.D., Moré, J.J., Munson, T.S.: Benchmarking optimization software with COPS 3.0. Tech. rep., Argonne National Laboratory (2004) · Zbl 1142.90498
[33] Armand, P; Lankoandé, I, An inexact proximal regularization method for unconstrained optimization, Math. Methods Oper. Res., (2016) · Zbl 1364.90311
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.