Introduction to Newton's Method

Newton's Method is an iterative algorithm for minimizing a function. It belongs to the class of line search methods. Before discussing Newton’s Method in detail, it is useful to understand the general idea behind line search methods.

The Idea Behind Line Search Methods

Line search methods are iterative algorithms used to find local minima of a function. The central idea is simple: at each iteration, we choose a search direction and a step size, and then move along that direction so that the function value decreases.

Mathematically, this update is written as

$$x_{k+1} = x_k + \alpha_k p_k,$$

where $\alpha_k$ is the step size at iteration $k$, and $p_k$ is the search direction (also called the descent direction) at iteration $k$. The step size and search direction must be chosen such that the value of the function $f$ decreases at the new point $x_{k+1}$.

All line search methods follow this same basic framework; they differ primarily in how the search direction $p_k$ is chosen.

A familiar example of a line search method is the gradient descent algorithm. In gradient descent, the search direction is taken to be the negative gradient of the function:

$$x_{k+1} = x_k - \alpha_k \nabla f(x_k).$$

Before moving on to the next section, it is important to remember that line search methods help us find a local minimum, and not necessarily the global minimum.

---

Newton's Method

If you observe, gradient descent uses only the first derivative of the function $f$. Newton’s method, on the other hand, leverages second-order information as well.

If a function $f : \mathrm{R}^n \to \mathrm{R}$ is twice differentiable in an open neighbourhood of a point $x$, then the second derivative, or the Hessian, of $f$ at $x$ is given by

$$\nabla^2 f(x) = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2}(x) & \frac{\partial^2 f}{\partial x_1 \partial x_2}(x) & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n}(x) \\[4pt] \frac{\partial^2 f}{\partial x_2 \partial x_1}(x) & \frac{\partial^2 f}{\partial x_2^2}(x) & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n}(x) \\[4pt] \vdots & \vdots & \ddots & \vdots \\[4pt] \frac{\partial^2 f}{\partial x_n \partial x_1}(x) & \frac{\partial^2 f}{\partial x_n \partial x_2}(x) & \cdots & \frac{\partial^2 f}{\partial x_n^2}(x) \end{bmatrix}.$$

Geometrically, $\nabla^2 f(x)$ represents the curvature of the function at $x$.

Alright, let's understand Newton's method from first principles.

At iteration $k$, we are at the point $x_k$, and we want to move to a new point $x_k + \alpha_k p_k$ such that the value of the function $f$ decreases. We assume that the step size $\alpha_k$ is fixed and sufficiently small. Furthermore, we assume that $f$ is twice differentiable in an open neighbourhood of $x_k$. Under these assumptions, we can take the second-order Taylor series approximation of $f$ around $x_k$:

$$f(x_k + \alpha_k p_k) \approx f(x_k) + \alpha_k \cdot \nabla f(x_k)^T p_k + \frac{1}{2} \alpha_k^2 \cdot p_k^T \nabla^2 f(x_k) p_k.$$

Since $\alpha_k$ is fixed, our goal is to find a search direction $p_k$ along which the function decreases.

Here's the big idea: instead of minimizing $f$ directly, we minimize its second-order approximation. We find the optimal $p_k$ by taking the gradient of the approximation with respect to $p_k$ and setting it equal to zero:

$$\begin{align*} \nabla_{p_k} \left( f(x_k) + \alpha_k \cdot \nabla f(x_k)^T p_k + \frac{1}{2} \cdot \alpha_k^2 \cdot p_k^T \nabla^2 f(x_k) p_k \right) = 0 \\[4pt] \implies \nabla_{p_k} \left( f(x_k) \right) + \nabla_{p_k} \left( \alpha_k \cdot \nabla f(x_k)^T p_k \right) + \nabla_{p_k} \left( \frac{1}{2} \cdot \alpha_k^2 \cdot p_k^T \nabla^2 f(x_k) p_k \right) = 0 \\[4pt] \implies \alpha_k \cdot \nabla_{p_k} \left( \nabla f(x_k)^T p_k \right) + \frac{\alpha_k^2}{2} \cdot \nabla_{p_k} \left( p_k^T \nabla^2 f(x_k) p_k \right) = 0 \end{align*}$$

