A Line Search Algorithm for Unconstrained Optimization

Affiliation(s)

College of Mathematics and Information Science, Guangxi University, Nanning, China.

School of Mathematical Science, Guangxi Teachers Education University, Nanning, China..

College of Mathematics and Information Science, Guangxi University, Nanning, China.

School of Mathematical Science, Guangxi Teachers Education University, Nanning, China..

ABSTRACT

It is well known that the line search methods play a very important role for optimization problems. In this paper a new line search method is proposed for solving unconstrained optimization. Under weak conditions, this method possesses global convergence and R-linear convergence for nonconvex function and convex function, respectively. Moreover, the given search direction has sufficiently descent property and belongs to a trust region without carrying out any line search rule. Numerical results show that the new method is effective.

It is well known that the line search methods play a very important role for optimization problems. In this paper a new line search method is proposed for solving unconstrained optimization. Under weak conditions, this method possesses global convergence and R-linear convergence for nonconvex function and convex function, respectively. Moreover, the given search direction has sufficiently descent property and belongs to a trust region without carrying out any line search rule. Numerical results show that the new method is effective.

Cite this paper

nullG. Yuan, S. Lu and Z. Wei, "A Line Search Algorithm for Unconstrained Optimization,"*Journal of Software Engineering and Applications*, Vol. 3 No. 5, 2010, pp. 503-509. doi: 10.4236/jsea.2010.35057.

nullG. Yuan, S. Lu and Z. Wei, "A Line Search Algorithm for Unconstrained Optimization,"

References

[1] G. Yuan and X. Lu, “A New Line Search Method with Trust Region for Unconstrained Optimization,” Commu- nications on Applied Nonlinear Analysis, Vol. 15, No. 1, 2008, pp. 35-49.

[2] G. Yuan, X. Lu, and Z. Wei, “New Two-Point Stepsize Gradient Methods for Solving Unconstrained Optimi- zation Problems,” Natural Science Journal of Xiangtan University, Vol. 29, No. 1, 2007, pp. 13-15.

[3] G. Yuan and Z. Wei, “New Line Search Methods for Uncons- trained Optimization,” Journal of the Korean Statistical Society, Vol. 38, No. 1, 2009, pp. 29-39.

[4] Y. Yuan and W. Sun, “Theory and Methods of Optimi- zation,” Science Press of China, Beijing, 1999.

[5] D. C. Luenerger, “Linear and Nonlinear Programming,” 2nd Edition, Addition Wesley, Reading, MA, 1989.

[6] J. Nocedal and S. J. Wright, “Numerical Optimization,” Springer, Berlin, Heidelberg, New York, 1999.

[7] Z. Wei, G. Li, and L. Qi, “New Quasi-Newton Methods for Unconstrained Optimization Problems,” Applied Mathe- matics and Computation, Vol. 175, No. 1, 2006, pp. 1156- 1188.

[8] Z. Wei, G. Yu, G. Yuan, and Z. Lian, “The Superlinear Convergence of a Modified BFGS-type Method for Unconstrained Optimization,” Computational Optimiza- tion and Applications, Vol. 29, No. 3, 2004, pp. 315-332.

[9] G. Yuan and Z. Wei, “The Superlinear Convergence Anal- ysis of a Nonmonotone BFGS Algorithm on Convex Objective Functions,” Acta Mathematica Sinica, English Series, Vol. 24, No. 1, 2008, pp. 35-42.

[10] G. Yuan and Z. Wei, “Convergence Analysis of a Modified BFGS Method on Convex Minimizations,” Computational Optimization and Applications, Science Citation Index, 2008.

[11] Y. Dai and Y. Yuan, “A Nonlinear Conjugate Gradient with a Strong Global Convergence Properties,” SIAM Journal of Optimization, Vol. 10, No. 1, 2000, pp. 177- 182.

[12] Z. Wei, G. Li, and L. Qi, “New Nonlinear Conjugate Gradient Formulas for Large-Scale Unconstrained Optimi- zation Problems,” Applied Mathematics and Computation, Vol. 179, No. 2, 2006, pp. 407-430.

[13] G. Yuan and X. Lu, “A Modified PRP Conjugate Gradient Method,” Annals of Operations Research, Vol. 166, No. 1, 2009, pp. 73-90.

[14] J. C. Gibert, J. Nocedal, “Global Convergence Properties of Conjugate Gradient Methods for Optimization,” SIAM Journal on Optimization, Vol. 2, No. 1, 1992, pp. 21-42.

[15] Y. Dai and Y. Yuan, “Nonlinear Conjugate Gradient Methods,” Shanghai Science and Technology Press, 2000.

[16] E. Polak and G. Ribiè, “Note Sur la Xonvergence de Directions Conjugèes,” Rev Francaise Informat Recher- che Operatinelle 3e Annèe, Vol. 16, 1969, pp. 35-43.

