Paperlane

no. 14 · Friday 13 November 2026

A Sequential Cubic Programming Method with Second-Order Complexity Guarantees for Equality Constrained Optimization

Nikos Dimou and Michael J. O'Neill

math.OC · v2 · 49 pp

Abstract

We develop a new method for equality constrained optimization problems based on a sequential cubic programming framework. Each iteration utilizes a step decomposition based on the Jacobian of the constraints into a normal and a tangential component, the latter of which is found by solving a subproblem involving cubic regularization. The method incorporates second-order correction steps as necessary to ensure global convergence to second-order stationary points as well as local quadratic convergence. In addition, we show that the algorithm is the first to obtain worst case complexity guarantees on the order of $\mathcal{O}(ε_g^{-3/2})$ for the gradient of the Lagrangian, $\mathcal{O}(ε_H^{-3})$ in terms of second-order stationarity, and $\mathcal{O}(ε_c^{-1})$ in terms of the constraint violation. These are the best known complexity guarantees of any method for this class of problems.

comments
49 pages; Appendix C added
fields
Optimization and Control
pdf ↗ page arXiv:2604.02747 ↗