凸风险函数的逆优化

条件风险值的优化。风险日记2 21–41。Ruszczy\'nski，Andrzej，A.Shapiro。凸风险函数的优化。运筹学数学31（3）433–452。Schaefer，A.J.2009年。逆整数规划。优化字母3 483–489。Zhang，J.，Z.Liu。计算一些线性规划反问题。计算与应用数学杂志72（2）261–273。Zhang，J.，C.Xu。线性约束凸可分离编程问题的逆优化。《欧洲运筹学杂志》200 671–679。引理3.4Proof的证明。应用定理3.3，我们立即得到ρ*（y） =最大值∈J{y>~ Xj- 任意y的δj}∈ R|Ohm|+∩ C和其他具体内容。我们有ρ*（y）≤ maxj公司∈J{y>~ Xj- δ*j} 福里∈ R|Ohm|+∩ C、 自δ起*j=ρ（~ Xj）=支持∈R|Ohm|+∩C{p>~ Xj- maxj公司∈J{p>~ Xj- δj}}≤ 支持∈R|Ohm|+∩C{p>~ Xj- （p>~ Xj- δj）}=δj。对于任何y，我们也有∈ R|Ohm|+∩ C、 ρ*（y） =sup~Z{y>~Z- ρ（~Z）}≥ maxj公司∈J{y>~ Xj-ρ（~ Xj）}=最大值∈J{y>~ Xj- δ*j} 。B推论4.5证明。对于任意Z和σ∈ ∑，我们有ρ（σ（~Z））=supp∈R|Ohm|+p> σ（~ Z）- ρ*（p） =支持∈R|Ohm|+σ-1（p）>~ Z- ρ*（p） =支持∈R|Ohm|+p> ~Z- ρ*（σ（p））。（36）因此，如果ρ*（σ（p））=ρ*（p） 对于任何σ∈ ∑，我们得到ρ（σ（~Z））=ρ（~Z）。相反，由于共轭的定义，我们得到ρ*（σ（p））=sup~Z~Z>σ（p）- ρ（~Z）=sup~Zσ-1（~ Z）>p- ρ（~Z）=sup~Z~Z>p- ρ（σ（~Z）），如果ρ（σ（~Z））=ρ（~Z），对于任何σ∈ ∑，我们有ρ*（σ（p））=ρ*（p） 。C命题证明4.8证明。

命题4.7意味着反问题可以等价地写成infρl，p | |ρl，p- §ρFcvx||∞以x为准*（d）∈ arg minx∈X（d）ρl，p（~ Z（X））d=1。。。，D、 ρl，p（~ Lk）≤ ρl，p（~英国）K∈ K、 （37）其中ρl，pdenotes是一个由顶点集{σ（~ Xj）}σ支持的律不变对偶C分段线性风险函数∈∑，j∈Jand次梯度集Cσ。可以仔细遵循命题3.7证明中的论点，将目标函数重新表述为maxσ∈∑，j∈J{|ρl，p（σ（~ Xj））- §ρFcvx（σ（~ Xj））|}，（38），然后通过验证命题3.7中的所有步骤是否适用于此处，重新制定第一组约束条件。实际上，我们可以将第一组约束中的优化问题重写为min（x，~ W）∈π（d）ρl，p（~ W）对于任何固定的d，其中集合∏（d）：={（x，~ W）| ~ W≥~Z（x），x∈ X（d）}自ρl起，pis单调。π（d）是凸的~W（d）*∈ {σ（~ Xj）}σ∈∑，j∈Jallows让我们写出最优性条件，即必须存在次梯度y∈ ρl，p（~ W*（d） ）如此>（~ W）-~W*（d） （）≥ 0，（x，~ W）∈ ∏（d）<=> y> ~W*（d）≤ minx公司∈X（d）y>~ Z（X）。自ρl，p∈ RFcvx，根据定理3.3，我们得到ρl，p（~ W*（d） ）=ρ**l、 p（~ W）*（d） ）=arg maxy{y>~ W*（d）- ρ*l、 p（y）}。等效地，对于任何固定的dy∈ ρl，p（~ W*（d） （）<=> {y:y>~ W*（d）- ρ*l、 p（y）≥ ρl，p（~ W*（d） ）}<=> {y:y>~ W*（d）- 最大σ∈∑，j∈J{y>σ（~ Xj）- ρl，p（σ（~ Xj））}≥ ρl，p（~ W*（d） ），y∈ R|Ohm|+∩ Cσ}<=> {y:y>~ W*（d）- y> σ（~ Xj）+ρl，p（σ（~ Xj））≥ ρl，p（~ W*（d） ），σ∈ ∑，J∈ J，y∈ R|Ohm|+∩ Cσ}，（39），其中引理3.4应用于第二行以推导共轭。最后，应用命题3.6，将（38）、（39）和（37）中的ρl、p（σ（~ Xj））替换为δj，为我们提供了最终公式。D命题4.9证明。我们首先考虑第二个问题（28）的减少。

