Third-Order Newton Methods with Semidefinite Programming

Abstract

We study a third-order Newton method in which each iteration is obtained by minimizing the third-order Taylor expansion of the objective via a semidefinite programming (SDP) subproblem. In contrast to classical Newton methods, which rely on quadratic approximations, our approach leverages higher-order information to better capture the local geometry of the objective. We establish cubic convergence under standard assumptions, including strong convexity and sufficiently accurate initialization. We also propose practical modifications to address infeasibility of the SDP subproblem, including regularization and alternative objective formulations.

arXiv comment27 pages, 10 figures