Online Successive Convex Approximation for Two-Stage Stochastic Nonconvex Optimization
- 24 September 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 66 (22) , 5941-5955
Abstract
Two-stage stochastic optimization, in which a longterm master problem is coupled with a family of short-term subproblems, plays a critical role in various application areas. However, most existing algorithms for two-stage stochastic optimization only work for special cases, and/or are based on the batch method, which requires huge memory and computational complexity. To the best of our knowledge, there still lack efficient and general two-stage online stochastic optimization algorithms. This paper proposes a two-stage online successive convex approximation (TOSCA) algorithm for general two-stage non-convex stochastic optimization problems. At each iteration, the TOSCA algorithm first solves one short-term subproblem associated with the current realization of the system state. Then it constructs a convex surrogate function for the objective of the long-term master problem. Finally, the long-term variables are updated by solving a convex approximation problem obtained by replacing the objective function in the long-term master problem with the convex surrogate function. We establish the almost sure convergence of the TOSCA algorithm and customize the algorithmic framework to solve three important application problems. Simulations show that the TOSCA algorithm can achieve superior performance over existing solutions.Keywords
Funding Information
- Science and Technology Program of Shenzhen, China (JCYJ20170818113908577)
- National Natural Science Foundation of China (61571383)
- RGC (16209916)
- China Recruitment Program of Global Young Experts
This publication has 27 references indexed in Scilit:
- Optimized Uplink Transmission in Multi-Antenna C-RAN With Spatial Compression and ForwardIEEE Transactions on Signal Processing, 2015
- Two Timescale Joint Beamforming and Routing for Multi-Antenna D2D Networks via Stochastic Cutting PlaneIEEE Transactions on Signal Processing, 2015
- A Vector-Perturbation Technique for Near-Capacity Multiantenna Multiuser Communication—Part I: Channel Inversion and RegularizationIEEE Transactions on Communications, 2005
- Financial planning via multi-stage stochastic optimizationComputers & Operations Research, 2004
- Gradient Convergence in Gradient methods with ErrorsSIAM Journal on Optimization, 2000
- Asymptotically optimal rate of convergence of smoothed stochastic recursive algorithmsStochastics and Stochastic Reports, 1994
- Acceleration of Stochastic Approximation by AveragingSIAM Journal on Control and Optimization, 1992
- Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with RecourseMathematics of Operations Research, 1991
- Feasible direction methods for stochastic programming problemsMathematical Programming, 1980
- A linearization method in limiting extremal problemsCybernetics and Systems Analysis, 1977