Paper ID sheet UCL-INMA-2008.011


Accelerated line-search and trust-region methods

P.-A. Absil, K. A. Gallivan
In numerical optimization, line-search and trust-region methods are two important classes of descent schemes, with well-understood global convergence properties. Here we consider ``accelerated'' versions of these methods, where the conventional iterate is allowed to be replaced by any point that produces at least as much decrease in the cost function as a fixed fraction of the decrease produced by the conventional iterate. A detailed convergence analysis reveals that global convergence properties of line-search and trust-region methods still hold when the methods are accelerated. The analysis is performed in the general context of optimization on manifolds, of which optimization in $\mathbb{R}^n$ is a particular case. This general convergence analysis sheds a new light on the behavior of several existing algorithms.
Key words
line search; trust region; subspace acceleration; sequential subspace method; Riemannian manifold; optimization on manifolds; Riemannian optimization; Arnoldi; Jacobi-Davidson; LOBPCG
SIAM Journal on Numerical Analysis, Vol. 47, No. 2, pp. 997-1018, 2009
BibTeX entry

  author = "P.-A. Absil and K. A. Gallivan",
  title = "Accelerated line-search and trust-region methods",
  journal = "SIAM J. Numer. Anal.",
  fjournal = "SIAM Journal on Numerical Analysis",
  volume = 47,
  number = 2,
  year = 2009,
  pages = "997--1018",