A Retrospective Filter Trust Region Algorithm for Unconstrained Optimization

Yue Lu, Zhongwen Chen
DOI: 10.4236/am.2010.13022                

Abstract

In this paper, we propose a retrospective filter trust region algorithm for unconstrained optimization, which is based on the framework of the retrospective trust region method and associated with the technique of the multi-dimensional filter. The new algorithm gives a good estimation of trust region radius, relaxes the condition of accepting a trial step for the usual trust region methods. Under reasonable assumptions, we analyze the global convergence of the new method and report the preliminary results of numerical tests. We compare the results with those of the basic trust region algorithm, the filter trust region algorithm and the retrospective trust region algorithm, which shows the effectiveness of the new algorithm.

Keywords

Unconstrained Optimization, Retrospective, Trust Region Method, Multi-Dimensional Filter Technique

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. J. D. Powell, “A New Algorithm for Unconstrained Optimization,” In: J. B. Rosen, O. L. Mangasarian and K. Ritter, Eds., Nonlinear Programming, Academic Press, New York, 1970.
[2]	K. Levenberg, “A Method for The Solution of Certain Nonlinear Problems in Least Squares,” The Quarterly of Applied Mathematics, Vol. 2, No. 2, 1944, pp. 164-168.
[3]	D. W. Marquardt, “An Algorithm for Least Squares Estimation of Nonlinear Inequalities,” SIAM Journal on Applied Mathematics, Vol. 11, No. 2, 1963, pp. 431-441.
[4]	M. J. D. Powell, “Convergence Properties of a Class of Minimization Algorithms,” In: O. L. Mangasarian, R. R. Meyer and S. M. Robinson, Eds., Nonlinear Programming, Academic Press, New York, 1975, pp. 1-27.
[5]	M. J. D. Powell, “On the Global Convergence of Trust-Region Algorithms for Unconstrained Optimization,” Mathematical Programming, Vol. 29, No. 3, 1984, pp. 297-303.
[6]	G. A. Schultz, R. B. Schnabei and R. H. Byrd, “A Family of Trust-Region-Based Algorithms for Unconstrained Minimization with Strong Global Convergence,” SIAM Journal on Numerical Analysis, Vol. 22, No. 1, 1985, pp. 47-67.
[7]	D. C. Sorensen, “Newton’s Method with a Model Trust Region Modifications,” SIAM Journal on Numerical Analysis, Vol. 19, No. 2, 1982, pp. 409-426.
[8]	J. J. More, “Recent Developments in Algorithms and Software for Trust Region Methods,” In A. R. Bachem, M. Grotshel and B. Korte, Eds., Mathematical Programming: The State of the Art, Springer-Verlag, Berlin, 1983, pp. 258-287.
[9]	Y. X. Yuan, “On the Convergence of Trust Region Algorithm,” Mathematica Numerica Sinica, Vol. 16, No. 3, 1996, pp. 333-346.
[10]	M. Lalee, J. Nocedal and T. Plantenga, “On the Implentation of an Algorithm for Large-Scale Equality Constrained Optimization,” SIAM Journal on Optimization, Vol. 8, No. 3, 1998, pp. 682-706.
[11]	A. Friedlander, J. M. Martinez and S. A. Santos, “A New Trust Region Algorithm for Bound Constrained Minimization,” Applied Mathematics and Optimization, Vol. 30, No. 3, 1994, pp. 235-266.
[12]	A. R. Conn, N. I. M. Gould and P. L. Toint, “Convergence Properties of Minimization Algorithms for Convex Constraints Using a Structured Trust Region,” SIAM Journal on Optimization, Vol. 6, No. 4, 1996, pp. 1059- 1086.
[13]	A. R. Conn, N. I. M. Gould and P. L. Toint, “Trust Region Methods,” MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2000.
[14]	R. Fletcher and S. Leyffer, “Nonlinear Programming without a Penalty Function,” Mathematical Programming, Vol. 91, No. 2, 2002, pp. 239-269.
[15]	R. Fletcher, N. I. M. Gould, S. Leyffer, P. L. Toint and A. Wachter, “Global Convergence of a Trust-Region SQP- Filter Algorithm for General Nonlinear Programming,” SIAM Journal on Optimization, Vol. 13, No. 3, 2002, pp. 635-659.
[16]	R. Fletcher, S. Leyffer and P. L. Toint, “On the Global Convergence of a Filter-SQP Algorithm,” SIAM Journal on Optimization, Vol. 13, No. 1, 2002, pp. 44-59.
[17]	M. Ulbrich, S. Ulbrich and L. N. Vicente, “A Globally Convergent Primal Dual Interior-Point Filter Method for Nonconvex Nonlinear Programming,” Mathematical Programming, Vol. 100, No. 2, 2003, pp. 379-410.
[18]	A. W?chter and L. T. Biegler, “Line Search Filter Methods for Nonlinear Programming: Motivation and Global Convergence,” SIAM Journal on Optimization, Vol. 16, No. 1, 2005, pp. 1-31.
[19]	A. W?chter and L. T. Biegler, “Line Search Filter Methods for Nonlinear Programming: Local Convergence,” SIAM Journal on Optimization, Vol. 16, No. 1, 2005, pp. 32-48.
[20]	R. Fletcher, S. Leyffer and P. L. Toint, “A Brief History of Filter Methods,” SIAG/OPT Views and News, Vol. 18, No. 1, 2006, pp. 2-12.
[21]	N. I. M. Gould, C. Sainvitu and P. L. Toint, “A Filter- Trust-Region Method for Unconstrained Optimization,” SIAM Journal on Optimization, Vol. 16, No. 2, 2005, pp. 341-357.
[22]	W. H. Miao and W. Y. Sun, “A Filter Trust-Region Method for Unconstrained Optimization,” Numerical Mathematics ? A Journal of Chinese Universities. Gaodeng Xuexiao Jisuan Shuxue Xuebao, Vol. 29, No. 1, 2007, pp. 88-96.
[23]	L. Grippo, F. Lampariello and S. Lucidi, “A Nonmonotone Line Search Technique for Newton’s Methods,” SIAM Journal on Numerical Analysis, Vol. 23, No. 4, 1986, pp. 707-716.
[24]	P. L. Toint, “Non-Monotone Trust-Region Algorithms for Nonlinear Optimization Subject to Convex Constraints,” Mathematical Programming, Vol. 77, No. 1, 1997, pp. 69-94.
[25]	F. Bastin, V. Malmedy, M. Mouffe, P. L. Toint and D. Tomanos, “A Retrospective Trust-Region Method for Unconstrained Optimization,” Mathematical Programming, Vol. 123, No. 2, 2010, pp. 395-418.
[26]	A. Sartenaer, “Automatic Determination of an Initial Trust Region in Nonlinear Programming,” SIAM Journal on Scientific Computing, Vol. 18, No. 6, 1997, pp. 1788- 1803.
[27]	X. S. Zhang, Z. W. Chen and J. L. Zhang, “A Self-Adaptive Trust Region Method Unconstrained Optimization,” Operations Research Transactions, Vol. 5, No. 1, 2001, pp. 53-62.
[28]	N. I. M. Gould, D. Orban, A. Sartenaer and P. L. Toint, “Sensitivity of the Trust-Region Algorithms to Their Parameters,” 4OR: A Quarterly Journal of Operations Research, Vol. 3, No. 3, 2005, pp. 227-241.
[29]	K. Schittkowski, “More Test Examples for Nonlinear Programming Codes,” Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin, Heideberg, Vol. 282, 1987.
[30]	H. Y. Benson, “Nonlinear Optimization Models by AMPL: Cute Set.” http://www.princeton.edu/~rvdb/ampl/nlmodels