【鲁棒优化】| 论文笔记：The Price of Robustness - 列不确定性部分的推导

作者：刘兴禄，清华大学，博士在读

欢迎关注我们的微信公众号 运小筹

前言

• 最近读者群的一个小伙伴问到了一个关于鲁棒优化经典论文中理论推导的一个小问题。该问出自近些年鲁棒优化中最为经典的论文之一：《The Price of Robustness》。
• 我仔细地回答了这个问题，给出了本问题的一个完整、详细的推导，还专门写成了笔记。个人觉得比较有趣，这里分享给大家，希望对大家有帮助。
• 这位读者问的问题，只根据当前文献，确实有些细节拿捏不到(但是依然可以推出来)，只有结合了另外两篇更先前的论文才能顺理成章的把问题讲的更清楚。我之前读这里的时候也没有这么细究，就直接想当然的过去了，现在看来当时也是有些读得粗糙了。所以在此，我也非常感谢这位读者的提问。另外，文中涉及到提问者自己上传的图片，也是获得了使用许可的。

问题：column-wise uncertainty的模型为什么是这样？来自论文原文

这位读者的问题来源于下面的图片。

(图片来自文献：Bertsimas D, Sim M. The price of robustness[J]. Operations research, 2004, 52(1): 35-53.)

• 问题
  为什么图中column-wise uncertainty下的模型是这样的？具体来讲，就是为什么会有$-y_j⩽x_j⩽y_j$这个约束？以及下面的部分是怎么推出来的？比如最优解时一定有$y^{\ast }=|x^{\ast }|$，为什么？

这个问题看似不难，不就是很明显令$y=|x|$就行嘛。但是其实是有一些隐藏细节的。

第一次看到这个问题，第一个回答者给出的解答如下图：

我当时也是这么认为的，另外由于忙着改书，并且也觉得这个回答确实是对的，没问题，就没仔细研究。

直到这位同学再次发出疑问：

(图片来自某读者)

由于没人回答，我好奇看了一眼。之后答应这位读者回答他。但是我仔细过了一遍，也觉得确实有值得探索的地方。

我自己的推导：所有详细步骤全部列举出来了

$$\begin{array}{rlrl}\max & \sum _j{c}_j{x}_j& & \\ s.t.& \sum _j{a}_{ij}{x}_j+\sum _{j\in J_i}{\hat{a}}_{ij}{y}_j⩽b_i,& \forall i& \\ & -y_j⩽x_j⩽y_j,& & \forall j\\ & \mathbf{l}⩽\mathbf{x}⩽\mathbf{u}& & \\ & \mathbf{y}⩾0& & \end{array}$$

我们整理约束1，得到
$$\begin{array}{rl}& \sum _j{a}_{ij}{x}_j+\sum _{j\in J_i}{\hat{a}}_{ij}{y}_j⩽b_i\\ ⟺& \\ & \sum _{j\in J_i}\left(a_{ij}{x}_j+{\hat{a}}_{ij}{y}_j\right)+\sum _{j\notin J_i}{a}_{ij}{x}_j⩽b_i\end{array}$$

且约束其实等价于下面的形式
$$\begin{array}{rlrl}& -y_j⩽x_j⩽y_j,& & \forall j\\ ⟺& & & \\ & |x_j|⩽y_j,& & \forall j\end{array}$$

由于

1. $y_j⩾|x_j|$；
2. 目标函数是$\max cx$

• 根据1， 2，可得，最优解中，一定有$y^{\ast }=|x^{\ast }|$。

这个说起来很直观，但是我还是来证明一下：

命题：考虑下面的问题
$$\begin{array}{rlrl}\max & \mathbf{c}\mathbf{x}& & \\ s.t.& \sum _j{a}_{ij}{x}_j+\sum _{j\in J_i}{\hat{a}}_{ij}{y}_j⩽b_i,& \forall i& \\ & y_j⩾|x_j|,& & \forall j\\ & \mathbf{l}⩽\mathbf{x}⩽\mathbf{u}& & \\ & \mathbf{y}⩾0& & \end{array}$$
则在最优解中，一定有$y^{\ast }=|x^{\ast }|$。

证明：
（反证法）假设最优解为$({\mathbf{y}}^{\ast },{\mathbf{x}}^{\ast })$, 根据约束，他们一定满足${\mathbf{y}}^{\ast }⩾|{\mathbf{x}}^{\ast }|$。

