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
Additional Information
- Yannan Chen
- Affiliation: School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210046, China; and School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
- Email: ynchen@zzu.edu.cn
- Wenyu Sun
- Affiliation: Corresponding author: School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210046, China
- Email: wysun@njnu.edu.cn
- Received by editor(s): January 12, 2011
- Received by editor(s) in revised form: December 25, 2012, and May 1, 2013
- Published electronically: May 19, 2014
- Additional Notes: This work was supported by the National Natural Science Foundation of China (Nos. 11171159 and 11071122), the Specialized Research Fund for the Doctoral Program of Higher Education of China (No. 20103207110002), and the Graduate Student Research and Innovation Project of Jiangsu Province of China (No. CXZZ12_0384).
- © Copyright 2014 American Mathematical Society
- Journal: Math. Comp. 84 (2015), 187-208
- MSC (2010): Primary 65K05, 90C30
- DOI: https://doi.org/10.1090/S0025-5718-2014-02847-0
- MathSciNet review: 3266957