下载掌阅APP，畅读海量书库
立即打开
考虑机会约束（2.2.3）的情况，其中，关于随机变量 ζ ℓ ，我们知道
是独立的（即
P
是由满足式（2.3.1）的所有分布组成的）。注意，在更为一般的情况下，从给定的以
ζ
ℓ
期望值为中心的有限区间段上取值的独立随机变量
ζ
ℓ
可以通过确定性参数
α
ℓ
，
β
ℓ
进行“缩放”，即
，进而简化为式（2.3.1）（参考评注1.2.2）。
注意机会约束（2.2.2）的主要部分可以重写为
在式（2.3.1）的情况下，对于固定值 x ，随机变量 η 的均值为零，标准差为
机会约束要求式（2.3.2）满足概率大于等于1
。工程师将会对这个要求给予回应，认为一个随机变量“从不”会大于它的均值加上3倍标准差，所以
η
“从不”大于
。我们不需要像工程师那样明确地说，只需说
η
“几乎从不”大于
，其中，
Ω
是数量级为1的“可靠参数”，
Ω
越大，
η
大于上述值的可能性就越小。因此我们得到了随机扰动约束（2.3.2）的一个参数化“保守”版本：
看上去，似乎通过正确定义
Ω
，该约束中的每个可行解都至少以1
-的概率满足了式（2.3.2）中不等式的要求。事实确实如此，稍后将通过简单的分析表明，我们的“工程论证”是合理的。
具体来说，以下步骤是正确的（证明见评注2.4.10和命题2.4.2）。
命题2.3.1 令 z ℓ ， ℓ =1，…， L 是确定性系数， ζ ℓ ， ℓ =1，…， L 是在[-1，1]上取值的均值为零的独立随机变量。对于所有 Ω ≥0，有
作为一个直接的结论，我们得到
进而，我们可以得到如下结果。
推论2.3.2 在式（2.3.1）的情况下，锥二次约束（2.3.3）是机会约束
可计算的易处理保守近似。
特别地，当
时，约束（2.3.3）是机会约束（2.2.2）的一个易处理保守近似。
现在让我们进行以下重要观察：
鉴于例1.3.3可知，不等式（2.3.3）只不过是不确定线性不等式（2.2.1）和式（1.3.5）的RC，其中式（1.3.5）中的扰动集 Z 为球
这一观察值得深入讨论。
A .就其本身而言，假设 ζ ℓ 在[-1，1]上变化（这是式（2.3.1）中假设的一部分内容），作为式（1.3.5）中的扰动集 Z ，建议考虑盒
Box 1 ={ ζ ：-1≤ ζℓ ≤1， ℓ =1，…， L }
对于这个扰动集 Z ，其不确定线性不等式（2.2.1）和式（1.3.5）的相关RC为
（见例1.3.2。）在式（2.3.1）的情况下，“盒RC”保证了“对扰动具有100%的免疫”，这意味着盒RC的每个可行解对于问题中概率为1的随机扰动不等式是可行的。对于和不确定性（2.3.1）相同的随机模型，“球RC”即锥约束（2.3.3）所能保证的“免疫能力”较弱，可以保证“（1-exp{
-Ω
2
/2}）·100%免疫”。注意，请使用适当的
Ω
，“不可靠”exp{
-Ω
2
/2}值可忽略不计：当
Ω
=5.26时，该值小于10
-6
；当
Ω
=7.44时，该值小于10
-12
。在实际应用中，大小为10
-12
的概率和零概率的情况是相同的，所以我们有充分的理由认为，当
Ω
=7.44时，球RC与盒RC一样“实际可靠”
。鉴于两个RC模型的“免疫能力”基本相同，那么比较潜在的扰动集Box
1
和Ball
Ω
的大小便非常有意义。这个比较为我们带来了惊喜：当扰动集的维数
L
并非很小时，具有“一级的”
Ω
的球Ball
Ω
，即
Ω
=7.44，就直径、体积等所有自然尺寸测量而言，比单位盒Box
1
小得多。例如，
●Ball
Ω
和Box
1
的欧氏直径分别为2
Ω
和
；当
Ω
=7.44时，从
L
=56开始，第二个模型的直径比第一个模型的直径大，并且随着
L
的增大，第二个模型的直径与第一个模型的直径的比率逐渐增大至∞；
●球和盒的体积比为
其中，Γ是EulerGamma函数。当 Ω =7.44时，该比率从 L =237开始小于1，并在 L →∞时，以超指数速率变为0。
B .作为一个与A中所述内容相反的论点，我们可以认为当 L 很小时，不确定性集Ball 7.44 基本大于不确定性集Box 1 。当然，这里有一个有趣的对球RC的“修正”，它使这个反论点无效。考虑到当扰动集 Z 是单位盒与以原点为中心、半径为 Ω 的球的交点：
命题2.3.3 不确定线性约束（2.2.1）与不确定性集（2.3.9）的RC等价于锥二次约束模型
在式（2.3.1）的情况下，这个模型中每一个可行解的 x 分量至少以1-exp{ -Ω 2 /2}的概率满足随机扰动不等式（2.2.1）。
证明
式（2.2.1）的RC可表示为式（2.3.10）且扰动集为（2.3.9）的这一事实很容易由例1.3.7给出，其中，
σ
ℓ
≡1。现在让我们证明如果式（2.3.1）发生，且
x
，
z
，
w
是式（2.3.10）的可行解，那么
x
是至少以1-exp{
-Ω
2
/2}的概率满足式（2.2.1）的可行解。事实上，当
时，我们有
因此，对于每一个与式（2.3.1）匹配的分布 P ，我们有
其中，最后一个不等式是由命题2.3.1得到的。
注意，扰动集（2.3.9）从不比扰动集Box 1 大，正如A中所述，对于每一个固定的 Ω ，当扰动向量 ζ 的维数 L 较大时，它比后一个集合小得多。然而，命题2.3.3认为，当扰动向量是随机的且服从扰动集（2.3.1）， Ω =7.44时，与小扰动集（2.3.9）相关的RC的“免疫能力”基本上与100%可靠的盒RC的相同。当我们考虑式（2.2.1）接下来的特殊情况时，这一现象变得更加引人注目： ζ ℓ 是独立的，且其中每一个值以1/2的概率取值±1。在这种情况下，当 L ＞ Ω 2 时，扰动集（2.3.9）甚至不包含随机扰动向量的单个实现。因此，RC（2.3.10）的“免疫能力”不能用基本扰动集包含“几乎所有”随机扰动向量的实现来解释。
C .我们的考虑证明了使用“奇怪”扰动集（如椭球和椭球与超平行体的交点）的合理性：虽然似乎很难想象出从这些扰动集产生扰动的自然扰动机制，但我们的分析表明，在“免疫”时，这些扰动集确实会自然出现针对式（2.3.1）中所述的随机扰动的解。例1.3.8中考虑的“预算”扰动集也是如此。
命题2.3.4 考虑不确定线性约束（2.2.1）在预算不确定情况下的RC：
根据例1.3.8，这时RC模型可以由变量 x ， z ， w 上的约束组
表示。在式（2.3.1）的情况下，该组的每个可行解的
x
分量至少以
的概率满足随机扰动不等式（2.2.1）。
因此，目前的解中
起的作用与
Ω
在命题2.3.3的解中起到的作用是相同的。
证明 令 （ x ， z ， w ） 对式（2.3.12）是可行的，我们有
其中，最后一个≤是通过柯西不等式得到的。因此，
。由于
x
，
z
，
w
满足式（2.3.12），我们有
，该式与式（2.3.12）相结合，表明
x
，
z
，
w
满足式（2.3.10）且
。现在我们可以应用命题2.3.3得出结论，在式（2.3.1）的情况下，
x
能够以大于等于
的概率满足式（2.2.1）。
评注2.3.5
命题2.3.4的证明表明，“预算”RC（2.3.11）比球RC（2.3.3）更为保守（即与更大的扰动集相关），前提是，根据
，预算RC中的不确定性预算
γ
与球RC中的可靠性参数
Ω
相关。问题是：我们为什么要对预算RC感兴趣？命题2.3.4中所表达的关于该RC模型唯一的“好消息”，对于不太保守的球RC来说成立吗？答案是，预算RC可以用线性约束组表示，也就是说，它与潜在的不确定约束（2.2.1）的例子具有相同的“复杂水平”。因此，当对不确定LO问题中的每一个不确定约束使用预算不确定性模型时，该问题的RC本身就是LO问题，因此可以由已经完善的商业LO求解器进行处理。与此相反，球RC（2.3.3）导致了一个锥二次问题，这对计算的要求更高（尽管该问题可以被高效处理）。
例2.3.6 让我们将概述的方法应用于下列单期投资组合选择问题上。
现在一共有200份资产。第200份资产（银行存款）的年回报率为 r 200 =1.05，变动可能性为零。其余资产的年回报率 r ℓ ， ℓ =1，…，199是从期望值为 μ ℓ 的区间段[ μ ℓ -σ ℓ ， μ ℓ + σ ℓ ]中取值的独立随机变量；其中，
我们的目标是在资产之间分配1美元，以最大化所产生投资组合的风险值，所要求的风险水平是
。
我们希望解决不确定LO问题
其中， y ℓ 是投资于第 ℓ 份资产的资金。不确定数据是年回报率 r ℓ ， ℓ =1，…，199，它们的自然参数是
r ℓ = μℓ + σ ℓ ζℓ
其中， ζ ℓ ， ℓ =1，…，199是在[-1，1]上变化的均值为零的独立随机扰动。设 x =[ y ； -t ]∈ℝ 201 ，问题变成了最小化 x 201 ，受以下约束
其中，
这个问题中唯一的不确定约束是不等式（2.3.13. a ）。我们考虑了3个扰动集以及与式（2.3.13）相关的鲁棒对等。
（i）盒RC忽略了影响不确定不等式的扰动集的随机性信息，仅仅利用了扰动集在[-1，1]上变化的信息。式（2.3.13. a ）的基本扰动集 Z 为
（ii）由命题2.3.3给出的球-盒RC，其保守参数为
该式确保鲁棒最优解至少以1-
=0.995的概率满足受不确定性影响的约束。式（2.3.13.
a
）的基本扰动集
Z
是
（iii）由命题2.3.4给定的预算RC，其中，不确定性预算
其所能保证的概率结果与球-盒RC相同。式（2.3.13. a ）的基本扰动集 Z 是
盒RC 。不确定不等式的相关RC由式（2.3.8）给出；经过直接计算，由式（2.3.13）得到的RC模型就变成了LO问题
正如预期的那样，这只是我们不确定问题的实例，对应于不确定年回报率最坏的可能值 r ℓ = μℓ-σ ℓ ， ℓ =1，…，199。由于这些值小于保证的资金回报率，鲁棒最优解规定将我们的初始资金存放在银行，保证年回报率为1.05，即保证5%的收益。
球-盒RC 。不确定不等式的相关RC由命题2.3.3给出。由式（2.3.13）得到的RC是如下锥二次问题
鲁棒最优解的值为1.1200，意味着在风险值低至
=0.5%时，可以获得12.0%的收益。资金之间的资产分配如图2-1所示。
图2-1 展示了例2.3.6单期投资组合选择问题的鲁棒最优解。沿着 x 轴：坐标1，2，…，200表示资产。a：预期的回报率，b：回报率值域的上下端点，c：球-盒RC模型的投资资金，%，d：预算RC模型的投资资金，%
预算RC 。不确定不等式的相关RC由命题2.3.4给出。由式（2.3.13）得到的RC是如下LO问题
鲁棒最优解的值为1.1014，意味着在风险值低至
=0.5%时，可以获得10.1%的收益。资金之间的资产分配如图2.1所示。
讨论 。首先，我们看到随机性信息是多么有用——在风险低至0.5%的情况下，球-盒RC（12%）和预算RC（10%）产生的投资组合收益的风险值是盒RC（5%）所保证收益的两倍。还请注意，球-盒RC和预算RC都建议采用“积极的”投资决策，而盒RC建议将初始资金保留在银行中。另外，预算RC比球-盒RC更加保守。最后，我们应该记住，球-盒RC和预算RC提供的投资组合设计相关的实际风险（即，实际年总回报低于相应鲁棒最优解计算得到的回报的概率）大部分为0.5%，且可能低于该值；实际上，问题中这两种RC都利用了机会约束
的保守近似。
发现实际风险有多小是件很有趣的事。当然，答案取决于不确定回报率的实际概率分布（回想一下，在我们的模型中，我们只假设了已知这些分布的部分信息，特别是这些分布的支持和期望信息）。假设“现实中”的 ζ ℓ ， ℓ =1，…，199，仅取极值±1，概率各为1/2，并利用1000000个实例作为样本进行蒙特卡罗模拟，我们发现，按系数为10来计算时，“球-盒”的投资组合的实际风险小于要求的0.5%的风险值，“预算”模型的投资组合，按系数为50来计算时，其实际风险也小于要求的0.5%的风险值。根据这一观察结果，我们似乎可以通过“调整”参数来降低模型的保守性，也就是说，用更大的值替换RC中所要求的风险值，并且希望由此产生的实际风险（可以通过模拟来估计）仍然低于所要求的水平。通过这种调整，将式（2.3.16）中的可靠性参数 Ω =3.255降低至 Ω =2.589，最后得到鲁棒最优解的值为1.1470（即，得到了14.7%的收益，而不是最初的12.0%），同时保证经验风险（根据500000个以上的实际样本进行估计）仍然低至0.47%。同样，将式（2.3.17）中的不确定性预算 γ =45.921降低至 γ =30.349（即，将收益由10.12%增加至13.95%），同时经验风险降低至0.42%。
例2.3.7 考虑以下问题。
信号恢复 。给定信号 s ∈ S ={ s ∈ℝ n ： s i =±1， i =1，…， n }的间接观测值
（
A
是一个给定的
m
×
n
矩阵，
ξ
～
N
（0
，
I
m
）是观测噪声，
ρ
≥0是一个确定性的噪声水平），求信号的一个估计值
：
如下要求应当被满足：
这里的
＜＜1是给定的容差，且sign[
v
]以坐标态的方式作用：sign[[
v
1
；…；
v
n
]]=[sign（
v
1
）；…；sign（
v
n
）]。
根据式（2.3.18），被观测信号
s
∈
S
可以被当作一个有意义的蜂窝通信模型（在一定程度上有所简化）。还请注意一下，式（2.3.19）形式的信号估计是具有一定实用性的——虽然从对噪声的敏感性角度来看，这不是最好的估计方法，但由于其计算简单，这一方法在实际中经常被使用。最后，让我们解释一下式（2.3.19）背后的原理。假设
s
是随机高斯信号（与
ξ
无关），且均值为零，从均方误差的角度出发，最佳信号恢复方法实际上是线性的：
=
Gu
，
G
是定义的适当矩阵（也叫作维纳滤波器）。工程师经常把简单问题的最优解作为更复杂问题的“实际解”，维纳滤波器也不例外。根据式（2.3.18）得到的线性估计量
Gu
通常应用于不是零均值高斯信号
s
的情况中。现在，当我们提前知道
s
是一个±1向量时，我们尝试用如下方法来改进线性估计量
Gu
：假设
Gu
与
s
之间的距离并非太远（即，
Gu
与
s
之间典型欧几里得距离小于1），则向量sign[
Gu
]“等典型地”将是精确的
s
。综上所述，让我们把信号恢复问题作为一个数学难题来对待。我们的第一个观察是直接的：
式（2.3.20）的一个充要条件是
其中，
是
G
的第
i
行，ErfInv是由以下关系式定义的逆误差函数：
事实上，假设 G 满足式（2.3.20）。那么对于所有 i ≤ n ，我们有
仅当 g i ≠ 0 时，后者是成立的（否则该式左边的概率为1），且等价于
由于
，该式又等价于
我们可以看到式（2.3.21）在其中体现出来了。反之亦然，如果产生了后一种关系式，那么，将上述推理颠倒过来，我们就会看到
由于 ξ 是对称分布的，所以后一个关系式等价于式（2.3.20）。观察到当 ρ ＞0时，式（2.3.21）清楚地表明 （ GA ） ii ＞0。将 G 中的行乘以适当的正值常数，我们可以将 G 归一化，对所有的 i ，有 （ GA ） ii =1成立，而且这种归一化显然不会影响式（2.3.21）的有效性。由此可知，我们所关心的问题等价于如下优化问题
注意，虽然这个问题不是完全凸的，但其在计算上是易处理的：对于每一个正的 ρ ，右边的约束模型是 G 中有效可计算的凸约束模型，我们可以有效地检查它是否可行。如果它对一个给定的 ρ 是可行的，那么它对所有更小的 ρ 也是可行的，所以对于这个组可行的最大 ρ 值（这正是我们想要找到的 ρ ）可以很容易地通过二分法求得其高精度的近似值。我们将要证明实际上不需要使用二分法——我们的问题有一个封闭形式的解。具体来说，以下方法是正确的。
命题2.3.8 当且仅当矩阵 A 的秩等于 n （信号 s 的维数）， ρ ＞0时，问题（2.3.23）有一个可行解，在这种情况下式（2.3.23）的最优解如下：
● G 是 A 的伪逆矩阵，也就是说， n × m 矩阵转置的行属于 A 的像空间，且 GA = I （这些条件唯一定义 G 矩阵）；
●
。
证明
首先，通过观察，我们发现，如果Rank
（
A
）
＜
n
，则问题（2.3.23）没有
ρ
＞0条件下的可行解。事实上，假设Rank
（
A
）
＜
n
并且（
ρ
＞0，
G
）
是这个问题的一种可行解，那么矩阵
GA
的像
L
⊂ℝ
n
是ℝ
n
的一个固有线性子空间，因此它不与2
n
个象限ℝ
κ
={
s
：
κ
i
s
i
≥0，1≤
i
≤
n
}，
κ
i
=±1中至少一个象限存在内部相交情况。事实上，存在一个与
L
正交的非零向量
e
；当
e
i
≠0时，设
κ
i
=sign（
e
i
），当
e
i
=0时，
κ
i
=1，我们确保对所有的
f
∈intℝ
κ
，有
e
T
f
＞0，使得
L
不能与intℝ
κ
相交。因此，存在
κ
∈
S
时，
L
不与intℝ
κ
相交的情况，这意味着，至少有一个
i
满足
（
κ-GAκ
）
i
≥1。另外，
（
G
，
ρ
）是式（2.3.23）的可行解，意味着
；这些关系清楚地表明了我们想要的矛盾
。
现在假设Rank
（
A
）
=
n
，因此存在
A
的伪逆矩阵，记为
G
†
。设
ρ
*
=（ErfInv（
）·
，我们可以得到式（2.3.23）的一个可行解（
ρ
*
，
G
†
）。让我们来证明这个解是最优的。为此，假设式（2.3.23）存在一个可行解
，让我们将这个假设引入到一个矛盾中。令
a
i
，
i
=1，…，
n
为
A
的列，
是
G
†
的行。由于
G
†
A
=
I
，因此
令
是
的行。我们可以观察到，不失一般性地假设
属于
A
的像空间。事实上，可以通过在
A
像空间上的正交投影来替换
中的（转置的）行。我们不改变
而且不增加
中行的欧几里得范数并因此保留了
对式（2.3.23）的可行性。进一步，由
可得
，因此对所有的
i
，有
。现在到了最后一步：对每一个
i
，我们都有
，对于部分
i
而言，不等关系为等式关系；不失一般性地，我们假设
现在，令
则
f
（
g
1
）=1。我们认为
。事实上，设
ν
=
ρ
ErfInv（
），有
该严格不等式由
和
ν
＞
ν
*
得到，且该结论不等式从
出发，对式（2.3.23）是可行的。现在，向量
属于
A
的像空间，而且该像空间是由向量
g
1
，…，
g
n
张成的。实际上，根据伪逆矩阵的定义，向量
g
i
属于这个空间；根据
G
†
As
=
0
而不是
G
†
As
=
s
≠
0
，若它们线性张成的空间小于
A
的像空间，则存在向量
As
，
s
≠
0
，正交于
g
1
，…，
g
n
。由此可见，对于部分
r
k
，有
由于
，我们有
r
1
=0，也就是说，
。我们现在得到了想要的矛盾
命题2.3.8给我们带来了好消息和坏消息。好消息是，解决这个问题的方法简单而自然；坏消息是，当
A
是病态时，该命题所建议的最优方案得到的最优恢复结果仍然较差，因为“直接恢复”
将会增大噪声。在表2-1中，我们给出了目前对两个随机生成的32×32的矩阵
A
的数值结果：首先，从
N
（0，1）分布中进行条目抽样，然后，我们用相同的方式生成矩阵，但是需要将该矩阵的某一列乘以一个较小的数使得该矩阵处于病态。这个实验表明了我们的近似值有多精确：对于第一个矩阵，
ρ
=0.0122（这保证了精确恢复的概率至少达到0.999），100000份实验样本中有3份恢复错误，这意味着在这种噪声水平条件下，真正的错误概率几乎不低于10
-5
；同时，在噪声水平为0.75
ρ
（10
-3
）的条件下，错误概率被证明是小于10
-6
的。
表2-1 信号恢复问题中两个实例的噪声临界水平值
我们能“打败”由 A 的伪逆矩阵给出的直接恢复吗？答案是肯定的，只要我们稍微限制一下实验信号集合 S 即可。例如，假设我们的信号 s 是坐标为±1的向量，并且在 s 的项中，至少有 k 个1和 k 个-1；这里 k ≤ n /2是一个给定的整数。令 S k 是所有这种类型信号的集合（在这种表示法中， S 0 表示 S ）。对式（2.3.23）的推导过程可以由 S k 替换 S ，得到问题的等价重新表述是
与 k =0的情况唯一的区别是在计算方面
当
k
=0时，该计算值为
。现在，这个计算值的形式为
其中，
是ℝ
n
-1
中的坐标为±1且至少有
k
-1个坐标为-1以及至少有
k
个坐标为1的所有向量的集合。事实上，我们有
为了计算
F
，请注意
是多面体
极值点的集合。
因此，
其中，结论等式由线性规划对偶定理给出。由此可知式（2.3.24）等价于显式计算易处理的优化问题
对于这个问题，封闭解似乎是不可能实现的；然而，在命题2.3.8之前提出的基于二分法的方法可以有效地解决这个问题。该问题的最优解得到的恢复结果是否“优于”基于
A
伪逆矩阵的直接恢复结果，取决于
A
的“几何结构”。实验表明，对于随机生成的矩阵
A
，这两个解的效果基本相同。同时，对于特殊的矩阵
A
，基于式（2.3.25）的最优解的恢复方法大大优于“直接”恢复方法。例如，考虑这种情况：
A
靠近超平面
上的正交投影
P
，具体来说，
其中， 1 是全1向量。该矩阵与 P 的靠近程度由 γ 控制——这个参数越接近于0，则 A 越接近于 P 。在表2-2中，我们给出了当 n =32， k =1， A = A γ ， γ =0.005和 γ =0.001时的实验数值结果。
表2-2
A
在超平面
及
k
=1上近距离投影的实验
我们可以看出，为了确保恢复的可靠性达到0.9999，基于 G † = A -1 的方法所要求的噪声水平本质上比基于式（2.3.25）的最优解所要求的噪声水平更小。例如，在 γ =0.001，噪声水平在0.0135的条件下，基于 G † 的方法在10000个实例样本上估计，恢复的错误率高达0.68（即使噪声水平降低1/2，恢复的错误率也仍然达到了0.42）。与此相反，在噪声水平为0.0135的条件下，基于式（2.3.25）的方法被证明可以实现可靠性达到0.9999的恢复。注意，这种明显的性能优势是通过禁止2 32 =4294967296个坐标为±1的信号而得到的，即所有坐标为1的信号和所有坐标为-1的信号。
需要补充的是，“缺陷”观测式（2.3.18）（例如，Rank （ A ） ＜ n ）的信号 s ∈ S 0 高度可靠恢复的问题本身并不一定是病态的。例如，考虑 m =Rank （ A ） = n -1这种情况。然后通过以下序列变换方法获得 s 的观测值：（a）投影到超平面上 （ A 零空间的正交补），（b）对投影应用可逆线性变换，（c）对结果添加噪声。从观测结果中恢复 s ∈ S 0 的可能性取决于（a）中的投影限定在单位立方体的顶点集上时是否为一对一的映射。无论这种情况是否为真实的（当 A 处于“一般位置”时确实如此），只要没有噪声，我们就可以从观测中准确地恢复信号，因此，只要噪声水平足够低，我们就可以以任意高的可靠性恢复信号。什么是不可能的呢？——将噪声水平独立开来！——对式（2.3.19）形式的信号做到无差错恢复。