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

Liwei Zhang, Yule Zhang, Jia Wu, Xiantao Xiao

INFORMS Journal on Computing · 2022 · Volume 34 · Issue 6

DOI: 10.1287/ijoc.2022.1228

Abstract

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 𝑂 ⁡ ( 𝐾 − 1 / 2 ) 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 𝑂 ⁡ ( l o g ( 𝐾 ) ⁢ 𝐾 − 1 / 2 ) O ⁡ ( log ( K ) ⁢ K − 1 / 2 ) constraint violation bound and 𝑂 ⁡ ( l o g 3 / 2 ⁢ ( 𝐾 ) ⁢ 𝐾 − 1 / 2 ) 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 .

Keywords

stochastic approximation, linearized proximal method of multipliers, expectation constrained stochastic program, expected convergence rate, high-probability bound

Enable JavaScript for citation tools and additional paper interactions.