Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimization

DOI10.1007/S10107-023-01981-1arXiv2112.14799MaRDI QIDQ6126655FDOQ6126655

Michael J. O'Neill, Daniel P. Robinson, Frank E. Curtis

Publication date: 9 April 2024

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: A worst-case complexity bound is proved for a sequential quadratic optimization (commonly known as SQP) algorithm that has been designed for solving optimization problems involving a stochastic objective function and deterministic nonlinear equality constraints. Barring additional terms that arise due to the adaptivity of the monotonically nonincreasing merit parameter sequence, the proved complexity bound is comparable to that known for the stochastic gradient algorithm for unconstrained nonconvex optimization. The overall complexity bound, which accounts for the adaptivity of the merit parameter sequence, shows that a result comparable to the unconstrained setting (with additional logarithmic factors) holds with high probability.

Full work available at URL: https://arxiv.org/abs/2112.14799

zbMATH Keywords

nonlinear optimizationstochastic optimizationworst-case complexitysequential quadratic optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Methods of successive quadratic programming type (90C55) Complexity and performance of numerical algorithms (65Y20) Large-scale problems in mathematical programming (90C06) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonlinear programming (90C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Robust Stochastic Approximation Approach to Stochastic Programming
• Optimal Solvers for PDE-Constrained Optimization
• Exact penalty functions in nonlinear programming
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• Practical Methods for Optimal Control and Estimation Using Nonlinear Programming
• A line search exact penalty method using steering rules
• Automatic decrease of the penalty parameter in exact penalty function methods
• Elementary Probability
• Steering exact penalty methods for nonlinear programming
• An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity
• An adaptive augmented Lagrangian method for large-scale constrained optimization
• A penalty-interior-point algorithm for nonlinear constrained optimization
• Adaptive Barrier Update Strategies for Nonlinear Interior Methods
• On the complexity of finding first-order critical points in constrained nonlinear optimization
• Numerical solution of a nonlinear parabolic control problem by a reduced SQP method
• Probability
• On the complexity of an augmented Lagrangian method for nonconvex optimization
• Exploiting negative curvature in deterministic and stochastic optimization
• Stochastic Model-Based Minimization of Weakly Convex Functions
• Complexity Analysis of a Trust Funnel Algorithm for Equality Constrained Optimization
• Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization

Cited In (4)

• Fully stochastic trust-region sequential quadratic programming for equality-constrained optimization problems
• Stochastic nested primal-dual method for nonconvex constrained composition optimization
• Sequential quadratic optimization for stochastic optimization with deterministic nonlinear inequality and equality constraints
• A sequential quadratic programming method with high-probability complexity bounds for nonlinear equality-constrained stochastic optimization

This page was built for publication: Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6126655)