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

Michael J. O'Neill; Nikos Dimou

arxiv: 2604.02747 · v1 · submitted 2026-04-03 · 🧮 math.OC

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

Nikos Dimou , Michael J. O'Neill This is my paper

Pith reviewed 2026-05-13 19:26 UTC · model grok-4.3

classification 🧮 math.OC

keywords sequential cubic programmingequality constraintscomplexity analysissecond-order stationaritycubic regularizationnonconvex optimizationglobal convergence

0 comments

The pith

A sequential cubic programming method achieves the best known complexity guarantees for equality constrained optimization problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a new algorithm for solving optimization problems subject to equality constraints. It builds each step by splitting the update into a normal direction that reduces constraint violation and a tangential direction solved via cubic regularization. This structure delivers global convergence to second-order stationary points along with local quadratic convergence. The key advance is the first proof of worst-case iteration bounds scaling as O(ε_g to the power -3/2) for the Lagrangian gradient, O(ε_H to the -3) for second-order measures, and O(ε_c to the -1) for feasibility. These rates improve on all prior methods for nonconvex equality-constrained problems.

Core claim

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 O(ε_g^{-3/2}) for the gradient of the Lagrangian, O(ε_H^{-3}) in terms of second-od

What carries the argument

The decomposition of the step into normal and tangential components using the constraint Jacobian, with the tangential step obtained from a cubic-regularized subproblem.

If this is right

The method converges globally to points satisfying second-order necessary conditions.
Local convergence occurs at a quadratic rate near solutions.
It requires at most O(ε_g^{-3/2}) iterations to make the Lagrangian gradient small.
Constraint violation is reduced to ε_c in O(ε_c^{-1}) iterations.
The second-order stationarity measure reaches ε_H in O(ε_H^{-3}) iterations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The cubic regularization approach may allow easier implementation than trust-region methods in some software environments.
Future work could adapt the framework to problems with inequality constraints.
Practical performance on large-scale problems would depend on efficient solvers for the cubic subproblems.

Load-bearing premise

The cubic regularization subproblems must be solved to sufficient accuracy at every iteration for the complexity bounds to hold.

What would settle it

Constructing or identifying an equality-constrained problem instance on which the algorithm requires more than a constant multiple of ε_g^{-3/2} iterations to reach the target gradient tolerance would falsify the complexity result.

read the original 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}(\epsilon_g^{-3/2})$ for the gradient of the Lagrangian, $\mathcal{O}(\epsilon_H^{-3})$ in terms of second-order stationarity, and $\mathcal{O}(\epsilon_c^{-1})$ in terms of the constraint violation. These are the best known complexity guarantees of any method for this class of problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper delivers the first O(ε_g^{-3/2}) and O(ε_H^{-3}) worst-case complexity bounds for first- and second-order stationarity on equality-constrained problems using a sequential cubic programming approach with normal-tangential decomposition.

read the letter

The main point is that the authors give the first complexity results matching the unconstrained cubic regularization rates for equality-constrained nonlinear programs. They reach O(ε_g^{-3/2}) on the Lagrangian gradient, O(ε_H^{-3}) on second-order stationarity, and O(ε_c^{-1}) on feasibility, and these are presented as the best known for the class. The method works by splitting each step into a normal component that reduces constraint violation and a tangential component solved with cubic regularization, then adding second-order corrections when needed to secure global convergence to second-order points plus local quadratic convergence. Under the usual LICQ, twice-continuous differentiability, and bounded-Hessian assumptions, the analysis carries through without circularity or extra ε dependence, as the stress-test note confirms. The normal-tangential split preserves the standard cubic descent and stationarity arguments. A minor soft spot is the standing assumption that the cubic subproblems can be solved to the required accuracy each outer iteration; this is standard in the literature but shifts the practical cost onto the inner solver, and the paper stays focused on outer-iteration bounds. If numerical tests are included they would be useful for seeing whether the method competes on moderate problems, but the core contribution is the theoretical guarantee. This is for readers who track worst-case analysis in constrained optimization. Anyone working on complexity results for nonlinear programming will get value from the new bounds and the framework. It deserves a serious referee because the claims are sharp, the proof structure holds, and the improvement over prior work is clear. I would send it out for review.

Referee Report

0 major / 3 minor

