×

zbMATH — the first resource for mathematics

A dwindling filter line search method for unconstrained optimization. (English) Zbl 1307.65085
Summary: 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.

MSC:
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
Software:
CUTE ; GALAHAD; CUTE; L-BFGS; CUTEr
PDF BibTeX Cite
Full Text: DOI
References:
[1] [cute-1] 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. · Zbl 0886.65058
[2] Chen, Yan Nan; Sun, Wen Yu, A new nonmonotone optimization method with trust region and second-order line search, Numer. Math. J. Chinese Univ., 32, 4, 369-386 (2010) · Zbl 1240.65182
[3] Dolan, Elizabeth D.; Mor{\'e}, Jorge J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, Ser. A, 201-213 (2002) · Zbl 1049.90004
[4] Fasano, G., Planar conjugate gradient algorithm for large-scale unconstrained optimization. I. Theory, J. Optim. Theory Appl., 125, 3, 523-541 (2005) · Zbl 1079.90162
[5] Fasano, G., Planar conjugate gradient algorithm for large-scale unconstrained optimization. II. Application, J. Optim. Theory Appl., 125, 3, 543-558 (2005) · Zbl 1079.90163
[6] Fasano, Giovanni; Roma, Massimo, Iterative computation of negative curvature directions in large scale optimization, Comput. Optim. Appl., 38, 1, 81-104 (2007) · Zbl 1171.90549
[7] Ferris, M. C.; Lucidi, S.; Roma, M., Nonmonotone curvilinear line search methods for unconstrained optimization, Comput. Optim. Appl., 6, 2, 117-136 (1996) · Zbl 0860.90111
[8] Fletcher, Roger; Gould, Nicholas I. M.; Leyffer, Sven; Toint, Philippe L.; W{\"a}chter, Andreas, Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming, SIAM J. Optim., 13, 3, 635-659 (2003) (2002) · Zbl 1038.90076
[9] Fletcher, Roger; Leyffer, Sven, Nonlinear programming without a penalty function, Math. Program., 91, 2, Ser. A, 239-269 (2002) · Zbl 1049.90088
[10] Fletcher, Roger; Leyffer, Sven; Toint, Philippe L., On the global convergence of a filter-SQP algorithm, SIAM J. Optim., 13, 1, 44-59 (electronic) (2002) · Zbl 1029.65063
[11] [FletcherLeyfferToint-2006] 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.
[12] Gonzaga, Cl{\'o}vis C.; Karas, Elizabeth; Vanti, M{\'a}rcia, A globally convergent filter method for nonlinear programming, SIAM J. Optim., 14, 3, 646-669 (electronic) (2003) · Zbl 1079.90129
[13] Gould, Nicholas I. M.; Leyffer, Sven; Toint, Philippe L., A multidimensional filter algorithm for nonlinear equations and nonlinear least-squares, SIAM J. Optim., 15, 1, 17-38 (2004) · Zbl 1075.65075
[14] Gould, N. I. M.; Lucidi, S.; Roma, M.; Toint, Ph. L., Exploiting negative curvature directions in linesearch methods for unconstrained optimization, Optim. Methods Softw., 14, 1-2, 75-98 (2000) · Zbl 0988.90039
[15] Gould, Nicholas I. M.; Orban, Dominique; Toint, Philippe L., GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization, ACM Trans. Math. Software, 29, 4, 353-372 (2003) · Zbl 1068.90525
[16] Gould, Nick I. M.; Sainvitu, Caroline; Toint, Philippe L., A filter-trust-region method for unconstrained optimization, SIAM J. Optim., 16, 2, 341-357 (2005) · Zbl 1122.90074
[17] Kreji{\'c}, Nata{\v{s}}a; Lu{\v{z}}anin, Zorana; Stojkovska, Irena, Gauss-Newton-based BFGS methods with filter for unconstrained minimization, Appl. Math. Comput., 211, 2, 354-362 (2009) · Zbl 1165.65357
[18] Li, ChengJin; Sun, WenYu, On filter-successive linearization methods for nonlinear semidefinite programming, Sci. China Ser. A, 52, 11, 2341-2361 (2009) · Zbl 1185.65099
[19] Li, Shujun; Liu, Zhenhai, A new trust region filter algorithm, Appl. Math. Comput., 204, 1, 485-489 (2008) · Zbl 1167.65034
[20] Liu, Dong C.; Nocedal, Jorge, On the limited memory BFGS method for large scale optimization, Math. Programming, 45, 3, (Ser. B), 503-528 (1989) · Zbl 0696.90048
[21] Long, Jun; Zeng, Sanyun, A new filter-Levenberg-Marquardt method with disturbance for solving nonlinear complementarity problems, Appl. Math. Comput., 216, 2, 677-688 (2010) · Zbl 1197.65065
[22] Lucidi, Stefano; Rochetich, Francesco; Roma, Massimo, Curvilinear stabilization techniques for truncated Newton methods in large scale unconstrained optimization, SIAM J. Optim., 8, 4, 916-939 (electronic) (1998) · Zbl 0912.90259
[23] McCormick, Garth P., A modification of Armijo’s step-size rule for negative curvature, Math. Programming, 13, 1, 111-115 (1977) · Zbl 0367.90100
[24] Miao, Wei Hua; Sun, Wen Yu, A filter trust-region method for unconstrained optimization, Numer. Math. J. Chinese Univ., 29, 1, 88-96 (2007) · Zbl 1142.65364
[25] Mor{\'e}, Jorge J.; Sorensen, Danny C., On the use of directions of negative curvature in a modified Newton method, Math. Programming, 16, 1, 1-20 (1979) · Zbl 0394.90093
[26] Nie, Pu-yan; Lai, Ming-yong; Zhu, Shu-jin; Zhang, Pei-ai, A line search filter approach for the system of nonlinear equations, Comput. Math. Appl., 55, 9, 2134-2141 (2008) · Zbl 1144.90491
[27] Nocedal, Jorge, Updating quasi-Newton matrices with limited storage, Math. Comp., 35, 151, 773-782 (1980) · Zbl 0464.65037
[28] Nocedal, Jorge; Wright, Stephen J., Numerical optimization, Springer Series in Operations Research and Financial Engineering, xxii+664 pp. (2006), Springer: New York:Springer · Zbl 1104.65059
[29] Ribeiro, Ademir A.; Karas, Elizabeth W.; Gonzaga, Cl{\'o}vis C., Global convergence of filter methods for nonlinear programming, SIAM J. Optim., 19, 3, 1231-1249 (2008) · Zbl 1169.49034
[30] Sainvitu, Caroline; Toint, Philippe L., A filter-trust-region method for simple-bound constrained optimization, Optim. Methods Softw., 22, 5, 835-848 (2007) · Zbl 1169.90458
[31] [Sun-09] 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.
[32] [SunYuan-2006] Wenyu Sun and Ya xiang Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer Optimization and Its Applications, vol. 1, Springer, New York, 2006.
[33] Sun, Wen-yu; Zhou, Qun-yan, An unconstrained optimization method using nonmonotone second order Goldstein’s line search, Sci. China Ser. A, 50, 10, 1389-1400 (2007) · Zbl 1132.65057
[34] W{\"a}chter, Andreas; Biegler, Lorenz T., Line search filter methods for nonlinear programming: local convergence, SIAM J. Optim., 16, 1, 32-48 (electronic) (2005) · Zbl 1115.90056
[35] W{\"a}chter, Andreas; Biegler, Lorenz T., Line search filter methods for nonlinear programming: motivation and global convergence, SIAM J. Optim., 16, 1, 1-31 (electronic) (2005) · Zbl 1114.90128
[36] Wang, Zhujun; Zhu, Detong, A filter-line-search method for unconstrained optimization, J. Appl. Math. Comput., 34, 1-2, 329-342 (2010) · Zbl 1207.49039
[37] Yang, Zhenghao; Sun, Wenyu; Dang, Chuangyin, A filter-trust-region method for \(LC^1\) unconstrained optimization and its global convergence, Anal. Theory Appl., 24, 1, 55-66 (2008) · Zbl 1164.65022
[38] Zhang, Yan; Sun, Wenyu; Qi, Liqun, A nonmonotone filter Barzilai-Borwein method for optimization, Asia-Pac. J. Oper. Res., 27, 1, 55-69 (2010) · Zbl 1186.90113
[39] Zhou, Qun-yan; Sun, Wen-yu, An adaptive nonmonotonic trust region method with curvilinear searches, J. Comput. Math., 24, 6, 761-770 (2006) · Zbl 1133.65036
[40] Zhou, Qun-yan; Sun, Wen-yu, A nonmonotone second-order steplength method for unconstrained minimization, J. Comput. Math., 25, 1, 104-112 (2007) · Zbl 1142.65367
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.