Stochastic Approximation Proximal Method of Multipliers for Convex Stochastic Programming

DOI10.1287/MOOR.2022.1257MaRDI QIDQ6199237zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

constraint violation regretconvex stochastic optimizationhigh probability regret boundobjective regretproximal method of multipliersstochastic approximation

Mathematics Subject Classification ID

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

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.

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

Cited in

(7)

• Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm
• A single cut proximal bundle method for stochastic convex composite optimization
• Complexity analysis of inexact cubic-regularized primal-dual methods for finding second-order stationary points
• A two-phase stochastic momentum-based algorithm for nonconvex expectation-constrained optimization
• Stochastic-constrained stochastic optimization with Markovian data
• An augmented Lagrangian-type stochastic approximation method for convex stochastic semidefinite programming defined by expectations
• A stochastic augmented Lagrangian method for stochastic convex programming

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)