Summary. The manuscript develops a sequential cubic programming algorithm for equality-constrained nonlinear optimization. Each iteration decomposes the search direction into normal and tangential components using the constraint Jacobian, solves a cubic-regularized subproblem in the tangent space, and applies second-order correction steps when needed. The paper proves global convergence to second-order stationary points, local quadratic convergence, and worst-case complexity bounds of O(ε_g^{-3/2}) on the Lagrangian gradient norm, O(ε_H^{-3}) on the second-order stationarity measure, and O(ε_c^{-1}) on constraint violation, claiming these are the best known for the problem class.

Significance. If the analysis holds, the result is significant because it extends the favorable complexity properties of cubic regularization to the equality-constrained setting while preserving second-order guarantees. The normal-tangential decomposition plus corrections is a technically clean way to recover the O(ε_H^{-3}) rate that matches the best unconstrained cubic methods, and the O(ε_c^{-1}) constraint bound is attractive for feasibility-driven applications. The combination of global convergence, local quadratic rate, and these complexity results strengthens the case for cubic-based methods over first-order or penalty approaches for this problem class.

minor comments (3)

[Abstract] Abstract and §1: the claim that the bounds are 'the best known' would be strengthened by a short explicit comparison table or paragraph citing the rates from the closest prior works (e.g., sequential quadratic programming or augmented Lagrangian cubic methods).
[§3.2] §3.2 and Assumption 3.1: the tolerance to which the tangential cubic subproblem must be solved is stated in terms of the current iterate quantities; it would help to include a short remark confirming that this tolerance is independent of the target ε values and can be achieved by standard cubic solvers.
[Algorithm 1] Figure 1 and Algorithm 1: the flow chart and pseudocode use slightly inconsistent notation for the normal/tangential steps (v_N vs. n_k); harmonizing the symbols would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive evaluation and recommendation of minor revision. The report accurately summarizes the algorithm's normal-tangential decomposition, cubic subproblem, second-order corrections, global convergence to second-order stationary points, local quadratic convergence, and the complexity bounds O(ε_g^{-3/2}), O(ε_H^{-3}), and O(ε_c^{-1}). We appreciate the recognition that these rates match the best known for the equality-constrained setting.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's central claims rest on a novel sequential cubic programming algorithm that decomposes steps into normal and tangential components, solves a cubic-regularized tangential subproblem, and applies second-order corrections as needed. The stated complexity bounds are obtained by standard descent and stationarity arguments applied to this structure under the usual LICQ, twice-continuous differentiability, and bounded-Hessian assumptions; none of the bounds are obtained by fitting parameters to data, by renaming a known result, or by load-bearing self-citation. The analysis is therefore self-contained and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims depend on standard assumptions in nonlinear optimization theory and the ability to solve the proposed subproblems, with no new entities introduced.

axioms (1)

domain assumption Objective and constraint functions are twice continuously differentiable with Lipschitz continuous derivatives.
Required for cubic regularization and second-order analysis in optimization algorithms.

pith-pipeline@v0.9.0 · 5443 in / 1348 out tokens · 45272 ms · 2026-05-13T19:26:57.202626+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

[1]

Bai and S

Y. Bai and S. Mei. Analysis of sequential quadratic programming through the lens of riemannian optimization.arXiv preprint arXiv:1805.08756, 2018

work page arXiv 2018
[2]

Bellavia, D

S. Bellavia, D. Palitta, M. Porcelli, and V. Simoncini. Regularized methods via cubic model subspace minimization for nonconvex optimization.Computational Optimization and Applications, 90(3):801–837, 2025

work page 2025
[3]

A. S. Berahas, F. E. Curtis, D. Robinson, and B. Zhou. Sequential quadratic optimization for nonlinear equality constrained stochastic optimization.SIAM Journal on Optimization, 31(2):1352–1379, 2021

work page 2021
[4]

A. S. Berahas, R. Bollapragada, and J. Shi. Modified line search sequential quadratic methods for equality-constrained optimization with unified global and local convergence guarantees.arXiv preprint arXiv:2406.11144, 2024

work page arXiv 2024
[5]

A. S. Berahas, M. Xie, and B. Zhou. A sequential quadratic programming method with high- probability complexity bounds for nonlinear equality-constrained stochastic optimization. SIAM Journal on Optimization, 35(1):240–269, 2025

work page 2025
[6]

Bertsekas.Network optimization: continuous and discrete models, volume 8

D. Bertsekas.Network optimization: continuous and discrete models, volume 8. Athena Scientific, 1998

