Convex Optimization 2026, 38 - Newton's Method

For x ∈ dom f the vector Δx_nt = -∇²f(x)^-1∇f(x) is the Newton step. Positive definiteness of the second derivative implies that ∇f(x)^TΔx_{nt < 0}, if the derivative exists, which qualifies the Newton step as a descent direction. The second-order Taylor approximation of f at x is a convex quadratic function of the deviation, and is minimized when this deviation is set equal to the Newton step (p. 485). The Newton step is the steepest descent direction at x for the quadratic norm defined by the Hessian. This indicates that the Newton step is a good search direction. The optimality condition ∇f(x^*) = 0 can be linearized to ∇f(x + v) ≈ ∇f(x) + ∇²f(x)v = 0, which is linear in v and is solved by setting the deviation to the Newton step. The Newton step is an affine quantity (p. 486). The Newton decrement at x is defined as λ(x) = (∇f(x)^T∇²f(x)^-1f(x))^1/2, which can function as a stopping criterion by relating λ(x) = (Δx_nt^T∇²f(x)Δx_nt)^1/2 (Eq. 9.29). It also shows up in backtracking line search as ∇f(x)^TΔx_nt = -λ(x)² (Eq. 9.30). These are used to define Newton's method (Algorithm 9.5):

• Compute Newton step and decrement
• Stopping criterion: λ²/2 ≤ ϵ
• Set step size t by backtracking line search
• Update x = x + tΔx_nt

If f is twice continuously differentiable and strongly convex with constant m, it implies that ∃M > 0: ∇²f(x) ⪯ MI ∀ x ∈ S. If the Hessian is also Lipschitz-continuous on S with constant L, then L can be interpreted as a bound on the third derivative of f. Given a small L, Newton's method is expected to work well on f.