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

通过线性规划的强对偶，F（u，w）=sup∧∈LMinf（x，y）∈F`（x，y，λ），其中拉格朗日`由`（x，y，λ）定义：=wTEu[Cx+Qy]+Xi∈Ohmpi∧Ti（xi- E[x]=wTEu[Cx+Qy]+Xi∈Ohm圆周率λi- E~λTxi，对于每个x∈ LM，y∈ LN，~λ∈ LM。给定这样的x，y，λ，注意`（x，y，λ）=`（x，y，λ）=wTEu[Cx+Qy]+Xi∈OhmpiλTixi=wTEu[Cx+Qy]+EλTx,如果我们设置λ：=λ- E~λ. 在这种情况下，E[λ]=0。因此，我们得到f（u，w）=supλ∈LM公司inf（x，y）∈F`（x，y，λ）| E[λ]=0= supλ∈LM公司inf（x，y）∈FwTEu[Cx+Qy]+EλTx| E[λ]=0= supλ∈LM（Xi∈Ohmfi（ui，λi，w）| E[λ]=0），（5.8），其中fi（ui，λi，w），由（5.2）定义，是场景i子问题的最佳值∈ Ohm. 定理的断言来自（5.6）和（5.8）。5.1.2对偶丛方法为了求解定理5.1中给出的（D（w）），我们提出了一种对偶丛方法，它构造了fi（·，·，w），i∈ Ohm, 和-β（·，w）。上近似值基于这些函数在点（u（`）、λ（`））处的次梯度，这些点是通过解决所谓的主问题迭代生成的。读者可参考Ruszczy\'nski（2006）了解捆绑方法的详细信息。对于i∈ Ohm, ui∈ RJ+，λ∈ RM，我们表示为ui，λifi（ui，λi，w）点（ui，λi）处凹函数fi（·，·，w）的次微分，即，ui，λifi（ui，λi，w）是所有向量的集合（gui，gλi）∈ RJ+Msuch thatfi（ui，λi，w）≤ fi（ui，λi，w）+gTui（ui- ui）+gTλi（λi- λi，（5.9）对于所有ui∈ RJ+，λi∈ RM。注意，（5.9）的右侧为fi（·，·，w）提供了一个有效的上近似值。因此，（5.9）被称为切割。类似地，我们表示为u(-β） （u，w）凹函数的次微分-点u处的β（·，w）∈ MJ，是所有向量ρu=（ρu，…，ρuI）的集合∈ RJ×Isuch- β（u，w）≤ -β（u，w）+Xi∈OhmρTui（ui- ui）（5.10）适用于所有u∈ 乔丹。

我们称（5.10）为-β（·，w）。在下一个命题中，我们将展示如何计算函数fi（·，·，w）在点（ui，λi）的次微分。提案5.2。对于i∈ Ohm, ui∈ RJ+，λi∈ RM，letAi（ui，λi，w）：=arg min（xi，yi）∈金融机构wT[ui·（Cxi+Qiyi）]+π（λi）Txi.然后ui，λifi（ui，λi，w）=co{（w·（Cxi+Qiyi），pixi）|（xi，yi）∈ Ai（ui，λi，w）}。证据设νi（xi，yi，ui，λi，w）：=wT[ui·（Cxi+Qiyi）]+piλTixi。函数Дi（xi，yi，·，·，w）是所有函数（xi，yi）∈ 金融机构。函数Дi（·，·，ui，λi，w）对于所有ui也是有效且连续的∈ RJ+，λi∈ RM。最后，假设集fi是紧的。根据Ruszczy\'nski（2006）中的定理2.87，该命题的断言如下。接下来，我们将演示如何计算函数的次梯度-μ点处的β（·，w）。提案5.3。回想一下，集合A=u∈ LJ | 0∈ R（u）是u的R.验收集∈ LJ+，letB（u，w）：=arg最大值∈AwTEu[u]，并假设B（u，w）6=. 然后u(-β） （u，w） co{（w·u，…，w·uI）| u=（u，…，uI）∈ B（u，w）}。证据设ν（u，u，w）：=wTEu[u]。函数Д（u，·，w）适用于所有u∈ A、 函数Д（·，u，w）也是所有u的唯一连续函数∈ M、 根据Ruszczy\'nski（2006）中的定理2.87，该命题的断言如下。备注5.4。对于实际风险度量，如多元熵风险度量（见示例2.3），函数-β（·，w）是可微分的，次微分是单态的。对于相干的多元风险度量，如多元CVaR（参见示例2.2），存在一个凸锥Q MJ因此-β（u，w）=0如果u∈ Q和-β（u，w）=-∞ 否则对于具有风险规避参数ν的多元CVaR∈ （0，1）J，Q=（u∈ MJ公司ujipi≤1.- νj，我∈ Ohm, j∈ J） 。对于一致的多元风险度量，u(-β） （u）是u处Q的所有法线方向的集合。