work page 1998
[7]

J. T. Betts.Practical methods for optimal control and estimation using nonlinear program- ming. SIAM, 2010

work page 2010
[8]

E. G. Birgin and J. M. Martinez. A newton-like method with mixed factorizations and cubic regularization for unconstrained minimization.Computational Optimization and Ap- plications, 73(3):707–753, 2019

work page 2019
[9]

E. G. Birgin, J. Gardenghi, J. M. Mart´ ınez, S. A. Santos, and P. L. Toint. Evaluation complexity for nonlinear constrained optimization using unscaled kkt conditions and high- order models.SIAM Journal on Optimization, 26(2):951–967, 2016

work page 2016
[10]

L. E. Bourkhissi and I. Necoara. Complexity of linearized quadratic penalty for optimization with nonlinear equality constraints.Journal of Global Optimization, 91(3):483–510, 2025

work page 2025
[11]

R. H. Byrd, R. B. Schnabel, and G. A. Shultz. A trust region algorithm for nonlinearly constrained optimization.SIAM Journal on Numerical Analysis, 24(5):1152–1170, 1987

work page 1987
[12]

Carmon and J

Y. Carmon and J. C. Duchi. Analysis of krylov subspace solutions of regularized non-convex quadratic problems.Advances in Neural Information Processing Systems, 31, 2018

work page 2018
[13]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. Adaptive cubic regularisation methods for uncon- strained optimization. part i: motivation, convergence and numerical results.Mathematical Programming, 127(2):245–295, 2011. 37

work page 2011
[14]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. Adaptive cubic regularisation methods for uncon- strained optimization. part ii: worst-case function-and derivative-evaluation complexity. Mathematical programming, 130(2):295–319, 2011

work page 2011
[15]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming.SIAM Journal on Optimization, 21(4):1721–1739, 2011

work page 2011
[16]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. Complexity bounds for second-order optimality in unconstrained optimization.Journal of Complexity, 28(1):93–108, 2012

work page 2012
[17]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization.SIAM Journal on Optimization, 23(3):1553–1574, 2013

work page 2013
[18]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. On the complexity of finding first-order critical points in constrained nonlinear optimization.Mathematical Programming, 144(1):93–106, 2014

work page 2014
[19]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization.Journal of Complexity, 53:68–94, 2019

work page 2019
[20]

Cartis, N

C. Cartis, N. I. M. Gould, and P. L. Toint. Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled kkt conditions and high-order models. In I. C. Demetriou and P. M. Pardalos, editors,Approximation and Optimization: Algorithms, Complexity and Applications, pages 5–26. Springer International Publishing, Cham, 2019

work page 2019
[21]

F. E. Curtis, D. P. Robinson, and M. Samadi. A trust region algorithm with a worst-case iteration complexity ofO(ϵ −3/2) for nonconvex optimization.Mathematical Programming, 162(1):1–32, 2017

work page 2017
[22]

F. E. Curtis, D. P. Robinson, and M. Samadi. Complexity analysis of a trust funnel algorithm for equality constrained optimization.SIAM Journal on Optimization, 28(2): 1533–1563, 2018

work page 2018
[23]

F. E. Curtis, M. J. O’Neill, and D. P. Robinson. Worst-case complexity of an sqp method for nonlinear equality constrained stochastic optimization.Mathematical Programming, 205 (1):431–483, 2024

work page 2024
[24]

F. E. Curtis, D. P. Robinson, and B. Zhou. Sequential quadratic optimization for stochas- tic optimization with deterministic nonlinear inequality and equality constraints.SIAM Journal on Optimization, 34(4):3592–3622, 2024

work page 2024
[25]

Facchinei, V

F. Facchinei, V. Kungurtsev, L. Lampariello, and G. Scutari. Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and iteration complexity.Mathematics of Operations Research, 46(2):595–627, 2021

work page 2021
[26]

Y. Fang, S. Na, M. W. Mahoney, and M. Kolar. Fully stochastic trust-region sequential quadratic programming for equality-constrained optimization problems.SIAM Journal on Optimization, 34(2):2007–2037, 2024

work page 2007
[27]

Y. Fang, J. Lavaei, and S. Na. High probability complexity bounds of trust-region stochastic sequential quadratic programming with heavy-tailed noise.arXiv preprint arXiv:2503.19091, 2025. 38

