Stochastic Sequential Quadratic Programming for Optimization with Functional Constraints

Stochastic convex optimization problems with nonlinear functional constraints are ubiquitous in signal processing applications including constrained least-squares, set-membership adaptive filtering, and trajectory optimization under uncertain fields.

The presence of non-linear functional constraints renders the traditional projected stochastic gradient descent and related projection-based methods inefficient, and motivates the use of first-order methods.

However, existing first-order methods, including primal and primal--dual algorithms, typically rely on a bounded (sub-)gradient assumption, which may be too restrictive in high-dimensional settings.

We propose a stochastic sequential quadratic programming (SSQP) algorithm that works entirely in the primal domain, avoids projecting onto the feasible region, obviates the need for bounded gradients, and achieves state-of-the-art oracle complexity under standard smoothness and convexity assumptions.

A faster version, namely SSQP-Skip, is also proposed where the quadratic subproblems can be skipped in most iterations.

Finally, we develop an accelerated variance-reduced version of SSQP (VARAS), whose oracle complexity bounds match those for solving unconstrained finite-sum convex optimization problems.

The superior performance of the proposed algorithms is demonstrated via numerical experiments on real datasets.