这里包含且仅包含两种情形：${\mathbf{y}}^{\ast }>|{\mathbf{x}}^{\ast }|$或者${\mathbf{y}}^{\ast }=|{\mathbf{x}}^{\ast }|$。

如果最优解满足：${\mathbf{y}}^{\ast }>|{\mathbf{x}}^{\ast }|$， 约束2显然满足。

我们再来看约束1。
$$\begin{array}{rl}\sum _j{a}_{ij}{x}_j^{\ast }+\sum _{j\in J_i}{\hat{a}}_{ij}{x}_j^{\ast }<\sum _j{a}_{ij}{x}_j^{\ast }+\sum _{j\in J_i}{\hat{a}}_{ij}{y}_j^{\ast }⩽b_i,& \forall i(\ast )\end{array}$$
由于我们的目标函数是$\max \mathbf{c}\mathbf{x}$，而$(\ast )$式显示，一定$\exists x_j^{\ast }$还有可以增大的空间，因此我们有，必然$\exists (\bar{\mathbf{y}},\bar{\mathbf{x}})$使得原问题可行（这里其实更专业的写法是写成$\exists (\bar{\mathbf{y}},\bar{\mathbf{x}})\in \mathbf{S}$，其中$\mathbf{S}$表示上述问题的可行域，意思就是说这个也是个可行解。这里我只是提及一下）， 并且使得$\bar{\mathbf{x}}$中所有分量都不小于${\mathbf{x}}^{\ast }$的分量，即
$${\bar{x}}_j⩾{\bar{x}}_j^{\ast },\forall j$$。并且至少存在一个分量大于${\mathbf{x}}^{\ast }$的分量，即并且$\exists j^{\prime }$，满足$${\bar{x}}_{j^{\prime }}>x_{j^{\prime }}^{\ast }$$
由于$(\bar{\mathbf{y}},\bar{\mathbf{x}})$是可行解，因此满足 （实际上这一句可以不要）
$$\begin{array}{r}\sum _j{a}_{ij}{\bar{x}}_j+\sum _{j\in J_i}{\hat{a}}_{ij}{\bar{y}}_j⩽b_i\end{array}$$
因此，可行解$(\bar{\mathbf{y}},\bar{\mathbf{x}})$必然导致$\mathbf{c}\bar{\mathbf{x}}>\mathbf{c}{\mathbf{x}}^{\ast }$，从而推出$({\mathbf{y}}^{\ast },{\mathbf{x}}^{\ast })$不是最优解。这与原假设矛盾。
所以，若$({\mathbf{y}}^{\ast },{\mathbf{x}}^{\ast })$为问题的最优解，则一定满足${\mathbf{y}}^{\ast }=|{\mathbf{x}}^{\ast }|$。原命题得证。

在下面的讨论中，我们就直接不加证明地使用这个结论了。

但是这个为什么就要做这个线性化了呢，现在的版本不都是$(a_{ij}+z_{ij}{\hat{a}}_{ij})x_j$吗，其中 ($-1⩽z_{ij}⩽1$)，这里一般都不是绝对值呀，都没怎么见过$(a_{ij}{x}_j+{\hat{a}}_{ij}|x_j|)$这样的形式，这里我比较好奇，想去探索一下。

一些探索：约束表达式为什么会是$(a_{ij}{x}_j+{\hat{a}}_{ij}|x_j|)$的形式

约束表达式为什么会是$(a_{ij}{x}_j+{\hat{a}}_{ij}|x_j|)$的形式？

为了搞明白这个问题，我就去调研了两篇更早的文献：

[1]: Ben-Tal A, Nemirovski A. Robust solutions of linear programming problems contaminated with uncertain data[J]. Mathematical programming, 2000, 88(3): 411-424.
[2]: Soyster A L. Convex programming with set-inclusive constraints and applications to inexact linear programming[J]. Operations research, 1973, 21(5): 1154-1157.

我从文献[1]中找到了答案。主要是根据这一段的内容：

(图片来自文献：Ben-Tal A, Nemirovski A. Robust solutions of linear programming problems contaminated with uncertain data[J]. Mathematical programming, 2000, 88(3): 411-424.)

以下推导，全部都省去了原论文中右端项$\delta \max [1,b[i]]$这一项。请读者周知。

