Line search methods

Authors: Lihe Cao, Zhengyi Sui, Jiaqi Zhang, Yuqing Yan, and Yuhui Gu (6800 Fall 2021).

Introduction

When solving unconstrained optimization problems, the user need to supply a starting point for all algorithms. With the initial starting point, $x_{0}$, optimization algorithms generate a sequence of iterates $\{x_{k}\}_{k=0}^{\infty }$ which terminates when an approximated solution has been achieved or no more progress can be made. Line Search is one of the two fundamental strategies for locating the new $x_{k+1}$ given the current point.

Exact Search

Steepest Descent Method

Given the intuition that the negative gradient $-\nabla f_{k}$ can be an effective search direction, steepest descent follows the idea and establishes a systematic method for minimizing the objective function. Setting $-\nabla f_{k}$ as the direction, steepest descent computes the step-length $\alpha ^{k}$ by minimizing a single-variable objective function. More specifically, the steps of Steepest Descent Method are as follows.

PSEUDOCODE HERE

One advantage of the steepest descent method is that it has a nice convergence theory. For a steepest descent method, it converges to a local minimal from any starting point.

Theorem: global convergence of steepest descent Let the gradient of $f\in C^{1}$ be uniformly Lipschitz continuous on $R^{n}$. Then, for the iterates with steepest-descent search directions, one of the following situations occurs:

• $\nabla f(x_{k})=0$ for some finite $k$
• $\lim _{k\to \infty }f(x_{k})=-\infty$
• $\lim _{k\to \infty }\nabla f(x_{k})=0$

Steepest descent method is a special case of gradient descent in that the step-length is rigorously defined. Generalization can be made regarding the choice of $\alpha$.