首先注意，与yσ相关的约束*,Dc可以等效地写为，yσ*,d替换byyd，y>d ~ Xd≤ hd（yd）y>d（σ（~ Xi）-~Xd）≤ δi- δd，我∈ J \\{d}，σ∈ ∑，d=1。。。，D（40）码∈ R|Ohm|+∩ Cσ。我们证明了其他约束，即（28）中的第二个和第三个约束，通常也可以简化为toy>j（σ（~ Xi）-~Xj）≤ δi- δj，j∈ Ji 6=j，σ∈ ∑（41）yj∈ R|Ohm|+∩ Cσ，j∈ J我们通过证明给定任何可行解（u*, δ*, 第二个问题（28）的yσ，j）我们总是可以构造一个可行解（u*, δ*, yσ，j）与yσ，j满足yσ，j：=∑σ（Xσ∈∑σ-1（yσ，j）），σ∈ ∑，给出相同的最优值u*. 将此解代入（28）的第二个约束，我们得到y>σ，j（σ（~ Xi）- σ（~ Xj））=|∑|（σ（Pσ∈∑σ-1（yσ，j））>（σ（~ Xi）- σ（~ Xj））=|∑|（Pσ∈∑σ-1（yσ，j））>（σ00-1（σ（~ Xi））-~Xj）=∑|（Pσ∈∑y>σ，j（σ（σ00-1（σ（~ Xi）））- σ（~ Xj））≤|∑|（Pσ∈∑（δi- δj））=δi- δj，其中最后一个不等式是由于yσ，j的可行性。对于（28）的第三个约束，可以如下验证。自yσ，j∈ R|Ohm|+∩Cσ，我们有σ-1（yσ，j）∈ R|Ohm|+∩ Cσ。我们还有pσ∈∑∑∑∑σ-1（yσ，j）∈ Cσ，因为求和是凸组合，集合Cσ是凸的。鉴于此，我们还有yσ，j∈ Cσ定义为Cσ。。因此，我们可以用yσ，jbyσ（yj）代替某些yj∈ RMin在（28）中的第二个和第三个常数中，并得出减少值（41）。现在，约束（41）和（40）都可以重新安排为以下一般形式>jσ（~ Xi）≤ δi- δj+y>j ~ Xj，σ∈ ∑，j∈ J（42）我们一般展示了y>jσ（~ X）形式的约束≤ Bσ∈ ∑对于某些X和b可以被约化，然后可以应用于约化（41）和（40）。首先回想一下，置换矩阵Qσ是满足σ（~ X）=QσX和（Qσ）m，n的矩阵∈ {0，1}和Q>σ1=~ 1，Qσ1=~ 1。

因此，y>jσ（~ X）≤ Bσ∈ ∑可写为最大σ∈∑y>jQσ~X≤ b和asmaxQ∈Conv（{Qσ}σ∈∑y>jQ~X≤ b、 应用Birkho ff（1946）的结果，我们可以将所有置换矩阵的凸包重新表示为线性约束，并得出以下公式Maxq{y>jQ~X | Q>~1=~1，Q~1=~1，Q∈ RM×M+}≤ b、 通过推导上述线性规划的对偶问题，我们得到了minv，w{->v+->w | ~ Xy>- v ~>-~1w>≤ 0}≤ B<=> v、 w：~>v+~>w≤ b、 ~ Xy>- v ~>-~1w>≤ 由于总是存在满足上述约束的置换矩阵，因此上述线性规划具有强对偶性。我们现在考虑减少问题（27）。优化问题可以等价地表示为ASUPP∈R|Ohm|+∩Cσ，tp>~ Z- t受p>σ（~ Xj）影响≤ t+(R)δj，σ∈ ∑，j∈ J（43）我们可以应用上述相同的技术再次减少约束（43），这将导致最终公式。E命题证明4.12证明。假设4.11成立，我们始终可以转换Z（x，ξ）（满足假设4.1）分布和分布集{Fj}j中规定的概率值∈对于某些固定M，以n/M形式表示的Jto比率∈ Z+和n∈{1，…，M}。通过考虑具有M个均匀分布结果的结果空间，我们可以等效地将随机损失Z（x）定义为Ohm := {ωi}Mi=1满足Z（x，ξ（ω））∈ {Z（x，ξo）}τo=1和|{ω| Z（x，ξ（ω））=Z（x，ξo）}|=(R)pξoM，类似地Xjas a映射Xj：Ohm → 满足Xj（ω）的R∈ {（~Sj）o}τjo=1和{ω| Xj（ω）=（~Sj）o}pjoM。假设优化问题（29）和（30）是基于上述随机损失的定义而制定的。我们将在下文中说明如何进一步减少这些问题。

