Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization. (English) Zbl 1244.90216

Summary: At each outer iteration of standard Augmented Lagrangian methods one tries to solve a box-constrained optimization problem with some prescribed tolerance. In the continuous world, using exact arithmetic, this subproblem is always solvable. Therefore, the possibility of finishing the subproblem resolution without satisfying the theoretical stopping conditions is not contemplated in usual convergence theories. However, in practice, one might not be able to solve the subproblem up to the required precision. This may be due to different reasons. One of them is that the presence of an excessively large penalty parameter could impair the performance of the box-constraint optimization solver. In this paper a practical strategy for decreasing the penalty parameter in situations like the one mentioned above is proposed. More generally, the different decisions that may be taken when, in practice, one is not able to solve the Augmented Lagrangian subproblem will be discussed. As a result, an improved Augmented Lagrangian method is presented, which takes into account numerical difficulties in a satisfactory way, preserving suitable convergence theory. Numerical experiments are presented involving all the CUTEr collection test problems.


90C30 Nonlinear programming
Full Text: DOI


[1] Andreani, R., Haeser, G., Martínez, J.M.: On sequential optimality conditions for smooth constrained optimization. Optimization (to appear) · Zbl 1225.90123
[2] Andreani, R., Birgin, E.G., Martínez, J.M., Schuverdt, M.L.: On Augmented Lagrangian Methods with general lower-level constraints. SIAM J. Optim. 18, 1286–1309 (2007) · Zbl 1151.49027 · doi:10.1137/060654797
[3] Andreani, R., Birgin, E.G., Martínez, J.M., Schuverdt, M.L.: Augmented Lagrangian methods under the Constant Positive Linear Dependence constraint qualification. Math. Program. 111, 5–32 (2008) · Zbl 1163.90041 · doi:10.1007/s10107-006-0077-1
[4] Andreani, R., Martínez, J.M., Schuverdt, M.L.: On the relation between the Constant Positive Linear Dependence condition and quasinormality constraint qualification. J. Optim. Theory Appl. 125, 473–485 (2005) · Zbl 1125.90058 · doi:10.1007/s10957-004-1861-9
[5] Andreani, R., Martínez, J.M., Svaiter, B.F.: A new sequential optimality condition for constrained optimization and algorithmic consequences. SIAM J. Optim. (to appear) · Zbl 1217.90148
[6] Andretta, M., Birgin, E.G., Martínez, J.M.: Practical active-set Euclidian trust-region method with spectral projected gradients for bound-constrained minimization. Optimization 54, 305–325 (2005) · Zbl 1079.65070 · doi:10.1080/02331930500100270
[7] Birgin, E.G., Fernández, D., Martínez, J.M.: On the boundedness of penalty parameters in an Augmented Lagrangian method with lower level constraints. Technical Report, Department of Applied Mathematics, State University of Campinas, Brazil
[8] Birgin, E.G., Martínez, J.M.: A box-constrained optimization algorithm with negative curvature directions and spectral projected gradients. Computing [Suppl.] 15, 49–60 (2001) · Zbl 1002.65067 · doi:10.1007/978-3-7091-6217-0_5
[9] Birgin, E.G., Martínez, J.M.: Large-scale active-set box-constrained optimization method with spectral projected gradients. Comput. Optim. Appl. 23, 101–125 (2002) · Zbl 1031.90012 · doi:10.1023/A:1019928808826
[10] Buys, J.D.: Dual algorithms for constrained optimization problems. Doctoral Dissertation, University of Leiden, Leiden, the Netherlands (1972)
[11] Byrd, R.H., Lu, P., Nocedal, J.: A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Stat. Comput. 16, 1190–1208 (1995) · Zbl 0836.65080 · doi:10.1137/0916069
[12] Coleman, T.F., Li, Y.: On the convergence of reflective newton methods for large-scale nonlinear minimization subject to bounds. Math. Program. 67, 189–224 (1994) · Zbl 0842.90106 · doi:10.1007/BF01582221
[13] Coleman, T.F., Li, Y.: An interior, trust region approach for nonlinear minimization subject to bounds. SIAM J. Optim. 6, 418–445 (1996) · Zbl 0855.65063 · doi:10.1137/0806023
[14] Conn, A.R., Gould, N.I.M., Sartenaer, A., Toint, Ph.L.: Convergence properties of an Augmented Lagrangian algorithm for optimization with a combination of general equality and linear constraints. SIAM J. Optim. 6, 674–703 (1996) · Zbl 0856.90098 · doi:10.1137/S1052623493251463
[15] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Global convergence of a class of trust region algorithms for optimization with simple bounds. SIAM J. Numer. Anal. 25, 433–460 (1988) · Zbl 0643.65031 · doi:10.1137/0725029
[16] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Testing a class of methods for solving minimization problems with simple bounds on the variables. Math. Comput. 50, 399–430 (1988) · Zbl 0645.65033 · doi:10.1090/S0025-5718-1988-0929544-3
[17] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: 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 · doi:10.1137/0728030
[18] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: LANCELOT: a Fortran Package for Large-Scale Nonlinear Optimization (Release A). Springer Series in Computational Mathematics, vol. 17. Springer, New York (1992) · Zbl 0761.90087
[19] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust Region Methods. MPS/SIAM Series on Optimization. SIAM, Philadelphia (2000) · Zbl 0958.65071
[20] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Lancelot: A Fortran Package For farge Scale Nonlinear Optimization. Springer, Berlin (1992) · Zbl 0761.90087
[21] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[22] Gould, N.I.M., Orban, D., Toint, Ph.L.: CUTEr and SifDec: a constrained and unconstrained testing environment. ACM Trans. Math. Softw. 29, 373–394 (2003) · Zbl 1068.90526 · doi:10.1145/962437.962439
[23] Hager, W.W., Zhang, H.: A new active set algorithm for box constrained optimization. SIAM J. Optim. 17, 526–557 (2006) · Zbl 1165.90570 · doi:10.1137/050635225
[24] Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 45, 303–320 (1969) · Zbl 0174.20705 · doi:10.1007/BF00927673
[25] Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization, pp. 283–298. Academic Press, New York (1969) · Zbl 0194.47701
[26] Qi, L., Wei, Z.: On the constant positive linear dependence condition and its application to SQP methods. SIAM J. Optim. 10, 963–981 (2000) · Zbl 0999.90037 · doi:10.1137/S1052623497326629
[27] Rockafellar, R.T.: A dual approach for solving nonlinear programming problems by unconstrained optimization. Math. Program. 5, 354–373 (1973) · Zbl 0279.90035 · doi:10.1007/BF01580138
[28] Wächter, A., Biegler, L.T.: 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 · doi:10.1007/s10107-004-0559-y
[29] Zhu, C., Byrd, R.H., Nocedal, J.: L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization. ACM Trans. Math. Softw. 23, 550–560 (1997) · Zbl 0912.65057 · doi:10.1145/279232.279236
[30] http://www.ime.usp.br/\(\sim\)egbirgin/tango/
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.