文章链接：
https://doi.org/10.1287/opre.2018.0340
PART/1
研究背景
现实中的网络优化问题在优化阶段经常涉及不确定参数，随机优化是解决这种不确定性的一种关键方法。本文给出了在随机优化问题中SAA方法所需要的样本数量的上界。改进来了现有方法的样本复杂度，对应用在该框架下的方法提供更快的近似算法，如随机Steiner树问题等。
PART/2
文章模型
随机优化问题举例——两阶段不限容的工厂选址
假设有一个可能的工厂选址集合F_0和可能的客户集合C_0。实际的客户集合C_1是C_0的一个子集，是随机的。现在的问题是选择一个合适的工厂选址集合F_1（是F_0的子集）以最小化这些工厂的建造成本总和以及客户具体最近的工厂的距离总和。
在第一阶段，利用C_1的分布信息构造一个初始的工厂集合F_2；在第二阶段，采样获得C_1的分布，扩充F_2输出一个完备的解F_1。
这个两阶段优化问题的难点在于第二阶段的求解耗时较长，以及很难去平衡求解成本（第一阶段较低，第二阶段较高）和准确度（第一阶段的概率和第二阶段的准确度）。
在工厂选址问题的例子中，通常认为应该选择尽可能少的工厂以最小化目标函数。假定在第一阶段中每一个候选的客户j∈C_0以一个未知概率p_j出现，且与C_1中的其他客户独立。或者更现实一点，有一个可以从分布中抽取C_1的盲盒，输出任意数量的想从第一阶段得到的样本。在上面这两种分布假设下，两阶段随机工厂选址的目标是在第一阶段更加精确地提供F_2，并且在第二阶段当C_1揭示时选择近优的附加工厂。
两阶段随机规划：
假定X是有限的，且该模型是一个离散优化问题，解集也是从一个有限族中选取。随机变量ω的概率分布为π，ω∈Ω。Resource action r∈R需要被采取以保证场景ω的需求被满足。在两阶段模型中，c(x)表示第一阶段采取行动x的成本。给定一个特定的情景ω和第一阶段行动x，第二阶段的成本q(x,ω)表示为：
其中cost项表示情景ω下第一阶段采取行动x，第二阶段采用行动r的第二阶段成本。
要解决问题（1），有一种方法（SAA，sample average approximation）是采集N个独立样本ω_1,…,ω_N（服从分布π），用如下的样本平均函数近似f：
现在要讨论的问题是，问题（3）的解也是问题（1）中f的一个较优解。进一步定义
如果x^满足上述条件，则说它是函数f的一个α近似最小值解。
PART/3
研究问题
(1) 样本数量需要多少？
(2) 假定预期的准确度为1-ε，置信度为1-δ。给定ε和δ，N要多大才能使得（3）中的最优解有1-δ的概率是函数f的（1+ε）近似最小值解?
PART/4
研究结论
1.假设
（1）非负性
（2）第一阶段行动为空（第一阶段成本最小，但第二阶段会产生极高的成本）
（3）界定膨胀因子（第二阶段的成本——第一阶段不采取行动与第一阶段采取x行动的，相差不会超过λc(x)。
2. 改进的样本复杂度上界
本文提出的改进样本复杂度如定理2所示。
样本复杂度至少为：
才能以1-δ的概率得到1+ε近似优的解。
3. 定理2证明
用Chernoff bound得到引理1：
设置一个阈值M1，将所有的情景ω_1,ω_2,…划分成两个子集，分别表示为高和低。随机分解第二阶段的成本。
令Z*=f(x*)，其中x*是函数f的最小值解。令M1=λZ*/ε，用于将scenarios划分成两类——q(0, ω)≥M1划分为高，其余的划分为低。假定有N个独立样本ω_1,…,ω_N（服从分布π）令，其中
令其中的
期望是关于N个独立样本ω_1,…,ω_N的。因此，
令p=Pr[ω为高]，有
本文证明了：
A+B以一个高概率等于：
令A=A1+A2，其中：
证明了以下claim：
得到：
识别二维码关注我们
文章推荐人 | 付严亮
笔记审核人 | 王子川
校对 | 罗陈斌
排版 | 邹维海