首先请注意，优化问题（29）可以等效为supp、s、vj、wjs，服从~>vj+~>wj- p> ~Z≤\'\'δj- s、 j∈ J（44）~ Xjp>- vj ~>-~1w>j≤ 0，j∈ 日本∈ R|Ohm|+∩ Cσ。还请注意，如果给定任何固定的u*, {δ*j} j∈J、 优化问题（30）中的约束可以等效地写成asyd∈ G（~ Xd，δ*d、 {δ*i} 我∈J）∩ {y | y>~ Xd≤ hd（y）}，d=1。。。，D、 （45）yj∈ G（~ Xj，δ*j、 {δ*i} 我∈J） ，则，J∈ J \\{1，…，D}，（46）其中G（~ Y，t，{δi}i）∈J） 是由y上的以下约束系统表示的参数化集：vi，wisuch that ~>vi+~>wi- y> ~是的≤ δi- T我∈ J（47）~ Xiy>- vi ~>-~1w>i≤ 0我∈ J（48）y∈ R|Ohm|+∩ Cσ。（49）可以看出，第一个优化问题中的约束条件（44）也可以用P表示∈ G（~Z，s，{δi}i∈J） 。（50）由于samesteps可用于减少约束（46）（使用（47）-（49））和（50）（使用（47）-（49）），因此我们仅给出约束的减少（45）和（47）-（49））。由于需要考虑任何固定d的（45），因此从这里开始，我们只考虑d=1，并删除变量的索引d，以简化表示。给定{δ}的固定集*j} j∈J、 让y*, 五、*i、 w*注意满足（45）和（47）-（49）的可行解决方案。Foro=1。。。，τ、 让我（1）注意到~X的索引集n，例如（~X）n=（~S）o，因此| I（1）o |=(R)p（1）oM。我们声称解决方案v*我有以下几点**∈ RM，w**我∈ RMS满足任何n∈ I（1）o（y**)n=| I（1）o | Xa∈I（1）o（y*)A和（w**i） n=| i（1）o | Xa∈I（1）o（w*i） a，o=1。。。，τ、 也将满足（45）和（47）-（49）。

为了验证第一个约束（47），我们有~>v*i+~>w**我- （y）**)>~X=~>v*i+Pτo=1 | i（1）o | i（1）o | Pa∈I（1）o（w*i） a-Pτo=1（~S）o | I（1）o | I（1）o | Pa∈I（1）o（y*)a=~>v*i+Pτo=1Pa∈I（1）o（w*i） a-Pτo=1（~S）oPa∈I（1）o（y*)a=~>v*i+~>w*我- （y）*)>~十、≤ δ*我- δ*.为了验证第二个约束（48），我们对任何n∈ I（1）o，o=1。。。，τXi（y**)N- 五、*我-~1（w**)n=（| I（1）o）（~ XiXa）∈I（1）o（y*)A.- （| I（1）o |）v*我-~Xa公司∈I（1）o（w*i） （a）≤ 0，其中最后一个不等式可通过对（48）中的列求和得到，即，对于o=1。。。，τXn∈I（1）o（~ Xiy*>- 五、*i ~>-~1瓦*i> ）（：，n）≤ 为了验证第三个约束（49），我们将构造一系列解y（1）*, ..., y（τ）*满足（τ）*= Y**y（τ）*∈ R|Ohm|+∩ Cσ。对于o=1。。。，τ、 设∑o注意满足（σ（y）的所有置换算子σ的集合*))a=（y*)A.a/∈ I（1）o。换言之，集合由所有置换组成，这些置换只置换条目a∈ I（1）o.Seto=1，我们构造y（1）*按y（1）*:=Pσ∈∑I（1）o |！σ（y*). 可以确认y（1）*满意度（y（1）*)n=| I（1）| Xa∈I（1）（y）*)aforn∈ I（1）和（y（1）*)n=（y*)没有。考虑到y*∈ R|Ohm|+∩ Cσ，我们必须有σ（y*) ∈ R|Ohm|+∩ Cσ由Cσ和y（1）的定义确定*∈ Cσ，因为求和是凸组合。对于o≥ 2，我们可以构造y（o）*=Pσ∈∑o | I（1）o |！σ（y（o-（1）*). 通知（o）-（1）*∈ R|Ohm|+∩ Cσ，y（o）*∈ R|Ohm|+∩ Cσ必须保持且y（o）*满足任何∈ I（1）o，o=1。。。，o（y（o）*)n=| I（1）o | Xa∈I（1）o（y*)a、 和（y（o）*)n=（y*)没有。通过归纳，y（τ）*∈ R|Ohm|+∩ Cσ和y（τ）=y**.对于约束y>~ X≤ h（y）in（45），自（y）起**)>~X=τXo=1（~S）o | I（1）o | I（1）o | Xa∈I（1）o（y*)a=（y*)>~十、 和（y）**)>~Z（x）=τXo=1Z（x，ξo）| I（1）o | | I（1）o | Xa∈I（1）o（y*)a=（y*)>~Z（x），我们已经满足了。因此，我们可以通过施加一些y来减少约束（45）和（47）-（49∈ Rτ，~w∈ Rτ表示a∈ I（1）o，o=1。。。，τ、 （y）a=（￠y）o和（wi）a=（￠wi）o。