因此，切割（5.10）总是令人满意的；因此，可以忽略它。在bundle方法的每次迭代k中，我们解决了主问题maxxi∈Ohmθi+η-xi∈Ohm%ui- u（k）i-xi∈Ohm%λi-(R)λ（k）i（MP（w））s.t.θi≤ fi（u（`）i，λ（`）i，w）+gTu（`）i（ui- u（`）i）+gTλ（`）i（λi- λ（`）i），我∈ Ohm, ` ∈ L（5.11）η≤ -β（u（`），w）+Xi∈OhmρTu（`）i（ui- u（`）i），` ∈ L（5.12）Xi∈Ohmpiλi=0（5.13）Xi∈Ohmui=1（5.14）ui∈ RJ+，λi∈ RM，θi∈ R我∈ Ohm (5.15)η ∈ R、 （5.16）L={1，…，k}，%>0。这里，k·k表示适当维度上的欧几里德范数。请注意，u的约束条件（5.14）和（5.15）等同于具有u∈ MJ和λ的约束（5.13）等价于E[λ]=0。u（k）∈ MJ，(R)λ（k）∈ E[(R)λ（k）]=0的lm是问题的参数，称为中心，在束方法中初始化和更新。目标函数中的二次项是Moreau-Yosida正则化项，它们使整个目标函数严格凸。这些正则化项强制（MP（w））的最优解靠近中心。设（u（k+1）、λ（k+1）、θ（k+1）、η（k+1））为（MP（w））的最优解。计算次梯度（gu（k+1）i，gλ（k+1）i）∈ ui，λifi（u（k+1）i，λ（k+1）i），我∈ Ohm,（ρu（k+1），ρu（k+1）I）∈ uβ（u（k+1），w）在该最佳解决方案下，使用（5.9）和（5.10），对每个函数fi（·，·，w），i∈ Ohm, 和-在下一次迭代中将β（·，w）添加到（MP（w）），以改进这些函数的上近似。中心按以下方式更新。在迭代k中，检查在点（u（k），λ（k））处评估的（D（w））的客观值之间的差异，即Pi∈Ohmfi（u（k）i，λ（k）i，w）-β（u（k），w），以及在中心评估的目标值u（k-1） ，(R)λ（k-1） ，即Pi∈Ohmfi（°u（k-1） i，’λ（k-1） i，w）- β（(R)u（k-1） ，w），大于阈值。

如果是，这意味着（D（w））的最优解接近（u（k），λ（k））。因此，新中心u（k）、？λ（k）分别设置为u（k）、λ（k）。这称为下降步骤。否则，中心保持不变，即，’u（k），’λ（k）设置为’u（k-1） ，(R)λ（k-1） ，分别为。我们的双束方法的步骤如算法3所示。根据（Ruszczy'nski，2006，定理7.16），束方法生成序列（(R)u（k），(R)λ（k））k∈n收敛到（D（w））为k的最优解→ ∞. 在实践中，算法3第22行中的停止条件不满足。因此，通常情况下，在出现Nxi时停止算法∈Ohmθ（k+1）i+η（k+1）-\'F（k+1）≤ ε（5.17），对于一些小常数ε>0。备注5.5。注意，（MP（w））的目标函数可以替换为θ+η-xi∈Ohm%ui- u（k）i-xi∈Ohm%λi-(R)λ（k）i约束（5.11）可替换为θ≤xi∈Ohmfi（u（`）i，λ（`）i，w）+gTu（`）i（ui- u（`）i）+gTλ（`）i（λi- λ（`）i）, ` ∈ 五十、 这样可以得到sumPi的上近似值∈Ohmfi（·，·，w）。与（5.11）中的多个片段相比，这为PI提供了更宽松的上近似值∈Ohmfi（·，·，w）。然而，当一个addsI=|Ohm| 在多次切割版本中，每次迭代都会进行切割，这种方法会添加一次切割。5.1.3原始解的恢复原始和对偶Benson算法都需要问题（P（w））的最优解（x（w），y（w），z（w））。因此，在定理5.6中，我们建议一种从主问题（MP（w））的解中恢复最优原始解的方法。定理5.6。设L={1，…，k}为对偶丛方法最后一次迭代时的索引集，对于某些ε>0，具有近似停止条件（5.17）。设n+1为满足近似停止条件后的第一次下降迭代，并设L={1，…，n}。

