Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm

This paper considers the problem of minimizing a convex expectation function with a set of inequality convex expectation constraints. We propose a stochastic augmented Lagrangian-type algorithm—namely, the stochastic linearized proximal method of multipliers—to solve this convex stochastic optimization problem. This algorithm can be roughly viewed as a hybrid of stochastic approximation and the traditional proximal method of multipliers. Under mild conditions, we show that this algorithm exhibits $O(K^{-1/2})$ expected convergence rates for both objective reduction and constraint violation if parameters in the algorithm are properly chosen, where K denotes the number of iterations. Moreover, we show that, with high probability, the algorithm has a $O(\log (K)K^{-1/2})$ constraint violation bound and $O({\log }^{3/2}(K)K^{-1/2})$ objective bound. Numerical results demonstrate that the proposed algorithm is efficient.

History: Accepted byAntonio Frangioni, Area Editor for Design & Analysis ofAlgorithms—Continuous.

Funding: This work was supported by the National Natural Science Foundation of China [Grants 11971089, 11731013, 12071055, and 11871135].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information [https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1228] or is available from the IJOC GitHub software repository (https://github.com/INFORMSJoC) at http://dx.doi.org/10.5281/zenodo.6818229.