Primal-Dual Inexact Newton-MR for Nonconvex Optimization with Equality Constraints
Abstract
Optimization problems with nonlinear equality constraints arise throughout science, engineering, and increasingly in machine learning. Prominent methods for solving such problems include sequential quadratic programming and, more broadly, primal-dual Newton methods. Classical analyses of these methods typically rely on strong assumptions, perhaps most notably positive definiteness of the Lagrangian Hessian on the null space of the constraint Jacobian. In practice, this assumption often necessitates strong regularization or the use of a positive definite Hessian surrogate. Moreover, in large-scale settings, solving the primal-dual Newton subproblem exactly is often computationally infeasible. To address these issues, we propose an inexact primal-dual Newton method with an inner solver based on the conjugate residual (CR) method. Exploiting recently established properties of CR, including negative-curvature detection, iterate monotonicity, and descent guarantees, our method handles indefiniteness in the subproblem directly as it arises. Our method thereby avoids detrimental regularization of the Lagrangian Hessian while naturally accommodating inexact solves. We establish worst-case global convergence guarantees and demonstrate strong empirical performance on large-scale, nonconvex problems.
Related
- On the Regularization of Primal-Dual Dynamics in Time-Dependent Nonconvex Optimization
- Langevin for Nonconvex Optimization: Exact, Inexact and Zeroth-Order
- Accelerated primal-dual dynamics and algorithms for convex optimization with nonlinear inequality constraints
- Projected Primal–Dual Gradient Preference Optimization Under Category-Wise Split-Conformal Safety Constraints for Large Language Model Post-Training
- Convergence Analysis via ODE Approach for Convex Optimization with Linear Equality Constraints
BibTeX
@misc{smee2026primaldual,
title = {{Primal-Dual Inexact Newton-MR for Nonconvex Optimization with Equality Constraints}},
author = {Oscar Smee and Fred Roosta},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09683},
eprint = {2609.09683},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09683},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Primal-Dual Inexact Newton-MR for Nonconvex Optimization with Equality Constraints
AU - Oscar Smee
AU - Fred Roosta
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.09683
UR - https://arxiv.org/abs/2609.09683
AB - Optimization problems with nonlinear equality constraints arise throughout science, engineering, and increasingly in machine learning. Prominent methods for solving such problems include sequential quadratic programming and, more broadly, primal-dual Newton methods. Classical analyses of these methods typically rely on strong assumptions, perhaps most notably positive definiteness of the Lagrangian Hessian on the null space of the constraint Jacobian. In practice, this assumption often necessitates strong regularization or the use of a positive definite Hessian surrogate. Moreover, in large-scale settings, solving the primal-dual Newton subproblem exactly is often computationally infeasible. To address these issues, we propose an inexact primal-dual Newton method with an inner solver based on the conjugate residual (CR) method. Exploiting recently established properties of CR, including negative-curvature detection, iterate monotonicity, and descent guarantees, our method handles indefiniteness in the subproblem directly as it arises. Our method thereby avoids detrimental regularization of the Lagrangian Hessian while naturally accommodating inexact solves. We establish worst-case global convergence guarantees and demonstrate strong empirical performance on large-scale, nonconvex problems.
ER -