对于中心为？u（k），？λ（k）且指数集为L的（M P（w）），设τ=（τ（`）i）i∈Ohm,`∈五十、 θ=（θ（`））`∈五十、 σ∈ RM，ψ∈ RJ，ν=（νi）i∈Ohm是拉格朗日对偶算法3（P（w））1:k的对偶丛方法← 0，L← , γ ∈ （0，1），θ（1）i← ∞ 对于每个i∈ Ohm, η(1)← ∞,\'\'F（1）← 0;2： Letu（1）∈ MJ，λ（1）∈ l确保Eλ(1)= 0;3： 重复4：k← k+1；5： 对于每个i∈ Ohm do6：计算子问题min（xi，yi）的最优解（x（k）i，y（k）i）和最优值fi（u（k）i，λ（k）i，w）∈金融机构带u（k）i·（Cxi+Qiyi）i+pi（λ（k）i）Txi;7： 计算次梯度gu（k）i=w·（Cx（k）i+Qiy（k）i），gλ（k）i=pix（k）i；8： 结束9：计算β（u（k），w）和次梯度（ρu（k），ρu（k）I）∈ u(-β） （u（k），w）；10： F（k）←圆周率∈Ohmfi（u（k）i，λ（k）i，w）- β（u（k），w）；11： 如果F（k）<π∈Ohmθ（k）i+η（k）然后12:L← L∪ {k} ；13： 结束if14：如果（k=1）或（k≥ 2和F（k）≥ (1 - γ） \'F（k）+γ（Pi∈Ohmθ（k）i+η（k）））然后15：(R)u（k）← u（k），？λ（k）← λ（k）；16： else17：(R)u（k）← u（k-1） ，(R)λ（k）←(R)λ（k-1);18： 结束if19：解决主问题。设（u（k+1）、λ（k+1）、θ（k+1）、η（k+1））为最优解；20： （可选）删除主问题解决方案中对偶变量为零的所有切割；21:F（k+1）←圆周率∈Ohmfi（(R)u（k）i，(R)λ（k）i，w）- β（(R)u（k），w）；22:untilPi∈Ohmθ（k+1）i+η（k+1）=F（k+1）；23：返回\'F（k+1）：最佳值P（w）；（？（k），？（k））：一个（D（w））的最优解；分别分配给约束（5.11）、（5.12）、（5.13）、（5.14）、（5.15）的变量，带τ（`）i≥ 0, θ(`)≥0，νi∈ RJ+用于每个i∈ Ohm, ` ∈ 五十、 设（x（`）i，y（`）i）是算法3第6行中每个i的子问题的最优解∈ Ohm 和`∈ 五十、 让τ（n+1）=（τ（`，n+1）i）i∈Ohm,`∈五十、 θ（n+1）=（θ（`，n+1））`∈五十、 σ（n+1），ψ（n+1），ν（n+1）=（ν（n+1）i）∈Ohm是（MP（w））的对偶最优解。

