A Sequential Quadratic Programming Method With High-Probability Complexity Bounds for Nonlinear Equality-Constrained Stochastic Optimization

Albert S. Berahas, Miaolan Xie, Baoyu ZhouSIAM J. Optim 2025 · DOI

TL;DR

This paper introduces a new algorithm, SS-SQP, for solving complex optimization problems with noisy objective functions and derivatives, while keeping the constraints exact. It provides theoretical guarantees on how quickly the algorithm finds a good solution, even with imperfect information, and shows promising results on benchmark problems.

What Problem Does This Paper Address?

Many real-world optimization problems involve finding the best solution when the objective function (what we want to minimize or maximize) is not perfectly known. Instead, we only have noisy estimates of its value and its rate of change (gradient). This is common in areas like machine learning, where data is used to approximate these quantities. When these problems also have constraints (e.g., "the solution must satisfy this equation"), solving them becomes even harder. Traditional methods struggle with this combination of noisy objectives and exact constraints. Existing stochastic optimization methods often either simplify the problem by ignoring constraints or require even more assumptions about the noise. This paper tackles the challenge of developing an efficient and theoretically sound method for nonlinear equality-constrained stochastic optimization problems where the constraints are known precisely, but the objective function and its gradient are only available through noisy, probabilistic oracles.

Methods

The core of this paper is the development of a Sequential Quadratic Programming (SQP) method adapted for stochastic optimization, called SS-SQP. SQP methods are known for their effectiveness in handling constrained optimization. The key innovations here are:

  • Step-Search Approach: Unlike traditional line-search methods that fix a search direction and then find a step size, SS-SQP uses a "step-search" strategy. This means the search direction can be updated even if a step is not taken, allowing for more flexibility in noisy environments.
  • Probabilistic Oracles: The algorithm is designed to work with "inexact probabilistic zeroth- and first-order oracles." This means it can handle noisy estimates of the objective function's value (zeroth-order) and its gradient (first-order). These oracles have parameters that control their accuracy and reliability, and importantly, can even produce biased estimates.
  • Merit Function and Model: A merit function is used to balance the objective function and constraint violation. The algorithm uses a model of this merit function to guide its progress and ensure sufficient improvement at each step.
  • Modified Sufficient Decrease Condition: To account for noise in the objective function estimates, a relaxed sufficient decrease condition is employed. This allows for some increase in the merit function, making the algorithm more robust to noisy evaluations.
  • Theoretical Guarantees: The paper provides a high-probability iteration complexity bound. This means they prove, with very high confidence, that the algorithm will find a "first-order ɛ-stationary" iterate (a good approximation of a solution) within a certain number of steps, specifically $O(\varepsilon^{-2})$. This bound is comparable to deterministic SQP methods when the noise is low.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments on standard benchmark problems.

Key Insights and Ideas

  • Balancing Noise and Constraints: The SS-SQP algorithm demonstrates that it's possible to effectively handle noisy objective functions while maintaining exact constraints, a common scenario in practical applications.
  • Step-Search Adaptability: The step-search mechanism proves crucial for adapting to noisy gradient information, allowing the algorithm to make progress even when a traditional line-search might get stuck.
  • Merit Function as a Guide: The carefully designed merit function and its model act as a robust guide, helping the algorithm navigate the complex landscape of stochastic optimization with constraints.
  • Theoretical Rigor for Stochasticity: Providing high-probability complexity bounds for such a method is a significant theoretical contribution, offering confidence in its convergence properties.

Key Results

The paper presents a theoretical guarantee that the SS-SQP algorithm achieves an $O(\varepsilon^{-2})$ iteration complexity with high probability for finding an $\varepsilon$-stationary point. This complexity matches that of deterministic SQP methods when noise is absent. Numerical experiments on a subset of the CUTEst collection show that SS-SQP performs competitively with, and often better than, an existing adaptive stochastic SQP method (AS-SQP), especially as the noise in the gradient evaluations increases. The results highlight the advantage of using exact function evaluations when available.

Limitations and Future Work

  • Exact Constraints: The current SS-SQP method assumes that constraint function values and their Jacobians are available exactly. Extending the framework to handle stochastic constraints is a significant area for future work.
  • Inequality Constraints: The current work focuses on equality constraints. Future research could explore extending the SS-SQP algorithm to handle inequality constraints as well.
  • Oracle Assumptions: The theoretical analysis relies on specific probabilistic oracle conditions. While these are motivated by practical scenarios, further investigation into their practical implications and potential relaxations could be beneficial.

Summary updated

BibTeX
@article{berahas2025sequential,
  author = {Albert S. Berahas and Miaolan Xie and Baoyu Zhou},
  title = {{A Sequential Quadratic Programming Method With High-Probability Complexity Bounds for Nonlinear Equality-Constrained Stochastic Optimization}},
  journal = {SIAM J. Optim},
  year = {2025},
  doi = {10.1137/23m1549006},
}
Figure