鲁棒线性优化问题研究综述

书书书第２４卷第８期Ｖｏｌ．２４Ｎｏ．８控　制　与　决　策犆狅狀狋狉狅犾犪狀犱犇犲犮犻狊犻狅狀　２００９年８月　　Ａｕｇ．２００９收稿日期：２００８１０１２；修回日期：２００９０２２３．作者简介：邓鹏华（１９８３—），男，陕西洋县人，博士生，从事不确定决策、军事需求论证的研究；毕义明（１９６３—），男，山东阳信人，教授，博士生导师，从事不确定决策、作战建模与仿真等研究．　　文章编号：１００１０９２０（２００９）０８１１２１０５鲁棒线性优化问题研究综述邓鹏华，刘　颖，毕义明，杨　萍（第二炮兵工程学院基础部，西安７１００２５）摘　要：鲁棒优化（ＲＯ）是从计算复杂性的角度研究不确定优化模型鲁棒最优解的数学方法．从单阶段鲁棒优化和多阶段鲁棒优化两个方面对鲁棒线性优化（ＲＬＯ）理论的研究进展进行综述，前者的研究主要基于不同形式的不确定集合，后者的研究则基于前者的方法．研究多阶段不确定决策中决策变量受不确定参数实现值影响的情况，其核心是影响函数连续时的仿射可调鲁棒对应模型和函数离散时的有限适应性模型．最后对ＲＬＯ的研究前景作了展望．关键词：不确定决策；单阶段鲁棒线性优化；多阶段鲁棒线性优化中图分类号：Ｏ２２４　　　　文献标识码：Ａ犛狌狉狏犲狔狅狀狉狅犫狌狊狋犾犻狀犲犪狉狅狆狋犻犿犻狕犪狋犻狅狀犇犈犖犌犘犲狀犵犺狌犪，犔犐犝犢犻狀犵，犅犐犢犻犿犻狀犵，犢犃犖犌犘犻狀犵（ＤｅｐａｒｔｍｅｎｔｏｆＢａｓｉｃＳｃｉｅｎｃｅ，ＴｈｅＳｅｃｏｎｄＡｒｔｉｌｌｅｒｙＥｎｇｉｎｅｅｒｉｎｇＣｏｌｌｅｇｅ，Ｘｉ’ａｎ７１００２５，Ｃｈｉｎａ．Ｃｏｒｒｅｓｐｏｎｄｅｎｔ：ＤＥＮＧＰｅｎｇｈｕａ，Ｅｍａｉｌ：[e-mail]）犃犫狊狋狉犪犮狋：Ｒｏｂｕｓｔｏｐｔｉｍｉｚａｔｉｏｎｉｓａｍａｔｈｅｍａｔｉｃａｌｍｅｔｈｏｄｔｏａｄｄｒｅｓｓｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｓｆｏｒｔｈｅｕｎｃｅｒｔａｉｎｏｐｔｉｍｉｚａｔｉｏｎｍｏｄｅｌｓｉｎｔｅｒｍｓｏｆｃｏｍｐｕｔａｔｉｏｎａｌｃｏｍｐｌｅｘｉｔｙ．Ｍａｉｎｄｅｖｅｌｏｐｍｅｎｔｓｏｆｒｏｂｕｓｔｌｉｎｅａｒｏｐｔｉｍｉｚａｔｉｏｎ（ＲＬＯ）ａｒｅｓｕｒｖｅｙｅｄｆｒｏｍｔｗｏａｓｐｅｃｔｓ，ｓｉｎｇｌｅｓｔａｇｅａｎｄｍｕｌｔｉｓｔａｇｅｒｏｂｕｓｔｏｐｔｉｍｉｚａｔｉｏｎ．Ｔｈｅｆｏｒｍｅｒｉｓｂａｓｅｄｏｎｖａｒｉｏｕｓｍｏｄｅｌｉｎｇｆｏｒｍｓｏｆｕｎｃｅｒｔａｉｎｔｙｓｅｔ，ｗｈｉｌｅｔｈｅｌａｔｔｅｒｉｎｖｅｓｔｉｇａｔｅｓｔｈａｔｔｈｅｄｅｃｉｓｉｏｎｖａｒｉａｂｌｅｓｅｎｔａｒｅｄｅｐｅｎｄｏｎｔｈｅｒｅａｌｉｚａｔｉｏｎｏｆｕｎｃｅｒｔａｉｎｔｙｐａｒａｍｅｔｅｒｓｏｎｔｈｅｂａｓｉｓｏｆｔｈｅｆｏｒｍｅｒｔｈｅｏｒｉｅｓ，ｍａｉｎｌｙｉｎｖｏｌｖｉｎｇａｆｆｉｎｅｌｙａｄｊｕｓｔａｂｌｅｒｏｂｕｓｔｃｏｕｎｔｅｒｐａｒｔｉｎｔｈｅｃａｓｅｏｆｃｏｎｔｉｎｕｏｕｓｄｅｐｅｎｄｅｎｔｆｕｎｃｔｉｏｎａｎｄｆｉｎｉｔｅａｄａｐｔａｂｉｌｉｔｙｍｏｄｅｌｉｎｔｈｅｃａｓｅｏｆｄｉｓｃｒｅｔｅｄｅｐｅｎｄｅｎｔｆｕｎｃｔｉｏｎ．Ｆｉｎａｌｌｙ，ｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｅｓｏｆＲＬＯａｒｅｐｒｏｓｐｅｃｔｅｄ．犓犲狔狑狅狉犱狊：Ｄｅｃｉｓｉｏｎｍａｋｉｎｇｕｎｄｅｒｕｎｃｅｒｔａｉｎｔｙ；ＳｉｎｇｌｅｓｔａｇｅＲＬＯ；ＭｕｌｔｉｓｔａｇｅＲＬＯ１　引　　言优化理论研究最为成熟的是凸优化［１］．传统的凸优化模型是确定的，而现实世界本质上是不确定的．不确定性使得传统优化模型的最优解在不确定环境中可能为可行解但不再最优，或使原最优解变为非可行解．研究不确定性的基本途径是概率方法，Ｄａｎｔｚｉｇ［２］和Ｃｈａｒｎｅｓ等［３］分别提出了随机规划和机会约束规划模型．Ｌｉｕ［４］突破了可行集的概念，代之以不确定环境，提出了相关机会规划．这几类随机模型均假定随机参数的概率分布已知．在实际工程应用中，要得到随机参数的概率分布非常困难．首先是往往缺乏必要的历史数据；其次是实际问题中有多种形式的不确定性，仅用概率理论难以完全刻画．在经济和军事等领域，决策的鲁棒性至关重要．鲁棒优化（ＲＯ）理论是从计算复杂性的角度，研究参数在某个不确定集合内具有最坏情况值的不确定问题．ＲＯ理论不仅考虑大规模问题的易处理性，而且强调通过概率保证控制解的鲁棒性与最优性之间的折衷程度［５７］．本文对目前研究较为成熟的鲁棒线性优化（ＲＬＯ）理论进行综述．首先阐述了单阶段不确定决策中的ＲＬＯ理论，包括Ｓｏｙｓｔｅｒ模型、基于椭球的不确定集合、基于基约束的ＲＬＯ模型、基于一般范数的ＲＬＯ模型和基于风险偏好的ＲＬＯ模型；然后阐述了多阶段不确定决策中ＲＬＯ的仿射可调鲁棒对应（ＡＡＲＣ）模型和有限适应性（ＦＡ）模型；最后对ＲＬＯ理论的发展作了总结和展望．２　单阶段不确定决策的鲁棒线性优化单阶段不确定决策的特征是只有一次决策，所有决策都同时进行，决策前不知有关不确定参数的任何信息，因此不存在修正问题．２．１　犛狅狔狊狋犲狉鲁棒线性优化模型　　　控　　制　　与　　决　　策第２４卷对于如下一般的不确定ＬＰ问题：ｍａｘ犮Ｔ狓；ｓ．ｔ．∑犼∈犑珘犪犻犼狓犼≤犫犻，犻∈犐，珘犪犼∈犓犼，　　狓犼≥０，犼∈犑．（１）其中系数犃具有列方向上的区间不确定性，犃的每一列都属于一个凸集犓犼．该问题等价于如下问题：ｍａｘ犮Ｔ狓；ｓ．ｔ．ｍａｘ珘犪犼∈犓犼｛∑犼∈犑珘犪犻犼狓犼｝≤犫犻，犻∈犐，　　狓犼≥０，犼∈犑．（２）这便增加了问题的计算复杂性．为此，Ｓｏｙｓｔｅｒ提出将犃中所有值都用其最坏情况值代替并重新求解［８］，从而将不确定问题变为确定的ＬＰ问题．假定犪犻犼为犪犻犼最坏情况值，则式（１）可转化为ｍａｘ犮Ｔ狓；ｓ．ｔ．∑犼∈犑犪犻犼狓犼≤犫犻，犻∈犐，犪犼∈犓犼，　　狓犼≥０，犼∈犑．（３）Ｓｏｙｓｔｅｒ模型同样适用于价值向量犆不确定的线性ＲＯ问题．它能处理参数的不确定性并保持线性性质，但因过多强调解的适用性和模型易处理性而牺牲了解的最优性，因此被认为过于保守［８］．２．２　犅犲狀犜犪犾和犌犺犪狅狌犻的改进模型ＢｅｎＴａｌ等［９１１］和Ｇｈａｏｕｉ等［１２，１３］针对Ｓｏｙｓｔｅｒ模型的过分保守问题，分别提出将不确定系数看作未知概率分布的对称有界变量珘犪犻犼∈［珔犪犻犼－＾犪犻犼，珔犪犻犼＋＾犪犻犼］，其中珔犪犻犼为不确定参数珘犪犻犼的估计值．基于椭球不确定集合，式（１）可重新建模为ｍａｘ犮Ｔ狓ｓ．ｔ．∑犼珔犪犻犼狓犼＋∑犼∈犑犻＾犪犻犼狔犻犼＋Ω犻∑犼∈犑犻犪２犻犼狕２犻槡犼≤犫犻，　　－狔犻犼≤狓犼－狕犻犼≤狔犻犼，　　犻，犼∈犑犻，狓≥０，狔≥０．（４）其中Ω犻为违反约束条件的概率参数．对于模型的所有可行解而言，约束条件被违反的最大概率为ｅｘｐ（－Ω２犻／２）．显然，式（４）的可行解是式（１）可行解的子集，因此前者在一定程度上减小了后者的保守性．然而，在椭球不确定集合表示下，ＬＰ的鲁棒对应（ＲＣ）（即式（４））为ＳＯＣＰ，ＳＯＣＰ的鲁棒等价为ＳＤＰ，而ＳＤＰ的鲁棒等价问题是ＮＰｈａｒｄ问题．因此，基于椭球不确定集的ＲＯ方法增加了计算复杂性．另外，该模型无法控制解的鲁棒性与可行性之间的折衷程度，也无法处理离散优化问题．２．３　解的鲁棒性控制模型为解决ＲＯ模型中解的鲁棒性与可行性折衷问题，Ｂｅｒｔｓｉｍａｓ提出一种新的模型［１４］．对于椭球不确定集合，令相对不确定性为μ犻犼＝（珘犪犻犼－珔犪犻犼）／＾犪犻犼∈［－１，１］．一般只有部分参数是不确定的，故引入参数Γ犻，称为约束犻的不确定代价，使基约束∑犼∈犑狘μ犻犼狘≤Γ犻．显然，当Γ犻＝０时，退化为确定性模型；当Γ犻＝狘犑犻狘时，为Ｓｏｙｓｔｅｒ模型，它产生最保守的解；当Γ犻∈（０，狘犑犻狘）时，由Γ犻控制解的鲁棒性与最优性的折衷．若Γ犻为整数，则表示存在不确定的参数个数；否则，表示有└Γ犻┘个不确定参数，另有一个参数珘犪犻狋，其变化幅度为（Γ犻－└Γ犻┘）＾犪犻狋．建立不确定集合　犃＝｛珘犪犻犼狘珘犪犻犼＝珔犪犻犼＋＾犪犻犼μ犻犼，犻，犼，μ∈犎｝，（５）其中犎＝｛μ狘狘μ犻犼狘≤１，犻，犼，∑狘犑犻狘犼＝１狘μ犻犼狘≤Γ犻，犻｝．（６）由此式（２）可变为ｍａｘ｛犮Ｔ狓狘珔犪′犻狓＋ｍａｘμ犻∈犎犻∑狘犑犻狘犼＝１＾犪犻犼狓犼μ犻犼≤犫犻，犻，狓∈犡｝．（７）其中犎犻满足条件（６）．对于某一给定的犻，式（７）约束不等式左边第２项可转化为ｍａｘμ犻∈犎犻｛∑狘犑犻狘犼＝１＾犪犻犼狓犼μ犻犼狘∑狘犑犻狘犼＝１μ犻犼≤Γ犻，０≤μ犻犼≤１，犼｝．（８）于是，式（２）可转化为如下线性形式：ｍａｘ犮Ｔ狓；ｓ．ｔ．∑犼珔犪犻犼狓犼＋μ犻Γ犻＋∑犼∈犑犻狆犻犼≤犫犻，犻，　　μ犻＋狆犻犼≥＾犪犻犼狔犼，犻，犼∈犑犻，　　－狔犼≤狓犼≤狔犼，犼，犾犼≤狓犼≤狌犼，犼，　　狆犻犼≥０，犻，犼∈犑犻，狔犼≥０，犼，　　μ犻≥０，犻．（９）设μ犻犼为［－１，１］上对称分布的随机变量，要使违反不确定约束∑犼∈犑珘犪犻狓≤犫犻的最大概率为ε犻，则Γ犻的最小值为１＋Φ－１（１－ε犻）／狘犑犻槡狘．基于基约束不确定集合的ＲＬＯ模型的ＲＣ为线性模型，因此具有明显的计算优势，适合于解决离散不确定ＲＬＯ问题［１５，１６］．然而，这些模型中不确定数据之间是完全独立的．文献［１４］将上述模型推广到不确定数据相关的情况，证明同样可保持原有优化２２１１第８期邓鹏华等：鲁棒线性优化问题研究综述　　　问题的线性特性．２．４　基于一般范数的犚犔犗模型文献［１７］将不确定集合定义为犣＝｛珦犃狘‖犕（ｖｅｃ（珦犃）－ｖｅｃ（珡犃））‖≤Δ｝．其中：犕为可逆矩阵，珡犃为确定集合，‖·‖为某种形式的范数．则式（１）可转化为如下形式：ｍａｘ犮Ｔ狓；ｓ．ｔ．犪Ｔ犻狓＋Δ‖（犕Ｔ）－１狓犻‖≤犫犻，　　狓∈犡，犻＝１，２，…，犿．（１０）其中：‖·‖为对偶范数；狓犻∈犚（犿×狀）×１为向量，其第（犻－１）狀至第犻×狀个元素属于犚狀×１，其他元素为０．基于范数的不确定集合将产生一个对应范数约束的ＲＣ问题．文献［１７］指出：当范数类型为１范数或∞范数（二者对偶）时，其对应的鲁棒问题可表示为线性规划模型；当范数类型为欧氏范数时，则其ＲＣ为二次锥问题．对于鲁棒解可行性的概率保证问题，文献［１７］给出了下述结论：假定珦犃为任意分布，期望珡犃∈犚犿×狀和协方差阵犆∈犚（犿×狀）（犿×狀）已知，允许珦犃中各元素具有相关性．令狓∈犚狀×１为模型（１０）的最优解，狓犻∈犚（犿×狀）×１为一个向量，其第（犻－１）狀至第犻×狀个元素为狓，其他元素为０．则有：１）狓对第犻个约束中不确定参数的鲁棒概率满足犘（犪Ｔ犻狓≤犫犻）≥１－１１＋Δ２（‖犆１／２狓犻‖／‖犆１／２狓犻‖２）２；（１１）２）如果基于欧氏范数定义不确定集合，则有犘（犪Ｔ犻狓≤犫犻）≥１－１／（１＋Δ２）．（１２）基于范数不确定集合的鲁棒优化模型是从更广义的层次提出的，它不同于前面基于椭球不确定集合和基于基约束鲁棒线性优化模型．２．５　基于风险偏好的犚犔犗模型上述鲁棒优化模型都与参数不确定集合有关，尽管集合表示形式不同，但集合中的元素在问题求解中保持不变，无法反映不同方案的风险．为此，文献［１８］提出将线性优化中的不确定集合与风险偏好———表示为一致风险测度（ＣＲＭ）联系起来．［１９］进一步利用不确定集合构建了ＣＲＭ，并证明对于ＲＬＯ，不确定集合与ＣＲＭ构成双射关系［１４］．［２０］将ＣＲＭ扩展到更一般的风险测度———凸风险测度（满足凸性、单调性和平移不变性的风险测度），提出４种形式的鲁棒定义，并将它们与不同的凸风险测度相对应，给出了相应的概率保证．基于风险偏好的ＲＬＯ模型将不确定约束犪Ｔ狓≤犫，犪∈犣变为犪Ｔ狓≤犫＋β（犪），犪∈犚狀．其中β（犪）为惩罚函数．则上述鲁棒优化问题相当于：若犪∈犝，则β（犪）＝０；否则，β（犪）＝＋∞．上述模型是该模型的特例，从而该模型更少保守性．３