Using standard identities from matrix calculus, we have

$$\nabla_{p_k} \left( \nabla f(x_k)^T p_k \right) = \nabla f(x_k),$$

and, since the Hessian $\nabla^2 f(x_k)$ is symmetric, we have

$$\nabla_{p_k} \left( p_k^T \nabla^2 f(x_k) p_k \right) = 2\nabla^2 f(x_k) p_k,$$

Substituting these into the expression above yields

$$\alpha_k \cdot \nabla f(x_k) + \alpha_k^2 \cdot \nabla^2 f(x_k) p_k = 0$$

Assuming that the Hessian $\nabla^2 f(x_k)$ is invertible (we will revisit this assumption later), we can solve for $p_k$:

$$p_k = - \frac{1}{\alpha_k} \left[ \nabla^2 f(x_k) \right]^{-1} \nabla f(x_k).$$

Since $p_k$ is a search direction, scaling by a positive constant does not affect its direction. We therefore drop the constant factor and obtain the Newton direction:

$$p_k = - \left[ \nabla^2 f(x_k) \right]^{-1} \nabla f(x_k).$$

We now check whether $p_k$ is a legitimate descent direction. A legitimate descent direction is one that makes an acute angle with the direction of steepest descent, which is $-\nabla f(x_k)$.

Mathematically, $p_k$ is a legitimate descent direction if

$$\begin{align*} 0 &< \left( - \nabla f(x_k) \right)^T p_k \\[4pt] &= \left( \nabla f(x_k) \right)^T \left[ \nabla^2 f(x_k) \right]^{-1} \nabla f(x_k). \end{align*}$$

The above expression is of the form

$$x^T A x,$$

which is strictly positive for all non-zero $x$ if $A$ is positive definite. Therefore, the Newton direction is a legitimate descent direction if the matrix

$$\left[ \nabla^2 f(x_k) \right]^{-1}$$

is positive definite.

Addressing the Assumptions

At the beginning, we made a subtle assumption: we assumed that $p_k$ minimizes the second-order approximation of $f$ when the gradient of the approximation with respect to $p_k$ is zero. This is true only when the quadratic approximation is a convex function, which occurs when the Hessian $\nabla^2 f(x_k)$ is positive definite.

All eigenvalues of a positive definite matrix are strictly positive. This implies that a positive definite matrix is invertible, since a non-invertible matrix must have at least one eigenvalue equal to zero. Moreover, because the eigenvalues of the inverse of a matrix are the reciprocals of the eigenvalues of the original matrix, the inverse of a positive definite matrix is also positive definite.

Therefore, if the Hessian $\nabla^2 f(x_k)$ is positive definite, all the assumptions made in the above derivation are satisfied, and the Newton direction is well-defined and guarantees a decrease in the function value at the new point.

Note that these assumptions can also be satisfied even when $\nabla^2 f(x_k)$ is not positive definite. However, when $\nabla^2 f(x_k)$ is positive definite, the assumptions are guaranteed to hold.

---

Conclusion

Gradient descent minimizes the function iteratively, whereas Newton’s method directly targets the minimum of a local quadratic approximation in each step. This allows Newton’s method to converge faster than gradient descent. However, Newton’s method assumes that the function is locally twice differentiable and that its Hessian is positive definite. This limits its applicability in practice.

Moreover, since the Hessian must be computed (and often inverted) at every iteration, Newton’s method is computationally expensive. To address these issues, several modified approaches, such as Quasi-Newton methods, have been developed.

I hope you enjoyed this article. We derived Newton’s method from first principles and discussed its advantages and limitations. We did not, however, explore its rate of convergence or its various modifications. I hope to discuss them in the future.