×

Structured minimal-memory inexact quasi-Newton method and secant preconditioners for augmented Lagrangian optimization. (English) Zbl 1147.90412

Summary: Augmented Lagrangian methods for large-scale optimization usually require efficient algorithms for minimization with box constraints. On the other hand, active-set box-constraint methods employ unconstrained optimization algorithms for minimization inside the faces of the box. Several approaches may be employed for computing internal search directions in the large-scale case. In this paper a minimal-memory quasi-Newton approach with secant preconditioners is proposed, taking into account the structure of Augmented Lagrangians that come from the popular Powell-Hestenes-Rockafellar scheme. A combined algorithm, that uses the quasi-Newton formula or a truncated-Newton procedure, depending on the presence of active constraints in the penalty-Lagrangian function, is also suggested. Numerical experiments using the Cute collection are presented.

MSC:

90C53 Methods of quasi-Newton type
65H10 Numerical computation of solutions to systems of equations
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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. (2007, in press). DOI: 10.1007/s10107-006-0077-1 · Zbl 1163.90041
[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. (2007, in press) · Zbl 1151.49027
[3] 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
[4] Barzilai, J., Borwein, J.M.: Two point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[5] Birgin, E.G., Castillo, R., Martínez, J.M.: Numerical comparison of Augmented Lagrangian algorithms for nonconvex problems. Comput. Optim. Appl. 31, 31–56 (2005) · Zbl 1101.90066 · doi:10.1007/s10589-005-1066-7
[6] 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
[7] Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10, 1196–1211 (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[8] Birgin, E.G., Martínez, J.M., Raydan, M.: Algorithm 813: SPG–Software for convex-constrained optimization. ACM Trans. Math. Softw. 27, 340–349 (2001) · Zbl 1070.65547 · doi:10.1145/502800.502803
[9] Birgin, E.G., Martínez, J.M., Raydan, M.: Inexact spectral projected gradient methods on convex sets. IMA J. Numer. Anal. 23, 539–559 (2003) · Zbl 1047.65042 · doi:10.1093/imanum/23.4.539
[10] Bongartz, I., Conn, A.R., Gould, N.I.M., Toint, P.L.: CUTE: constrained and unconstrained testing environment. ACM Trans. Math. Softw. 21, 123–160 (1995) · Zbl 0886.65058 · doi:10.1145/200979.201043
[11] Burdakov, O., Martínez, J.M., Pilotta, E.A.: A limited memory multipoint secant method for bound constrained optimization. Ann. Oper. Res. 117, 51–70 (2002) · Zbl 1025.90038 · doi:10.1023/A:1021561204463
[12] Byrd, R.H., Lu, P.H., Nocedal, J., Zhu, C.Y.: A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Comput. 16, 1190–1208 (1995) · Zbl 0836.65080 · doi:10.1137/0916069
[13] Conn, A.R., Gould, N.I.M., Toint, P.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
[14] Conn, A.R., Gould, N.I.M., Toint, P.L.: LANCELOT: a Fortran Package for Large Scale Nonlinear Optimization. Springer, Berlin (1992) · Zbl 0761.90087
[15] Dai, Y.H., Fletcher, R.: On the asymptotic behaviour of some new gradient methods. Math. Program. 103, 541–549 (2005) · Zbl 1099.90038 · doi:10.1007/s10107-004-0516-9
[16] Dai, Y.H., Liao, L.Z.: R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. 22, 1–10 (2002) · Zbl 1002.65069 · doi:10.1093/imanum/22.1.1
[17] Dennis, J.E., Schnabel, R.B.: Least change secant updates for quasi-Newton methods. SIAM Rev. 21, 443–459 (1979) · Zbl 0424.65020 · doi:10.1137/1021091
[18] Diniz-Ehrhardt, M.A., Gomes-Ruggiero, M.A., Martínez, J.M., Santos, S.A.: Augmented Lagrangian algorithms based on the spectral projected gradient for solving nonlinear programming problems. J. Optim. Theory Appl. 123, 497–517 (2004) · Zbl 1186.90109 · doi:10.1007/s10957-004-5720-5
[19] 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
[20] Dostál, Z.: Inexact semimonotonic Augmented Lagrangians with optimal feasibility convergence for convex bound and equality constrained quadratic programming. SIAM J. Numer. Anal. 43, 96–115 (2005) · Zbl 1089.65047 · doi:10.1137/S0036142903436393
[21] Dostál, Z., Friedlander, A., Santos, S.A.: Augmented Lagrangian with adaptive precision control for quadratic programming with simple bounds and equality constraints. SIAM J. Optim. 13, 1120–1140 (2003) · Zbl 1043.65076 · doi:10.1137/S1052623499362573
[22] Dostál, Z., Gomes, F.A.M., Santos, S.A.: Duality based domain decomposition with natural coarse space for variational inequalities. J. Comput. Appl. Math. 126, 397–415 (2000) · Zbl 0970.65074 · doi:10.1016/S0377-0427(99)00368-4
[23] Fletcher, R.: Practical Methods of Optimization. Academic, London (1987) · Zbl 0905.65002
[24] Fletcher, R.: On the Barzilai–Borwein method. Department of Mathematics, University of Dundee, NA/207, Dundee, Scotland (2001) · Zbl 1118.90318
[25] Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM Rev. 47, 99–131 (2005) · Zbl 1210.90176 · doi:10.1137/S0036144504446096
[26] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore/London (1996) · Zbl 0865.65009
[27] Groceri, G.M., Sottosanto, G.N., Maciel, M.C.: Augmented Penalization algorithms based on BFGS secant approximations and trust region. Technical report, Departamento de Matemáticas, Universidad Nacional del Sur, Bahía Blanca, Argentina (2005)
[28] Gurwitz, C.: A test for cancellation errors in quasi-Newton methods. ACM Trans. Math. Softw. 18, 133–140 (1992) · Zbl 0893.65045 · doi:10.1145/146847.146876
[29] Hager, W.W.: Analysis and implementation of a dual algorithm for constrained optimization. J. Optim. Theory Appl. 79, 37–71 (1993) · Zbl 0797.90092 · doi:10.1007/BF00940552
[30] Hager, W.W., Zhang, H.: A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J. Optim. 16, 170–192 (2005) · Zbl 1093.90085 · doi:10.1137/030601880
[31] Hager, W.W., Zhang, H.: Algorithm 851: CG_DESCENT. A conjugate gradient method with guaranteed descent, ACM Trans. Math. Softw. 32, 113–137 (2006) · Zbl 1346.90816
[32] Hager, W.W., Zhang, H.: A survey of nonlinear conjugate gradient methods. Pac. J. Optim. 2, 35–58 (2006) · Zbl 1117.90048
[33] 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
[34] Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969) · Zbl 0174.20705 · doi:10.1007/BF00927673
[35] Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Stand. 49, 409–436 (1952) · Zbl 0048.09901
[36] Krejić, N., Martínez, J.M., Mello, M.P., Pilotta, E.A.: Validation of an Augmented Lagrangian algorithm with a Gauss–Newton Hessian approximation using a set of hard-spheres problems. Comput. Optim. Appl. 16, 247–263 (2000) · Zbl 0997.90103 · doi:10.1023/A:1008716329104
[37] Martínez, J.M., Qi, L.: Inexact Newton methods for solving nonsmooth equations. J. Comput. Appl. Math. 60, 127–145 (1995) · Zbl 0833.65045 · doi:10.1016/0377-0427(94)00088-I
[38] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999) · Zbl 0930.65067
[39] Oren, S.S.: Self-scaling variable metric algorithms without line search for unconstrained minimization. Math. Comput. 27, 873–885 (1973) · Zbl 0304.65045 · doi:10.1090/S0025-5718-1973-0329259-8
[40] Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization, pp. 283–298. Academic, New York (1969) · Zbl 0194.47701
[41] Qi, L., Sun, J.: A nonsmooth version of Newton method. Math. Program. 58, 353–367 (1993) · Zbl 0780.90090 · doi:10.1007/BF01581275
[42] Qi, L., Wei, Z.: On the constant positive linear dependence condition and its application to SQP method. SIAM J. Optim. 10, 963–981 (2000) · Zbl 0999.90037 · doi:10.1137/S1052623497326629
[43] Raydan, M.: On the Barzilai and Borwein choice of steplength for the gradient method. IMA J. Numer. Anal. 13, 321–326 (1993) · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321
[44] Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7, 26–33 (1997) · Zbl 0898.90119 · doi:10.1137/S1052623494266365
[45] Rockafellar, R.T.: The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl. 12, 555–562 (1973) · Zbl 0254.90045 · doi:10.1007/BF00934777
[46] Rockafellar, R.T.: Augmented Lagrange multiplier functions and duality in nonconvex programming. SIAM Journal on Control 12, 268–285 (1974) · Zbl 0285.90063 · doi:10.1137/0312021
[47] Zhu, C.Y., Byrd, R.H., Lu, P.H., Nocedal, J.: Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization. ACM Trans. Math. Softw. 23, 550–560 (1995) · Zbl 0912.65057 · doi:10.1145/279232.279236
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.