多目标风险规避两阶段随机规划问题

让我们用R表示（PV）在目标函数下的可行区域的图像，即R=z∈ RJ | z∈ R（Cx+Qy），（x，y）∈ 十、=[（x，y）∈XR（Cx+Qy）。（PV）的上部图像定义为setP=cl R=cl[（x，y）∈XR（Cx+Qy）。（3.1）特别是，我们有P∈ G、 即P是闭凸上集；见备注2.1。求（PV）的“最小”z向量被理解为计算集P的边界。为了完整性，我们回顾了（PV）的最小值概念。定义3.1。A点（x、y、z）∈ X×rj称为（PV）的弱极小化子（弱有效解），如果z∈ R（Cx+Qy）和z是R的弱极小元，即不存在z∈ R这样的Z∈ z+RJ++。定义3.2。（L¨ohne et al.（2014）定义3.2）A集合Z 如果满足以下条件，则X×Rj称为（PV）的弱解：1。恶意：持有cl公司z∈ RJ |（x，y，z）∈ Z+ RJ公司+= P、 2。最小值：每个（x、y、z）∈ Z是（PV）的弱极小值。理想情况下，人们会对计算（PV）的弱解Z感兴趣。然而，除了一些特殊情况（例如，当R和上部图像P的值为多面体集时），此类Z由无数个可行点组成，也就是说，仅使用无数个R值是不可能恢复P的。因此，我们的目标是提出通过无数个可行点近似计算P的算法。定义3.3。（L¨ohne等人（2014）中的定义3.3）让 > 0、非空有限集Z X×R称为有限弱-如果满足以下条件，则求解（PV）：1。-恶意：持有coz∈ RJ |（x，y，z）∈\'\'Z+ RJ公司+- 1. P、 2。最小值：每个（x、y、z）∈Z是（PV）的弱极小值。正如L¨ohne et al.（2014）所指出的，有限的-解决方案“Z”提供了P的外部和内部近似值，即COz∈ RJ |（x，y，z）∈\'\'Z+ RJ公司+- 1. P 有限公司z∈ RJ |（x，y，z）∈\'\'Z+ RJ+。

（3.2）让我们也介绍加权和标量化问题，其中权向量为w∈ RJ+\\{0}：最小wTz s.t.z∈ R（Cx+Qy），（x，y）∈ 十、（P（w））将P（w）定义为（P（w））的最佳值。在本节的其余部分，我们将讨论（P（w））最优解的存在性以及（P（w））和（PV）之间的关系。提案3.4。让w∈ RJ+\\{0}。然后，存在（P（w））的最优解（x，y，z）。证据注意P（w）=inf（x，y）∈Xхw（Cx+Qy），其中，Дw（·）是在（2.2）中定义的R乘以w的标度化。由于Дw（·）允许（2.3）中的对偶表示，它是LJ上的下半连续函数。此外，X是假设的紧集。根据Aliprantis和Border（2006）中的定理2.43，可以得出（P（w））的最优解存在。备注3.5。注意可行区域（x、y、z）∈ X×RJ | z∈ R（Cx+Qy）由于多变量风险度量R具有无界值，of（PV）通常不是紧的。然而，在L¨ohne etal。（2014），假设向量优化问题的可行区域是紧的。因此，假设只有X是紧的，命题3.4推广了L¨ohne等人（2014）的类似结果。Lohne等人（2014）在没有证据的情况下陈述了以下命题。这可以表示为Jahn（2004）中定理5.28的直接应用。提案3.6。（L¨ohne et al.（2014）中的命题3.4）让w∈ RJ+\\{0}。（P（w））的每个最优解（x，y，z）都是（PV）的一个弱极小值。命题3.6暗示，在弱意义上，解（PV）被理解为解族（P（w））w∈加权和标量化的RJ+\\{0}。4凸Benson算法（PV）凸Benson算法有一个原始变量和一个对偶变量。

原始近似算法计算（3.2）意义上的上部图像P的一系列外部近似，而对偶近似算法处理相关的向量最大化问题，称为几何对偶问题。为了解释这些算法的细节，我们应该定义几何对偶的概念以及一个新的尺度化问题（P（v）），称为参考变量v的尺度化问题∈ RJ。4.1参考变量的标量化问题问题（P（v））需要找到从点v进入上部图像P的最小步长∈ RJ\\P沿方向1=（1，…，1）T∈ RJ。其配方为asminαs.t.v+α1∈ R（Cx+Qy），（x，y）∈ X，α∈ R、 （P（v））注意，（P（v））是一个具有集值约束的标量凸优化问题。我们用P（v）表示（P（v））的最优值。我们放松了集值约束v+α1∈ R（Cx+Qy），并使用Borwein（1981）第3.2节的结果获得以下对偶问题：最大化γ∈RJ+inf（x，y）∈十、 α∈Rα+infz∈R（Cx+Qy）-v-α1γTz. （LD（v））注意，（LD（v））是通过将（P（v））的风险约束重写为0来构造的∈ R（Cx+Qy）- v- α1和计算集R的支持函数（Cx+Qy）- v- 双变量γ的α1∈ RJ+。下一个命题陈述了（P（v））和（LD（v））之间的强对偶关系。提案4.1。（Borwein（1981）中的定理19和方程（3.23））让v∈ RJ。然后，存在（P（v））的时间解（x（v），y（v），α（v））和（LD（v））的γ（v），并给出了这两个问题的最优值。最后，我们回顾了（P（v））和（PV）之间的关系。由于L¨ohne et al.（2014）中的证明可以直接应用于我们的案例，因此，下一个命题没有提供证明。提案4.2。（L¨ohne et al.（2014）中的命题4.5）让v∈ RJ。

如果（x（v），y（v），α（v））是（P（v））的最优解，那么（x（v），y（v），v+α（v）1）是（PV）的弱极小值。4.2几何二元论W是RJ中的单位单纯形，即W=w∈ RJ+| wT1=1.对于每个j∈ J，设e（J）是RJ中的jthunit向量，也就是说，e（J）的jthntry是一，其他所有的entries都是零。几何对偶问题（PV）定义为向量最大化问题max（w，…，wJ-1，P（w））Tw。r、 t.K（DV）s.t.w∈ W，其中K是所谓的订货锥，定义为K=λe（J）|λ≥ 0. 与（PV）的上部图像P类似，我们可以定义（DV）asD的下部图像D：=（w，…，wJ-1，p）∈ RJ | w=（w，…，wJ-1，wJ）∈ W，p≤ P（w）.备注4.3。与备注2.1类似，下图像D是一个闭凸K-下集，即cl co（D- K） =D。接下来，我们说明了D与（P（w）），（P（v）），（LD（v））的最优解之间的关系。提案4.4。（L¨ohne et al.（2014）中的命题3.5）让w∈ W如果（P（w））有一个确定的最佳值P（w），那么（w，…，wJ-1，P（w））是D的边界点，也是D的K-极大元，也就是说，不存在D∈ D使得dJ>P（w）。提案4.5。（L¨ohne et al.（2014）中的命题4.6、4.7）让v∈ RJ。如果（x（v），y（v），α（v））是（P（v））的非最优解，而γ（v）是（LD（v））的最优解，那么γ（v）是（DV）的最大化子，即，（γ（v），γJ-1（v），P（γ（v））是下图像D的K-最大元素。此外，{z∈ RJ |γT（v）z≥ γT（v）（v+α（v）1）}是点（v+α（v）1）处P的支撑半空间。提案4.6。让w∈ RJ+\\{0}。如果（x（w），y（w），z（w））是（P（w））的最优解，则{d∈ RJ |（zJ（w）- z（w），zJ（w）- zJ公司-1（w），1）Td≤ zJ（w）}是点（w，…，wJ）处D的支撑半空间-1，P（w））。证据根据命题4.4，d：=（w，…，wJ-1，P（w））是D的边界点。此外，它遵循（zJ（w）- z（w）。

，zJ（w）- zJ公司-1（w），1）Td=-wTz（w）+zJ（w）+P（w）=zJ因为P（w）=wTz（w）。因此，该命题的主张如下。提案4.7。（L¨ohne et al.（2014）中的命题3.10）让 > 0.（a）设“Z”为有限弱-（PV）的解。然后，引脚（(R)Z）：=coz∈ RJ |（x，y，z）∈\'\'Z+ RJ+是上部图像P的内部近似值，即引脚（(R)Z） P、 此外，Dout（(R)Z）=nd∈ RJ公司|zJ公司- zzJ公司- zJ公司-1, 1Td公司≤ zJ，z∈\'\'Zo是下部图像D的外部近似值，即D Dout（(R)Z）。（b） 让我们成为一个终结者-（DV）的解决方案。然后，Din（(R)W）：=co(（w，…，wJ-1，P（w））T | w∈\'\'W) - Kis是D的内部近似值，即Din（(R)W） D、 此外，撅嘴（(R)W）=z∈ RJ | wTz≥ P（w），w∈\'\'W是P的外近似值，即P 撅嘴（(R)W）。问题（P（w）），（P（v））和上述命题构成了原始和对偶convexBenson算法的基础。以下各节简要介绍了这些算法。4.3原始算法原始算法从上部图像P的初始外部近似Pf开始。对于每个j∈ 该算法通过求解加权和标量化问题（P（e（J）），用方向向量e（J）计算P的支撑半空间。如果（x（j），y（j），z（j））是（P（e（j））的最优解，则该半空间在点z（j）处支持上部图像P。然后，将Pis定义为这些J支撑半空间的交点。该算法迭代获得序列P P P . . .  P对于内部外部近似，它分别更新（PV）和（DV）的弱最小值和最大值集Z和W。在iterationk，算法首先计算Vk，即Pk的所有顶点的集合。对于每个顶点v∈ Vk，计算出（x（v），y（v），α（v））到（P（v））的最优解。最佳α（v）是找到P的边界点（v+α（v）1）所需的最小步长。

由于命题4.2中的三元组（x（v），y（v），v+α（v）1）是（PV）的弱极小化子，因此将其添加到集合Z中。然后，计算对偶问题（LD（v））的最优解γ（v），它是（DV）的最大化子（见命题4.5）并添加到集合W中。此过程将继续，直到顶点v的步长大于错误参数 > 检测到0。对于这样的v，利用命题4.5，得到了点（v+α（v）1）处P的支撑半空间。通过将Pk与该支撑半空间相交，外部近似值更新为Pk+1。当所有顶点都处于-到上部图像P的距离。在终止时，算法使用命题4.7计算上部图像P的内外近似值Pin（\'Z）、Pout（\'W）和Din（\'W）、Dout（\'Z）和下部图像D。请注意，Pout（\'W）和Pk都是P的外部近似值。然而，Pout（\'W）比Pk更接近外部近似值。原因是当PKI更新时，只有-使用到P的距离。另一方面，计算Pout（(R)W）时会考虑所有顶点。此外，该算法还返回一个finiewak-解决方案Z到（PV）和最终解决方案-（DV）的解W（见L¨ohne et al.（2014）中的定理4.9）。原始算法的步骤作为算法1.4.4对偶算法提供。对偶算法的步骤遵循与原始算法类似的方式；然而，作为主要区别，在每次迭代中，都会获得双图像D的外部近似值。此外，对偶算法不需要求解（P（v））；在初始化步骤和迭代中，对于不同的权重w，只需求解（P（w））。

（P（w））的最优解用于更新D的外部近似值，如命题4.6所示。算法1原始近似算法1：计算每个j的（x（j），y（j），z（j））到（P（e（j）））的最优解∈ J2： 设P={z∈ RJ:eT（j）z≥ P（e（j）），j∈ J}；3： k级← 0;\'\'Z← {（x（j），y（j），z（j））| j∈ J}；\'\'W← {e（j）| j∈ J}；4： 重复5：M← RJ；6： 计算Pk顶点的集合Vkof；7： 对于每个v∈ Vkdo8：计算（P（v））的最优解（x（v），y（v），α（v））和（LD（v））的最优解γ（v）；9： \'\'Z←\'\'Z∪ {（x（v），y（v），v+α（v）1）}；\'\'W←\'\'W∪ {γ（v）}；10： 如果α（v）> 然后11:M← M∩新西兰∈ RJ：γT（v）z≥ γT（v）（v+α（v）1）o；12： 中断；13： 结束if14：结束for15：如果M 6=RJTEN16：Pk+1← 主键∩ M、 k级← k+1；17： 结束if18：直到M=RJ；19： 按照第4.7条中的要求计算销（\'Z）、Pout（\'W）、Din（\'W）、Dout（\'Z）；20： 返回\'\'Z:A有限弱-（PV）的解决方案；“W：一个文件”-解决方案（DV）；销（\'Z）、Pout（\'W）、Din（\'W）、Dout（\'Z）；最后，该算法使用命题4.7计算上部图像P和下部图像D的内外近似值。此外，该算法返回一个有限弱-解决方案Z到（PV）和最终解决方案-（DV）的解W（见L¨ohne et al.（2014）中的定理4.14）。对偶算法的步骤作为标量问题的算法2.5场景分解提供。在本节中，我们感兴趣的是解决标量化问题（P（w））和（P（v））。请注意，这些问题是单目标多变量风险规避两阶段随机规划问题。对于这样的问题，问题的大小随着场景数量I的增加而增加。通过按场景进行分解，可以实现高效的解决方案。

在单变量情况下，对于风险中性的两阶段随机规划问题，请参见Birge和Louveaux（1997）、Birge和Louveaux（1988）、Kall和Mayer（2005）、Ruszczy'nski（2003）、Van Slyke和Wets（1969），了解场景分解的解决方法。对于两阶段风险规避随机规划问题中的场景分解，读者可以参考Ahmed（2006）、Miller和Ruszczy'nski（2011）、F'abi'an（2008）、Kristo Offersen（2005）了解具有单一一致风险规避目标函数的问题，也可以参考Liu等人（2016）了解机会约束问题。按照Collado等人（2012）的建议，对于具有动态一致风险度量的多阶段随机规划问题，也可以采用情景分解解决方法。与这些研究不同，我们所解决的标度化问题是具有多元凸风险测度的两阶段风险规避随机规划问题；因此，这些问题需要不同于现有问题的解决方法。算法2对偶近似算法1：计算η=（J，…，J）T的最优解（x（η），y（η）），z（η））到（P（η））；2： 设D={D∈ RJ | P（η）≥ dJ}；3： k级← 0;\'\'Z← {（x（η），y（η），z（η））}；\'\'W← {η};4： 重复5：M← RJ；6：计算Dk的顶点集Vkof；7： 对于每个t=（t，…，tJ-1，tJ）T∈ Vkdo8：设w=（t，…，tJ）-1, 1 -PJ公司-1j=1tj）T；9： 计算最优解（x（w），y（w），z（w））到（P（w））；10： \'\'Z←\'\'Z∪ {（x（w），y（w），z（w））}；11： 如果w∈ RJ++或tJ- P（w）≤  然后12:W←\'\'W∪ {w} ；13： 结束if14：如果tJ- P（w）> 然后15:M← M∩nd公司∈ RJ |（zJ（w）- z（w）。

，zJ（w）- zJ公司-1（w），1）Td≤ zJ（w）o；16： 中断；17： 结束if18：结束for19：如果M 6=RJTEN20：Dk+1← 丹麦∩ M、 k级← k+1；21：结束if22：直到M=RJ；23：计算销（(R)Z），Pout（(R)W）；Din（\'W），Dout（\'Z），如第4.7条所述；24：返回\'\'Z:A有限弱-（PV）的解决方案；“W：一个文件”-解决方案（DV）；销（\'Z）、Pout（\'W）、Din（\'W）、Dout（\'Z）；5.1加权和标量化问题∈ RJ+\\{0}。第3节中定义的加权和标度化问题（P（w））可以更明确地重写为：min wTz（P（w））s.t.z∈ R（Cx+Qy）Ax=bTix+Wiyi=hi，我∈ Ohmz∈ RJ，x∈ RM+，彝语∈ RN+，我∈ Ohm.我们提出了（P（w））的拉格朗日对偶形式，其目标函数是情景可分解的。详情见第5.1.1节。基于这种对偶重格式，在第5.1.2节中，我们提出了（P（w））的对偶割平面算法，称为对偶束方法，它提供了非最优对偶解。由于第4节中的Benson算法除了需要最优对偶解外，还需要一个最优原始解，因此在第5.1.3节中，我们证明了这种原始解可以从对偶丛方法中所谓的主问题的对偶中获得。5.1.1情景分解为了推导（P（w））的分解算法，我们将第一阶段变量x随机化∈ RMand将其视为元素x∈ LMX实现，xi∈ RM。为了确保新公式与前一公式的等价性，我们添加了所谓的非对抗性约束spi（xi- E[x]=0，我∈ Ohm,等于x=…=xi让我们介绍一下：=（x，y）∈ LM×LN |（xi，yi）∈ 金融机构，我∈ Ohm, （5.1）其中∈ Ohm,金融机构：=(xi，yi)∈ RM+×RN+| Axi=b，Tixi+Wiyi=hi.使用此符号并使用非对抗性约束，我们可以将（P（w））重写如下：min wTz（P（w））s.t。

z∈ R（Cx+Qy）pi（xi）- E[x]=0，我∈ Ohm（x，y）∈ F、 z∈ RJ。注意，（P（w））的最佳值是P（w）。以下定理通过以拉格朗日方式放松非对抗性约束，提供了（P（w））的对偶公式。我们把这个对偶公式称为（D（w））。定理5.1。它保持SP（w）=supu∈MJ，λ∈LM（Xi∈Ohmfi（ui，λi，w）- β（u，w）| E[λ]=0，（D（w）），其中，对于每个i∈ Ohm, ui∈ RJ+，λi∈ RM，fi（ui，λi，w）：=inf（xi，yi）∈金融机构wT[ui·（Cxi+Qiyi）]+πλTixi, （5.2）和β由（2.1）定义。证据我们可以写ep（w）=inf（x，y）∈F、 z∈RJ公司wTz | z∈ R（Cx+Qy），pi（xi- E[x]=0，我∈ Ohm（5.3）=inf（x，y）∈Finfz公司∈R（Cx+Qy）wTz | pi（xi）- E[x]=0，我∈ Ohm（5.4）=inf（x，y）∈F（supu∈MJ公司wTEu[Cx+Qy]- β（u，w）| pi（xi- E[x]=0，我∈ Ohm), （5.5）如果到最后一行的通道为（2.3）。利用Sion（1958）的极大极小定理，我们可以互换最后一行中的上确界和内确界。该产量sp（w）=supu∈MJ（F（u，w）- β（u，w）），（5.6），其中，对于每个u∈ MJ，F（u，w）：=inf（x，y）∈FwTEu[Cx+Qy]| pi（xi- E[x]=0，我∈ Ohm. （5.7）让我们确定u∈ 乔丹。请注意，F（u，w）是大型线性规划的最佳值，其中不同情景下决策变量之间的唯一耦合约束是非对抗性约束。为了得到可分解为每个场景的子问题的该问题的表达式，我们将非对抗性约束对偶化。读者可参考Shapiro等人（2009）第2.4.2节，了解非对抗性约束双重化的详细信息。为此，让我们指定拉格朗日乘数∧，λI∈ 非预期约束的风险管理。注意，我们可以将其视为随机拉格朗日乘数∧的实现∈ LM。