鲁棒优化的方法及应用

《鲁棒优化的方法及应用》由会员分享，可在线阅读，更多相关《鲁棒优化的方法及应用（24页珍藏版）》请在装配图网上搜索。

1、.页眉鲁棒优化的方法及应用 杨威在实际的优化中决策过程中，我们经常遇到这样的情形，数据是不确定的或者是非精确的；最优解不易计算，即使计算的非常精确，但是很难准确的实施；对于数据的一个小的扰动可能导致解是不可行。鲁棒优化是一个建模技术，可以处理数据不确定但属于一个不确定集合的优化问题。早在19世纪70年代，Soyster就是最早开始研究鲁棒优化问题的学者之一，他的文章给出了当约束矩阵的列向量属于一个椭球形不确定的集合时的鲁棒线性优化问题。几年以后Falk沿着这条思路做了非精确的线性规划。在以后的很长的一段时间里，鲁棒优化方面都没有新的成果出现。直到19世纪末，Ben-Tal,Nemirovski

2、的工作以及这时计算技术的发展，尤其是对于半定优化和凸优化内点算法的发展，使得鲁棒优化又成为一个研究的热点。 一个一般的数学规划的形式为其中为设计向量，为目标函数，是问题的结构元素。表示属于特定问题的数据。是数据空间中的某个不确定的集合。对于一个不确定问题的相应的鲁棒问题为 这个问题的可行解和最优解分别称为不确定问题的鲁棒可行和鲁棒最优解。这篇文章主要回顾了鲁棒优化的基本算法，目前的最新的研究结果及在经济上的应用。1 鲁棒优化的基本方法1.1鲁棒线性规划一个不确定线性规划所对应的鲁棒优化问题为，如果不确定的集合是一个计算上易处理的问题，则这个线性规划也是一个计算上易处理的问题。并且有下列的结论：

3、假设不确定的集合由一个有界的集合的仿射像给出，如果是1线性不等式约束系统构成，则不确定线性规划的鲁棒规划等价于一个线性规划问题。2由锥二次不等式系统给出，则不确定线性规划的鲁棒规划等价于一个锥二次的问题。3 由线性矩阵不等式系统给出，则所导致的问题为一个半定规划问题。1.2鲁棒二次规划考虑一个不确定的凸二次约束问题对于这样的一个问题，即使不确定集合的结够很简单，也会导致NP难的问题，所以对于这种问题的处理通常是采用它的近似的鲁棒规划问题。考虑一个不确定的优化问题，假设不确定集合为，而表示名义的数据，而表示一个扰动的集合，假设是一个包含原点的凸紧集。不确定问题可以看成是一个不确定问题的参数族，表

4、示不确定的水平。具有椭圆不确定性的不确定的凸二次规划问题的近似鲁棒问题其中则问题可一转化为一个半定规划问题 具有椭圆不确定集合的不确定锥二次问题的近似鲁棒规划考虑不确定锥二次规划它的约束为逐侧的不确定它的左侧的不确定的集合是一个椭圆其中右侧的不确定集合是有界的，它的半定表示为，为线性映射。则半定规划为其中1.3鲁棒半定规划一个不确定的半定规划的鲁棒规划为由一个箱式不确定集合影响的不确定半定规划的近似鲁棒问题。则半定规划的近似的鲁棒优化为由一个球不确定集合影响的不确定半定规划的近似鲁棒问题。则半定规划问题为具有易处理的鲁棒counterparts的不确定线性规划。 如果多胞形是由有限集合的凸包给

5、出的，则鲁棒规划为2 鲁棒优化的几种新的方法 鲁棒规划的最近的研究包括了对于可调节的鲁棒优化的研究以及对于鲁棒凸优化的研究。2.1不确定的线性规划的可调节的鲁棒解不确定线性规划为，其中不确定集合是一个非空的紧的凸集，称为recourse矩阵。当是确定的情况下，则称相应的不确定线性规划为固定recourse的。定义：线性规划的鲁棒counterpart为 ，则它的可调节的鲁棒counterpart为。可调节的鲁棒规划比一般的鲁棒规划灵活，但是同时它也比一般的鲁棒规划难解。对于一个不确定线性规划的鲁棒规划是一个计算上易处理的问题，然而它相应的可调节的鲁棒规划却是不易处理的问题。但是如果不确定集合是

