Introduction

In the following, we primarily work with functions \( f:\mathbb{R}^2 \to \mathbb{R}\). For user provided functions, finite differences are used to compute the gradient and hessian. This means, for a small \(h>0\), we compute \[ \nabla f(x,y) \approx \frac{1}{h} \left( f(x+h,y)-f(x,y), f(x,y+h)-f(x,y) \right)^T \] \[ \nabla^2 f(x,y) \approx \frac{1}{2h} \begin{pmatrix} (\nabla f(x+h,y)- \nabla f(x-h,y))^T \\ (\nabla f(x,y+h)- \nabla f(x,y-h))^T \end{pmatrix} \]

Line Search Descent

The core idea is simple. Starting at some initial point \(p_0\), we iteratively update the point by moving along a descent direction \( \Delta p \): \[ p_k \gets p_{k-1} + t \cdot \Delta p \]. For \(\Delta p\) to be a descent direction, \( \nabla f(p)^T \Delta p \lt 0\) must hold. This is not always the case for the Newton Step \( \Delta p = - \nabla^2 f(p)^{-1} \nabla f(p) \) in which case we fallback to the Gradient Descent \( \Delta p = -\nabla f(p) \)
The step size \(t\) id determined using backtracking line search,
meaning an initial step size \(t_0\) is decreased (\( t_k \gets \tau \cdot t_{k-1} \) with \(\tau \in (0,1)\)) until the function value is sufficiently smaller. To that end, we check the Armijo Condition \[ f(p + t \Delta p) \leq f(p) + t \alpha \nabla f(p)^T \Delta p \] with a damping coefficient \( \alpha \in (0,1) \)
The algorithm stops, when \( \lambda^2 = - \nabla f(p)^T \Delta p \leq 2 \epsilon \).
An interesting example to compare the Newton Step vs. Gradient Descent is the function \( f(x,y)=x^2 + 10y^2 \).

Click anywhere to start the Line Search.

TBA

What is this?