300 Years Later, Newton's Method gets an Update

Jeffrey Zhang, Yale BIDS

Joint work with Amir Ali Ahmadi, Abraar Chaudry

AAMU-UAH Joint Seminar, 4/18/2025

Newton’s Method

Newton’s method is an iterative optimization function that minimizes the second order Taylor expansion in each iteration

The Newton iterate

Convergence of Newton’s Method

• Classical result in optimization: Newton’s method has quadratic convergence
• Formally,

​

Newton’s method doesn’t always work!

Functions with S-shaped gradients are difficult for Newton’s method

Higher order information in Newton’s method

Using higher order derivative information can improve Newton’s method by generating closer approximations

​

Empirically, using higher order information can result in faster, more stable algorithms

Why haven’t we done this?

Optimizing high degree polynomials is hard!

• Implementing these methods requires optimizing higher degree polynomials

​

• Informal theorem: Most optimization problems are NP-hard at degree 4 at the least

Some NP-hard problems:

• Globally minimizing a polynomial of degree 4
• Locally minimizing a polynomial of degree 4
• Finding a second-order point of a polynomial of degree 4
• Finding a critical point of a polynomial of degree 3

A bridge to higher-order methods

If there were algorithms to minimize the high degree approximations, then they would immediately yield higher order Newton methods

​

Example: a third-order Newton method is possible!

A different higher order method

Outline

• An Introduction to Sums of Squares

​

• Convergence of Higher Order Newton Methods

​

• Numerical Examples

Sums of Squares

Sum of Squares and Polynomial Optimization

• Sum of squares relaxations enable finding lower bounds for polynomial optimization problems

sos

• There are extensions for constrained optimization, but they won’t be needed here

Sum of Squares Convexity

SoS Convex Polynomials and SoS Relaxations

• Key theorem (by Lasserre):

POP:

1^st order Lasserre relaxation:

• All we need is the unconstrained version

Outline

• An Introduction to Sums of Squares

​

• Convergence of Higher Order Newton Methods

​

• Numerical Examples

Our Newton Algorithm

Main idea: Leverage sos convexity to produce an implementable algorithm

To-do checklist

An SoS-convex approximation exists

A consequence of a more general statement about cones

And it has a unique global minimum

Proof (of lemma) sketch:

1. Use the lemma to lower bound the polynomial by a coercive quadratic function
2. This polynomial must then be coercive, so it has a global minimum
3. If this polynomial has multiple global minima, then it cannot be coercive

Proof: Using a quadrature rule by Clenshaw and Curtis

​

Interpretation: When integrating the Hessian of a function along a line in a region where the function is convex, the lowest eigenvalue can be bounded below based on the endpoints of the integration.

Convergence

Use a “close enough” to a point with a PD Hessian argument

Convergence

Let’s try to generalize where we can

Convergence

Quadrature again!

We can lower bound this using the lemma.

We just got everything we wanted!

Convergence

Convergence

Outline

• An Introduction to Sums of Squares

​

• Convergence of Higher Order Newton Methods

​

• Numerical Examples

The univariate setting

Example 1

(strictly convex)

Example 2

(strongly convex)

Example 3

The Beale function (nonconvex)

An addendum: global convergence

• Recall the convex regularized framework, which was globally convergent under certain assumptions:

​

​

• Our algorithm chooses the coefficient on the regularizer based on the solution to an SDP
• If we had a guess for the relevant Lipschitz constant, we could choose between the higher of the SDP value and the Lipschitz constant
• Caveat: Slightly different handling when d is even

​

Thank you!

Questions?