下载掌阅APP，畅读海量书库
立即打开
在不确定线性优化问题的背景下，处理随机数据不确定性最直接的方法是由年代久远的机会约束概念（见文献[40]）提出的。考虑一个不确定线性不等式
（参考式（1.3.4）和式（1.3.5））并假设扰动向量
ζ
是随机的，概率分布
P
是完全已知的。理想情况下，我们希望使用候选解
x
，使有效约束的概率为1。然而，这个“理想目标”意味着要回到扰动的不确定但有界模型上；事实上，很容易看出，当且仅当
x
是鲁棒可行解且扰动集是以
P
支持的闭凸包时，可以为几乎所有
ζ
的实现找到一个满足式（2.2.1）要求的
x
。利用随机性扰动的唯一有意义的方法是，对于一个候选解
x
，要求其能满足
ζ
的“几乎所有”实现的约束条件，具体来说，至少需要以1-
的概率满足约束，其中
∈（0，1）是预先指定的较小容差。该方法与随机扰动约束（2.2.1）以及机会约束
相关，其中
是与分布
P
有关的概率。注意式（2.2.2）是一个普通的确定性约束。将不确定LO问题中所有受不确定性影响的约束替换为机会约束，并最小化这些约束下的目标函数（不失一般性地，我们可以假设是确定的），最终得到（LO
U
）的机会约束问题，即一个确定性优化问题。
上述方法似乎很自然，但它有一个严重的缺点——通常会导致NP难问题。原因有两个方面：
●通常，即使在P很简单的情况下，也很难高精度估计约束（2.2.2）左边的概率。
例如，文献[68]中表明，当
ζ
ℓ
独立且均匀分布在[-1，1]上时，对约束（2.2.2）左边概率的计算已经是NP难问题了。这意味着，除非P=NP，否则没有算法可以做到在输入一个给定的有理数
x
，有理数
和有理数
δ
∈（0，1）时，可以在给定精度
δ
的范围内，以多项式的时间估计
p
（
x
）
。除非
ζ
在一个中等基数的有限集中取值，否则唯一已知估计
p
（
x
）
的一般方法是基于蒙特卡罗模拟的；然而，这种方法要求样本的基数为1/
δ
，其中
δ
是所需的估计精度。由于该精度有意义的取值范围是小于等于
的，因此，我们得出结论，在实际情况下，当
大概为0.0001或更小时，蒙特卡罗方法使用起来较为困难。
●通常情况下，约束（2.2.2）的可行集是非凸的，这使得机会约束下的优化问题非常棘手。
注意，虽然上述第一个难题只会在
非常小的情况下出现，但是第二个难题使得机会约束优化对于“大”
来说也是难以实现的。
本质上，唯一已知没有出现上述困难的情况是
ζ
为一个高斯随机向量且
小于1/2。
由于与机会约束相关的计算难以实现，那么，一个很自然的做法是用其计算上易处理的保守近似来代替机会约束。保守近似的概念定义如下。
定义2.2.1
令
，
P
，
是机会约束（2.2.2）的数据，并令
S
是
x
和附加变量
v
上的一个凸约束组。如果
S
的每一对可行解
（
x
，
v
）中的
x
分量是满足机会约束的可行解，那么，我们认为
S
是机会约束（2.2.2）的保守凸近似。
如果形成 S 的凸约束可以被高效计算的话，那么约束（2.2.2）的保守凸近似 S 可理解为易于计算的。
很明显，将给定机会约束优化问题中的机会约束替换为其保守凸近似，我们最终得到了关于 x 和附加变量的凸优化问题，即机会约束问题的“保守近似”模型：对于机会约束问题，每个近似可行解的 x 分量都是可行的。如果所讨论的保守凸近似是易处理的，则上述近似是可高效计算约束的凸规划，因此可以被高效处理。
在接下来的内容中，当谈到保守凸近似问题时，为了简洁起见，我们将“凸”视为“默认”条件并省略不写。
机会约束（2.2.2）与随机扰动约束（2.2.1）以及给定的随机扰动分布 P 是相关联的，并且当我们知道这个分布时，使用这个约束便是合理的。事实上，我们通常只知道 P 的部分信息，也就是说，我们只知道 P 属于一个给定的分布族 P 。在这种情况下，将式（2.2.2）变为模糊机会约束
是有意义的。
当然，对机会约束的保守易处理近似的定义可以直接扩展到模糊机会约束的情况。在接下来的内容中，我们通常跳过形容词“模糊”，其确切含义取决于我们讨论的分布 P 的信息是部分已知还是完全已知的。
接下来，我们提出了一个简单的方法来实现机会约束问题的保守近似。