Line search algorithms with guaranteed sufficient decrease

ABSTRACT

The development of software for minimization problems is often based on a line search method. We consider line search methods that satisfy sufficient decrease and curvature conditions, and formulate the problem of determining a point that satisfies these two conditions in terms of finding a point in a set T(&mgr;). We describe a search algorithm for this problem that produces a sequence of iterates that converge to a point in T(&mgr;) and that, except for pathological cases, terminates in a finite number of steps. Numerical results for an implementation of the search algorithm on a set of test functions show that the algorithm terminates within a small number of iterations.

REFERENCES

• 1: AL-BAALI, M. 1985. Descent property and global convergence of the Fletcher-Reeves method with inexact line searches. IMA J. Namer. Anal. 5, 121-124.
• 2: M Al-Baali , R Fletcher, An efficient line search for nonlinear least squares, Journal of Optimization Theory and Applications, v.48 n.3, p.359-377, March 1986 [doi>10.1007/BF00940566]
• 3: BYRD, R. H., NOCEDAL, J., AND YUAN, Y. 1987. Global convergence of a class of quasi-Newton methods on convex problems. SIAM J. Numer. Anal. 24, 1171-1190.
• 4: DE~, J. E., A~D SCm~AB~L, R. E. 1983. N~rner~cal Method~ for Unconstrained Optimization and Nonhnear Equations. Prentice-Hall, Englewood Cliffs, N.J.
• 5: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 6: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 7: GILBERT, J. C., AND NOCEDAL, J. 1992. Global convergence properties of conjugate gradient methods for optimization. SIAM J. Optim. 2, 21-42.
• 8: G~LL, P. E., ANn MURKY, W. 1974. Safeguarded steplength algorithms for optimization using descent methods. Rep. NAC 37, National Physical Laboratory, Teddington, England.
• 9: GILL, P. E., MURRAY, W., SAUNVERS, M. A., AND WRIGHT, M. H. 1979. Two steplength algorithms for numerical optimization. Rep. SOL 79-25, Systems Optimization Laboratory, Stanford Univ., Stanford, Calif.
• 10: HAGER, W. W. 1989. A derivative-based bracketing scheme for univariate minimization and the conjugate gradient method. Comput. Math. Appl. 18, 779-795.
• 11: LEMARECnAL, C. 1981. A view of line-searches. In Optimization and Optimal Control, A. Auslender, W. Oettli, and J. Stoer, Eds. Lecture Notes in Control and Information Science, vol. 30. Springer-Verlag, Heidelberg, 59 78.
• 12: D. C. Liu , J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical Programming: Series A and B, v.45 n.3, p.503-528, Dec. 1989 [doi>10.1007/BF01589116]
• 13: MOR~, J. J., AND SORENSEN, D. C. 1984. Newton's method. In Studies in Numerical Analysis, G. H. Golub, Ed. Mathematical Association of America, Washington, D.C., 29 82.
• 14: Dianne P. O'Leary, Robust regression computation computation using iteratively reweighted least squares, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.466-480, Jul. 1990 [doi>10.1137/0611032]
• 15: POWELL, M. J. D. 1976. Some global convergence properties of a variable metric method without line searches. In Nonlinear Programming, R. W. Cottie and C. E. Lemke, Eds. SIAM-AMS Proceedings, vol. IX. American Mathematical Society, Providence, R.I., 53-72.
• 16: Tamar Schlick , Aaron Fogelson, TNPACK—A truncated Newton minimization package for large-scale problems: I. Algorithm and usage, ACM Transactions on Mathematical Software (TOMS), v.18 n.1, p.46-70, March 1992 [doi>10.1145/128745.150973]
• 17: Tamar Schlick , Aaron Fogelson, TNPACK—a truncated Newton minimization package for large-scale problems: II. Implementation examples, ACM Transactions on Mathematical Software (TOMS), v.18 n.1, p.71-111, March 1992 [doi>10.1145/128745.150975]
• 18: D. F. Shanno , K. H. Phua, Algorithm 500: Minimization of Unconstrained Multivariate Functions [E4], ACM Transactions on Mathematical Software (TOMS), v.2 n.1, p.87-94, March 1976 [doi>10.1145/355666.355673]
• 19: SH~NO, D. F., ~D PHVA, K. H. 1980. Remark on Algorithm 500. ACM Trans. Math. Softw. 6, 618-622.
• 20: YANAL H., OZAWA, M., AND KANEKO, S. 1981. Interpolation methods in one dimensional optimization. Computing 27, 155-163.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming
      G.1.7 Ordinary Differential Equations
          Subjects: Convergence and stability
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Reliability and robustness; Algorithm design and analysis; Efficiency

General Terms:
Algorithms, Performance

Keywords:
conjugate gradient algorithms, line search algorithms, nonlinear optimization, truncated Newton algorithms, variable metric algorithms