这导致以下约束~>vi+1>（λo wi）- （λo ~y）>~S≤ δi- δ（51）~ Xiy>- vi ~>-~1w>i≤ 0（52）LF（y）∈ R|Ohm|+∩ Cσ（53）（λo ~y）>~S≤ minx公司∈X（λo y）>~ Z（x）（54），其中λ：=（| I（1）||I（1）τ|）和~Z（x）：=（Z（x，ξ）。。。，Z（x，ξτ））>。我们现在表明，可以进一步减少上述四个约束。让我（I）注意~Xisuch的指数集n，（~Xi）n=（~Si）o，o=1。。。，τI因此| I（I）o |=(R)pioM。不难看出，对于任何（vi）asuch∈ I（I）与（vi）相关的其他约束在（52）中相同。由于减少了（vi）a，a对于（51）总是可行的，如果存在任何（v*i） a6=（v*i） b对于a、b∈ I（I）o，我们总是可以通过减少较大的一个来使它们相等（不违反任何约束）。因此，我们可以得出这样的结论：我们总是可以为某些人强加∈ Rτithat（vi）a=（vi）或任何a∈ I（I）o。这导致将第一个约束（51）重新表述为~>（λIo vi）+1>（λo wi）- （λo ~y）>~S≤ δi- δ、 式中λi：=（| i（i）||I（I）τI |）和（52）至~Si▄y>- vi ~>-~1w>i≤ 0、出租（λio vi）=^vi，（λo wi）=^wi，和（λ）o y）=^y，我们已经（52）变成~Si（（λ）-1.o ^y）>- （（λi）-1.o ^vi）~>-~1（（λ）-1.o ^wi）>≤ 0（55）和（53）变为（λ）-1.o ^y）∈ R|Ohm|+∩ Cσ和（51），（54）减少到（32）（j=1）和（34）（d=1）。最后，乘法（~ 1λ>）o （~ Si（（λ）-1.o ^y）>- （（λi）-1.o ^vi）~>-~1（（λ）-1.o ^wi）>）≤ 0得出（33）的最终公式（j=1）。F示例4.5的证明。让M∈ Z+是一个常数，使得pk，k=1。。。，K和'pjo，o=1。。。，τjc可表示为n/M，n∈ {1，…，M}。首先，给出阶跃谱φ-（p） ，为了应用示例2.6中的表示式Cσ，我们得到φj=RjMj-1Mφ-（t） 对于任何j，dt=(R)φKm∈ {1，…，M}这样pk-1.≤J-1M<jM≤ pk，因此|{j |φj=(R)φkM}|=（pk- 主键-1） M。

