×

Subspace Barzilai-Borwein gradient method for large-scale bound constrained optimization. (English) Zbl 1173.90584

Summary: An active set subspace Barzilai-Borwein gradient algorithm for large-scale bound constrained optimization is proposed. The active sets are estimated by an identification technique. The search direction consists of two parts: some of the components are simply defined; the other components are determined by the Barzilai-Borwein gradient method. In this work, a nonmonotone line search strategy that guarantees global convergence is used. Preliminary numerical results show that the proposed method is promising, and competitive with the well-known method SPG on a subset of bound constrained problems from CUTEr collection.

MSC:

90C52 Methods of reduced gradient type
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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
[2] 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
[3] Barzilai, J., Borwein, J.M.: Two point step size gradient method. IMA J. Numer. Anal. 8, 141–148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[4] Bertsekas, D.P.: Projected Newton methods for optimization problems with simple constrains. SIAM J. Control. Optim. 20, 221–246 (1982) · Zbl 0507.49018 · doi:10.1137/0320018
[5] Birgin, E.G., Martínez, J.M.: Large-scale active-set box-constrained optimization method with spectral projected gradients. Comput. Optim. Appl. 22, 101–125 (2002) · Zbl 1031.90012 · doi:10.1023/A:1019928808826
[6] Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10, 1196–1121 (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[7] 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
[8] 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
[9] Burdakov, O.P., Martínez, J.M., Pilotta, E.A.: A limited memory multipoint secant method for bound constrained optimization. Annal. Oper. Res. 117, 51–70 (2002) · Zbl 1025.90038 · doi:10.1023/A:1021561204463
[10] Byrd, R.H., Lu, P.H., 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
[11] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Global convergence of a class of trust region algorithm for optimization with simple bounds. SIAM J. Numer. Anal. 25, 433–460 (1988) · Zbl 0643.65031 · doi:10.1137/0725029
[12] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: A globally convergent augmented Lagrangean algorithm for optimization with general constraints and simple bounds. SIAM J. Numer. Anal. 28, 545–572 (1991) · Zbl 0724.65067 · doi:10.1137/0728030
[13] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: CUTE: constrained and unconstrained testing environment. ACM Trans. Math. Softw. 21, 123–160 (1995) · Zbl 0886.65058 · doi:10.1145/200979.201043
[14] Dai, Y.H., Fletcher, R.: Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100, 21–47 (2005) · Zbl 1068.65073 · doi:10.1007/s00211-004-0569-y
[15] Dai, Y.H., Fletcher, R.: On the asymptotic behaviour of some new gradient methods. Math. Program. (Ser. A) 13, 541–559 (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. 26, 1–10 (2006) · Zbl 1002.65069
[17] Dai, Y.H., Yuan, J.Y., Yuan, Y.: Modified two-point stepsize gradient methods for unconstrained optimization. Comput. Optim. Appl. 22, 103–109 (2002) · Zbl 1008.90056 · doi:10.1023/A:1014838419611
[18] Dai, Y.H., Hager, W.W., Schittkowski, K., Zhang, H.: The cyclic Barzilai-Borwein method for unconstrained optimization. IMA J. Numer. Anal. 26, 604–627 (2006) · Zbl 1147.65315 · doi:10.1093/imanum/drl006
[19] Diniz-Ehrhardt, M.A., Gomes-Ruggiero, M.A., Martínez, J.M., Santos, S.A.: Augmented Lagrangian algorithm 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
[20] 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
[21] Facchinei, F., Júdice, J., Soares, J.: An active set Newton’s algorithm for large-scale nonlinear programs with box constraints. SIAM J. Optim. 8, 158–186 (1998) · Zbl 0911.90301 · doi:10.1137/S1052623493253991
[22] Facchinei, F., Lucidi, S., Palagi, L.: A truncated Newton algorithm for large scale box constrained optimization. SIAM J. Optim. 12, 1100–1125 (2002) · Zbl 1035.90103 · doi:10.1137/S1052623499359890
[23] Grippo, L., Sciandrone, M.: Nonmonotone globalization techniques for the Barzilai-Borwein gradient method. Comput. Optim. Appl. 23, 143–169 (2002) · Zbl 1028.90061 · doi:10.1023/A:1020587701058
[24] Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23, 707–716 (1986) · Zbl 0616.65067 · doi:10.1137/0723046
[25] Goldfarb, D.: Extension of Davidon’s variable metric algorithm to maximization under linear inequality and constraints. SIAM J. Appl. Math. 17, 739–764 (1969) · Zbl 0185.42602 · doi:10.1137/0117067
[26] Gould, N.I.M., Orban, D., L, Ph.: Toint, Numerical methods for large-scale nonlinear optimization. Acta Numer. 14, 299–361 (2005) · Zbl 1119.65337 · doi:10.1017/S0962492904000248
[27] 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
[28] 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
[29] Luenberger, D.G.: Introduction to Linear and Nonlinear Programming, 2nd edn. Addison–Wesley, Reading (1986) · Zbl 0649.90029
[30] Martínez, J.M.: BOX-QUACAN and the implementation of Augmented Lagrangian algorithms for minimization with inequality constraints. Comput. Appl. Math. 19, 31–56 (2000) · Zbl 1119.90327
[31] Ni, Q., Yuan, Y.: A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization. Math. Comput. 66, 1509–1520 (1997) · Zbl 0886.65065 · doi:10.1090/S0025-5718-97-00866-1
[32] Raydan, M.: On the Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. IMA J. Numer. Anal. 13, 321–326 (1993) · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321
[33] 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
[34] Zhang, H., Hager, W.W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14, 1043–1056 (2004) · Zbl 1073.90024 · doi:10.1137/S1052623403428208
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.