Newton Method and Quasi Newton Method

机器学习

---

Newton Method

Considering unconstrainted optimization problem

$$\min_{x\in \mathbf R^n} f(x)$$
where $x^*$ is the minimum of objective function.

Assuming $f(x)$ is twice differentiable, and $x^{(k)}$ is value of $x$ in $k$-th iteration, the taylor expansion of $f(x^{(k)})$ is

$$f(x) = f(x^{(k)}) + g_k^T(x - x^{(k)}) + \frac 1 2 (x - x^{(k)})^T H(x^{(k)}) (x - x^{(k)})$$
where $g^k = g(x^{(k)}) = \nabla f(x^{(k)})$, and $H(x^{(k)})$ is Hesse matrix of $f(x)$
$$H(x) = \left[ \frac{\partial^2 f}{\partial x_i \partial x_j} \right]_{n \times n}$$

Algorithm

Input: objective function $f(x)$, gradient $g(x) = \nabla f(x)$, Hesse matrix $H(x)$;
Output: minimum $x^*$.

1. Pick init point $x^{(0)}$, set $k = 0$.
2. Calculate $g_k = g(x^{(k)})$.
3. Stop if $\| g_k \| \lt \epsilon$, let $x^* = x^{(k)}$.
4. Calculate $H_k = H(x^{(k)})$ and $p_k$
   $$H_k p_k = -g_k$$
5. Set $x^{(k+1)} = x^{(k)} + p_k$.
6. Set $k = k + 1$, goto step (2).

Quasi Newton Method

Calculating $H^{-1}$ is rather expensive. Quasi newton method approximates $H_k^{-1}$ with $G_k = G(x^{(k)})$.

In newton method, we have

$$g_{k+1} - g_k = H_k(x^{(k+1)} - x^{(k)})$$
Let $y_k = g_{k+1} - g_k$ and $\delta_k = x^{(k+1)} - x^{(k)}$,
$$y_k = H_k \delta_k$$
The equation above are called quasi newton condition. Algorithms picking $G_k$ approximating $H_k^{-1}$ or $B_k$ approximating $H_k$ are called quasi newton method.

BFGS

Approxiamate $H$ with

$$B_{k+1} = B_k + \frac{y_k y_k^T}{y_k^T \delta_k} - \frac{B_k \delta_k \delta_k^T B_k}{\delta_k^T B_k \delta_k}$$
where $y_k = g_{k+1} - g_k$ and $\delta_k = x^{(k+1)} - x^{(k)}$.

Algorithm

Input: objective function $f(x)$, $g(x) = \nabla f(x)$, precision $\epsilon$;
Output: minimum $x^*$ of $f(x)$.

1. Pick init point $x^{(0)}$, positive-definite matrix $B_0$, $k=0$.
2. Calculate $g_k = g(x^{(k)})$, stop if $\| g_k \| \lt \epsilon$, let $x^* = x^{(k)}$.
3. Calculate $p_k$ with $B_k p_k = -g_k$.
4. 1D search:
   $$f(x^{(k)} + \lambda_k p_k) = \min_{\lambda \ge 0} f(x^{(k)} + \lambda p_k)$$
5. Let $x^{(k+1)} = x^{(k)} + \lambda_k p_k$.
6. Calculate $B_{k+1}$:
   $$B_{k+1} = B_k + \frac{y_k y_k^T}{y_k^T \delta_k} - \frac{B_k \delta_k \delta_k^T B_k}{\delta_k^T B_k \delta_k}$$
7. Set $k = k + 1$, goto step (2).