Sampling Bounds for Stochastic Optimization
Sampling Bounds for Stochastic Optimization
复制标题
随机优化的采样范围
DOI：
10.1007/11538462_22
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Martin Pál
中科院分区：
文献类型：
--
作者：
M. Charikar;C. Chekuri;Martin Pál
一大类随机优化问题可以被建模为最小化目标函数f，该目标函数f取决于向量x∈X的选择以及由概率分布ω∈Ω给出的随机外部参数π。目标函数的值是随机变量，通常目标是找到x∈X以最小化预期成本Eω[fω(X)]。每个ω都被称为一个场景。我们考虑当Ω是大的或无限的，并且我们被允许以黑箱方式从π抽样时的情况。一种常见的方法被称为样本平均近似(SAA)方法，即从π中选取足够多的独立样本，并使用它们来逼近π和相应的Eω[fω(X)]。这是实践中使用的几种情景缩减方法之一。
最近，人们对可以由上述框架建模的组合优化问题的两阶段随机版本有很大的兴趣。特别是，我们对模型感兴趣，在该模型中，参数λ限定了如果决策被推迟到第二阶段，成本增加的相对因素。虽然该方法已被广泛分析，但(1+e)近似所需样本数的已知界限取决于π的方差，即使在假设λ为固定常数的情况下也是如此。Shmoys和Swamy[13，14]证明了当f可以建模为线性规划或凸规划时，多项式数量的样本就足够了。他们使用对椭球法的修改来证明这一点。
本文在Kley wegt，Shapiro，Homem-de-Mello[6]等方法的基础上给出了一个不同的证明，证明了SAA方法的样本数是多项式的。我们的证明不是基于f的计算性质，因此也适用于整数规划。我们进一步证明，即使当我们只有一个近似算法来解决抽样问题时，SAA方法的小变化也足以获得样本大小的界。因此，当π被显式地给出时，我们能够扩展为当π被给出为黑盒抽样预言时的情况设计的一些算法。
A large class of stochastic optimization problems can be modeled as minimizing an objective function f that depends on a choice of a vector x ∈ X, as well as on a random external parameter ω∈ Ω given by a probability distribution π. The value of the objective function is a random variable and often the goal is to find an x ∈ X to minimize the expected cost Eω[fω(x)]. Each ω is referred to as a scenario. We consider the case when Ω is large or infinite and we are allowed to sample from π in a black-box fashion. A common method, known as the SAA method (sample average approximation), is to pick sufficiently many independent samples from π and use them to approximate π and correspondingly Eω[fω(x)]. This is one of several scenario reduction methods used in practice.
There has been substantial recent interest in two-stage stochastic versions of combinatorial optimization problems which can be modeled by the framework described above. In particular, we are interested in the model where a parameter λ bounds the relative factor by which costs increase if decisions are delayed to the second stage. Although the SAA method has been widely analyzed, the known bounds on the number of samples required for a (1+e) approximation depend on the variance of π even when λ is assumed to be a fixed constant. Shmoys and Swamy [13,14] proved that a polynomial number of samples suffice when f can be modeled as a linear or convex program. They used modifications to the ellipsoid method to prove this.
In this paper we give a different proof, based on earlier methods of Kleywegt, Shapiro, Homem-De-Mello [6] and others, that a polynomial number of samples suffice for the SAA method. Our proof is not based on computational properties of f and hence also applies to integer programs. We further show that small variations of the SAA method suffice to obtain a bound on the sample size even when we have only an approximation algorithm to solve the sampled problem. We are thus able to extend a number of algorithms designed for the case when π is given explicitly to the case when π is given as a black-box sampling oracle.