6、有限集合的凸包，则固定recourse的ARC是通常的线性规划。从实际的应用来看，只有当原不确定问题的鲁棒counterpart在计算上容易处理的时候，鲁棒优化方法才有意义。当可调节的变量是数据的仿射函数时，可以得到一个计算上易处理的鲁棒counterpart.对于的仿射可调节的鲁棒counterpart (AARC)可以表示为。如果是一个计算上易处理的集合，则在固定recourse的情况下，的仿射可调节的鲁棒counterpart (AARC)是一个计算上易处理的问题。如果是这样的一个集合，是一个非空的凸紧集。在固定的recourse的情况下，AARC具有这样的形式如果不确定的集合是一个锥表

7、示的，则的仿射可调节的鲁棒counterpart (AARC)是一个锥二次或半定规划。如果recourse也是可变的，则AARC是不易处理的问题，这时采用它的近似形式。在简单椭圆不确定集合的情况下，AARC等价于一个半定规划。当扰动的集合是一个中心在原点的箱式集合或者是一个关于原点对称的多胞形集合，则AARC可以有一个半定规划来近似。对于多期的决策问题也是一个可调节的鲁棒优化问题。考虑一个两期的决策问题其中是不确定的，但属于一个闭的有界的不确定集合。可行集依赖于和参数。则可以表示为，或。可调节的鲁棒counterpart问题可以表示为， 可以等价的表示为 。 如果包含有限数量的元素，则对于每个

8、，都存在着相应的满足上面的问题。则问题可以转化为一个等价的单层优化问题这样的一个单层的优化问题对于许多类的函数和集合，这是一个易处理的问题。比如，其中，在这种情况下，问题等价于一个二次约束的优化问题如果不确定集合是有限集合的凸包，则考虑下面的问题如果是拟凸的，则。则问题转化为一个单层的优化问题。 2.2一个锥二次问题的鲁棒解一个锥二次约束的形式为，或者是等价的形式，是Lorentz锥。假设不确定参数属于一个有界的集合。两种类型的不确定集合常常用到，一个是范数有界的不确定集合，一个是扰动的向量属于一个有界的扰动集合时的结构不确定集合。对于参数的结构不确定为，其中是描述扰动的向量，是表示扰动幅度的

9、向量，是扰动集合，是名义数值，为扰动方向。是椭圆的交集 ，为对称的正半定矩阵，且是正定的。对于一个单侧不确定的锥二次约束，El Ghaoui和Lebret证明了在不确定集合是范数有界的情况下，问题等价于一个锥二次约束。Ben-Tal,Nemirovski给出了在扰动集合是椭圆集合的交集的结构不确定的情况下，如果是简单的椭圆不确定集合，则相应的鲁棒counterpart为一个线性矩阵不等式，在一般的情况下，问题是NP难的，但是可以用线性矩阵不等式来近似。Ben-Tal等研究了逐侧不确定的锥二次约束，即对于影响左侧的不确定独立于影响右侧的不确定。，是相互独立的集合。则是问题的可行解，但且仅当存在，

10、使得，和成立。在具有椭球交集的结构不确定的集合的情况下，这两个问题是易处理的。在很多的情况下，影响两侧的不确定集合是相互依存的。比如考虑一个不确定的锥二次约束 ， (*)其中关于是仿射的。是中心在原点的椭圆的交集。，为对称的正半定矩阵，且是正定的。如果存在着，且满足下式，则满足(*)式。其中 如果向量被分成两部分，其中表示不可调节的变量，表示可调节的变量。假设目标函数是确定的，独立于可调节的变量，则相应的锥优化问题为，是一个锥。则相应于不确定集合的鲁棒counterpart为则可调节的鲁棒规划为。可调节的鲁棒规划比一般的鲁棒灵活一些。但是这样会导致所得到的问题是不易处理的。克服计算上缺点的一个

11、方法是限制可调节的变量为一个仿射函数。，这样得到了仿射可调节的鲁棒规划为对于结构不确定的锥二次约束可表示为，如果分别用表示的子向量，并且分别对应于不可调节的部分和可调节的部分，则上面的约束可以表示为(*)，若，则上面的约束即为仿射可调节的约束。下面分成两种情况来讨论，一种是固定的recourse,即是确定的，一种是可变的recourse，即是不确定的。在第一种情况下，如果约束由(*)表达，扰动集合为中心在原点的椭圆的交集，如果存在和使得下式成立，则会存在一个解满足(*)，对于所有的扰动成立， 其中， 在第二种情况下，如果扰动很小，使得二次项可以被忽略，则可以用上面的半定规划来近似。如果二次项不

