Houjun Liu

Newton's Method

\begin{equation} f(x) \approx f(x_{t-1}) + (x-x_{t-1}) f’(x_{t-1}) + \frac{(x-x_{t-1})^{2}}{2} f’’(x_{t-1}) \end{equation}

Taking a derivative with respect to this, we obtain:

\begin{equation} f’(x_{t-1}) + (x-x_{t-1}) f’’(x_{t-1}) \end{equation}

Solving the update equation for zero, we obtain that:

\begin{equation} x = x_{t-1} - \frac{f’(x_{t-1})}{f’’(x_{t-1})} \end{equation}

This converges quadratically!!

For gradients:

\begin{equation} x_{t} = x_{t-1} - \qty(\bold{H}_{g})^{-1}\bold{g}_{k} \end{equation}

Failure Case

If the function is near an inflection point (i.e. with bad quadratic approximation), you may converge at a point which doesn’t satisfy SONC (i.e. you will get an inflection but not a minima).