上图定义了，具有不确定性的约束系数$a_{ij}$的真实值${\tilde{a}}_{ij}$的范围是$[a_{ij}-ϵ|a_{ij}|,a_{ij}+ϵ|a_{ij}|]$，因此就有
$$\begin{array}{r}|{\tilde{a}}_{ij}-a_{ij}|⩽ϵ|a_{ij}|\end{array}$$

我们令不确定的列的下标集合为$J_i$，因此约束可以写成

$$\begin{array}{r}\sum _{j\notin J_i}{a}_{ij}{x}_j+\sum _{j\in J_i}{\tilde{a}}_{ij}{x}_j⩽b_i,\forall i\end{array}$$

接下来就开始正式推导。

我们做一个等价变化，凑一下等式
$$\begin{array}{rl}& \sum _{j\notin J_i}{a}_{ij}{x}_j+\sum _{j\in J_i}{\tilde{a}}_{ij}{x}_j⩽b_i,\forall i\\ ⟹& \sum _{j\notin J_i}{a}_{ij}{x}_j+\sum _{j\in J_i}{a}_{ij}{x}_j+\sum _{j\in J_i}\left({\tilde{a}}_{ij}-a_{ij}\right)x_j⩽b_i,\forall i\\ ⟹& \sum _j{a}_{ij}{x}_j+\sum _{j\in J_i}\left({\tilde{a}}_{ij}-a_{ij}\right)x_j⩽b_i,\forall i\text{(注意第一项求和的index变化)}\end{array}$$

我们做个标注
$$\begin{array}{r}\sum _j{a}_{ij}{x}_j+\sum _{j\in J_i}\left({\tilde{a}}_{ij}-a_{ij}\right)x_j⩽b_i,\forall i(1)\end{array}$$

到这里，我们需要做一步放缩，上面提到
$$|{\tilde{a}}_{ij}-a_{ij}|⩽ϵ|a_{ij}|$$
因此
$$\begin{array}{rl}& |{\tilde{a}}_{ij}-a_{ij}|⩽ϵ|a_{ij}|\\ ⟹& -ϵ|a_{ij}|⩽{\tilde{a}}_{ij}-a_{ij}⩽ϵ|a_{ij}|\end{array}$$
因此就有
$$\begin{array}{r}\left({\tilde{a}}_{ij}-a_{ij}\right)x_j⩽ϵ|a_{ij}||x_j|\end{array}$$
注意，这里一定得是乘以$|x_j|$，因为乘以一个$⩾0$的数才能保证不等号的方向。

基于此，我们对约束的左端进行放缩
$$\begin{array}{rl}& \sum _j{a}_{ij}{x}_j+\sum _{j\in J_i}\left({\tilde{a}}_{ij}-a_{ij}\right)x_j\\ ⩽& \sum _j{a}_{ij}{x}_j+\sum _{j\in J_i}ϵ|a_{ij}||x_j|\end{array}$$
而论文中说，如果后者成立，前者就成立，所以我们可以直接采取放缩后的表达式，因此约束变成。
$$\begin{array}{r}\sum _j{a}_{ij}{x}_j+\sum _{j\in J_i}ϵ|a_{ij}||x_j|⩽b_i,\forall i(\ast )\end{array}$$

易得，$(\ast )$是$(1)$的一个比较紧的松弛，$(\ast )$成立$⟹$$(1)$成立。但是改模型是非线性的，含有绝对值，我们可以将其等价线性化。

• 注意，目标函数为$\max cx$

我们继续往下推。我们将上述模型线性化，去掉绝对值。线性化的方法就是

1. 引入辅助变量$y$代替$|x|$，且$y⩾0$.
2. 引入约束$y⩾x$
3. 引入约束$y⩾-x$

• 由于目标函数为$\max cx$，因此最后$y$的取值一定会等于$|x|$，也就是最优解中，一定有$y=|x|$

我们基于上面的来整理一下：
$y⩾x$ 且 $y⩾-x$

等价于$x⩽y$ 且 $-y⩽x$

也就是
$$\begin{array}{r}-y⩽x⩽y\end{array}$$

因此，我们的问题就可以等价为下面的形式

$$\begin{array}{rl}\max & \sum _j{c}_j{x}_j\\ s.t.& \sum _j{a}_{ij}{x}_j+\sum _{j\in J_i}ϵ|a_{ij}|y_j⩽b_i,\forall i\\ & -y_j⩽x_j⩽y_j,\forall j\\ & \mathbf{l}⩽\mathbf{x}⩽\mathbf{u}\\ & \mathbf{y}⩾0\end{array}$$