[17] M. J. D. Powell, “Nonconvex Minimization Calculations and the Conjugate Gradient Method,” Lecture Notes in Mathematics, Springer-Verlag, Berlin, Vol. 1066, 1984, pp. 122-141.

[18] L. Grippo and S. Lucidi, “A Globally Convergent Version of the Polak-RibiÈRe Gradient Method,” Mathematical Programming, Vol. 78, No. 3, 1997, pp. 375-391.

[19] W. W. Hager and H. Zhang, “A New Conjugate Gradient Method with Guaranteed Descent and an Efficient Line Search,” SIAM Journal on Optimization, Vol. 16, No. 1, 2005, pp. 170-192.

[20] Z. Wei, S. Yao, and L. Liu, “The Convergence Properties of Some New Conjugate Gradient Methods,” Applied Mathematics and Computation, Vol. 183, No. 2, 2006, pp. 1341-1350.

[21] G. H. Yu, “Nonlinear Self-Scaling Conjugate Gradient Methods for Large-scale Optimization Problems,” Thesis of Doctor's Degree, Sun Yat-Sen University, 2007.

[22] G. Yuan, “Modified Nonlinear Conjugate Gradient Methods with Sufficient Descent Property for Large-Scale Optimization Problems,” Optimization Letters, Vol. 3, No. 1, 2009, pp. 11-21.

[23] G. Yuan, “A Conjugate Gradient Method for Uncons- trained Optimization Problems,” International Journal of Mathematics and Mathematical Sciences, Vol. 2009, 2009, pp. 1-14.

[24] G. Yuan, X. Lu, and Z. Wei, “A Conjugate Gradient Method with Descent Direction for Unconstrained Optimi- zation,” Journal of Computational and Applied Mathe- matics, Vol. 233, No. 2, 2009, pp. 519-530.

[25] L. Zhang, W. Zhou, and D. Li, “A Descent Modified Polak-RibiÈRe-Polyak Conjugate Method and its Global Convergence,” IMA Journal on Numerical Analysis, Vol. 26, No. 4, 2006, pp. 629-649.

[26] Y. Liu and C. Storey, “Efficient Generalized Conjugate Gradient Algorithms, Part 1: Theory,” Journal of Optimi- zation Theory and Application, Vol. 69, No. 1, 1992, pp. 17-41.

[27] Z. J. Shi, “Convergence of Line Search Methods for Unconstrained Optimization,” Applied Mathematics and Computation, Vol. 157, No. 2, 2004, pp. 393-405.

[28] J. J. Moré, B. S. Garbow, and K. E. Hillstrome, “Testing Unconstrained Optimization Software,” ACM Transac- tions on Mathematical Software, Vol. 7, No. 1, 1981, pp. 17-41.

[29] E. D. Dolan and J. J. Moré, “Benchmarking Optimization Software with Performance Profiles,” Mathematical Programming, Vol. 91, No. 2, 2002, pp. 201-213.

[30] Y. Dai and Q. Ni, “Testing Different Conjugate Gradient Methods for Large-scale Unconstrained Optimization,” Journal of Computational Mathematics, Vol. 21, No. 3, 2003, pp. 311-320.

[1] G. Yuan and X. Lu, “A New Line Search Method with Trust Region for Unconstrained Optimization,” Commu- nications on Applied Nonlinear Analysis, Vol. 15, No. 1, 2008, pp. 35-49.

[2] G. Yuan, X. Lu, and Z. Wei, “New Two-Point Stepsize Gradient Methods for Solving Unconstrained Optimi- zation Problems,” Natural Science Journal of Xiangtan University, Vol. 29, No. 1, 2007, pp. 13-15.

[3] G. Yuan and Z. Wei, “New Line Search Methods for Uncons- trained Optimization,” Journal of the Korean Statistical Society, Vol. 38, No. 1, 2009, pp. 29-39.

[4] Y. Yuan and W. Sun, “Theory and Methods of Optimi- zation,” Science Press of China, Beijing, 1999.

[5] D. C. Luenerger, “Linear and Nonlinear Programming,” 2nd Edition, Addition Wesley, Reading, MA, 1989.

[6] J. Nocedal and S. J. Wright, “Numerical Optimization,” Springer, Berlin, Heidelberg, New York, 1999.

[7] Z. Wei, G. Li, and L. Qi, “New Quasi-Newton Methods for Unconstrained Optimization Problems,” Applied Mathe- matics and Computation, Vol. 175, No. 1, 2006, pp. 1156- 1188.

[8] Z. Wei, G. Yu, G. Yuan, and Z. Lian, “The Superlinear Convergence of a Modified BFGS-type Method for Unconstrained Optimization,” Computational Optimiza- tion and Applications, Vol. 29, No. 3, 2004, pp. 315-332.