12、能够被忽略，则需要增加一些变量后能够用一个半定规划来近似。 2.3 鲁棒凸优化2.3.1鲁棒凸二次约束的规划问题 一个凸二次约束的规划问题为，其中为决策向量，为参数。上面的这个问题可以转化为一个二阶的锥规划问题由于上述的模型对于参数很敏感，所以有必要研究其对应的鲁棒问题一个一般的鲁棒凸二次规划问题为当不确定的集合是椭球时，上面的问题可以转化为一个半定规划问题，这里我们来确定的结构，使它能够转化为一个二阶锥规划。分成以下的三种情况:1离散集合和多边形不确定集合对于离散形式的集合定义为，鲁棒约束等价于K个凸二次约束。或者等价的个二阶锥约束。对于离散集合的凸包为，则鲁棒约束等价于将上面的两种情况下的

13、集合推广到多边形的不确定集合。如果决策向量满足鲁棒约束，对于所有的，当且仅当存在着，使得其中是的第列，。2范数约束的不确定的集合一个决策向量满足鲁棒约束，对于所有的，当且仅当存在和，满足，其中，二次项和锥项的不确定性是独立的，即一个决策向量满足鲁棒约束，对于所有的，当且仅当存在和，满足，其中，3因子化的不确定的集合如果不确定的集合定义为一个决策向量满足鲁棒约束，对于所有的，当且仅当存在，使得下式成立其中是的谱分解，。2.3.2二次约束的二次规划的鲁棒解 对于一个非凸的二次约束的二次优化问题 其中是一个多面体，并且包含在中，每个的形式为。任何一个二次多项式可以写成两个正系数的二次多项式的差，一个

14、一般的(QQP)可以写成由于，则问题可以转化为通过变换记号，可以得到这样的形式 其中，所有的系数为正的。，并且为单调递增的二次函数使得由于孤立的最优解即使是可计算的，但是它是难于实施，因为它对一个小的扰动非常的不稳定，因而，从实际的观点来看，只有非孤立的可行解有意义。 Essential 最优解，表示所以非孤立的可行解的集合。 Essential可行解：满足。一个非孤立的可行解称为是Essential最优解，如果它满足寻找Essential最优解的方法是：从一个初始的Essential可行解，寻找一个更好的Essential可行解，直到不能获得比当前的可行解更好的可行解为止。假设为一个Esse

15、ntial可行解的目标函数值，给定：如果，由于单调递增，则如果，则即为一个Essential可行解如果，则需要考虑一个辅助的问题求解采用分支定界的方法。这篇文章中给出了一个successive incumbent transcending(SIT)算法。3 鲁棒优化的应用 鲁棒优化现在已经应用到了各个研究领域，这里我们主要给出了在金融上的应用。1Ruijun Shen和Shuzhong Zhang将鲁棒的观点应用于基于scenario树的投资组合的选择问题中，给出了一阶段和两阶段的组合选择模型相应的鲁棒规划问题。这里允许概率分布存在ambiguity.这样的一个问题能够转化为一个有限的锥形式凸

16、规划问题。并且在不允许卖空的情况下，效用函数采用下半方差的负值，参数的不确定集合是椭球形的，则相应的问题可以转化成一个二阶锥规划问题。 假设想从种资产中选择一个投资组合并且持有一段时间，假设初始的财富为1，持有期末有种可能的结果。即所有的可能的scenario可以通过一个具有个叶子的一阶段树来表示。假设收益向量的第个元素表示表示第种资产的收益。则基于scenario的单阶段的组合选择模型为 是股票的数量，是每个节点scenario的数量是持有的股票，是模型中的决策向量是如果scenario 出现的话个股票的收益是scenario 出现的概率是分量全为1的向量是允许的投资组合集合则两阶段的效用极

17、大化投资模型为 表示如果scenario 出现在第一阶段，scenario 出现在第二阶段表示条件概率scenario 出现在第二阶段在scenario 出现在第一阶段的条件下的概率。第二阶段允许的投资组合是第二阶段的recourse问题的最优解则上面的问题可以写成(P2) 假设可行集为凸集令，且由定义可知为非负的向量问题(P2)是可分的，则可得由于是凹的，则上面的问题为凸规划。单阶段模型的鲁棒规划模型确定的情景树有两个缺点：一个是每个情境中收益的模糊性，一个是每个情景发生的条件概率的模糊性。实际上在我们的模型中用到的收益向量为估计值。并且我们并不知道确切的收益为多少，但是根据统计分析，我们知

