数学优化思想的作用 鲁棒优化第三章（上）|不确定最优化与不确定集

引言：

《鲁棒优化入门》为「运筹OR帷幄」优化理论科普丛刊系列的第二本。这本电子书介绍了一些鲁棒优化的最基本的概念和最新的研究进展，借以对鲁棒优化进行框架性地梳理，为有志于运用鲁棒优化解决实际问题，有志于从事鲁棒优化学术研究的朋友提供概念性和框架性的入门。

具体内容包括：精典鲁棒优化和分布鲁棒优化；多阶段问题及线性决策规则和鲁棒优化对多阶段问题近似求解；鲁棒性优化和机器学习；以及鲁棒优化模型的求解及其在语言包中的实现。

3.1不确定最优化（under）

在实际生活中不确定性广泛存在，为了愈发合理的对不确定问题进行确切描述，不确定性优化渐渐被学界注重。最早在20世纪50年代、Zadeh和等人便开始对不确定性优化进行了研究(A,1959;E,1970)。在对不确定性优化问题的描述之前，我们先来看一下传统的确定性优化问题：

其中，

是决策向量，为目标函数，为约束条件。在（3.1）中，无论是约束条件还是目标函数，其对应的参数都是确定的。但是，在实际问题求解中，模型中一些参数我们很难事先确定。对于一些特定的优化问题而言，一个参数的不同就可能造成先前所求得的最优解显得毫无意义(El,1998)。为了解决这类问题，不确定性问题的优化求解就显得非常重要。

随着社会的不断发展，我们所须要求解模型的复杂度不断上升，模型的不确定性也在不断扩大，例如客机班机的线路规划、电网的最优调度、物流路径的最优规划等等。在实际生活中数学优化思想的作用，导致模型不确定的症结主要来自以下几个方面：

1）数据统计和采集过程引起的数据遗失、数据误差过大而形成的影响。

2）天气等不可抗力诱因的干扰，对问题的剖析形成的影响。

3）认知不全造成现有模型与实际生活中存在误差形成的影响。

4）对于一些无法求解的非凸非线性模型，进行简化描述而形成的影响。

为了更好地对不确定性优化问题进行描述，我们首先给出不确定性优化物理模型的通常抒发：

在（3.2）中，

为不确定参数，表示不确定参数的集合。为了求解模型（3.2），以等人的工作为开端，相关学者提出了一系列的求解优化方式，例如：随机规划(Birgeand,2011)、鲁棒优化(Ben-Taletal.,2009)、灵敏度剖析(Ben-Taletal.,2009)、模糊规划(刘宝碇,1998)等等。不确定性优化的理论和技巧不断地被开发下来。不确定性优化的理论也根据剖析阶段的不同被分为事前剖析方式和事后剖析方式两大类。接出来我们主要对这两大类的不确定理论展开表述。

事前剖析方式

模糊规划(Fuzzy)

当

是一个模糊逻辑集合时，模型（3.2）成为了处理软约束^1规划问题的求解模型，即模糊规划。这类规划是为了应对因为实际生活中，有时难以提供确切的决策的情况下而形成的一类规划求解理论。对于模糊规划问题的详尽求解步骤，可以参照文献(刘宝碇,1998)。在模糊规划中，须要根据决策者的个人经验来获取不确定参数的模糊隶属函数，常常存在较大的主观性，在实际中运用时也须要经过多次调整，存在众多限制。

随机规划()

当

是一个随机不确定集合时，上述模型成为了处理随机性数据的规划求解问题，即随机规划。随机规划依据不同的决策规则，可以分为三类：(a)期望模型。首先确定不确定参数的分布模型，之后通过选定离散或连续的机率分布函数对不确定参数进行描述数学优化思想的作用，最终通过期望来取代不确定参数，使不确定问题转化为确定性问题并求解。假如目标函数和约束中存在随机参数，只须要将各随机参数转化为期望值，便可以将模型转化为确定性模型从而求解。

(b)机会约束规划模型。浅显来讲，机会约束规划模型是指容许决策不满足约束条件，然而决策满足约束条件的机率不高于事先设定的置信水平的规划求解模型。该模型是一种在一定机率下达到最优的理论。该模型须要事先给定置信水平。模型描述如下：

(c)相死机会约束规划模型(Liu,1997)。相死机会约束规划是当决策者面临多个风波时，希望最大化满足这种风波的机率而形成的一种规划方式。无论是期望模型还是机会约束规划模型，最终都是确定性优化求解并得出确切值。相死机会规划即使求解结果是确定的，但并不代表一定实现，规划的目的是极大化该风波的实现几率。

事后剖析方式