根据上文，我们令$ϵ|a_{ij}|={\hat{a}}_{ij}$，则上述模型就可以写成与《The Price of Robustness》论文中完全相同的形式
$$\begin{array}{rl}\max & \sum _{j\in J}{c}_j{x}_j\\ s.t.& \sum _j{a}_{ij}{x}_j+\sum _{j\in J_i}{\hat{a}}_{ij}{y}_j⩽b_i,\forall i\\ & -y_j⩽x_j⩽y_j,\forall j\\ & \mathbf{l}⩽\mathbf{x}⩽\mathbf{u}\\ & \mathbf{y}⩾0\end{array}$$

• 注意，这个是线性化后的模型，由于是等价线性化，因此在最优解中，一定有$y^{\ast }=|x^{\ast }|$。当然，也可以通过上面说的两个条件很明显地推出来。即

1. $y_j⩾|x_j|$；
2. 目标函数是$\max cx$。

这样就搞清楚了，为什么最开始图中的等价中出现了$(a_{ij}{x}_j+{\hat{a}}_{ij}|x_j|)$的形式，原来是由于那一步放缩导致的。

到这里，上面的疑惑也是探索了，但是我在看那篇更早的文献《Convex programming with set-inclusive constraints and applications to inexact linear programming》的时候，还是有一些小的体会，也顺便跟大家聊聊。

一些理解：关于column-wise uncertainty

在溯源的过程中，读到了文献《Convex programming with set-inclusive constraints and applications to inexact linear programming》，这篇论文是1972年被OR接收的。

文章探讨的问题如下：

这篇文献中，将每一列$K_i$都称之为activity sets(活动集合)，然后把右端部分$K$称之为resource set（资源集合）。

这个可能比较抽象，我们来举个例子来直观解释一下。

我们以下料问题(Cutting stock problem)为例：

以下几张图来源于笔者即将出版的教材：《运筹优化常用模型、算法及案例实战：Python+Java实现》

问题：
一家棒料销售公司销售 10 英寸、11 英寸和 19 英寸的棒料产品。客户需要 46个 10 英寸，22 个 11 英寸，43 个 19 英寸的产品。棒料销售公司需要截断 80 英寸的原材料棒料，来满足客户的需求，同时最小化使用棒材的根数。问该公司最好需要多少棒材，以及如何切割棒材？

下表列出了5中切割方案以及相应的数据。

我们基于这5个pattern，可以写出线性规划模型(这里实际上是0-1整数规划，但是由于是举例子，我们就当做是线性的)。

在上述模型中，右端常数向量$b$就是resource set（资源集合）
$$b=\left[\begin{array}{c}46\\ 22\\ 43\end{array}\right]$$
$b$其实有很多种可能的值，上面的选取只是其中一种，论文中考虑$b$的可选值构成一个凸集，即 K = { b ∈ R m } K = \{b \in \mathbb{R}^m\} K={b∈Rm}是凸集。

这就是说，我们的资源是可以在这个可行域$K$中变动，比如客户今天的需求是
$$b=\left[\begin{array}{c}46\\ 22\\ 43\end{array}\right]$$
明天的需求变成了
$$b=\left[\begin{array}{c}40\\ 26\\ 30\end{array}\right]$$
如果$b$在$K$内可以随意取值，但是其具体值我们不能提前获知，那这就是一种column-wise uncertainty。

想到这里，我就越发觉得，前辈们的想法真的超级棒呀！

同样的，如果每一列，例如第4列，
$${\mathbf{a}}_4=\left[\begin{array}{c}5\\ 1\\ 1\end{array}\right]$$
这是一种切割方案，是说，切割4个长度为10英寸的，1个长度为11英寸的，1个长度为19英寸的。这不就是一种活动嘛，称之为activity set还是真的贴切。

为什么将一列约束对应的约束向量${\mathbf{a}}_i$的取值范围$K_i$叫activity set呢？是因为作者考虑${\mathbf{a}}_k$的具体取值，我们也是提前不知道的，因此它也有很多种可能性，但是其可能的取值区域是一个凸集，也就是${\mathbf{a}}_i\in K_i$，且$K_i$是个凸集。