查看约束LFj（（λFj）如何-1.o y）∈ R|Ohm|+∩ Cσ可以减少，我们首先应用Birkhoff（1946）的结果将Cσ重新表示为Cσ：={q | q=qφ，q ~ 1=1，q>~ 1=1，q≥ 0}。设I（j）o，o=1。。。，τjdenote LFj（（λFj）的指数n的集合-1.o y） 使得（LFj（（λFj））-1.o y） ）n=（（λFj）-1.o y） o因此| I（j）o |=（λFj）o。很明显，约束LFj（（λFj）-1.o y）∈ R|Ohm|+∩ 当且仅当以下约束集Qi=qj时，Cσ有可行解，i、 j∈ I（j）o，o=1。。。，τj，q=qφ，q ~ 1=1，q>~ 1=1，q≥ 0（56）具有可行的解决方案。我们首先展示了如何减少（56）。Let（q*, Q*) 表示上述约束的可行解决方案。我们声称解决方案q*以及以下Q的构造**（Q）**)（n，：）=| I（j）o | Xn∈I（j）o（Q*)（n，：），~n∈ I（j）o，o=1。。。，τj也是可行的。我们现在验证此声明。替换（q*, Q**) 在约束q=qφ中，我们得到了任意▄n∈ I（j）o，o=1。。。，τj（Q**φ） n=MXm=1φm（| I（j）o |）Xn∈I（j）o（Q*)（n，m）=（| I（j）o |）Xn∈I（j）oMXm=1φm（Q*)（n，m）=（| I（j）o |）Xn∈I（j）oq*n=q*n（由于q*i=q*Ji、 j∈ I（j）o，o=1。。。，τj）。我们可以验证Q**~1=1，采用上述相同步骤，φ替换为~1。替换Q**在约束Q>~ 1=1中，我们有Q**>~1=（MXn=1（Q**)（￠n，：）>=（τjXo=1 | I（j）o | I（j）o | Xn∈I（j）o（Q*)（n，：）>=~ 1。因此，我们可以通过对任何▄n施加该值来减少（56）∈ I（j）o，o=1。。。，τj，（Q）（n，：）=（\'Q）（o，：）对于某些\'Q∈ Rτj×M，导致Qi=\'qo，我∈ I（j）o，o=1。。。，τj，\'q=\'qφ，\'q~1=1，（（λFj ~>）o\'\'Q）>~ 1=1，\'\'Q≥ 0，（57）其中\'q∈ Rτj。

此外，约束LFj（（λFj）-1.oy）∈ R|Ohm|+∩Cσ可等效为y∈ Rτj+∩ C、 式中，C：={q | q=（（λFj ~>）o\'Q）φ，\'Q~1=~1，（（λFj ~>）o\'\'Q）>~ 1=1，\'\'Q≥ 0.}让^Q=（λFj ~>）oQ，我们有c：={Q | | Q=Qφ，Q ~ 1=λFj，Q>~ 1=1，Q≥ （58）接下来，让I（φ）kdenoteφ的指数集j，使得φj=(R)φkmk，对于k=1。。。，Kand因此| I（φ）k |=（pk- 主键-1） M.鉴于此，我们证明（58）中的约束可以进一步减少。让“q”*,^Q*是（58）的可行解决方案。我们声称*连同以下^Q施工**^Q**（：，~n）：=| I（φ）k | Xn∈I（φ）k^Q*（：，n），~n∈ I（φ）k，k=1。。。，Kis对于约束也是可行的。代入约束\'q=^qφ，我们得到了^q**φ=KXk=1 | I（φ）k |φkM | I（φ）k | Xn∈I（φ）k^Q*（：，n）=KXk=1Xn∈I（φ）k'φkM^Q*（：，n）=^Q*φ=(R)q*通过将φ替换为上述1，可以轻松验证约束条件^Q~1=λfjc。为了验证约束^Q>~ 1=1，我们有∈ I（φ）k，k=1。。，K（（^Q**)>~1） n=| I（φ）k |τjXo=1Xn∈I（φ）k^Q*（o，n）=| I（φ）k | Xn∈I（φ）kτjXo=1^Q*（o，n）=| I（φ）k | Xn∈I（φ）k=| I（φ）k | | I（φ）k |=1。因此，我们也可以将其用于任何▄n∈ I（φ）k，k=1。。，K、 ^Q（：，n）=Q（：，K），对于某些▄Q∈ Rτj×Kin（58），这导致将C中的第一个和第二个约束重新表述为“q=（~ 1λ>φ）oQ）（M？φ）和（~ 1λ>φ）oQ）~ 1=λFj，其中（λφ）k=（pk- 主键-1） M，因此也就是集合C intoC={q | q=（M）（~1λ>φ）o<<Q>>φ，（（~1λ>φ）o~Q）~1=λFj，~Q>~1=1，~Q≥ 0}。让˙Q=（M）（~ 1λ>φ）oQ，我们得出最终的简化形式。