基于矩信息的鲁棒优化模型、算法及应用

《基于矩信息的鲁棒优化模型、算法及应用》主要介绍不确定性环境下基于随机参数矩信息的鲁棒优化方法，讨论其模型构建、算法设计及实际应用等方面的*新研究成果。《基于矩信息的鲁棒优化模型、算法及应用》旨在为不确定性环境下优化决策提供理论建模、算法设计及分析的新方法和工具，同时为复杂环境下供应链管理、运营管理、物流运作等实际问题提供科学决策支持。

目录
“博士后文库”序言
前言
第1章 概述1
1.1 不确定性与风险1
1.2 不确定性优化方法概述2
1.2.1 确定性优化2
1.2.2 随机优化3
1.2.3 风险优化4
1.2.4 鲁棒优化11
1.3 鲁棒优化方法15
1.3.1 基于不确定性集的鲁棒优化15
1.3.2 基于分布函数集的鲁棒优化17
1.4 本章小结19
第2章 基于矩信息的鲁棒优化20
2.1 基于矩信息的鲁棒优化概述20
2.2 基于矩信息的鲁棒期望优化21
2.2.1 分段线性凸函数22
2.2.2 子优化问题函数24
2.3 基于矩信息的鲁棒CVaR优化25
2.3.1 *优概率不等式25
2.3.2 鲁棒CVaR34
2.3.3 基于RCVaR的鲁棒优化38
2.4 本章小结40
第3章 基于矩信息的鲁棒库存优化方法及算法41
3.1 批量订购问题41
3.1.1 问题背景41
3.1.2 顾客需求的分布函数集42
3.2 两阶段批量订购鲁棒优化模型45
3.2.1 问题模型45
3.2.2 第二阶段费用函数的等价*短路形式47
3.3 等价二阶锥规划模型49
3.4 参数搜索方法54
3.4.1 参数搜索的基本思想54
3.4.2 区间参数搜索方法56
3.4.3 需求不相关条件下子问题的求解57
3.4.4 需求部分相关条件下子问题的求解59
3.5 数值实验65
3.5.1 算法的有效性66
3.5.2 鲁棒模型的有效性67
3.6 本章小结68
第4章 基于矩信息的鲁棒路径规划方法69
4.1 鲁棒路径规划问题模型69
4.1.1 路径规划问题及可靠性准则69
4.1.2 鲁棒路径规划问题70
4.1.3 概率分布函数集的构造71
4.2 对偶估计方法71
4.2.1 对偶形式71
4.2.2 计算(P)下界的场景方法73
4.2.3 计算(P)上界的半正定规划方法73
4.3 原始估计方法76
4.3.1 RM\ETT的解析表达式76
4.3.2 求解(P)的原始估计方法79
4.4 数值实验80
4.5 本章小结83
第5章 随机参数*立的鲁棒优化模型的参数搜索算法84
5.1 旅行时间*立的鲁棒路径规划问题84
5.1.1 凹费用的*短路问题84
5.1.2 模型分析85
5.2 单调下降参数搜索86
5.3 交叉点参数搜索方法88
5.4 改进的区间参数搜索91
5.5 加速标签修正算法92
5.6 数值实验95
5.6.1 实验环境95
5.6.2 实际交通网络的计算结果97
5.6.3 网格网络的计算结果98
5.7 本章小结100
第6章 随机参数相关的鲁棒优化模型的拉格朗日算法101
6.1 旅行时间相关的鲁棒路径规划问题101
6.2 拉格朗日对偶问题103
6.2.1 协方差矩阵分解103
6.2.2 问题转化103
6.2.3 对偶化简104
6.3 拉格朗日算法105
6.3.1 约束生成算法105
6.3.2 次梯度投影算法107
6.4 处理负环的方法109
6.4.1 改进的约束生成算法110
6.4.2 改进的次梯度投影算法110
6.4.3 算法复杂度分析113
6.5 拉格朗日算法对偶间隙分析114
6.6 数值实验118
6.6.1 计算算例118
6.6.2 算法实现119
6.6.3 计算性能分析120
6.6.4 收敛性分析120
6.6.5 运行时间分析121
6.6.6 对偶间隙和*优性分析125
6.7 本章小结126
参考文献127
编后记135