灵敏度剖析（）是最典型的事后剖析技巧。灵敏度剖析依据需求的不同也被界定为局部灵敏度剖析(local)和全局灵敏度剖析()。这儿以模型（3.4）为例对灵敏度剖析展开一个简略的描述：

因为灵敏度剖析应对的是不确定性优化问题，因而有时会碰到须要添加圣经束的情况。这些情况下，假若最优解满足新添加的约束，则原模型的最优解仍是新模型的最优解，若不满足新添加的约束，则须要重新估算。但更多的研究内容是数据变化对最优解形成的影响。即：

、和变化造成模型最优值发生的改变。灵敏度剖析研究热点问题是，当参数在哪些范围内进行波动时，模型的最优解不会发生改变，具体的原理涉及到了基变量、非基变量、对偶单纯性等相关知识，这儿不再详尽描述，假如有兴趣的读者可以参考(陈宝林,2005)。灵敏度剖析方式其实相对其他不确定性优化方式而言比较简单，但灵敏度剖析方式仅是一个评价剖析工具，大大限制了该技巧的使用领域。

鲁棒优化（）

鲁棒优化也是一类事前剖析方式，之所以单独列下来，是由于鲁棒优化是针对传统优化方式不足，由鲁棒控制理论发展而至取代随机规划和灵敏度剖析的技巧。在（3.2）中，假如

是一个有界闭集，上述模型成为了处理不确定集合内所有不确定参数的优化问题，即鲁棒优化。相对于传统不确定性优化方式，鲁棒优化有如下优点：

鲁棒优化在建模过程中充分考虑了不确定性，并以集合的方式对变量进行描述。相对于随机规划和模糊规划，鲁棒优化不须要不确定参数的分布模型和不确定参数的模糊隶属函数。

鲁棒优化的约束条件是严格创立的，即只要不确定参数

属于不确定集合，所求出的解都能满足约束条件。即优化模型具有较强的鲁棒性，最优解对参数变化的敏感性低。

鲁棒优化似乎有着随机规划和模糊规划没有的优势，而且鲁棒优化模型本身是一个半无限优化问题，很难直接进行求解，鲁棒优化的估算结果受限于不确定集

的不同。我们会在3.2小节和3.3小节分别对鲁棒优化中的不确定集和鲁棒优化对方程及转换理论进行探讨。3.1.1鲁棒优化理论的发展

1973年，首次用鲁棒优化的思想来解决线性规划中的不确定性(,1973)。其实该方式基于最坏情况的基础上进行考虑，结果过分保守,并且为不确定性优化的发展开拓了全新的思路，开辟了鲁棒优化发展的公路。

等人在1995年首次提出鲁棒优化的概念(Metal.,1995)。她们给出了基于情境集鲁棒优化的通常模型框架，提出了解鲁棒（）和模型鲁棒（model）的概念，通过将目标函数分拆为聚合函数与罚函数来清除不确定参数对结果的影响。在此以后，不断有学者投入到鲁棒优化的研究中，在这方面的奠基之作是在20世纪90年代由以色列学者Ben-Tal和(Ben-Taland,1998,1999)和德国伯克利学院的(andHerv,1997)提出。Ben-Tal证明了假如不确定集合

是一个椭球不确定集（前面具体介绍），这么对于一些最重要的通常凸优化问题(线性规划、二次约束规划、半定规划等)，其鲁棒对方程要么是精确的，要么近似是一个可处理的问题，可以采用例如内点法的算法在方程时间内求解。除此之外，Ben-Tal给出了通常不确定半定规划问题的估算可处理的近似鲁棒对方程。在此以后，Ben-Tal等人又提出了可调鲁棒优化概念等概念，并被广泛运用到各行各业中。

21世纪初，和Sim(andSim,2004)在、Ben-Tal和的研究基础上提出了全新的鲁棒优化框架。和Sim的鲁棒优化囊括了离散优化，最主要的特征是所构建的鲁棒对方程不降低问题求解的复杂度。另一方面，和Sim的鲁棒优化容许出现约束违反()的情况，在这些情况下得到的鲁棒解大机率具有可行性。和Sim的理论因为其易处理性及实用性，遭到了学界的广泛认可。

3.1.2鲁棒优化研究路线

鲁棒优化自提出以来便遭到广泛关注，也不断地被各个领域的学者应用到各行各业中，对于鲁棒优化问题的求解思路也是太原小异。具体如下：

在上面我们早已提及，当模型(3.2)中的不确定集为闭集合时，(3.2)可以视为一个鲁棒优化模型。此时，目标函数和约束条件中均富含不确定参数，为了更浅显地描述，我们对（3.2）做一些变型：

