Monotone and nonmonotone trust-region-based algorithms for large scale unconstrained optimization problems. (English) Zbl 1267.90142
Summary: Two trust regions algorithms for unconstrained nonlinear optimization problems are presented: a monotone and a nonmonotone one. Both of them solve the trust region subproblem by the spectral projected gradient (SPG) method proposed by E. G. Birgin, J. M. Martínez and M. Raydan [SIAM J. Optim. 10, No. 4, 1196–1211 (2000; Zbl 1047.90077)]. SPG is a nonmonotone projected gradient algorithm for solving large-scale convex-constrained optimization problems. It combines the classical projected gradient method with the spectral gradient choice of steplength and a nonmonotone line search strategy. The simplicity (only requires matrix-vector products, and one projection per iteration) and rapid convergence of this scheme fit nicely with globalization techniques based on the trust region philosophy, for large-scale problems. In the nonmonotone algorithm, the trial step is evaluated by acceptance via a rule which can be considered by a generalization of the well-known fraction of Cauchy decrease condition and a generalization of the nonmonotone line search proposed by L. Grippo, F. Lampariello and S. Lucidi [SIAM J. Numer. Anal. 23, 707–716 (1986; Zbl 0616.65067)]. Convergence properties and extensive numerical results are presented. Our results establish the robustness and efficiency of the new algorithms.
MSC:
| 90C30 | Nonlinear programming |
| 90C06 | Large-scale problems in mathematical programming |
| 90C52 | Methods of reduced gradient type |
Keywords:
trust-region subproblems; spectral projected gradient method; nonmonotone line search; large scale problemsReferences:
| [1] | Ahookhosh, M., Amini, K.: An efficient nonmonotone trust-region method for unconstrained optimization. Numer. Algorithm (2011). doi: 10.1007/s11075-011-9502-5 · Zbl 1243.65066 |
| [2] | Andrei, N.: An unconstrained optimization test functions collection. Adv. Model. Optim. 10(1), 147–161 (2008) · Zbl 1161.90486 |
| [3] | Birgin, E., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10(4), 1196–1211 (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963 |
| [4] | Birgin, E., 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 |
| [5] | Chen, Z.-W., Han, J.-Y., Xu, D.-C.: A nonmonotone trust region method for nonlinear programming with simple bound constraints. Appl. Math. Optim. 43, 63–85 (2001) · Zbl 0973.65049 · doi:10.1007/s002450010020 |
| [6] | Conn, A., Gould, N.I.M., Toint, P.: Trust-Region Methods. SIAM-MPS, Philadelphia (2000) · Zbl 0958.65071 |
| [7] | Deng, N.Y., Xiao, Y., Zhou, F.J.: A nonmonotonic trust-region algorithm. J. Optim. Theory Appl. 76, 259–285 (1993) · Zbl 0797.90088 · doi:10.1007/BF00939608 |
| [8] | Dennis, J.E., Turner, K.: Generalized conjugate directions. Linear Algebra Appl. 88/89, 187–209 (1987) · Zbl 0644.65025 · doi:10.1016/0024-3795(87)90109-1 |
| [9] | Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program., Ser. A 91, 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [10] | Fletcher, R.: Low storage methods for unconstrained minimization. In: Allgower, E.L., Georg, K. (eds.) Computational Solution of Nonlinear Systems of Equations. Lectures in Applied Mathematics, vol. 26, pp. 165–179. American Mathematical Society, Providence (1990) |
| [11] | Fu, J., Sun, W.: Nonmonotone adaptive trust-region method for unconstrained optimization problems. Appl. Math. Comput. 163, 489–504 (2005) · Zbl 1069.65063 · doi:10.1016/j.amc.2004.02.011 |
| [12] | Glunt, W., Hayden, T.L., Raydan, M.: Molecular conformations from distance matrices. J. Comput. Chem. 14, 114–120 (1993) · doi:10.1002/jcc.540140115 |
| [13] | 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 |
| [14] | Ken, X., Han, J.: A class of nonmonotone trust region algorithms for unconstrained optimization problems. Sci. China 41(9), 927–932 (1998) · Zbl 0917.90271 · doi:10.1007/BF02880001 |
| [15] | Martínez, J.M.: Local minimizer of a quadratic function with spherical constraint. SIAM J. Optim. 10(4), 1196–1211 (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963 |
| [16] | Mo, J., Liu, C., Yan, S.: A nonmonotone trust region method based on nonincreasing technique of weighted average of the successive function values. J. Comput. Appl. Math. 209, 97–108 (2007) · Zbl 1142.65049 · doi:10.1016/j.cam.2006.10.070 |
| [17] | Mo, J., Zhang, K., Wei, Z.: A nonmonotone trust region method for unconstrained optimization. Appl. Math. Comput. 171, 371–384 (2005) · Zbl 1094.65059 · doi:10.1016/j.amc.2005.01.048 |
| [18] | Moré, J.J.: Recent developments in algorithms and software for trust region methods. In: Bachem, A., Grotschel, M., Korte, B. (eds.) Mathematical Programming: The State of the Art, pp. 258–287. Springer, Berlin (1984) |
| [19] | Moré, J.J., Garbow, B.S., Hillstrom, K.W.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7(1), 17–41 (1981) · Zbl 0454.65049 · doi:10.1145/355934.355936 |
| [20] | Powell, M.J.D.: Convergence properties of a class of minimization algorithms. In: Mangasarian, O.L., Meyer, R.R., Robinson, S.M. (eds.) Nonlinear Programming, vol. 2 pp. 1–27. Academic Press, New York (1975) · Zbl 0321.90045 |
| [21] | Raydan, M.: On the Barzilai and Borwein choice of the steplength for the gradient method. IMA J. Numer. Anal. 13, 321–326 (1993) · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321 |
| [22] | 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 |
| [23] | Schwetlick, H.: Nonstandard scaling matrices in trust region methods. In: Allgower, E.L., Georg, K. (eds.) Computational Solution of Nonlinear Systems of Equations. Lectures in Applied Mathematics, vol. 26, pp. 587–604. American Mathematical Society, Providence (1990) |
| [24] | Steihaug, T.: The conjugate gradient method and trust regions in large scale optimization. SIAM J. Numer. Anal. 20(3), 626–637 (1983) · Zbl 0518.65042 · doi:10.1137/0720042 |
| [25] | Sun, W.: Nonmonotone trust region method for solving optimization problems. Appl. Math. Comput. 156, 159–174 (2004) · Zbl 1059.65055 · doi:10.1016/j.amc.2003.07.008 |
| [26] | Tao, P.D. An, L.T.H.: A DC optimization algorithm for solving the trust–region subproblem. SIAM J. Optim. 8(2), 476–505 (1998) · Zbl 0913.65054 · doi:10.1137/S1052623494274313 |
| [27] | Toint, P.L.: Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints. Math. Program. 77, 69–94 (1997) · Zbl 0891.90153 |
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.