设x（w）=（（x（w））i）i∈Ohm, y（w）=（（y（w））i）i∈Ohm定义为（x（w））i：=x`∈Lτ（`）ix（`）i，（y（w））i：=X`∈Lτ（`）iy（`）i。此外，设z（w）是问题infz的极小值∈R（Cx（w）+Qy（w））wTz。那么，（x（w），y（w），z（w））是（P（w））在以下意义上的近似最优解：（a）（（x（w））i，（y（w））i）∈ 每个i的F∈ Ohm.（b） z（w）∈ R（Cx（w）+Qy（w））。（c） Asε→ 0，它保持（x（w））i- σ（n+1）→ 每个i 0∈ Ohm.（d） Asε→ 0，它保持wTz（w）→ P（w）。附录A.5.2中给出了定理5.6的证明，即参考变量let v的标度化问题∈ RJ\\P。第4.1节中定义的问题（P（v））用于确定从v沿方向1输入P的最小步长∈ rj可以更明确地重写为asminα（P（v））s.t.v+α1∈ R（Cx+Qy）Ax=bTix+Wiyi=高我∈ Ohmα ∈ R、 x个∈ RM+，彝语∈ 注册护士+我∈ Ohm.我们为（P（v））提出了一种基于场景的分解求解方法。即使我们遵循的步骤与（P（w））的步骤相似，分解也更加复杂，因为权重不是参数，而是（P（v））对偶问题中的决策变量（见下面的定理5.11）。因此，遵循与（P（w））中相同的步骤会导致非凸优化问题。为了解决这个凸性问题，我们提出了一个新的公式（P（v）），方法是在R的双重表示中引入有限的度量。本节的流程如下：在第5.2.1节和第5.2.2节中，我们提出了（P（v））的情景分解解方法。第5.2.3节专门讨论原始溶液的回收。5.2.1情景分解为了推导（P（v））的分解算法，我们将第一阶段变量x随机化∈ RMas in（P（w）），并添加非对抗性约束spi（xi- E[x]=0，我∈ Ohm.使用（5.1）定义的可行区域F，我们可以将（P（v））重写如下：minα（P（v））s.t。

v+α1∈ R（Cx+Qy）pi（xi）- E[x]=0我∈ Ohm（x，y）∈ Fα∈ 注意，（P（v））的最佳值是P（v）。与（P（w））的方法不同，为了获得（P（v））的凸对偶问题，我们在R的对偶表示中使用有限测度m而不是概率测度u。为此，让mjfb表示所有J维向量的集合m=（m，…，mJ）来定义测度Ohm, 也就是说，对于每个j∈ J，有限测度mjito为i指定基本事件{i}∈ Ohm. 对于m∈ MJfand i公司∈ Ohm, 我们还编写emi：=（mi，…，mJi）T∈ RJ。下面的引理提供了u和m之间的关系。引理5.7。对于每u∈ MJ和γ∈ RJ+\\{0}，存在m∈ mjf确定γTEu[u]=Xi∈OhmmTiui，γT1=Xi∈OhmmTi1，（5.18）每u∈ LJ。相反，对于每m∈ MJf，存在u∈ MJ和γ∈ RJ+\\{0}，使得（5.18）保持每u∈ LJ。证据Letu∈ MJ和γ∈ RJ+\\{0}。定义m∈ MJfbymji=γjuji，我∈ Ohm, j∈ J然后，微不足道的是，（5.18）适用于每一个u∈ LJ。相反，设m∈ MJf。定义u∈ MJ和γ∈ RJ+\\{0}乘以γj=Xi∈Ohmmji，uji=（mjiγjifγj>0，Iifγj=0，我∈ Ohm, j∈ J然后，微不足道的是，（5.18）适用于每一个u∈ LJ。回想一下，β是（2.1）中定义的R的最小惩罚函数。对于m∈ MJf，让我们定义▄β（m）=supu∈AXi公司∈OhmmTiui。（5.19）同样，回顾（5.2）中定义的功能。对于m∈ MJfandλ∈ LM，让我们定义fi（mi，λi）=inf（xi，yi）∈金融机构mTi（Cxi+Qiyi）+piλTixi. （5.20）因此，如果u∈ MJ，γ∈ RJ+\\{0}和m∈ 与引理5.7和λ相关的MJfare∈ LM，那么很明显β（u，γ）=β（m），fi（ui，λi，γ）=fi（mi，λi）。示例5.8。回顾关于多元熵风险度量的示例2.3。函数▄β（·）的形式为▄β（m）=Xj∈JδJH（mj | | p）- mjT公司+ infs公司∈C+Xj∈JδJsj公司- （mjT1）日志sj,式中，1=（1，…，1）T∈ RIand H（mj | p）是mj相对于p的相对熵，由H（mj | p）=Xi定义∈Ohmmjilogmjipi！。示例5.9。