18、道实际的值离我们估计的值不远，我们可以得到某些置信区间。（收益的模糊性）（概率分布的模糊性）假设所有的集合为凸的，紧的，非空的。令，则鲁棒模型为两阶段的鲁棒规划模型两阶段的模型中的估计量为,令，,令，.单阶段鲁棒模型的有限表示假设条件：1 没有卖空 2 一个半方差的非效用函数相当于一个给定的基准组合的下方风险，相应的效用函数为。模糊集合是椭球形的：，为了简便，假设是单位矩阵，则原模型可变形为则相应的鲁棒规划模型为进一步变形为利用结论将上面的规划变为对于一个一般的模型通过增加变量变为如果是一个凸集，则它的齐次锥是则可以得到如下的凸表示对于多阶段的鲁棒模型因此把球映射到区间，则上述模型等价于2R.

19、h.tutuncu, M.Koenig给出一个基于worse-case的方法。在一个简单的情况下，相应鲁棒优化问题是一个标准的二次规划问题，在大多数情况下，这个问题可以转化为一个鞍点问题。利用2003年Handorsson和Tutuncu给出的方法求解。作者给出了在不确定集合为区间时的鲁棒MVO模型，和鲁棒最大夏普比率问题。一个资产分配问题可以表示为在期望收益的下限上极小化方差或最大化一个风险调节的期望收益 （1） （2）其中对于期望收益的向量和协方差矩阵分别取成区间的形式采用区间型数据的原因：（1）区间的端点对应于历史数据中相应的统计的极值，在分析估计和Scenarios中。（2）建模者可以

20、选择置信水平，以预测区间的形式产生收益和协方差的估计。给定不确定集合，优化问题（1）（2）对应的鲁棒优化为 （7） （8）若是（8）一个给定正值的最优解，则也是（7）的最优解对于。US财政证券可以认为是无风险投资。如果这样的资产包含于资产类中，则有效的投资组合是这个无风险资产和一个风险组合的线性组合。这个最优的组合是具有最高夏普比率的组合。，为无风险的已知收益。假设是正定的。因为是正半定的，若它是正定的，则意味着没有冗余的资产。具有最高夏普比率的组合可以通过解决下面的优化问题给出： （11）这个目标函数是一个非线性，非凹的目标函数，难以解决。利用lifting技术对进行齐次化：，增加是为了或得

21、一个凸集。是一个锥，当是一个环的时候，是一个ice-cream锥，若是一个多面体，则。，由于是齐次的，则问题等价于，由于是齐次的，则增加规范化的约束不会影响最优解，则问题等价于 结论：给定一个可行的具有性质的组合集，这个集合中具有最大夏普比率的解可以通过下面的规划来解： （15）若是（15）的解，则。松弛问题如下：鲁棒有效前沿的算法：1利用SP算法解决没有期望收益约束的问题，令表示他的最优解，令2，解决问题，令表示他的最优解，3 选择，有效前沿上点的数量，解决问题3Mustafa C.Pinar 给出了多阶段的组合选择模型。目标是最大化最终期望收益和最小化与一个给定的财富水平的偏差。他们之间是

22、通过一个非负参数来平衡的。利用一个分段的线性罚函数，能够得到线性规划模型，并且能够确保如下阶段的最优性。假设有种资产，前种为风险的股票，第种为无风险资产，比如现金。表示1阶段初的决策向量，表示相应的组合种第种资产的市值。表示2阶段初的决策向量，表示一阶段和二阶段结束后的净资产收益。是有限概率空间上的离散的随机变量。假设市场的发展是离散的scenario树。表示随机变量相应于第一层scenario树的第n个节点的实现。基于最大的期望end-of-horizon组合值的没有交易费用的两阶段组合选择模型的随机规划为：其中由于recourse 问题的可分性，上面的优化问题等价于以上的模型假设决策者是风

23、险中立的，Mulvey,Vanderbei and Zenios建议通过由一个参数控制给目标函数增加一个风险项得到两阶段的鲁棒随机规划。他们的模型为 （4）则可分离的鲁棒优化模型为（5）Takriti and Ahmed证明了对于任意的方差测度，上式对能够给出当两阶段的组合决策问题对于recourse问题不是最优时的最优解。 如果是一个非减的函数，则上面的两个问题时等价的。Takriti and Ahmed利用了一个分段二次的方差度量 ，其中是目标函数值。是一组离散的随机变量，具有实现，而是相应的概率。为了是计算方便是所得的问题是一个线性规划，采用一个分段线性的方差测度 它仍然满足非减的条件。

