ROBUST STOCHASTIC APPROXIMATION APPROACH TO STOCHASTIC PROGRAMMING
ROBUST STOCHASTIC APPROXIMATION APPROACH TO STOCHASTIC PROGRAMMING
复制标题
DOI：
10.1137/070704277
复制
发表时间：
2009-01-01
影响因子：
3.1
通讯作者：
Shapiro, A.
中科院分区：
文献类型：
--
作者：
Nemirovski, A.;Juditsky, A.;Shapiro, A.
本文研究目标函数以期望形式给出的最优化问题。求解这类随机优化问题的一个基本困难是所涉及的多维积分（期望）不能高精度地计算。本文的目的是比较两种基于蒙特卡罗采样技术的计算方法，即随机逼近（SA）和样本平均逼近（SAA）方法。SA和SAA方法这两种方法都有很长的历史。目前的观点是，SAA方法可以有效地使用所考虑问题的特定（例如线性）结构，而SA方法是一种粗糙的次梯度方法，在实践中往往表现不佳。我们打算证明一个适当修改的SA方法可以竞争，甚至显着优于SAA方法对于某类凸随机问题。我们将分析扩展到凸凹随机鞍点问题，并给出了（我们认为非常鼓舞人心的）数值实验结果。
In this paper we consider optimization problems where the objective function is given in a form of the expectation. A basic difficulty of solving such stochastic optimization problems is that the involved multidimensional integrals (expectations) cannot be computed with high accuracy. The aim of this paper is to compare two computational approaches based on Monte Carlo sampling techniques, namely, the stochastic approximation (SA) and the sample average approximation (SAA) methods. Both approaches, the SA and SAA methods, have a long history. Current opinion is that the SAA method can efficiently use a specific (say, linear) structure of the considered problem, while the SA approach is a crude subgradient method, which often performs poorly in practice. We intend to demonstrate that a properly modified SA approach can be competitive and even significantly outperform the SAA method for a certain class of convex stochastic problems. We extend the analysis to the case of convex-concave stochastic saddle point problems and present (in our opinion highly encouraging) results of numerical experiments.