A single cut proximal bundle method for stochastic convex composite optimization
Preprint
Abstract
This paper considers optimization problems where the objective is the sum of a function given by an expectation and a closed convex composite function, and proposes stochastic composite proximal bundle (SCPB) methods for solving it. Complexity guarantees are established for them without requiring knowledge of parameters associated with the problem instance. Moreover, it is shown that they have optimal complexity when these problem parameters are known. To the best of our knowledge, this is the first proximal bundle method for stochastic programming able to deal with continuous distributions. Finally, we present computational results showing that SCPB substantially outperforms the robust stochastic approximation (RSA) method in all instances considered.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Inexact stochastic mirror descent for two-stage nonlinear stochastic programsMathematical Programming, 2020
- Rate of Convergence of the Bundle MethodJournal of Optimization Theory and Applications, 2017
- Probabilistic optimization via approximate p-efficient points and bundle methodsComputers & Operations Research, 2017
- Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measuresMathematical Programming, 2016
- Convex proximal bundle methods in depth: a unified analysis for inexact oraclesMathematical Programming, 2014
- Primal-dual subgradient methods for convex problemsMathematical Programming, 2007
- The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational StudyComputational Optimization and Applications, 2003
- Efficiency of Proximal Bundle MethodsJournal of Optimization Theory and Applications, 2000
- Asymptotic analysis of stochastic programsAnnals of Operations Research, 1991
- A multicut algorithm for two-stage stochastic linear programsEuropean Journal of Operational Research, 1988