转换后可以显著看出(应注意转换是否等价，具体参照第二章)，无论原鲁棒优化模型的目标函数是线性还是非线性，是否含不确定参数，都可以由(3.5)表示。并且模型(3.5)一般很难直接求解，为了便捷求解我们须要通过物理优化理论将模型(3.5)转换为一个能用商业软件直接求解的问题(以凸优化问题为主)，即鲁棒对等问题()。

目前，鲁棒优化的研究方向主要彰显在不确定集的选定及鲁棒对等转换理论上：

不确定集的选定。怎么选定合适的不确定集对不确定参数进行确切的描述，直接影响了模型的优化结果，但是不同的不确定集所对应的鲁棒对等问题也不同。

鲁棒对等转换理论。怎样把早已建立好的鲁棒优化模型转化成一个在估算上可通过通常商业优化软件直接求解的模型，直接影响了优化时间和优化结果。

3.2不确定集（set）

鲁棒优化中，不同的不确定集对结果影响非常显著，当不确定集合越精细、模型复杂度越高，求解越困难。当不确定集合越艰深时，所求出的最优解越保守数学优化思想的作用，越不经济。为了权衡两者的关系，怎么选择一个适宜的不确定集合仍然是相关学者的一个研究热点。常见的不确定集合主要有如下几类:

1.盒式不确定集（Boxset）

盒式不确定集合是最简单的不确定集合，也被叫做区间集。因为鲁棒优化是考虑最坏情况下的优化求解方式，对于一些模型可能会出现所有不确定参数都在区间集上下界进行优化的情况，但是实际中该情况发生的机率极低或不会发生，很容易出现过度保守的情况。

2.椭球不确定集（set）(Ben-Taletal.,2009;Boydand,2006)：椭球集/椭球交集

在Ben-Tal的精典专著《》称式(3.7)为椭球不确定集合，式(3.8)为椭球交集不确定集合。在Boyd的精典专著《》中称(3.8)为椭球集，(3.7)为退化的椭球。为了便捷描述，本文以Ben-tal的描述为准。上述公式中，

为不确定参数向量，为不确定参数的期望或预测值向量，为协残差矩阵，为不确定度，用以描画不确定参数扰动范围。相对于椭球集，椭球交集能更确切地对不确定参数进行描述，并且椭球交集在求解二次优化问题、锥二次优化、半定规划问题时无法直接求解，Ben-tal早已证明了这种优化问题中使用椭球交集时是NP-hard问题。假如采用椭球集，在线性规划、二次优化问题和锥二次优化时可以转化为可处理问题，并且在半定规划中，仍需满足众多限制能够求解。椭球不确定集即使可以挺好地表示好多类型集合，便捷数据输入，在一定程度上可以彰显不确定参数之间的关联性。并且椭球不确定游行降低问题求解的复杂度，因而应用不够广泛。

3.四面体不确定集（set）

四面体集合(and,2006)可以看作是椭球集合的一种特殊表现方式(Ben-Taland,1999)。虽然四面体不确定集无法描画不确定参数间的相关性，但其具有线性结构、易于控制不确定度，在实际工程问题中广受追捧(and,2006)。

4.基数/预算不确定集（set）

式中，

，

分别表示不确定参数的上下界，表示的预测值。最先提出这些不确定集合的是和Sim(andSim,2004)，因为这些不确定集合是基于不确定参数偏斜量的相对值进行重构的，才能对更精确描述参数的波动情况，因而也被称为基数不确定集(Retal.,2010;and,2017;etal.,2010)。

5.数据驱动不确定集（Data-set）

无论是采用盒式还是椭球式不确定集，就会出现所得到的解过分保守的情况，为了解决解的过度保守，一些学者依据历史数据进行不确定集的构造，也被称为数据驱动不确定集。数据驱动不确定集的建立，是使用统计假定检验的置信区间来精确描述不确定参数的分布。在04年、Sim和09年Ben-Tal等人的研究中，假设不确定参数为，其分布不能精确获得。最初始的研究是基于数据结构特点作出的先验假定。这种方式假定是没有依赖的，并且不会觉得边界分布是确定的。13年对数据驱动不确定集合的构造进行了进一步的改进。假定数据S有独立分布，这种S可以为不确定参数的分布添加更多的细节。而且通过这种细节信息，设计一个机率保证的集合，相对于传统的集合，新的集合更小，所求出的结果也不是这么的精确。关于数据驱动的先验假定和假定检验可以参照的研究(etal.,2018)。

去除以上常见的不确定集合，一些学者为了适应不同的情况以及更精确地对不确定参数进行描述，还衍生出了好多种组合不确定集合，具体如：盒式+椭球式不确定集、盒式+四面体不确定集、盒式+椭球式+四面体不确定集等等。