Taylor approximations and one Newton step

The idea

Near a point, a smooth function looks like a straight line (first order) and, more accurately, like a parabola (second order). Newton’s method for minimising replaces the function by that parabola, jumps to the bottom of the parabola, and repeats. Near the answer each step roughly squares the error.

The math, with a comment on each formula

f(x + h) \approx f(x) + f'(x)\,h In words: the tangent line; good for small steps h.

f(x + h) \approx f(x) + f'(x)\,h + \tfrac{1}{2} f''(x)\,h^2 In words: the tangent parabola, which also follows the bending of the graph.

h = -\frac{f'(x)}{f''(x)}, \qquad x_{\text{new}} = x - \frac{f'(x)}{f''(x)} \qquad (f''(x) > 0) In words: set the parabola’s slope f'(x) + f''(x)h to zero; the step is the slope divided by the curvature, taken downhill.

Worked example

First the line. With g(x) = \sqrt{x} at x = 4: g(4 + 0.1) \approx g(4) + g'(4)(0.1) = \frac{81}{40} = 2.025, while the true value is about 2.02485 (rounded to 5 decimals).

Now Newton. Minimise f(x) = x - \ln x for x > 0: f'(x) = 1 - \frac{1}{x} and f''(x) = \frac{1}{x^{2}} > 0, so f is convex and its minimum is where f' = 0, at x = 1. The Newton update simplifies to x_{\text{new}} = - x \left(x - 2\right). Starting from x_0 = \tfrac12: x_1 = \frac{3}{4}, \qquad x_2 = \frac{15}{16}, \qquad x_3 = \frac{255}{256} . In words: the distances to the answer are \frac{1}{2}, \frac{1}{4}, \frac{1}{16}, \frac{1}{256}; each is the square of the one before (quadratic convergence).

The kernel finds the same minimum:

minimize x - log(x)
subject to
x >= 0
# log needs x > 0; the bound tells the kernel so

with x = 1 and value 1 (status optimal).

Why it matters for optimization

Interior-point solvers such as Clarabel, one of the solvers ProvenDecisions uses, take Newton steps on the optimality conditions of the problem (kept away from the boundary), which is why they close in fast near the answer. In several variables f' becomes the gradient, f'' the Hessian, and the step solves a linear system. The linear approximation is also why a shadow price predicts the effect of a small change but not of a large one.