下载掌阅APP，畅读海量书库
立即打开
在本节中，我们研究了不确定LO问题的RC的“计算状态”。这样的情况是尽可能好的：我们将看到，本质上，只要凸不确定性集 U 本身是计算易处理的，具有不确定性集的不确定LO问题的RC是计算易处理的。前者意味着我们预先知道 U 的仿射包，一个点来自 U 的内部，我们可以访问一个有效成员oracle，给定输入点 u ，记录是否 u ∈ U 。这可以重新表述为一个精确的数学表述；然而，我们将证明这个表述的一个稍受限制的版本，它不需要对复杂性理论进行长时间探索。
我们的策略如下。首先，我们将自己约束在具有特定目标函数的不确定LO问题——回忆1.2.1节中的A部分，通过这个约束我们没有任何损失。其次，我们所需要的是一个不确定线性约束的RC的“计算易处理”表示，也就是说，通过一个有效可验证的凸不等式的显式（和“短”）组对RC的等价表示。给定不确定问题的每个约束条件的RC的表示，并将它们放在一起（参见1.2.1节中的B部分），我们将问题的RC重新表述为在显式凸约束的有限（和短）约束组下最小化原始线性目标函数的问题，以此作为一个计算易处理问题。
接下来，我们首先解释一下用凸不等式组表示约束意味着什么。每个人都明白2个变量的4个约束：
表示非线性不等式
从这个意义上说，式（1.3.2）和式（1.3.1）定义了相同的可行集。那么，以下关于5个不等式的线性不等式组
是否表示与式（1.3.2）相同的集合？在这里，每个人都同意表示成相同集合这一观点，尽管我们不能以前一种方式证明这个观点，因为式（1.3.2）和式（1.3.3）的可行集处在不同空间，因此不能彼此等同。
当谈到优化中的“问题/约束的等价表示”时，其实际含义可以形式化如下。
定义1.3.1
集合
代表集合
，如果
X
+
投影到
x
变量的空间正好是
X
，即
x
∈
X
，当且仅当存在
时，
（
x
，
u
）
∈
X
+
：
X ={ x ：∃ u ： （ x ， u ） ∈ X + }
一个约束组
S
+
（其变量
表示另一个约束组
S
（其变量
），如果前一个组的可行集代表后一个组的可行集。
有了这个定义，很明显组（1.3.3）确实代表约束（1.3.2），更一般地说，是2 n +1个线性不等式的组：
变量 x ， u 表示约束
要理解这种表示有多强大，请注意，要以式（1.3.1）的方式表示相同的约束，也就是说，在没有额外变量的情况下，它将需要多达2 n 个线性不等式。
回到一般情况，假设我们给定一个优化问题
其中
S
i
是变量
x
的约束组，在我们的处理过程中，约束组
的变量为
x
，
v
i
，这表示组
S
i
。显然，问题
等价于式（P）：对于目标函数值相同的（P），每个（P
+
）可行解的
x
分量都是可行的，并且问题中的最优值彼此相等，因此（P
+
）的
最优（根据目标函数）可行解的
x
分量是（P）的
最优可行解。我们应该说，（P
+
）同样代表原始问题（P）。重要的是，表示可以得到原始问题中不存在的期望属性。例如，适当的表示可以将形如
（具有
n
个变量、
m
个线性约束和
k
维向量
p
）
的问题转换为具有
n
+
k
个变量和
m
+2
k
+1个线性不等式约束的LO问题等。我们现在的目标是建立一个能够将半无限线性约束（特别是不确定线性不等式的鲁棒对等项）等价表示为显式凸约束有限组的表示，最终目标函数使用这些表示，以便将不确定LO问题的RC转换为显式（计算上易处理的）凸规划。
概述的策略使得我们能够专注于单个受不确定性影响的线性不等式——数据在不确定性集中变化的线性不等式族
其中不确定性集为
以及这种不确定不等式的RC的“易处理表示”
根据1.2.1节中的C部分所述，从现在起，我们假设相关扰动集 Z 是凸的。
本节从一些案例开始，在这些案例中我们可以“徒手”找到所需表示，具体地说，我们将讨论区间和简单椭球不确定性的案例。
例1.3.2 考虑区间不确定性的情况，其中 Z 在式（1.3.6）中是一个盒。不失一般性，我们可以通过以下假设使情况规范化：
在这种情况下，式（1.3.6）写为
一连串最终最大值显然是
，通过显式凸约束，我们得到了式（1.3.6）的表示：
这反过来又可以得到一个线性不等式组的表示：
例1.3.3 考虑椭球不确定性的情况下， Z 在式（1.3.6）中是一个椭球。我们可以通过假设 Z 近似为以原点为中心、半径为 Ω 的球，来规范化这种情况：
在这种情况下，式（1.3.6）为
我们通过显式凸约束（“锥二次不等式”）得到了式（1.3.6）的表示：
现在考虑一个相当一般的情况，若在式（1.3.6）中的扰动集 Z 由一个锥表示（参考附录A.2.4）：
其中 K 是ℝ N 中的封闭凸尖锥体，ℝ N 内部非空， P ， Q 是给定矩阵， p 是给定向量。在这种情况下，如果 K 不是一个多面体锥，假设这种表示是严格可行的：
定理1.3.4 扰动集 Z 由式（1.3.10）给出，在非多面体 K 的情况下，令式（1.3.11）也成立。则半无限约束（1.3.6）可以表示为变量 x ∈ℝ n ， y =ℝ N 的下列锥不等式组：
其中 K * ={ y : y T z ≥0，∀ z ∈ K }是 K 的对偶锥。
证明 我们有
x 对式（1.3.6）是可行的
最后一个式子表明当且仅当锥规划
的最优值≤ -d [ x ]时， x 对式（1.3.6）来说是可行的。首先，假设式（1.3.11）成立。然后式（CP）是严格可行的，因此，应用锥对偶定理（定理A.2.1），当且仅当（CP）问题
的锥对偶的最优值≤ -d [ x ]时，式（CP）中的最优值≤ -d [ x ]。现在假设 K 是多面体锥。在这种情况下，通常的LO对偶定理（不需要式（1.3.11）的有效性）得出了完全相同的结论：当且仅当式（CD）达到了最优值，并且≤ -d [ x ]，式（CP）的最优值≤ -d [ x ]。换句话说，在定理的前提下，当且仅当式（CD）有 p T y ≤ -d [ x ]的可行解 y 时， x 对式（1.3.6）来说是可行的。
观察到非负象限、洛伦兹以及半定锥是自对偶的，我们从定理1.3.4得到如下推论。
推论1.3.5 设式（1.3.6）中的非空扰动集为：
（i）多面体，由式（1.3.10）给出，在
K
的作用下有一个非负象限
。
（ii）可表示的锥二次，比如，由式（1.3.10）给出，在
K
的作用下有洛伦兹锥
L
k
=
的一个直积
。
（iii）可表示的半正定，由式（1.3.10）给出，在
K
的作用下有半正定锥
。
在（ii）和（iii）的情况下还假定式（1.3.11）成立。然后将具有扰动集 Z 的不确定线性不等式（1.3.4）～（1.3.5）的鲁棒对等（1.3.6）进行等价重新表述，表示为以下显式组：
●线性不等式，在情况（i）下；
●锥二次不等式，在情况（ii）下；
●线性矩阵不等式，在情况（iii）下。
在所有情况下，重新表述的大小是式（1.3.6）中变量的个数和 Z 的锥二次描述的大小，而重新表述的数据很容易通过式（1.3.10）扰动集 Z 的描述数据得到。
评注1.3.6 A .通常，式（1.3.10）中的锥 K 是更简单的 K 1 ，…， K S 的直积，因此采用以下形式表示式（1.3.10）：
在这种情况下，式（1.3.12）成为变量为 x ， y 1 ，…， y S 的锥约束组：
其中
是
K
s
的对偶锥。
B .线性矩阵不等式给出的不确定性集似乎是“奇异的”，然而，它们可以在相当实际的情况下出现，见1.4节。
1.3.3.1 例子
在两种特殊情况下，我们应用定理1.3.4来建立半无限不等式（1.3.6）易于处理的新公式。虽然乍一看，并不自然的“不确定模型”会导致我们去考虑“奇怪的”的扰动集，但稍后就会明白，这些集合是非常重要的——它们支持为随机不确定建模。
例1.3.7 Z 是同心共轴盒和椭球的交点，
其中给定参数 σ ℓ ＞0以及 Ω ＞0。
这里式（1.3.13）变为
其中
●
P
1
ζ
≡[
ζ
；0]，
p
1
=[
0
L
×1
；1]，
，由此，
；
●
P
2
ζ
=[
Σ
-1
ζ
；0]，其中
Σ
=Diag{
σ
1
，…，
σ
L
}，
p
2
=[
0
L
×1
：
Ω
]，
K
2
是维度为
L
+1的洛伦兹锥（由此
）。
设 y 1 =[ η 1 ； τ 1 ]， y 2 =[ η 2 ； τ 2 ]，其中 τ 1 ， τ 2 为1维， η 1 ， η 2 为 L 维，式（1.3.14）成为变量 τ ， η ， x 的约束组：
我们可以从这个组中消除变量
τ
1
，
τ
2
——对于组的每个可行解，我们有
，而用
来代替
τ
1
，
τ
2
仍是可行的。用变量
x
，
z
=
η
1
，
w
=
Σ
-1
η
2
简化组
这也是式（1.3.6）和式（1.3.15）的表示。
例1.3.8
【
不确定性预算
】考虑这种情况，
Z
是
球和
球的交叉点，具体地说，
其中， γ ，1≤ γ ≤ L 是给定的“不确定性预算”。
这里式（1.3.13）变为
Z ={ ζ ∈ℝ L ： P 1 ζ + p 1 ∈ K 1 ， P 2 ζ + p 2 ∈ K 2 }
其中
设 y 1 =[ z ； τ 1 ]， y 2 =[ w ； τ 2 ]，其中 τ 为1维， z 和 w 为 L 维，组（1.3.14）成为变量 τ 1 ， τ 2 ， z ， w ， x 的约束组：
同例1.3.7一样。我们可以消除变量 τ ，得到式（1.3.6）和式（1.3.17）的表示，由变量为 x ， z ， w 的约束组表示：
它可以进一步转化为 z ， w 以及额外变量的线性不等式组。