Let's say we want to use Newton's method to find optimal $x_*$ for $f:\mathbb{R}^n \to \mathbb{R}$ , with
$x_{t+1} = x_t + H_f(x_t)^{-1}\nabla f(x_t) $
Can $H_f(x_t)^{-1}$ be calculated only once and used in every iteration step, or do we need to calculate it every time?
Does equation $H_f(x_0)(x_*-x_0) = \nabla f(x_0)$ need to be calculated only once to recieve optimal value?
Best Answer
"Can $H_f(x_t)^{−1}$ be calculated only once and used in every iteration step, or do we need to calculate it every time?"
No, the equation $$ H_f(x_t)(x_{t+1} - x_t) = - \nabla f(x_t) $$ needs to be solved at every iteration. This is the reason every iteration in Newton's method is costly compared to other methods with slower convergence. The exception is the quadratic problem $$ \min f(x) , \quad f(x) = \frac{1}{2}x^T A x + b^T x $$ with $\nabla f(x) = A x + b$ and $H_f(x) = A$. This problem is exactly solved by one step of Newton's. $$ \begin{align} A(x_1 - x_0) &= - A x_0 - b \\ x_1 &= -A^{-1}b \end{align} $$ for which we see that $\nabla f(x_1) = 0$. Provided that $A$ is positive semidefinite this is a solution to $\min f(x)$.