编者按：
《鲁棒优化入门》为「运筹OR帷幄」优化理论科普丛书系列的第二本。这本电子书介绍了一些鲁棒优化的最基本的概念和最新的研究进展，旨在对鲁棒优化进行框架性地梳理，为有志于运用鲁棒优化解决实际问题，有志于从事鲁棒优化学术研究的同学提供概念性和框架性的入门。
具体内容包括：经典鲁棒优化和分布鲁棒优化；多阶段问题及线性决策规则和鲁棒优化对多阶段问题近似求解；鲁棒性优化和机器学习；以及鲁棒优化模型的求解及其在语言包中的实现。
本文为《鲁棒优化入门》电子书第三章内容的3.3节与3.4节。 可在GitHub下载本文或提出修改意见（ ）。后续章节也将逐步在公众号和GitHub发布，欢迎持续关注！
3.3 鲁棒对等问题（Robust counterpart）
让我们先回到模型 (3.5)：
在这个模型中，假如 有 个可能的取值，那么给定 和，约束
就等价于
共个约束。相应的， 也等价于
共 个约束。
然而，如3.2小节所描述，常见的不确定集合大部分都是连续集 (continuous set) 而非离散集 (discrete set), 也即对于模型(3.5)来说，它将有无限多个约束，由此产生了一个半无限规划模型。显然，这是难以直接求解的。为了对鲁棒优化问题进行求解，我们需要对原模型做出一定程度的转化，使得转化后模型能够通过商业软件直接进行求解。在这方面做出重要突破的学者有Allen L. Soyster、Aharon Ben-Tal、Arkadi Nemirovski、Dimitris Bertsimas和Melvyn Sim等。
实际上鲁棒，对于任意形如
的约束，我们都可以等价地将其写为：
当函数和集合满足一定条件时，不等式左边的问题可以转化为线性规划问题、凸优化问题、或者是锥优化问题。相应地，所对应的约束转化为线性约束、凸约束、或者锥约束。从而使得模型(3.5)能用商业软件进行求解。
一般地，我们定义形如
的式子为鲁棒约束 (robust constraint)。而将模型 (3.5)称为经典鲁棒优化模型，将其转化之后可以直接用商业软件进行求解的模型称为鲁棒对等问题 (robust counterpart)。而整个转化的过程大多数时候依赖于对偶理论。举例如下：
**示例3.1：**考虑如下鲁棒优化问题
其中.
约束 等价于
。对于不等式左边的问题，由2.1可知其对偶问题为：
也即约束 等价于
由此，可以得到问题 (3.11) 的鲁棒对等问题为：
3.4 经典鲁棒模型
接下来，我们将以Bertsimas and Sim (2003)为蓝本，简要介绍在鲁棒优化理论发展过程中经典的的三个模型：他们分别来自Soyster (1973)、Ben-Tal and Nemirovski (1999)和Bertsimas and Sim (2003)。
3.4.1 Soyster的鲁棒模型
如第一章所介绍，Soyster假设以下线性规划问题中
系数矩阵的每一列都在一个凸集中（也称为列不确定性），也即，，那么线性规划问题(3.13)将变成如下问题：
其所对应的鲁棒对等问题为
其中，。也即，对于每一个参数都取其在不确定集范围内的最大值。而这样得到的解虽然具有鲁棒性，但是同时也非常保守。
3.4.2 Ben-Tal 和 Nemirovski 的鲁棒模型
Ben-Tal和Nemirovski也认同具有不确定性。但是不同于Soyster (1973)，Ben-Tal and Nemirovski (2000)假设的第 行中，只有部分系数—用表示—具有不确定性。如果我们用表示具有不确定性的系数，且。其中, 为波动范围，为在内对称分布的随机变量，且满足。也即
其所对应的鲁棒对等问题为
在此问题中，为一给定的常量，并无直观的意义。求解结果高度依赖于常量。此外，此问题虽然可以通过调节来避免Soyster (1973)的极端保守情况，仍然比较保守。同时，此问题为二阶锥规划问题，求解起来稍显繁琐。
3.4.3 Bertsimas 和Sim 的鲁棒模型
为了克服 Soyster (1973)的保守性和Ben-Tal and Nemirovski (2000)中使用椭球不确定集而导致二阶锥规划问题，对于系数矩阵 A 中的第行，Bertsimas and Sim (2004)提出了预算不确定集(budget uncertainty set):
其中，,表示第行中不确定的参数个数。 也即，通过引入参数来调节模型的保守程度。假设不确定的参数个数不超过个，其中是小于等于的最大整数，并且假设的波动范围为，Bertsimas和Sim提出以下鲁棒优化模型：
当为整数时，此时，对第个约束，有如下形式:
当的值为0时，变量的系数均为标称值，约束变为名义问题（nominal problem）。当取最大值时，此时所有的不确定元素均不为标称值，模型等价于Soyster模型。当的值介于最大值和最小值之间变动时，模型的保守度也相应变动。当的值为时，约束违背（具体参考考Bertsimas and Sim 2004）的概率边界值与Ben-tal一致。因此，当的值过小时，鲁棒优化模型保守性差，较大概率发生约束违背。当的值过大时，计算结果过于保守。模型(3.18)是非线性模型，不能直接求解，Bertsimas和Sim对模型做出了如下转化：
模型转化的理论依据是对偶理论，具体的证明过程在作者稿件中有详细描述，有兴趣的读者可以自行翻阅，这里不再赘述。在此基础上，Bertsimas and Sim (2003)提出了鲁棒离散优化的模型:
其中，是区间内的整数，0}” data-formula-type=”inline-equation”>,是中不确定元素的个数。不同于Bertsimas and Sim (2004)鲁棒，Bertsimas and Sim (2003)考虑了目标函数的不确定性。对于目标函数中的，允许变化的不确定元素有个，取值为 $mathopboldsymbol c^top}limits_{j in mathcal{S}0} + mathop {max }limits{left{ {left. {mathcal{S}_0} rightmathcal{S_0 subseteq mathcalJ}_0,left{mathcal{S_0} right| leqslant {Gamma 0}} right}} sumlimits{j in mathcal{S}_0} {{d_j}} $，其余均为标称值。
同样的，模型(3.21)也需要经过处理才能求解，处理后的混合整数规划模型如下所示：
接下来，我们节选Bertsimas and Sim (2004)中的组合优化的例子来简要探讨鲁棒优化的具体运用。考虑如下的组合优化模型，
其中，定义决策变量代表每支股票的投资比例, 和分别为股票的期望回报率与回报率标准差，是控制风险和回报之间交易的一个参数。
考虑支股票，假如第支股票的回报率的期望和标准差分别为，且假设来平衡投资的回报期望和风险。模型(3.23)所对应的鲁棒优化模型为：
其鲁棒对等模型为：
此外，根据Bertsimas and Sim (2004)中的Proposition 1：
等价为以下的线性优化模型：
也即，我们可将模型(3.24)写为
在该模型中，随机变量代表实际股票回报率和期望值间的偏差。这个随机变量被约束在一个预算不确定集（Budget uncertainty set）中：
大部分鲁棒优化问题都可以用优化工具直接求解。我们将在本书第十章介绍相关内容。
参考文献
A, Cooper WW Chames, Chance-Constrained Programming, INFORMS, 1959。Baringo, Luis and Ana Baringo, “A Stochastic Adaptive Robust Optimization Approach for the Generation and Transmission Expansion Planning,” IEEE Transactions on Power Systems, 2017, PP (99), 1–1。Ben-Tal, A。 and A。 Nemirovski, “Robust Convex Optimization,” Mathematics of Operations Research, 1998, 23 (4), 769–805。_and_, “Robust solutions of uncertain linear programs,” Operations Research Letters, 1999, pp。 1–13。Ben-Tal, Aharon and Arkadi Nemirovski, “Robust solutions of linear programming problems contaminated with uncertain data,” Mathematical Programming, 2000, 88 (3), 411–424。
_, Laurent El Ghaoui, and Arkadi Nemirovski, Robust Optimization 2009。Bertsimas, Dimitris and Aurľlie Thiele, “Robust and Data-Driven Optimization: Modern Decision Making Under Uncertainty,” Tutorials in Operations Research, 04 2006, 4。_and Melvyn Sim, “Robust discrete optimization and network flows,” Mathematical Programming, 2003, 98(1-3), 49–71。_and_, “The Price of Robustness,” Operations Research, 2004, 52 (1), 35–53。Bertsimas, Dimitris J。, David B。 Brown, and Constantine Caramanis, “Theory and Applications of Robust Optimization,” Siam Review, 2010, 53 (3), 464–501。
Bertsimas, Dimitris, Vishal Gupta, and Nathan Kallus, “Data-driven robust optimization,” Mathematical Programming, 2018, 167 (2), 235–292。Birge, John R and Francois Louveaux, Introduction to stochastic programming 2011。Boyd, Stephen and Lieven Vandenberghe, “Convex optimization,” IEEE Transactions on Automatic Control, 2006, 51 (11), 1859–1859。E, Bellmann R。, “Decision Making in a Fuzzy Environment,” Management science, 1970, (17)。Ghaoui, Laurent Oustry Francois Lebret El, “Robust Solutions to Uncertain Semidefinite Programs,” SIAM Journal on Optimization, 1998, 9(1), 33–52。
Laurent, El Ghaoui I。 and Lebret I。 Herv, “Robust Solutions To Least-Squares Problems With Uncertain Data,” in “International Workshop on Recent Advances in Total Least Squares Techniques & Errors-in-variables Modeling” International Workshop on Recent Advances in Total Least Squares Techniques &Errors-in-variables Modeling 1997。Liu, Baoding, “Dependent-chance programming: A class of stochastic optimization,” Computers & Mathematics with Applications, 1997, 34 (12), 89–104。M, Mulvey J。, Vanderbei R。
J, and Zenios S。 A, “Zenios S A 。 Robust Optimization of Large-Scale Systems,” Operations Research, 1995, 43 (2), 264–281。R, Jiang, Zhang M, and Li G, “Two-StageRobust Power Grid Optimization Problem,” Social Science Electronic Publishing, 2010。Soyster, Allen L。, “Technical Note-Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming。,” Operations Research, 1973, 21 (5), 1154–1157。刘宝碇, 随机规划与模糊规划, 清华大学出版社, 1998。陈宝林, 最优化理论与算法, 清华大学出版社, 2005。
———END———
限 时 特 惠： 本站每日持续更新海量各大内部创业教程，一年会员只需98元，全站资源免费下载 点击查看详情
站 长 微 信： bear68899
‘