回顾多变量CVaR的示例2.2。函数▄β（·）的形式为▄β（m）=（0 ifmjipi≤1.-νjPi∈Ohmmji， 我∈ Ohm, j∈ J、+∞ 否则，每m∈ MJf。备注5.10。注意，一般来说，β（·，·）不是凸函数，因为（u，γ）7→ γTEu[u]不是凸函数。另一方面，β（·）是一个凸函数。的确，对于每一个我∈ Ohm 和u∈ A、 军情7处→ mTiuiis alinear函数使m 7→β（m）是一个凸函数，因为它是由u表示的线性函数的上确界∈ A、 类似地，fi（·，·，·）通常不是凹函数。然而，（mi，λi）7→f（mi，λi）在（xi，yi）索引的线性函数的范围内∈ 金融机构；因此，它是一个凹函数。定理5.11。它保持SP（v）=supu∈MJ，λ∈LM，γ∈RJ+（Xi∈Ohmfi（ui，λi，γ）- γ电视- β（u，γ）|γT1=1，E[λ]=0）=supm∈MJf，λ∈LM（Xi∈Ohmfi（mi，λi）-xi∈OhmmTiv-β（m）| Xi∈OhmmTi1=1，E[λ]=0）。（D（v））鉴于备注5.10，虽然定理5.11中提供的（P（v））的第一个重新公式不是一个凸优化问题，但第二个重新公式，即（D（v））是一个凸优化问题。定理5.11的证明使用引理5.7和以下独立引理。引理5.12。对于每个u∈ LJ，inf{α∈ R | v+α1∈ R（u）}=supγT（Eu[u]- 五）- β(u, γ) | u ∈ MJ，γT1=1，γ∈ RJ公司+.证据让u∈ LJ。注意inf{α∈ R | v+α1∈ R（u）}=inf{α∈ R | 0∈ R（u）- v- α1}是具有集值约束函数α7的单目标优化问题的最优值→H（α）=R（u）- v- α1. 利用Borwein（1981）中的Lagrange对偶，特别是定理19，我们得到了{α∈ R | v+α1∈ R（u）}=supγ∈RJinfα∈Rα+infz∈R（u）-v-α1γTz. （5.21）为了能够使用该结果，我们检查以下约束条件：H在0处打开∈ RJin认为对于每个α∈ 带0的R∈ H（α），对于每ε>0，在0附近存在一个开球V∈ RJ这样V[~α∈(α-ε、 α+ε）H（|α）。

（5.22）为此，让α∈ 带0的R∈ H（α），即v+α1∈ R（u）。设ε>0。由于R的单调性和平移性，1是RJ+的内点，R（u）+RJ+=R（u），因此v+（α+ε）1是R（u）的内点。另一方面，请注意[°α∈(α-ε、 α+ε）H（|α）=[|α∈(α-ε、 α+ε）R（u- v- α1）=R（u- v- （α+ε）1）=R（u）- v- （α+ε）1考虑到R的单调性和平移性。因此，0∈ RJ是上述联合体的一个内部点。因此，（5.22）对于一些开球V保持在0左右∈ RJand（5.21）如下。由于R（u）+RJ+=R（u）和R（u）是R的凸集，因此可以检查infz∈R（u）γTz=-∞ 对于每个γ/∈ RJ+。因此，（5.21）中的最高值可以在所有γ上进行评估∈ RJ+。最后，使用（2.3），我们得到inf{α∈ R | v+α1∈ R（u）}=supγ∈RJ+infα∈Rα+infz∈R（u）-v-α1γTz= supγ∈RJ+infα∈Rα- γT（v+α1）+supu∈MJ公司γTEu【u】- β(u, γ)!= supγ∈RJ+“infα∈R（1- γT1）α+supu∈MJ公司γT（Eu[u]- 五）- β(u, γ)#= 啜饮γT（Eu[u]- 五）- β(u, γ) | u ∈ MJ，γT1=1，γ∈ RJ公司+,其中，在最后一个等式中，我们使用infα∈R（1- 如果γT1=1和infα，则γT1）α=0∈R（1-γT1）α=-∞ 如果γT1 6=1。定理5.11的证明。使用引理5.12，我们可以写出ep（v）=inf（x，y）∈F、 α∈R{α| v+α1∈ R（Cx+Qy），pi（xi- E[x]=0我∈ Ohm}= inf（x，y）∈F{inf{α∈ R | v+α1∈ R（Cx+Qy）}pi（xi- E[x]=0我∈ Ohm}= inf（x，y）∈F（supu∈MJ，γ∈RJ+，γT1=1γT（Eu[Cx+Qy]- 五）- β(u, γ)| pi（xi- E[x]=0我∈ Ohm).利用Sion（1958）的极大极小定理，我们可以交换上确界和内确界，得到p（v）=supu∈MJ，γ∈RJ+，γT1=1F（u，γ）- γ电视- β(u, γ),其中，对于每个u∈ MJ，γ∈ RJ，F（u，γ）由（5.7）定义。因此，使用（5.8），我们得到p（v）=supu∈MJ，λ∈LM，γ∈RJ+（Xi∈Ohmfi（ui，λi，γ）- γ电视- β（u，γ）|γT1=1，E[λ]=0），其中fi由（5.2）定义。因此，第一次重新制定如下。

第二个重新公式源自第一个重新公式和引理5.7.5.2.2定理5.11中提供的求解（D（v））的对偶丛方法，我们提出了一种类似于第5.1.2节的对偶丛方法。在对偶束方法的每次迭代k中，我们解决下面给出的主问题（MP（v））。此处，（gmi，gλi）∈ RJ+Mdenotes点（mi，λi）处凹函数fi（·，·）的次梯度∈ RJ+×RM。类似地，（ρm，…，ρmI）∈ RJ×Idenotes凹函数的一个次梯度-m点处的|β（·）∈ MJf。我们称（5.23）和（5.24）为＠fi（·，·）和-β（·），分别为。maxXi公司∈Ohmθi+η-xi∈OhmmTiv-xi∈Ohm%惯性矩- \'m（k）i-xi∈Ohm%λi-(R)λ（k）i（MP（v））s.t.θi≤~fi（m（`）i，λ（`）i）+gTm（`）i（mi-m（`）i）+gTλ（`）i（λi-λ（`）i），我∈ Ohm, ` ∈ L（5.23）η≤ -β（m（`））+Xi∈OhmρTm（`）i（mi- m（`）i），` ∈ L（5.24）Xi∈Ohmpiλi=0（5.25）Xi∈OhmmTi1=1（5.26）mi∈ RJ+，λi∈ RM，θi∈ R我∈ Ohm (5.27)η ∈ R、 （5.28）这里，L={1，…，k}，%>0。算法4中提供了双束方法的步骤。与（5.17）类似，算法在实践中停止whenXi∈Ohmθ（k+1）i+η（k+1）-xi∈Ohm（m（k+1）i）Tv-\'F（k+1）≤ ε（5.29），对于某些ε>0。由于此算法的构造与算法3的构造类似，因此为了简洁起见，省略了详细信息。算法4（P（v））1:k的对偶丛方法← 0，L← , γ ∈ （0，1），θ（1）i← ∞ 对于每个i∈ Ohm, η(1)← ∞,\'\'F（1）← 0;2： 设m（1）∈ MJf，λ（1）∈ l确保Eλ(1)= 0;3： 重复4：k← k+1；5： 对于每个i∈ Ohm do6：计算子问题min（xi，yi）的最优解（x（k）i，y（k）i）和最优值fi（m（k）i，λ（k）i）∈金融机构（m（k）i）T（Cxi+Qiyi）+pi（λ（k）i）Txi;7： 计算次梯度gm（k）i=Cx（k）i+Qiy（k）i，gλ（k）i=pix（k+1）i；8： 结束第9步：计算￠β（m（k））和次梯度（ρm（k）。