第1章 概述
　　1.1 不确定性与风险
　　不确定性因素在各类系统中广泛存在，并且会对系统性能产生很大的影响。研究不确定性现象，降低系统决策的风险具有重要的理论价值和现实意义。
　　在学术界和工程实践中，目前对不确定性尚无一致认可的定义[1]。在通常的研究和工程应用中，我们可以采用具有特定概率分布的随机变量、模糊变量或者不确定性集等方式来描述和刻画系统的各类不确定性因素。Verderame等[2]详细讨论了农林业、电力能源、石油石化、交通运输等领域各类不确定性因素的描述方式，并指出研究者往往采用正态分布随机变量、指数分布随机变量、有界随机变量等来描述各类系统中的各种不确定性，如需求不确定性、运输服务时间不确定性、顾客到达数量不确定性、运输工具到达时间不确定性等。
　　不同研究者对于风险的定义也略有不同。一般来说，研究者往往采用不希望事件发生的概率及其发生时产生的后果严重程度等方式来定义风险[3-5]。具体而言，我们可以将风险定义为损失大小的不确定性或者某个事件可能结果的不确定性。风险的两个关键特征是其不确定性和呈现度。Samson等[1]深入分析了不确定性和风险两者之间的关系。他们采用不确定性区间来描述不确定性，然后以其随机概率分布描述风险，建立两阶段模型。
　　风险管理是一门研究历史悠久且内涵丰富的学科。在经历了20世纪30年代的经济大萧条之后，各国学者对风险的研究更加重视。20世纪70年代，学术界已经形成关于风险的比较系统化的研究体系。现在的风险管理已经成为组织管理的一个重要研究方向，并在金融财政、企业运营、项目管理等领域得到广泛的应用。在学术界，研究者对风险构成要素、风险判别、风险量化、风险评估、风险干预等理论和方法进行了深入的研究[6]。
　　不确定性优化决策和风险管理有紧密的联系。本书主要研究系统参数的不确定性，并认为其具有随机性，用随机变量的概率分布函数来描述决策问题中的不确定性。但是，由于不确定性的未知性，系统随机参数的精确概率分布信息往往无法得到。为此，一族概率分布函数(即分布函数集)被提出来。具体而言，随机参数的分布函数集可以基于随机参数的矩信息(支撑集、均值、协方差矩阵等)进行构造。假定该分布函数集包含随机参数的真实分布，为了降低系统决策的风险，人们提出一种抗干扰能力强、可靠性高的决策方法，即鲁棒优化方法。鲁棒优化方法的特点在于，通过选取合适的分布函数集和风险度量函数来提高决策的可靠性。
　　研究基于矩信息的鲁棒优化方法具有重要的理论意义。
　　一方面，传统的运筹优化方法，如线性规划、动态规划等，往往都假定系统参数的取值是确定的、已知的。然而，在实际工程应用中，我们往往无法提前预知这些参数的精确取值，或者系统参数的取值本身就处在随机波动中。为此，学者先后提出随机优化[7，8]、基于不确定性集的鲁棒优化[9-11]等处理方法。虽然这些方法可以处理系统参数的随机性和波动性，但是这些方法也存在一些不足之处。例如，需要假定已经知道系统随机参数的精确概率分布信息，或者大量历史采样信息。然而，在实际工程中，我们常常无法预知系统随机参数的精确概率分布信息，或者无法提前获得大量采样数据。即使我们将随机参数的概率分布假定为正态分布或者指数分布等常见的分布，处理随机模型(stochastic model，SM)往往也需要计算多重积分，从而导致模型计算比较困难。基于不确定性集的鲁棒优化方法可以处理模型参数的波动性，不需要提前知道系统参数的精确概率分布信息。但是，基于不确定性集的鲁棒优化方法给出的决策往往过于保守，导致系统性能不佳。与随机优化和基于不确定性集的鲁棒优化方法相比，基于矩信息的鲁棒优化模型只需要少量的历史样本就可以估计出系统随机参数的支撑集、均值和协方差等信息，不需要系统参数的精确概率分布信息，同时又能避免做出过于保守的决策，具有较好的系统性能。
　　另一方面，我们借鉴风险优化中的风险度量函数，将其作为鲁棒目标函数，提高决策的鲁棒性，并发展完善传统风险决策模型。传统风险决策模型往往基于随机参数的精确分布信息，因此可以看作随机优化模型的一部分。其对应的损失函数是单个随机变量。基于矩信息的鲁棒优化方法采用概率分布函数集描述系统随机因素，损失函数为一族随机变量。利用鲁棒优化的思想，我们将基于矩信息的鲁棒优化模型的风险定义为这一族概率分布中*差情况下的损失。因此，我们将传统风险度量的概念推广为鲁棒的风险度量。
　　1.2 不确定性优化方法概述
　　1.2.1 确定性优化
　　我们*先给出一般确定性优化问题(optimization problem，OP)的数学模型。该模型(P)具有如下形式，即
　　(P)minx∈Xf(x，ξ)(1.1)
　　其中，ξ为系统参数，这里假定其为已知的确定性参数；x为决策变量，是n维决策变量；X∈Rn为模型的可行域；f(x，ξ)为模型的目标函数，它的值取决于决策x和系统参数ξ。
　　在优化模型(P)中，我们认为其可行域和参数都是已知、确定性的。
　　为了简化后续讨论，假定系统的不确定性参数ξ只存在于模型的目标函数中，不影响系统的可行域。在后续的几节中，我们分别讨论处理不确定性环境下决策问题的随机优化方法、风险优化方法和鲁棒优化方法。我们假设优化模型的*优解总是存在，因此不再区分max(min)和sup(inf)。
　　1.2.2 随机优化
　　随机优化假定模型参数ξ是随机向量，其概率分布函数F是提前已知的。当ξ为随机向量时，对于任意的x∈X，f(x，ξ)也是一个随机变量。因此，随机优化可以利用期望函数来评价系统决策x∈X对应的系统费用，即随机优化模型以EF[f(x，ξ)]作为决策的目标函数，其中EF[ ]是根据分布函数F计算的期望值。随机优化(stochasticprogramming，SP)模型具有如下形式，即
　　(SP)minx∈XEF[f(x，ξ)](1.2)
　　随机优化模型可以分为三类，即两阶段随机优化模型、多阶段随机优化模型、随机机会约束模型[7]。
　　两阶段的随机优化模型根据决策时不确定性参数的取值是否已知，将决策分为两个阶段。其中，在**阶段进行决策时，决策者无法知道系统参数的具体取值，仅知道随机参数的概率分布信息；在第二阶段进行决策时，系统参数的真实取值可以被决策者观察到，因此系统决策者可以进行第二阶段的调整性决策，即决策者可以根据随机参数的具体实现和**阶段的决策选择第二阶段*优的决策。
　　两阶段的随机线性优化模型具有如下形式，即
　　mincTx+EF[Q(x，ξ)]
　　s.t.Ax=b，x.0
　　其中，x为**阶段决策变量；随机参数ξ的样本空间为Ω；*优值函数Q(x，ξ)定义为
　　minq(ω)Ty
　　s.t.T(ω)x+W(ω)y=h(ω)，y.0(1.3)
　　其中，y为第二阶段决策变量；对于给定的样本ω∈Ω，随机参数取值为ξ(ω)=(q(ω)，h(ω)，T(ω)，W(ω))。
　　当随机变量的取值数量有限时，该模型等价于一个具有特殊结构的大规模线性优化问题。Van Slyke等[12]利用该问题的对角块结构性质，通过对其对偶问题进行丹齐格–沃尔夫(Dantzig-Wolfe)分解，提出L形(L-shaped)算法。L-shaped算法包括可行性判断和*优性判断两部分。在可行性判断时，如果当前解不满足可行性条件，那么就增加可行切约束排除当前解；在*优性判断时，如果当前解不满足*优性条件，那么就增加*优切约束排除当前解。随后L-shaped算法被不断改进，并应用到其他两阶段的随机优化问题中。例如，Birge等[13]进一步改进了该算法，通过在同一个点增加多个约束提升计算的效率。Laporte等[14]提出
　　针对包含整数变量的两阶段随机线性优化问题的L-shaped算法。
　　多阶段随机优化模型是对两阶段模型的扩展，但是其求解难度更大。多阶段随机线性规划模型往往采用离散场景树的方法建模，等价于一个大规模的线性优化问题。Birge[15]提出针对此类问题的分解分区算法。Ruszczy′nski[16]进一步设计了针对多阶段随机优化问题的并行分解算法，提高了计算的效率。L.kketangen等[17]提出结合渐进障碍法和禁忌搜索来求解包含0-1变量的多阶段随机优化问题。
　　随机机会约束模型是处理约束集中包含随机参数的随机优化模型。两阶段和多阶段随机优化模型要求包含随机参数的等式约束和不等式约束都以概率1满足，而随机机会约束模型只要求此类约束以一定的概率p(一般p取值为0.95或者0.97)满足。随机机会约束模型具有如下形式，即
　　minEF[f(x，ξ)]
　　s.t.Prob(gj(x，ξ).0，j=1，2， ，J).p
　　x∈X.Rn(1.4)
　　一般而言，除非随机参数服从特定的概率分布，随机机会约束模型的求解是非常复杂的。采样平均估计(sample average approximation，SAA)方法是常用的求解随机机会约束模型的有效方法[18-20]。
　　1.2.3 风险优化
　　本节*先回顾风险优化中常用风险函数的定义，然后介绍一致风险函数的概念，*后讨论常见的风险优化模型。
　　1.风险函数
　　定义损失函数为L(x，ξ):X×P→R，其中X为决策空间或者可行域，P为随机参数ξ的分布函数集。对于给定的x0∈X，风险函数定义为
　　ρ[L(x0，ξ)]:P→R
　　即对于给定分布函数的随机变量ξ，风险函数为其指定一个实数值作为风险值。为了表述的简洁性，我们记Z:=ρ[L(x0，ξ)]。
　　常见的风险函数有如下几种。
　　1)期望风险函数
　　ρ(Z)=E[Z]
　　由大数定理可知，当随机现象反复出现，并且决策者关心的是系统的长期性能时，采用期望函数作为风险函数并基于此进行决策是合理的。但是，期望风险函数并没有考虑随机变量的波动性。因此，在某些情况下，系统费用可能会很高，甚至无法接受。
　　2)期望–方差风险函数
　　ρ(Z)=E[Z]+λSD[Z]
　　其中，SD[ ]为随机变量的标准差；λ为权重系数。
　　期望–方差风险函数考虑随机变量波动带来的风险，同时通过改变λ给出一系列的帕累托*优解。如果将权重系数看作期望和标准差的比，那么权重系数就是对风险的定价。
　　期望–方差风险函数也存在一定的缺陷。对于*小化问题，如果采用期望–方差风险函数作为目标函数，那么随机变量Z比期望值E[Z]低的波动也被视为不利的波动。为了克服这一弊端，研究者进一步提出基于上半方差的风险函数。
　　3)期望–上半波动风险函数
　　ρ(Z)=E[Z]+λ E(Z.E[Z])p+1/p
　　其中，p∈[1，+∞)；取正函数定义为
　　[x]+:=(0，x<0x，x.0
　　期望–上半波动风险函数可以区分有利波动和不利波动，克服期望–方差风险函数的缺陷。如果将定义中的期望值替换为确定值r，那么可以得到上半波动矩函数，即
　　M(Z)=E[Z.r]p+，p=0，1，2
　　当p=0时，该函数可以度量损失函数大于特定损失值的概率；当p=1时，该函数可以度量损失函数大于特定损失值的条件期望；当p=2时，该函数可以度量损失函数大于特定损失值的上半方差。
　　关于上半波动矩函数在分布集鲁棒模型中的应用，读者可以参见文献[21]。
　　4)风险价值(valueatrisk，VaR)
　　给定参数α∈(0，1)(一般α的值大于0.9)，假设随机变量Z(代表随机损失)的累积概率分布函数为FZ(z):=Prob(Z.z)，那么我们称随机变量的下α分位点(即随机变量比该值低的概率至少为α)为其在α水平