鲁棒优化最新章节_阿哈龙·本-塔尔著

4.2 机会约束的Bernstein近似

这个近似方案与我们在2.4节中使用的近似方案密切相关，回顾这个方案对我们开始熟悉Bernstein近似具有指导意义。

我们的目标是建立一个机会约束（4.0.1）的保守近似。为了实现这一目标，我们有以下方法。

1）我们假设 ζ _ℓ ， ℓ =1，…， L 与分布 P _ℓ 是独立的，使得

因此

2）我们已经从式（4.2.1）中推断出关系

的有效性是式（4.0.1）有效性的充分条件（2.4节中的陈述（*））

3）最后，我们从（2）中得到了充分条件，等价于关于以下不确定线性不等式

的[ z ₀ ；…； z _L ]的鲁棒可行性，其中使用适当选择的扰动集 Z （2.4节中的陈述（**））。

我们将要证明，概述的近似方案是一个更一般的特殊情况，即Bernstein近似。

4.2.1 Bernstein近似：基本观察

我们有以下假设。

问题1 式（4.0.1）中随机扰动 ζ =[ ζ ₁ ；…； ζ _L ]的分布 P 是

已知凸函数 Φ 在ℝ ^L 上处处有限且满足 Φ （0） =0。

例4.2.1 可以立即看到，在2.4节P.1～P.2的假设下（或者在上面第1项的同样假设下），关系（4.2.3）满足

给定 ∈（0，1），我们可以设置

Bernstein近似方案由以下表述给出。

命题4.2.2 在式（4.2.3）的假设下，是以下凸不等式的解集

并且这个凸不等式是机会约束（4.0.1）的标准保守近似。

对于此命题的证明，请看附录B.1.1。

我们目前的目标是制定一个方案，在有利的情况下，允许我们有效地描述集合。

4.2.2 Bernstein近似：对偶化

除了问题1，我们还有以下假设。

问题2 我们可以将式（4.2.3）中的凸函数 Φ 表示为以下形式：

其中，

● ϕ （ u ） 是关于ℝ ^M 的凸的下半连续函数，其值取实数并且趋于+∞。

● 是从ℝ ^M 到ℝ ^L 的一个仿射函数。

●每个水平集 U _c ={ u ： ϕ （ u ） ≤ c }， c ∈ℝ，其中 ϕ 是有界的。

注意在ℝ ^L 处处凸且有限的函数 Φ （·）都有一个必要的表示，例如，可以表示为

事实上，已知由后一种关系给出的函数 ϕ 是一个凸的下半连续函数，函数是关于 Φ 的勒让德变换（或Fenchel对偶，或共轭），

关于 ϕ 具有有界水平集的要求，在式（4.2.8）的情况下，这个要求很容易由 Φ 处处有限这一事实给出。以下众所周知的事实暗示了这一点。

命题4.2.3 由式（4.2.7）可知 Φ （·）和 ϕ （·）相连接， Φ 处处被定义，并且 ϕ 是下半连续的。假设 A 具有平凡核，则 ϕ 的水平集合有界。

此命题的证明见附录B.1.2。

例4.2.4 【 例4.2.1续 】函数（4.2.4）对式（4.2.7）有明确的表示，表示如下：

即

4.2.3 Bernstein近似：主要结果

概述的假设导致以下结果。

定理4.2.5 考虑机会约束不等式（4.0.1），并假设随机向量 ζ 的分布 P 满足假设问题1～2。集合

是一个非空凸紧集，并且对于式（4.2.5）给出的集合 Z _ϵ 有

特殊地，根据命题4.2.2，

是 z 满足机会约束（4.0.1）的充分条件，即 z 是以下不确定线性约束的鲁棒可行解的条件。

其中 z ₀ ， w 是变量，集合是式（4.2.11）给出的扰动集。

该命题的证明见附录B.1.3。

在式（4.2.11）中不确定性集在两个方面被定义：函数 Φ （·）、它的表示（4.2.7）以及表示的数据不是由 Φ 唯一定义的。然而，集合仅仅依赖于 Φ （·）。事实上，集合仅仅由 Φ 定义，因此凸紧集的支持函数可以仅基于 Φ 被表示。由式（4.2.11），

需要注意的是，闭合非空凸集的支持函数完全决定了这个集合（见文献[100]，第13章）。

底线如下。

每一个凸上界 Φ （ w ） ：ℝ ^L →ℝ， Φ （0） =0，对于随机扰动向量 ζ 的分布的对数矩生成函数

暗示了机会约束不等式的保守标准近似（4.0.1）。在问题2的假设下，这种近似形式为，其中被适当地定义为非空凸紧集。这种近似是不确定不等式 z ₀ + 在扰动集作用下的RC。

后一个结果扩展了2.4节中的结果，其中我们限制 Φ 为特定形式（4.2.1）。

例4.2.6 【 例4.2.4续 】观察在假设P.1～P.2下，定理4.2.5恢复了定理2.4.3。

4.2.4 Bernstein近似：示例

例4.2.7 【 高斯案例 】假设我们所知道的关于随机向量 ζ 的分量 ζ _ℓ 是独立的高斯随机变量，其均值 μ _ℓ 属于给定的区间并且变量属于区间， ℓ =1，…， L 。在这种情况下，可以得到以下结论。

（i）满足问题1并且涉及与上述信息相容的 ζ 所有分布的最佳（即最小）函数 Φ （ w ） 为

（ii）设置

对于（i）中给出的函数 Φ ，我们保证了问题2的有效性。

（iii）与概述的数据相关联的机会约束（4.0.1）的Bernstein近似，正是定理2.4.3给出的近似，参见例2.4.5。

例4.2.8 假设我们所知道的随机扰动 ζ _ℓ 是独立的，在区间[-1，1]上取值，它们的均值属于[-1，1]的给定子区间（参见例2.4.9）。在例2.4.9的陈述中，满足问题1并且涉及与上述信息相容的 ζ 所有分布的最佳（即最小）函数 Φ （·）为

很容易看出

由于一个直接的等式

这种关系表明

其中

它遵循设置

其中 ϕ _ℓ （·）是由式（4.2.14）给出的，我们得到了式（4.2.12）给出的函数 Φ （ w ） 的表达式，这是问题2中所要求的。由Bernstein近似给出的扰动集与概述的数据相联系，其中扰动集为

例4.2.9 考虑到例4.2.8描述的情况，假设对于所有的 ℓ ，都有（也就是说， ζℓ 是独立随机变量，均值为0，取值范围为[-1，1]）。让我们通过下面的实验来比较例2.4.9中机会约束（4.0.1）的保守近似和该约束的Bernstein近似。

（i）我们设置 z ₁ =…= z _L =1，假设 ζ 的“真实”分布（建立近似时未知）是单位盒顶点上的均匀分布，并考虑机会约束优化问题

（ii）将（ P ）中的机会约束替换为它的保守近似，我们将（ P ）替换为一个易于处理的近似问题，该问题具有易于计算的最优值，即Opt（）的下界。让我们绘制并互相比较（ P ）的真正最优值（这意味着当 z ₁ =…= z _L 时易于计算），并比较对于以下近似得到的下界关于的函数Opt（）的依赖性：