Line Search Methods

Resources: Nocedal-Wright2006_Book_NumericalOptimization.pdf Ch 3-3.1, 3.4, 3.5

---

Each iteration of a line search method computes a search direction $p_k$ and then decides how far to move along that direction. The iteration is given by

$$x_{k+1}=x_k+{\alpha }_k{p}_k$$

Where $\alpha$ is the Step Length, and the search direction $p_k$ is given by

$$p_k=-B_k^{-1}\nabla f_k$$

---

$B_k$ is different depending on which method we use

• Steepest Descent - $B_k=\mathbb{I}$
• Newton Direction - $B_k={\nabla }^{2}f(x_k)$
• Quasi-Newton - $B_k\approx {\nabla }^{2}f(x_k)$

Which means that that when $p_k$ is defined by the equation above and $B_k$ is a Positive-Definite Matrix, we have

$$p_k^T\nabla f_k=-\nabla f_k^T{B}_k^{-1}\nabla f_k<0$$

Therefore $p_k$ is a descent direction.