work page arXiv 2025
[28]

Fletcher, N

R. Fletcher, N. I. Gould, S. Leyffer, P. L. Toint, and A. W¨ achter. Global convergence of a trust-region sqp-filter algorithm for general nonlinear programming.SIAM Journal on Optimization, 13(3):635–659, 2002

work page 2002
[29]

G. H. Golub, Z. Zhang, and H. Zha. Large sparse symmetric eigenvalue problems with homogeneous linear constraints: the lanczos process with inner–outer iterations.Linear Algebra and its Applications, 309(1-3):289–306, 2000

work page 2000
[30]

N. I. Gould, D. P. Robinson, and H. S. Thorne. On solving trust-region and other regularised subproblems in optimization.Mathematical Programming Computation, 2(1):21–57, 2010

work page 2010
[31]

Goyens, A

F. Goyens, A. Eftekhari, and N. Boumal. Computing second-order points under equality constraints: revisiting fletcher’s augmented lagrangian.Journal of Optimization Theory and Applications, 201(3):1198–1228, 2024

work page 2024
[32]

G. N. Grapiglia and Y.-x. Yuan. On the complexity of an augmented lagrangian method for nonconvex optimization.IMA Journal of Numerical Analysis, 41(2):1546–1568, 2021

work page 2021
[33]

C. He, Z. Lu, and T. K. Pong. A newton-cg based augmented lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees.SIAM Journal on Optimization, 33(3):1734–1766, 2023

work page 2023
[34]

Hinze, R

M. Hinze, R. Pinnau, M. Ulbrich, and S. Ulbrich.Optimization with PDE constraints, volume 23. Springer Science & Business Media, 2008

work page 2008
[35]

X. Jia, X. Liang, C. Shen, and L.-H. Zhang. Solving the cubic regularization model by a nested restarting lanczos method.SIAM Journal on Matrix Analysis and Applications, 43 (2):812–839, 2022

work page 2022
[36]

F. Lieder. Solving large-scale cubic regularization by a generalized eigenvalue problem. SIAM Journal on Optimization, 30(4):3345–3358, 2020

work page 2020
[37]

Mokhtari, A

A. Mokhtari, A. Ozdaglar, and A. Jadbabaie. Escaping saddle points in constrained opti- mization.Advances in Neural Information Processing Systems, 31, 2018

work page 2018
[38]

Nesterov and B

Y. Nesterov and B. T. Polyak. Cubic regularization of newton method and its global performance.Mathematical programming, 108(1):177–205, 2006

work page 2006
[39]

Nocedal and S

J. Nocedal and S. J. Wright.Numerical optimization. Springer, 2006

work page 2006
[40]

Convergence to second-order stationarity for constrained non-convex optimization,

M. Nouiehed, J. D. Lee, and M. Razaviyayn. Convergence to second-order stationarity for constrained non-convex optimization.arXiv preprint arXiv:1810.02024, 2018

work page arXiv 2018
[41]

Y. Pei, S. Song, and D. Zhu. A sequential adaptive regularisation using cubics algorithm for solving nonlinear equality constrained optimization.Computational Optimization and Applications, 84(3):1005–1033, 2023

work page 2023
[42]

two-phase

Y. Xie and S. J. Wright. Complexity of proximal augmented lagrangian for nonconvex optimization with nonlinear equality constraints.Journal of Scientific Computing, 86:1–30, 2021. 39 Appendix A Extended Related work In equality constrained optimization, the landscape of theoretical results is shaped as much by the adopted optimality criteria as by the alg...

work page 2021

[1] [1]

Bai and S

Y. Bai and S. Mei. Analysis of sequential quadratic programming through the lens of riemannian optimization.arXiv preprint arXiv:1805.08756, 2018

work page arXiv 2018

[2] [2]

Bellavia, D

S. Bellavia, D. Palitta, M. Porcelli, and V. Simoncini. Regularized methods via cubic model subspace minimization for nonconvex optimization.Computational Optimization and Applications, 90(3):801–837, 2025

work page 2025

[3] [3]

A. S. Berahas, F. E. Curtis, D. Robinson, and B. Zhou. Sequential quadratic optimization for nonlinear equality constrained stochastic optimization.SIAM Journal on Optimization, 31(2):1352–1379, 2021

work page 2021

[4] [4]