24、则我们的问题变为可以将上面的模型推广到三阶段的情况。在这篇文章中作者还给出了包含线性交易费用的模型。表示一阶段买入资产的数量，表示一阶段买入一美元的资产的交易费表示一阶段卖出资产的数量，表示一阶段卖出一美元的资产的交易费表示的第个分量则对于风险资产， 对于无风险资产初始的资金要求为则可行集为带有交易成本的鲁棒两阶段的投资组合选择的模型为 4. Aharon Ben-Tal, Tamar Margalit Arkadi Nemirovski给出了一个多阶段的组合选择问题的鲁棒建模方法。假设有种类型的资产和现金。个投资阶段。目标是控制这些资产的一个投资组合。表示投资组合中资产在阶段开始时的数量。可

25、以有下列的方程给出：时，是来自前一个阶段的数量，表示资产收益。表示在阶段初买入的资产数量。表示在阶段初卖出的资产数量。时，是从前一个阶段得到的现金流；是在阶段卖出资产得到的资产数量，表示交易成本表示在阶段买入资产得到的资产数量，表示交易成本应该满足约束假设约束为简单的约束，即下界为0，上界为无穷大目标是极大化期末财富的总价值。可得到线性规划模型为 令，其中，则新的规划为 其中 数据的不确定性 决策向量不是实的，是的可测函数，当决策向量实施的时候，数据就是立即可知。 不确定线性规划的鲁棒规划 为维的决策向量，为精确可知的目标，为不确定的约束矩阵。锥二次规划， 是的期望，是随机变量的协方差矩阵。是

26、随机变量的协方差。. 锥规划模型可以用已有的算法求解。4结论：这里给出了鲁棒优化的基本算法，最新的发展和在金融上的应用。今后的研究方向是对鲁棒优化算法本身的研究，另一个是将其用到金融上。参考文献1A.L.Soyster. Convex programming and set-inclusive constraints and application to inexact linear programming. Operation Research,21:1154-1157,19732J.E.Falk. Exact solution of inexact linear programs. Ope

27、ration Research,24,17963A.Ben-Tal and A.Nemirovski. Robust convex optimization. Math.Oper.Res.23:769-805,19984A.Ben-Tal and A.Nemirovski. Robust solution of uncertain linear programs. Operation Research Letters,25,19995A.Ben-Tal and A.Nemirovski. Robust optimization-methodology and applications. Mat

28、h.Program,.Ser.B92:453-480,20026Shen Ruijun Zhang shuzhong Robust portfolio selection based on a muli-stage tree,European Journal of operation research,191:864-887,20087Mustafa C.Pinar Robust scenario optimization based on downside-risk measure for multi-period portfolio selection. OR spectrum,20058

29、 Aharon Ben-Tal, Tamar Margalit Arkadi Nemirovski, robust modeling of multi-stage portfolio problems, draft paper9A.Ben-Tal A.Goryashko E.Guslitzer A.Nemirovski Adustable robust soltutions of uncertain linear programs Math.Program.Ser.A99:351-376,200410Odellia Boni A.Ben-Tal Adjustable robust counte

30、rpart of conic quadratic problems,Math Meth Oper Res68:211-233,200811O.Boni,A.Ben-Tal,A.Nemirovski, Robust solutions to conic quadratic problems and their applications, Optim.Eng. 9:1-18,200812A.Takeda, S.Taguchi, R.H.Tutuncu, Adjustable robust optimization models for a nonlinear two-period system,

31、Optim. Theory appl,136:275-295,200813Hoang Tuy. N.T.Hoai-Phuong, A robust algorithm for quadratic optimization under quadratic constraints, Journal of Global Optimization,37:557-569,200714D.Goldfarb,G.Iyengar, Robust convex quadratically constrained programs, Math.Program. Ser.B, 97:495-515,200315 A.Ben-Tal and A.Nemirovski.Selected topics in robust convex optimization,Math.Program. Ser.B,112:125-158,200816 A.Ben-Tal,S.Boyd and A.Nemirovski. Extending scope of robust optimization:comprehensive robust counterparts of uncertain problems, Math.Program. Ser.B,107:63-89,2006.页脚