Further analysis and extension of the higher-order Newton method of Ahmadi, Chaudhry, and Zhang
Abstract
We extend a dth-order Newton method for unconstrained optimization by Ahmadi, Chaudhry, and Zhang [Advances in Mathematics, 452:109808] to optimization with SOS-convex polynomial constraints. Consider the problem of minimizing a smooth function f:ℝn→ℝ subject to SOS-convex polynomial constraints. Given an iterate x∈ℝn, Ahmadi et al. define the next iterate x+ as the minimizer of the dth-order Taylor expansion of f at x with a regularization term of degree d′, where d′ is the smallest even number greater than d, chosen such that this polynomial is SOS-convex, subject to the constraints. Constructing this polynomial and minimizing it subject to the constraints can both be reduced in time polynomial in n to a semidefinite program (SDP). We prove that, if f is strongly convex and the tensor of the dth-order partial derivatives of f is Lipschitz continuous, then our method converges locally to the optimal solution x∗ with order d. We further prove that, under certain constraint qualifications, the set of active constraints at x∗ is identified locally in a single iteration. Next, we study the worst-case performance of the third-order Newton method in the unconstrained setting for two classes of univariate f using performance estimation. Finally, we extend a globally convergent modification of the dth-order Newton method to the setting of SOS-convex polynomial constraints.
Related
- Convergence of a Randomized Newton Method in Nonconvex Optimization
- Acceleration of Newton's method for nonlinear algebraic systems by preflattening and elimination techniques
- A Lagrange-Newton method for solving optimal control problems on manifolds
- Mixed precision Newton's method for optimization
- A globally convergent stochastic semismooth Newton method for strongly convex problems in Hilbert spaces
BibTeX
@misc{voert2026further,
title = {{Further analysis and extension of the higher-order Newton method of Ahmadi, Chaudhry, and Zhang}},
author = {Lucas ter Voert and Etienne de Klerk},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01001},
eprint = {2609.01001},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01001},
}
RIS
TY - UNPB
TI - Further analysis and extension of the higher-order Newton method of Ahmadi, Chaudhry, and Zhang
AU - Lucas ter Voert
AU - Etienne de Klerk
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.01001
UR - https://arxiv.org/abs/2609.01001
AB - We extend a dth-order Newton method for unconstrained optimization by Ahmadi, Chaudhry, and Zhang [Advances in Mathematics, 452:109808] to optimization with SOS-convex polynomial constraints. Consider the problem of minimizing a smooth function f:ℝ^n→ℝ subject to SOS-convex polynomial constraints. Given an iterate x∈ℝ^n, Ahmadi et al. define the next iterate x^+ as the minimizer of the dth-order Taylor expansion of f at x with a regularization term of degree d^′, where d^′ is the smallest even number greater than d, chosen such that this polynomial is SOS-convex, subject to the constraints. Constructing this polynomial and minimizing it subject to the constraints can both be reduced in time polynomial in n to a semidefinite program (SDP). We prove that, if f is strongly convex and the tensor of the dth-order partial derivatives of f is Lipschitz continuous, then our method converges locally to the optimal solution x^∗ with order d. We further prove that, under certain constraint qualifications, the set of active constraints at x^∗ is identified locally in a single iteration. Next, we study the worst-case performance of the third-order Newton method in the unconstrained setting for two classes of univariate f using performance estimation. Finally, we extend a globally convergent modification of the dth-order Newton method to the setting of SOS-convex polynomial constraints.
ER -