A. S. Berahas, R. Bollapragada, and J. Shi. Modified line search sequential quadratic methods for equality-constrained optimization with unified global and local convergence guarantees.arXiv preprint arXiv:2406.11144, 2024

work page arXiv 2024

[5] [5]

A. S. Berahas, M. Xie, and B. Zhou. A sequential quadratic programming method with high- probability complexity bounds for nonlinear equality-constrained stochastic optimization. SIAM Journal on Optimization, 35(1):240–269, 2025

work page 2025

[6] [6]

Bertsekas.Network optimization: continuous and discrete models, volume 8

D. Bertsekas.Network optimization: continuous and discrete models, volume 8. Athena Scientific, 1998

work page 1998

[7] [7]

J. T. Betts.Practical methods for optimal control and estimation using nonlinear program- ming. SIAM, 2010

work page 2010

[8] [8]

E. G. Birgin and J. M. Martinez. A newton-like method with mixed factorizations and cubic regularization for unconstrained minimization.Computational Optimization and Ap- plications, 73(3):707–753, 2019

work page 2019

[9] [9]

E. G. Birgin, J. Gardenghi, J. M. Mart´ ınez, S. A. Santos, and P. L. Toint. Evaluation complexity for nonlinear constrained optimization using unscaled kkt conditions and high- order models.SIAM Journal on Optimization, 26(2):951–967, 2016

work page 2016

[10] [10]

L. E. Bourkhissi and I. Necoara. Complexity of linearized quadratic penalty for optimization with nonlinear equality constraints.Journal of Global Optimization, 91(3):483–510, 2025

work page 2025

[11] [11]

R. H. Byrd, R. B. Schnabel, and G. A. Shultz. A trust region algorithm for nonlinearly constrained optimization.SIAM Journal on Numerical Analysis, 24(5):1152–1170, 1987

work page 1987

[12] [12]

Carmon and J

Y. Carmon and J. C. Duchi. Analysis of krylov subspace solutions of regularized non-convex quadratic problems.Advances in Neural Information Processing Systems, 31, 2018

work page 2018

[13] [13]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. Adaptive cubic regularisation methods for uncon- strained optimization. part i: motivation, convergence and numerical results.Mathematical Programming, 127(2):245–295, 2011. 37

work page 2011

[14] [14]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. Adaptive cubic regularisation methods for uncon- strained optimization. part ii: worst-case function-and derivative-evaluation complexity. Mathematical programming, 130(2):295–319, 2011

work page 2011

[15] [15]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming.SIAM Journal on Optimization, 21(4):1721–1739, 2011

work page 2011

[16] [16]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. Complexity bounds for second-order optimality in unconstrained optimization.Journal of Complexity, 28(1):93–108, 2012

work page 2012

[17] [17]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization.SIAM Journal on Optimization, 23(3):1553–1574, 2013

work page 2013

[18] [18]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. On the complexity of finding first-order critical points in constrained nonlinear optimization.Mathematical Programming, 144(1):93–106, 2014

work page 2014

[19] [19]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint. Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization.Journal of Complexity, 53:68–94, 2019

work page 2019

[20] [20]

Cartis, N

C. Cartis, N. I. M. Gould, and P. L. Toint. Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled kkt conditions and high-order models. In I. C. Demetriou and P. M. Pardalos, editors,Approximation and Optimization: Algorithms, Complexity and Applications, pages 5–26. Springer International Publishing, Cham, 2019

work page 2019

[21] [21]

F. E. Curtis, D. P. Robinson, and M. Samadi. A trust region algorithm with a worst-case iteration complexity ofO(ϵ −3/2) for nonconvex optimization.Mathematical Programming, 162(1):1–32, 2017

work page 2017

[22] [22]

F. E. Curtis, D. P. Robinson, and M. Samadi. Complexity analysis of a trust funnel algorithm for equality constrained optimization.SIAM Journal on Optimization, 28(2): 1533–1563, 2018

work page 2018

[23] [23]

F. E. Curtis, M. J. O’Neill, and D. P. Robinson. Worst-case complexity of an sqp method for nonlinear equality constrained stochastic optimization.Mathematical Programming, 205 (1):431–483, 2024

work page 2024

[24] [24]

F. E. Curtis, D. P. Robinson, and B. Zhou. Sequential quadratic optimization for stochas- tic optimization with deterministic nonlinear inequality and equality constraints.SIAM Journal on Optimization, 34(4):3592–3622, 2024

