Non-Convex Constrained Stochastic Successive Convex Approximation

We consider stochastic non-convex optimization problem subject to non-convex deterministic constraints. The proposed algorithm hinges on successive convex approximation (SCA) techniques and utilizes recursive momentum-based acceleration which is widely used in the unconstrained settings. Remarkably, the proposed algorithm also achieves the optimal stochastic first order (SFO) complexity, at par with that achieved by state-of-the-art (unconstrained) stochastic optimization algorithms, and matches the SFO-complexity lower bound. At each iteration, the proposed algorithm entails constructing convex surrogates of the objective and the constraint functions, and solving the resulting convex optimization problem. A recursive update rule is employed to track the gradient of the objective function, and contributes to achieving faster convergence and improved SFO complexity. A key ingredient of the proof is a new parameterized version of the standard Mangasarian-Fromowitz Constraints Qualification, that allows us to bound the dual variables and hence establish that the iterates approach an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\epsilon$</tex>-stationary point. Finally, the algorithm is applied to an obstacle-avoiding trajectory optimization problem. Numerical results confirm the theoretical claims and illustrate that the performance is superior to that of the existing SCA algorithms.