[9] G. Yuan and Z. Wei, “The Superlinear Convergence Anal- ysis of a Nonmonotone BFGS Algorithm on Convex Objective Functions,” Acta Mathematica Sinica, English Series, Vol. 24, No. 1, 2008, pp. 35-42.

[10] G. Yuan and Z. Wei, “Convergence Analysis of a Modified BFGS Method on Convex Minimizations,” Computational Optimization and Applications, Science Citation Index, 2008.

[11] Y. Dai and Y. Yuan, “A Nonlinear Conjugate Gradient with a Strong Global Convergence Properties,” SIAM Journal of Optimization, Vol. 10, No. 1, 2000, pp. 177- 182.

[12] Z. Wei, G. Li, and L. Qi, “New Nonlinear Conjugate Gradient Formulas for Large-Scale Unconstrained Optimi- zation Problems,” Applied Mathematics and Computation, Vol. 179, No. 2, 2006, pp. 407-430.

[13] G. Yuan and X. Lu, “A Modified PRP Conjugate Gradient Method,” Annals of Operations Research, Vol. 166, No. 1, 2009, pp. 73-90.

[14] J. C. Gibert, J. Nocedal, “Global Convergence Properties of Conjugate Gradient Methods for Optimization,” SIAM Journal on Optimization, Vol. 2, No. 1, 1992, pp. 21-42.

[15] Y. Dai and Y. Yuan, “Nonlinear Conjugate Gradient Methods,” Shanghai Science and Technology Press, 2000.

[16] E. Polak and G. Ribiè, “Note Sur la Xonvergence de Directions Conjugèes,” Rev Francaise Informat Recher- che Operatinelle 3e Annèe, Vol. 16, 1969, pp. 35-43.

[17] M. J. D. Powell, “Nonconvex Minimization Calculations and the Conjugate Gradient Method,” Lecture Notes in Mathematics, Springer-Verlag, Berlin, Vol. 1066, 1984, pp. 122-141.

[18] L. Grippo and S. Lucidi, “A Globally Convergent Version of the Polak-RibiÈRe Gradient Method,” Mathematical Programming, Vol. 78, No. 3, 1997, pp. 375-391.

[19] W. W. Hager and H. Zhang, “A New Conjugate Gradient Method with Guaranteed Descent and an Efficient Line Search,” SIAM Journal on Optimization, Vol. 16, No. 1, 2005, pp. 170-192.

[20] Z. Wei, S. Yao, and L. Liu, “The Convergence Properties of Some New Conjugate Gradient Methods,” Applied Mathematics and Computation, Vol. 183, No. 2, 2006, pp. 1341-1350.

[21] G. H. Yu, “Nonlinear Self-Scaling Conjugate Gradient Methods for Large-scale Optimization Problems,” Thesis of Doctor's Degree, Sun Yat-Sen University, 2007.

[22] G. Yuan, “Modified Nonlinear Conjugate Gradient Methods with Sufficient Descent Property for Large-Scale Optimization Problems,” Optimization Letters, Vol. 3, No. 1, 2009, pp. 11-21.

[23] G. Yuan, “A Conjugate Gradient Method for Uncons- trained Optimization Problems,” International Journal of Mathematics and Mathematical Sciences, Vol. 2009, 2009, pp. 1-14.

[24] G. Yuan, X. Lu, and Z. Wei, “A Conjugate Gradient Method with Descent Direction for Unconstrained Optimi- zation,” Journal of Computational and Applied Mathe- matics, Vol. 233, No. 2, 2009, pp. 519-530.

[25] L. Zhang, W. Zhou, and D. Li, “A Descent Modified Polak-RibiÈRe-Polyak Conjugate Method and its Global Convergence,” IMA Journal on Numerical Analysis, Vol. 26, No. 4, 2006, pp. 629-649.

[26] Y. Liu and C. Storey, “Efficient Generalized Conjugate Gradient Algorithms, Part 1: Theory,” Journal of Optimi- zation Theory and Application, Vol. 69, No. 1, 1992, pp. 17-41.

[27] Z. J. Shi, “Convergence of Line Search Methods for Unconstrained Optimization,” Applied Mathematics and Computation, Vol. 157, No. 2, 2004, pp. 393-405.

[28] J. J. Moré, B. S. Garbow, and K. E. Hillstrome, “Testing Unconstrained Optimization Software,” ACM Transac- tions on Mathematical Software, Vol. 7, No. 1, 1981, pp. 17-41.

[29] E. D. Dolan and J. J. Moré, “Benchmarking Optimization Software with Performance Profiles,” Mathematical Programming, Vol. 91, No. 2, 2002, pp. 201-213.

[30] Y. Dai and Q. Ni, “Testing Different Conjugate Gradient Methods for Large-scale Unconstrained Optimization,” Journal of Computational Mathematics, Vol. 21, No. 3, 2003, pp. 311-320.