Stochastic Approximation Proximal Method of Multipliers for Convex Stochastic Programming

DOI10.1287/MOOR.2022.1257arXiv1907.12226OpenAlexW2964718684WikidataQ114058150 ScholiaQ114058150MaRDI QIDQ6199237FDOQ6199237

Authors: Liwei Zhang, Yu-Le Zhang, Xiantao Xiao, Jia Wu 

Publication date: 23 February 2024

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: This paper considers the problem of minimizing a convex expectation function over a closed convex set, coupled with a set of inequality convex expectation constraints. We present a new stochastic approximation type algorithm, namely the stochastic approximation proximal method of multipliers (PMMSopt) to solve this convex stochastic optimization problem. We analyze regrets of a stochastic approximation proximal method of multipliers for solving convex stochastic optimization problems. Under mild conditions, we show that this algorithm exhibits $mO(T^{-1/2})$ rate of convergence, in terms of both optimality gap and constraint violation if parameters in the algorithm are properly chosen, when the objective and constraint functions are generally convex, where $T$ denotes the number of iterations. Moreover, we show that, with at least $1-e^{-T^{1/4}}$ probability, the algorithm has no more than $mO(T^{-1/4})$ objective regret and no more than $mO(T^{-1/8})$ constraint violation regret. To the best of our knowledge, this is the first time that such a proximal method for solving expectation constrained stochastic optimization is presented in the literature.

Full work available at URL: https://arxiv.org/abs/1907.12226

Recommendations

• Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm
• Robust Stochastic Approximation Approach to Stochastic Programming
• Algorithms for stochastic optimization with function or expectation constraints
• Dynamic stochastic approximation for multi-stage stochastic optimization
• A single cut proximal bundle method for stochastic convex composite optimization

zbMATH Keywords

stochastic approximationconvex stochastic optimizationproximal method of multipliersconstraint violation regrethigh probability regret boundobjective regret

Mathematics Subject Classification ID

Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37) Stochastic programming (90C15)

Cited In (1)

• A single cut proximal bundle method for stochastic convex composite optimization

This page was built for publication: Stochastic Approximation Proximal Method of Multipliers for Convex Stochastic Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199237)