work page 2024

[25] [25]

Facchinei, V

F. Facchinei, V. Kungurtsev, L. Lampariello, and G. Scutari. Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and iteration complexity.Mathematics of Operations Research, 46(2):595–627, 2021

work page 2021

[26] [26]

Y. Fang, S. Na, M. W. Mahoney, and M. Kolar. Fully stochastic trust-region sequential quadratic programming for equality-constrained optimization problems.SIAM Journal on Optimization, 34(2):2007–2037, 2024

work page 2007

[27] [27]

Y. Fang, J. Lavaei, and S. Na. High probability complexity bounds of trust-region stochastic sequential quadratic programming with heavy-tailed noise.arXiv preprint arXiv:2503.19091, 2025. 38

work page arXiv 2025

[28] [28]

Fletcher, N

R. Fletcher, N. I. Gould, S. Leyffer, P. L. Toint, and A. W¨ achter. Global convergence of a trust-region sqp-filter algorithm for general nonlinear programming.SIAM Journal on Optimization, 13(3):635–659, 2002

work page 2002

[29] [29]

G. H. Golub, Z. Zhang, and H. Zha. Large sparse symmetric eigenvalue problems with homogeneous linear constraints: the lanczos process with inner–outer iterations.Linear Algebra and its Applications, 309(1-3):289–306, 2000

work page 2000

[30] [30]

N. I. Gould, D. P. Robinson, and H. S. Thorne. On solving trust-region and other regularised subproblems in optimization.Mathematical Programming Computation, 2(1):21–57, 2010

work page 2010

[31] [31]

Goyens, A

F. Goyens, A. Eftekhari, and N. Boumal. Computing second-order points under equality constraints: revisiting fletcher’s augmented lagrangian.Journal of Optimization Theory and Applications, 201(3):1198–1228, 2024

work page 2024

[32] [32]

G. N. Grapiglia and Y.-x. Yuan. On the complexity of an augmented lagrangian method for nonconvex optimization.IMA Journal of Numerical Analysis, 41(2):1546–1568, 2021

work page 2021

[33] [33]

C. He, Z. Lu, and T. K. Pong. A newton-cg based augmented lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees.SIAM Journal on Optimization, 33(3):1734–1766, 2023

work page 2023

[34] [34]

Hinze, R

M. Hinze, R. Pinnau, M. Ulbrich, and S. Ulbrich.Optimization with PDE constraints, volume 23. Springer Science & Business Media, 2008

work page 2008

[35] [35]

X. Jia, X. Liang, C. Shen, and L.-H. Zhang. Solving the cubic regularization model by a nested restarting lanczos method.SIAM Journal on Matrix Analysis and Applications, 43 (2):812–839, 2022

work page 2022

[36] [36]

F. Lieder. Solving large-scale cubic regularization by a generalized eigenvalue problem. SIAM Journal on Optimization, 30(4):3345–3358, 2020

work page 2020

[37] [37]

Mokhtari, A

A. Mokhtari, A. Ozdaglar, and A. Jadbabaie. Escaping saddle points in constrained opti- mization.Advances in Neural Information Processing Systems, 31, 2018

work page 2018

[38] [38]

Nesterov and B

Y. Nesterov and B. T. Polyak. Cubic regularization of newton method and its global performance.Mathematical programming, 108(1):177–205, 2006

work page 2006

[39] [39]

Nocedal and S

J. Nocedal and S. J. Wright.Numerical optimization. Springer, 2006

work page 2006

[40] [40]

Convergence to second-order stationarity for constrained non-convex optimization,

M. Nouiehed, J. D. Lee, and M. Razaviyayn. Convergence to second-order stationarity for constrained non-convex optimization.arXiv preprint arXiv:1810.02024, 2018

work page arXiv 2018

[41] [41]

Y. Pei, S. Song, and D. Zhu. A sequential adaptive regularisation using cubics algorithm for solving nonlinear equality constrained optimization.Computational Optimization and Applications, 84(3):1005–1033, 2023

work page 2023

[42] [42]

two-phase

Y. Xie and S. J. Wright. Complexity of proximal augmented lagrangian for nonconvex optimization with nonlinear equality constraints.Journal of Scientific Computing, 86:1–30, 2021. 39 Appendix A Extended Related work In equality constrained optimization, the landscape of theoretical results is shaped as much by the adopted optimality criteria as by the alg...

work page 2021