Two globally convergent nonmonotone trust-region methods for unconstrained optimization

详细信息    查看全文

• 作者：Masoud Ahookhosh ; Susan Ghaderi
• 关键词：Unconstrained optimization ; Black ; box oracle ; Trust ; region method ; Nonmonotone strategy ; Global convergence ; 90C30 ; 65K05
• 刊名：Journal of Applied Mathematics and Computing
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：50
• 期：1-2
• 页码：529-555
• 全文大小：784 KB
• 参考文献：1.Ahookhosh, M., Amini, K.: An efficient nonmonotone trust-region method for unconstrained optimization. Numer. Algorithms 59(4), 523–540 (2012)MathSciNet CrossRef MATH
  2.Ahookhosh, M., Amini, K.: A nonmonotone trust region method with adaptive radius for unconstrained optimization problems. Comput. Math. Appl. 60(3), 411–422 (2010)MathSciNet CrossRef MATH
  3.Ahookhosh, M., Amini, K., Bahrami, S.: A class of nonmonotone Armijo-type line search method for unconstrained optimization. Optimization 61(4), 387–404 (2012)MathSciNet CrossRef MATH
  4.Ahookhosh, M., Amini, K., Peyghami, M.R.: A nonmonotone trust-region line search method for large-scale unconstrained optimization. Appl. Math. Model. 36(1), 478–487 (2012)MathSciNet CrossRef MATH
  5.Ahookhosh, M., Esmaeili, H., Kimiaei, M.: An effective trust-region-based approach for symmetric nonlinear systems. Int. J. Comput. Math. 90(3), 671–690 (2013)CrossRef MATH
  6.Ahookhosh, M., Ghederi, S.: On efficiency of nonmonotone Armijo-type line searches. http://​arxiv.​org/​pdf/​1408.​2675 (2015)
  7.Amini, K., Ahookhosh, M.: A hybrid of adjustable trust-region and nonmonotone algorithms for unconstrained optimization. Appl. Math. Model. 38, 2601–2612 (2014)MathSciNet CrossRef
  8.Amini, K., Ahookhosh, M., Nosratipour, H.: An inexact line search approach using modified nonmonotone strategy for unconstrained optimization. Numer. Algorithms 66, 49–78 (2014)MathSciNet CrossRef MATH
  9.Andrei, N.: An unconstrained optimization test functions collection. Adv. Model. Optim. 10(1), 147–161 (2008)MathSciNet MATH
  10.Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10, 1196–1211 (2000)MathSciNet CrossRef MATH
  11.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)MathSciNet CrossRef MATH
  12.Bonnans, J.F., Panier, E., Tits, A., Zhou, J.L.: Avoiding the Maratos effect by means of a nonmonotone line search, II: inequality constrained problems—feasible iterates. SIAM J. Numer. Anal. 29, 1187–1202 (1992)MathSciNet CrossRef MATH
  13.Chamberlain, R.M., Powell, M.J.D., Lemarechal, C., Pedersen, H.C.: The watchdog technique for forcing convergence in algorithm for constrained optimization. Math. Progr. Study 16, 1–17 (1982)MathSciNet CrossRef MATH
  14.Conn, A.R., Gould, N.I.M., Toint, PhL: Trust-Region Methods, Society for Industrial and Applied Mathematics. SIAM, Philadelphia (2000)CrossRef
  15.Davidon, W.C.: Conic approximation and collinear scaling for optimizers. SIAM J. Numer. Anal. 17, 268–281 (1980)MathSciNet CrossRef MATH
  16.Deng, N.Y., Xiao, Y., Zhou, F.J.: Nonmonotonic trust region algorithm. J. Optim. Theory Appl. 76, 259–285 (1993)MathSciNet CrossRef MATH
  17.Dennis, J.E., Li, S.B., Tapia, R.A.: A unified approach to global convergence of trust region methods for nonsmooth optimization. Math. Progr. 68, 319–346 (1995)MathSciNet MATH
  18.Di, S., Sun, W.: Trust region method for conic model to solve unconstrained optimization problems. Optim. Methods Softw. 6, 237–263 (1996)CrossRef
  19.Dolan, E., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Progr. 91, 201–213 (2002)CrossRef MATH
  20.Erway, J.B., Gill, P.E.: A subspace minimization method for the trust-region step. SIAM J. Optim. 20(3), 1439–1461 (2009)MathSciNet CrossRef MATH
  21.Erway, J.B., Gill, P.E., Griffin, J.D.: Iterative methods for finding a trust-region step. SIAM J. Optim. 20(2), 1110–1131 (2009)MathSciNet CrossRef MATH
  22.Fletcher, R.: Practical Methods of Optimization, 2nd edn. Wiley, New York (1987)MATH
  23.Ferreira, P.S., Karas, E.W., Sachine, M.: A globally convergent trust-region algorithm for unconstrained derivative-free optimization. Comput. Appl. Math. (2014). doi:10.​1007/​s40314-014-0167-2
  24.Grapiglia, G.N., Yuan, J., Yuan, Y.: A derivative-free trust-region algorithm for composite nonsmooth optimization. Comput. Appl. Math. (2014). doi:10.​1007/​s40314-014-0201-4
  25.Gould, N.I.M., Orban, D., Toint, P.H.L.: CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Comput. Optim. Appl. (2014). doi:10.​1007/​s10589-014-9687-3
  26.Gould, N.I.M., Lucidi, S., Roma, M., Toint, PhL: Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9(2), 504–525 (1999)MathSciNet CrossRef MATH
  27.Gould, N.I.M., Orban, D., Sartenaer, A., Toint, PhL: Sensitivity of trust-region algorithms to their parameters. Q. J. Oper. Res. 3, 227–241 (2005)MathSciNet CrossRef MATH
  28.Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23, 707–716 (1986)MathSciNet CrossRef MATH
  29.Gürbüzbalaban, M., Overton, M.L.: On Nesterov’s nonsmooth Chebyshev–Rosenbrock functions. Nonlinear Anal. 75, 1282–1289 (2012)MathSciNet CrossRef MATH
  30.Hallabi, M.E., Tapia, R.: A global convergence theory for arbitraty norm trust region methods for nonlinear equations. Mathematical Sciences Technical Report, TR 87–25, Rice University, Houston, TX (1987)
  31.Mo, J., Liu, C., Yan, S.: A nonmonotone trust region method based on nonincreasing technique of weighted average of the succesive function value. J. Comput. Appl. Math. 209, 97–108 (2007)MathSciNet CrossRef MATH
  32.Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4(3), 553–572 (1983)CrossRef MATH
  33.Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, NewYork (2006)MATH
  34.Panier, E.R., Tits, A.L.: Avoiding the Maratos effect by means of a nonmonotone linesearch. SIAM J. Numer. Anal. 28, 1183–1195 (1991)MathSciNet CrossRef MATH
  35.Rojas, M., Sorensen, D.C.: A trust-region approach to the regularization of large-scale discrete forms of ill-posed problems. SIAM J. Sci. Comput. 26, 1842–1860 (2002)MathSciNet CrossRef
  36.Schultz, G.A., Schnabel, R.B., Byrd, R.H.: A family of trust-region-based algorithms for unconstrained minimization with strong global convergence. SIAM J. Numer. Anal. 22, 47–67 (1985)MathSciNet CrossRef
  37.Sorensen, D.C.: The \(q\) -superlinear convergence of a collinear scaling algorithm for unconstrained optimization. SIAM J. Numer. Anal. 17, 84–114 (1980)MathSciNet CrossRef MATH
  38.Sorensen, D.C.: Newton’s method with a model trust region modification. SIAM J. Numer. Anal. 19(2), 409–426 (1982)MathSciNet CrossRef MATH
  39.Steihaug, T.: The conjugate gradient method and trust regions in large scale optimization. SIAM J. Numer. Anal. 20(3), 626–637 (1983)MathSciNet CrossRef MATH
  40.Sun, W.: On nonquadratic model optimization methods. Asia Pac. J. Oper. Res. 13, 43–63 (1996)MATH
  41.Toint, Ph.L: An assessment of nonmonotone linesearch technique for unconstrained optimization. SIAM J. Sci. Comput. 17, 725–739 (1996)
  42.Toint, Ph.L: Non-monotone trust-region algorithm for nonlinear optimization subject to convex constraints. Math. Progr. 77, 69–94 (1997)
  43.Ulbrich, M., Ulbrich, S.: Nonmonotone trust region methods for nonlinear equality constrained optimization without a penalty function. Math. Progr. 95, 103–135 (2003)MathSciNet CrossRef MATH
  44.Xiao, Y., Zhou, F.J.: Nonmonotone trust region methods with curvilinear path in unconstrained optimization. Computing 48, 303–317 (1992)MathSciNet CrossRef MATH
  45.Xiao, Y., Chu, E.K.W.: Nonmonotone trust region methods, Technical Report 95/17. Monash University, Clayton, Australia (1995)
  46.Yuan, Y.: Conditions for convergence of trust region algorithms for nonsmooth optimization. Math. Progr. 31, 220–228 (1985)CrossRef MATH
  47.Zhang, H.C., Hager, W.W.: A nonmonotone line search technique for unconstrained optimization. SIAM J. Optim. 14(4), 1043–1056 (2004)MathSciNet CrossRef MATH
  48.Zhou, F., Xiao, Y.: A class of nonmonotone stabilization trust region methods. Computing 53(2), 119–136 (1994)MathSciNet CrossRef MATH
  
• 作者单位：Masoud Ahookhosh (1)
  Susan Ghaderi (2)
  
  1. Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, 1090, Vienna, Austria
  2. Department of Mathematics, Faculty of Science, Razi University, Kermanshah, Iran
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Computational Mathematics and Numerical Analysis
  Applied Mathematics and Computational Methods of Engineering
  Theory of Computation
  Mathematics of Computing
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1865-2085

文摘

This paper addresses some trust-region methods equipped with nonmonotone strategies for solving nonlinear unconstrained optimization problems. More specifically, the importance of using nonmonotone techniques in nonlinear optimization is motivated, then two new nonmonotone terms are proposed, and their combinations into the traditional trust-region framework are studied. The global convergence to first- and second-order stationary points and local superlinear and quadratic convergence rates for both algorithms are established. Numerical experiments on the CUTEst test collection of unconstrained problems and some highly nonlinear test functions are reported, where a comparison among state-of-the-art nonmonotone trust-region methods shows the efficiency of the proposed nonmonotone schemes. Keywords Unconstrained optimization Black-box oracle Trust-region method Nonmonotone strategy Global convergence