对于一个确定的取值${\mathbf{a}}_i$，作者称其为activity vector。

比如，一种方案，可以是
$${\mathbf{a}}_i=\left[\begin{array}{c}5\\ 1\\ 1\end{array}\right]$$

他也可以是
$${\mathbf{a}}_i=\left[\begin{array}{c}8\\ 0\\ 0\end{array}\right]$$
所以我们想到，上述模型中${\mathbf{a}}_1\sim {\mathbf{a}}_5$不就是可以看做是$K_i$这个图集中的元素嘛！哈哈。

也就是说，我们考虑，我们只有80英寸这一种棒材，这一个棒材如何切割，我们也不知道。但是每一种不同的切割方案，我们都可以叫做一个activity vector，所以，我们就可以把下料问题建模成为下面的问题

$$\begin{array}{rl}\max & x_1\\ s.t.& x_1{K}_1\subset K\\ & x_1⩾0\end{array}$$

如果我们有80英寸和100英寸两种棒材，则可以写为
$$\begin{array}{rl}\max & x_1+x_2\\ s.t.& x_1{K}_1+x_2{K}_2\subset K\\ & x_1⩾0\end{array}$$
如果说，我们考虑：如果可以在每一个activity set中选择任意的activity vector，则问题就变化为
$$\begin{array}{rl}\max & x_1+x_2\\ s.t.& x_1{\mathbf{a}}_1+x_2{\mathbf{a}}_2⩾\mathbf{b}\\ & x_1⩾0\end{array}$$
其中${\mathbf{a}}_1\in K_1$, ${\mathbf{a}}_2\in K_2$。

由于最后具体选择到的activity vector是哪个，我们也不知道，因此约束列向量是可以视为column-wise uncertainty的。

另外，由于每一列就是一个切割方案，因此这一列的可行方案可以通过求解下面的线性规划得到 （这里其实应该是整数规划，但是我们就姑且将其当成线性规划）：

$$\begin{array}{rl}\min & 1\\ s.t.& 10a_1+11a_2+19a_3⩽80\\ & a_1,a_2,a_3⩾0\end{array}$$

我们令${\mathbf{a}}_1=(a_1,a_2,a_3{)}^T$。由于线性规划的可行域是一个凸多面体，当然也就是一个凸集。因此，这就完全符合我们的假设，也就是${\mathbf{a}}_1$的活动集合activity set
K 1 = { a 1 ∣ min ⁡ 1 , s . t . 10 a 1 + 11 a 2 + 19 a 3 ⩽ 80 ; a 1 , a 2 , a 3 ⩾ 0 } K_1 = \{ \mathbf{a}_1 | \min \,\, 1, s.t. 10a_1+11a_2+19a_3\leqslant 80; a_1,a_2,a_3\geqslant 0\} K1​={a1​∣min1,s.t.10a1​+11a2​+19a3​⩽80;a1​,a2​,a3​⩾0}
是凸集。而${\mathbf{a}}_1$的的具体取值，可以是$K_1$中的任何值，这就是一种column-wise uncertainty。我们无法提前准确获知约束矩阵中的每一列的系数。

到这里，我们是不是对column-wise uncertainty有了一些更加直观的理解。

我觉得从列生成的角度，理解起来确实更有趣一些。我们确实决定要去用80英寸和100英寸的两种棒材去制作产品，但是具体怎么切割，我们也不知道，最后采用了哪种切割方案(也就是选了哪个activity vector)，我们事先也不能确定。这种不能事先确定列约束向量的情况，也是很有趣呢。

小结

好了，到这里，今天的分享就到此结束吧，希望之后哟更多的小伙伴来提一些有趣的问题。

另外，通过读论文，有学到了一些起名字的经验，比如这里涉及到的resource set，activity set等的，都是很形象很有趣。

参考文献

[1]: Ben-Tal A, Nemirovski A. Robust solutions of linear programming problems contaminated with uncertain data[J]. Mathematical programming, 2000, 88(3): 411-424.
[2]: Soyster A L. Convex programming with set-inclusive constraints and applications to inexact linear programming[J]. Operations research, 1973, 21(5): 1154-1157.
[3]: Bertsimas D, Sim M. The price of robustness[J]. Operations research, 2004, 52(1): 35-53.

---

** 作者： 刘兴禄， 清华大学博士在读**

---

欢迎关注我们的微信公众号 运小筹

公众号往期推文如下