A dwindling filter line search method for unconstrained optimization

Chen, Yannan; Sun, Wenyu

doi:10.1090/S0025-5718-2014-02847-0

A dwindling filter line search method for unconstrained optimization
HTML articles powered by AMS MathViewer

by Yannan Chen and Wenyu Sun PDF

Math. Comp. 84 (2015), 187-208 Request permission

Abstract:

A dwindling multidimensional filter is proposed and applied to a second-order line search framework for unconstrained optimization. Usually, the multidimensional filter is built up with a fixed envelope, which is not well-suited to line search frameworks. In this paper, we propose the dwindling multidimensional filter, whose envelope is dwindling as the step-length of line search decreasing. Combining the dwindling multidimensional filter and a second-order line search, the new algorithm globally converges to a second-order critical point, when the negative curvature direction is exploited. Detailed numerical results on small and large CUTE test problems indicate that the new algorithm is more competitive than some classical line search methods.

References

I. Bongartz, A. R. Conn, Nicholas I. M. Gould, and Philippe L. Toint, Cute: constrained and unconstrained testing environment, ACM Transactions on Mathematical Software 21 (1995), no. 1, 123–160.
Yan Nan Chen and Wen Yu Sun, A new nonmonotone optimization method with trust region and second-order line search, Numer. Math. J. Chinese Univ. 32 (2010), no. 4, 369–386 (Chinese, with English summary). MR 2790772
Elizabeth D. Dolan and Jorge J. Moré, Benchmarking optimization software with performance profiles, Math. Program. 91 (2002), no. 2, Ser. A, 201–213. MR 1875515, DOI 10.1007/s101070100263
G. Fasano, Planar conjugate gradient algorithm for large-scale unconstrained optimization. I. Theory, J. Optim. Theory Appl. 125 (2005), no. 3, 523–541. MR 2148660, DOI 10.1007/s10957-005-2087-1
G. Fasano, Planar conjugate gradient algorithm for large-scale unconstrained optimization. II. Application, J. Optim. Theory Appl. 125 (2005), no. 3, 543–558. MR 2148661, DOI 10.1007/s10957-005-2088-0
Giovanni Fasano and Massimo Roma, Iterative computation of negative curvature directions in large scale optimization, Comput. Optim. Appl. 38 (2007), no. 1, 81–104. MR 2332402, DOI 10.1007/s10589-007-9034-z
M. C. Ferris, S. Lucidi, and M. Roma, Nonmonotone curvilinear line search methods for unconstrained optimization, Comput. Optim. Appl. 6 (1996), no. 2, 117–136. MR 1398263, DOI 10.1007/BF00249642
Roger Fletcher, Nicholas I. M. Gould, Sven Leyffer, Philippe L. Toint, and Andreas Wächter, Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming, SIAM J. Optim. 13 (2002), no. 3, 635–659 (2003). MR 1972208, DOI 10.1137/S1052623499357258
Roger Fletcher and Sven Leyffer, Nonlinear programming without a penalty function, Math. Program. 91 (2002), no. 2, Ser. A, 239–269. MR 1875517, DOI 10.1007/s101070100244
Roger Fletcher, Sven Leyffer, and Philippe L. Toint, On the global convergence of a filter-SQP algorithm, SIAM J. Optim. 13 (2002), no. 1, 44–59. MR 1922433, DOI 10.1137/S105262340038081X
Roger Fletcher, Sven Leyffer, and Philippe L. Toint, A brief history of filter methods, SIAG/OPT Views-and-News 18 (2007), no. 1, 2–12.
Clóvis C. Gonzaga, Elizabeth Karas, and Márcia Vanti, A globally convergent filter method for nonlinear programming, SIAM J. Optim. 14 (2003), no. 3, 646–669. MR 2085935, DOI 10.1137/S1052623401399320
Nicholas I. M. Gould, Sven Leyffer, and Philippe L. Toint, A multidimensional filter algorithm for nonlinear equations and nonlinear least-squares, SIAM J. Optim. 15 (2004), no. 1, 17–38. MR 2112974, DOI 10.1137/S1052623403422637
N. I. M. Gould, S. Lucidi, M. Roma, and Ph. L. Toint, Exploiting negative curvature directions in linesearch methods for unconstrained optimization, Optim. Methods Softw. 14 (2000), no. 1-2, 75–98. International Conference on Nonlinear Programming and Variational Inequalities (Hong Kong, 1998). MR 1809604, DOI 10.1080/10556780008805794
Nicholas I. M. Gould, Dominique Orban, and Philippe L. Toint, GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization, ACM Trans. Math. Software 29 (2003), no. 4, 353–372. MR 2077337, DOI 10.1145/962437.962438
Nick I. M. Gould, Caroline Sainvitu, and Philippe L. Toint, A filter-trust-region method for unconstrained optimization, SIAM J. Optim. 16 (2005), no. 2, 341–357. MR 2197983, DOI 10.1137/040603851
Nataša Krejić, Zorana Lužanin, and Irena Stojkovska, Gauss-Newton-based BFGS methods with filter for unconstrained minimization, Appl. Math. Comput. 211 (2009), no. 2, 354–362. MR 2524164, DOI 10.1016/j.amc.2009.01.041
ChengJin Li and WenYu Sun, On filter-successive linearization methods for nonlinear semidefinite programming, Sci. China Ser. A 52 (2009), no. 11, 2341–2361. MR 2566650, DOI 10.1007/s11425-009-0168-6
Shujun Li and Zhenhai Liu, A new trust region filter algorithm, Appl. Math. Comput. 204 (2008), no. 1, 485–489. MR 2458387, DOI 10.1016/j.amc.2008.07.007
Dong C. Liu and Jorge Nocedal, On the limited memory BFGS method for large scale optimization, Math. Programming 45 (1989), no. 3, (Ser. B), 503–528. MR 1038245, DOI 10.1007/BF01589116
Jun Long and Sanyun Zeng, A new filter-Levenberg-Marquardt method with disturbance for solving nonlinear complementarity problems, Appl. Math. Comput. 216 (2010), no. 2, 677–688. MR 2601536, DOI 10.1016/j.amc.2010.01.098
Stefano Lucidi, Francesco Rochetich, and Massimo Roma, Curvilinear stabilization techniques for truncated Newton methods in large scale unconstrained optimization, SIAM J. Optim. 8 (1998), no. 4, 916–939. MR 1641270, DOI 10.1137/S1052623495295250
Garth P. McCormick, A modification of Armijo’s step-size rule for negative curvature, Math. Programming 13 (1977), no. 1, 111–115. MR 461907, DOI 10.1007/BF01584328
Wei Hua Miao and Wen Yu Sun, A filter trust-region method for unconstrained optimization, Numer. Math. J. Chinese Univ. 29 (2007), no. 1, 88–96 (Chinese, with English summary). MR 2337211
Jorge J. Moré and Danny C. Sorensen, On the use of directions of negative curvature in a modified Newton method, Math. Programming 16 (1979), no. 1, 1–20. MR 517757, DOI 10.1007/BF01582091
Pu-yan Nie, Ming-yong Lai, Shu-jin Zhu, and Pei-ai Zhang, A line search filter approach for the system of nonlinear equations, Comput. Math. Appl. 55 (2008), no. 9, 2134–2141. MR 2401120, DOI 10.1016/j.camwa.2007.08.037
Jorge Nocedal, Updating quasi-Newton matrices with limited storage, Math. Comp. 35 (1980), no. 151, 773–782. MR 572855, DOI 10.1090/S0025-5718-1980-0572855-7
Jorge Nocedal and Stephen J. Wright, Numerical optimization, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. MR 2244940
Ademir A. Ribeiro, Elizabeth W. Karas, and Clóvis C. Gonzaga, Global convergence of filter methods for nonlinear programming, SIAM J. Optim. 19 (2008), no. 3, 1231–1249. MR 2460740, DOI 10.1137/060672285
Caroline Sainvitu and Philippe L. Toint, A filter-trust-region method for simple-bound constrained optimization, Optim. Methods Softw. 22 (2007), no. 5, 835–848. MR 2354770, DOI 10.1080/10556780701322970
Wenyu Sun, Filter methods for optimization: motivation and development, invited talk, International Conference on Engineering Mathematics and Computational Mathematics, Hong Kong Polytechnical University, December 2009.
Wenyu Sun and Ya xiang Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer Optimization and Its Applications, vol. 1, Springer, New York, 2006.
Wen-yu Sun and Qun-yan Zhou, An unconstrained optimization method using nonmonotone second order Goldstein’s line search, Sci. China Ser. A 50 (2007), no. 10, 1389–1400. MR 2390457, DOI 10.1007/s11425-007-0072-x
Andreas Wächter and Lorenz T. Biegler, Line search filter methods for nonlinear programming: local convergence, SIAM J. Optim. 16 (2005), no. 1, 32–48. MR 2177768, DOI 10.1137/S1052623403426544
Andreas Wächter and Lorenz T. Biegler, Line search filter methods for nonlinear programming: motivation and global convergence, SIAM J. Optim. 16 (2005), no. 1, 1–31. MR 2177767, DOI 10.1137/S1052623403426556
Zhujun Wang and Detong Zhu, A filter-line-search method for unconstrained optimization, J. Appl. Math. Comput. 34 (2010), no. 1-2, 329–342. MR 2718789, DOI 10.1007/s12190-009-0324-8
Zhenghao Yang, Wenyu Sun, and Chuangyin Dang, A filter-trust-region method for $LC^1$ unconstrained optimization and its global convergence, Anal. Theory Appl. 24 (2008), no. 1, 55–66. MR 2422460, DOI 10.1007/s10496-008-0055-y
Yan Zhang, Wenyu Sun, and Liqun Qi, A nonmonotone filter Barzilai-Borwein method for optimization, Asia-Pac. J. Oper. Res. 27 (2010), no. 1, 55–69. MR 2646952, DOI 10.1142/S0217595910002582
Qun-yan Zhou and Wen-yu Sun, An adaptive nonmonotonic trust region method with curvilinear searches, J. Comput. Math. 24 (2006), no. 6, 761–770. MR 2269958
Qun-yan Zhou and Wen-yu Sun, A nonmonotone second-order steplength method for unconstrained minimization, J. Comput. Math. 25 (2007), no. 1, 104–112. MR 2292432