෼෍తϩόετ࠷దԽʹ͓͚Δύϥϝʔλͷબ୒‫ޙ‬౻ ॱ࠸ 11தԝେֶ ཧ޻ֶ෦ ‫ܦ‬ӦγεςϜ޻ֶՊ !
ʢ! 2021 ೥ 4 ݄͔ΒϏδωεσʔλαΠΤϯεֶՊʹ໊শมߋʣ

2021 ೥ 2 ݄ 5 ೔NTT σʔλ਺ཧγεςϜΞΧσϛοΫΧϯϑΝϨϯε
Virtual1 / 28Ξ΢τϥΠϯ1਺ཧ࠷దԽͱιϧόʔ

2෼෍తϩόετ࠷దԽ (DRO)

3σʔλ‫ۦ‬ಈ‫ܕ‬ͷ DRO2 / 28਺ཧ࠷దԽʢ਺ཧ‫ܭ‬ըʣmin(imize) f (x)xsubject to· · · ໨తx∈S· · · ৚݅x*x’

ͨͩ͠f ͸ x := (x1 , ..., xd ) ΛҾ਺ͱ͢Δؔ਺S ͸ม਺ (x1 , ..., xd ) ͷ੍‫ݶ‬Λද͢ू߹fS
࠷େԽ͸ −f ͷ࠷খԽ3 / 28ఆࣜԽͷྫʣൃి‫ܭ‬ը໰୊๭ిྗձࣾͰ͸ੴ୸ɼੴ༉֤ 1 ‫ج‬ͷൃి‫ػ‬Λอ༗͍ͯ͠ΔɽधཁΛຬͨ͠ɼൃిίετ͕࠷খʹͳΔΑ͏ൃిྔʦMWhʧΛܾΊ͍ܾͨΊ͍ͨ΋ͷ ɿఆࣜԽ ɿx1 ɿੴ୸ʹΑΔൃిྔɼmin

46x1 + 135x2

sub.tox1 + x2 ≥ 1000,150 ≤ x1 ≤ 6000 ≤ x2x1 ,x2x2 ɿੴ༉ʹΑΔൃిྔ←ൃిίετ←धཁྔ←ੴ୸ͷൃి্Լ‫ݶ‬←ੴ༉ͷൃి্Լ‫ݶ‬

x2:400の等高線

x11506004 / 28਺ཧ࠷దԽʢ਺ཧ‫ܭ‬ըʣιϧόʔ

Numerical Optimizer ... LP, MILP, SDP, NLP, meta-heuristicsɼetc.
Gurobi ... LP, SOCP, MILP, MISOCPIBM CPLEX ... LP, SOCP, MILP, MISOCP, CP, etc.
FICO Xpress-MP ... LP, SOCP, MILP, MISOCP, NLP, MINLP, CP, etc.
···—————————
MATLAB Optimization Toolbox ... LP, MIP, QP, NLP, etc.
Excel ιϧόʔ ... LP (simplex), NLP, GA, etc.
···—————————SCIP ... LP, SOCP, MILP, MISOCP
LPsolve ... LP, MIP
GLPK ... LP, MIP···
5 / 28ιϧόʔΛ࢖͏ʹ͸਺ࣜΛ༻͍ͨఆࣜԽ͕େ੾max

18xA + 11xB

sub.toxA + xB ≤ 40,
2xA ≤ 50,xB ≤ 25,xA , x B ≥ 0xA ,xB∵ ଟ͘ͷϞσϦϯά‫Ͱޠݴ‬͸௚઀తʹఆࣜԽΛ༩͑Δ
SIMPLEʢNTT σʔλ਺ཧγεςϜʣ

LPSolveʢϑϦʔʣOPLʢIBM ILOGʣ

Variable xA, xB;
Objective f(type=maximize);
f=18*xA+11*xB;
xA+xB<=40;
2*xA<=50;
xB<=25;xA>=0;
xB>=0;

max: 18 xA+11 xB;
xA+xB <= 40;
2 xA <= 50;
xB <= 25;

dvar float+ xA;
dvar float+ xB;
maximize 18*xA+11*xB;
subject to {xA+xB<=40;
2*xA<=50;
xB<=25;}6 / 281਺ཧ࠷దԽͱιϧόʔ

2෼෍తϩόετ࠷దԽ (DRO)

3σʔλ‫ۦ‬ಈ‫ܕ‬ͷ DRO

7 / 28ಈ‫ػ‬‫࣮ݱ‬໰୊ʹ͓͚Δ࠷దԽ໰୊ͷύϥϝʔλͷଟ͘͸σʔλ!
ʦ࠶‫ܝ‬ʧൃి‫ܭ‬ըͷྫ࠷খԽ
x1 ,x2

৚ɹ݅#46 x1 + 135 x2←ίετx1 + x2 ≥ 1000 ,150 ≤ x1 ≤ 600
0 ≤ x2←धཁྔ←ੴ୸ͷൃి্Լ‫ݶ‬←ੴ༉ͷൃి্Լ‫ݶ‬ʮ࠷దԽʯ͸༩͑ΒΕͨσʔλʹରͯ͠ʮ࠷దʯʢΛ໨ࢦ͢ʣ"$σʔλ͕ʢগ͠Ͱ΋ʣมԽ͢Δ৔߹ʹ͸࠷దੑ͸อূͰ͖ͳ͍ಛʹෆ࣮֬ੑΛ‫ؚ‬Ή৔߹ʹ͸ෆ࣮֬ੑͷϞσϧʹର͢Δཧղʢͱͦͷ‫ʹ݁ؼ‬
ର͢Δ֮‫ޛ‬ʣ͕ඞཁ8 / 28

Ben-Tal, Nemirovski (2000) ʹΑΔಈ‫ػ‬ͦ͏͍ͬͨσʔλͷଟ͘͸ “ृ͍ (ugly)”
ྫ NETLIB ͷ LP ͷςετ໰୊ूͷதͷ໰୊ྫ PILOT4ʢ1000 ม਺ɼ410 ੍໿ʣͷ 372 ൪໨ͷ੍໿ɿ
a! x ≡ −15.79081 x826 − 8.598819x827 − 1.88789x828 − 1.362417x829− 1.526049x830 − 0.031883x849 − 28.725555x850 − 10.792065x851− 0.19004x852 − 2.757176x853 − 12.290832x854 + 717.562256x855− 0.057865x856 − 3.785417x857 − 78.30661x858 − 122.163055x859− 6.46609x860 − 0.48371x861 − 0.615264x862 − 1.353783x863− 84.644257x864 − 122.459045x865 − 43.15593x866 − 1.712592x870− 0.401597x871 +x880 − 0.946049x898 − 0.946049x916≥b ≡ 23.387405!CPLEX ʹΑΔ࠷దղͷҰ෦ɿ
x∗826 = 255.6112787181108, x∗827 = 6240.488912232100,x∗828 = 3624.613324098961, x∗829 = 18.20205065283259,x∗849 = 174397.0389573037, x∗870 = 14250.00176680900,x∗871 = 25910.00731692178, x∗880 = 104958.3199274139! ΋੍͠໿ࣜͷ܎਺͕ͦΕͧΕ 0.1% ͣͭͣΕΔͱ੍໿ࣜͷҧ൓͸ӈลͷ 450%ʂ
9 / 28ϩόετ࠷దԽʢSoyster,’73ʣx࠷େԽx≥0৚ɹ݅c" xd!

j=1aj xj ≤ b

ਪఆ஋

x

a1 , ..., ad ͸ਖ਼͘͠ͳ͍͔΋͠Εͳ͍ ! ࠷దղ͕‫ʹ࣮ݱ‬͸࣮ߦෆՄೳ͔΋ͦ͜Ͱ δ|aj | ͿΕͯ΋࣮ߦՄೳͳΑ͏ʹ৚݅Λมߋɿaj!

[ aj − δ|aj |, aj + δ|aj | ]ਖ਼ఆ਺d!

j=1ãj wj ≤ b,∀ ãj ∈ [ aj − δ|aj | , aj + δ|aj | ]10 / 28‫ظ‬଴஋ͷ࠷దԽmin EP [f (x, Y)]xf : ίετؔ਺x : ܾఆม਺ʢϕΫτϧʣY : ֬཰ม਺ʢϕΫτϧʣP : ֬཰෼෍ʲ஫ʳ min EP [f (x, Y)] = − max EP [−f (x, Y)]
xx! −f ɿใुؔ਺11 / 28ྫʣ৽ฉചΓࢠ໰୊୯Ձ c Ͱ࢓ೖΕɼചΕΕ͹ r ͚ͩɼചΕͳ͚Ε͹ q ͚ͩ໭ͬͯ͘Δf (x, Y ) = cx − r min{x, Y } − q max{x − Y, 0} + s max{Y − x, 0}"#$% "#$% "#$%ച্࢒༨Ձ஋

‫ػ‬ձඅ༻

ͨͩ͠ 0 ≤ q < c < r, s ≥ 0

f : ෛͷརӹx : ࢓ೖΕ਺ʢx ≥ 0ʣ
Y : धཁ12 / 28ྫʣϙʔτϑΥϦΦબ୒໰୊f (x, R) := exp(−R" x)f : ෛͷࢦ਺‫༻ޮܕ‬x ∈ Rd : ϙʔτϑΥϦΦʢ౤ࢿ഑෼ൺ཰ʣϕΫτϧ! ੍໿෇͖ʢe.g., 1" x = 1.x ≥ 0ʣR ∈ Rd : ऩӹ཰)

いくらずつ投資したら良いか？

投資家の期待効用xAxB企業A

企業B

企業C

企業D

RARB

RCRDxDxC

収益率
13 / 28ྫʣϩδεςΟοΫճ‫ؼ‬&'f ((x, x0 ), (b, a)) := ln 1 + exp(−b(x" a + x0 ))f ɿෛͷର਺໬౓ͷ 1 ඪຊ෼(x, x0 ) ∈ Rd+1 ɿઢ‫ܗ‬Ϟσϧͷ܎਺ϕΫτϧͱ੾ย߲a ∈ Rd ɼb ∈ {±1}ɿઢ‫ܗ‬Ϟσϧͷઆ໌ม਺ͱόΠφϦΫϥεϥϕϧ

ココ14 / 28ඪຊฏ‫ࣅۙۉ‬ʢSAAʣ͔Β෼෍తϩόετ࠷దԽ΁min EP [f (x, Y)]x͠͹͠͹ P = ‫ݧܦ‬෼෍ Pn Ͱ୅༻֬཰

1n1nऔΓ͏Δ஋

Y1

Y2...
...

!
ඪຊฏ‫ࣅۙۉ‬ʢSample Average Approximation: SAAʣ#maxx(1nYn+n)*!
EPn f (x, Y) := n1f (x, Yi )i=1

͔͠͠ SAAʢͷղ xn (0)ʣͷࣄ‫ޙ‬ੑೳ͸ࣄલ͔ΒͷྼԽ͕ஶ͍͠Մೳੑ"$∵ ‫ݧܦ‬෼෍ Pn '= ਅͷ֬཰Ϟσϧ

15 / 28ඪຊฏ‫ࣅۙۉ‬ʢSAAʣ͔Β෼෍తϩόετ࠷దԽ΁min EPn [f (x, Y)]x࠷ѱͷέʔεΛߟ͑Δͱ͸ʁ

min max EQ [f (x, Y)]xQ∈Qx = x1 ͷͱ͖ͷ f ͷ෼෍

x = x2 ͷͱ͖ͷ f ͷ෼෍! x2 ͷํ͕ x1 ΑΓ޷·͍͠

15 / 28ඪຊฏ‫ࣅۙۉ‬ʢSAAʣ͔Β෼෍తϩόετ࠷దԽ΁min EPn [f (x, Y)]x!
෼෍తϩόετ࠷దԽʢDistributionally Robust Optimization: DROʣ"#$min max EQ [f (x, Y)]
xQ∈QQ : ෆ࣮֬ੑू߹ ʢತू߹ʹ‫ݶ‬ఆͯ͠ OKʣ! Q = Q(ε) : େ͖͞ͷύϥϝʔλ ε ≥ 0 ʹґଘʀQ(0) = {Pn }1Id1115 / 28

KL μΠόʔδΣϯεʹ‫ͮ͘ج‬ෆ࣮֬ੑू߹!
Kullback-Leibler (KL) μΠόʔδΣϯεʹ‫ͮ͘ج‬ෆ࣮֬ੑू߹
#͜ͷͱ͖Q(ε) =,q ∈ Rn : 1" q = 1, q ≥ 0,n!

i=1qi ln pqii ≤ ε-"$max EQ [f ] = max.
Q∈Qf "qn!
sub.toqi ln pqii ≤ ε,q

←λ≥0

i=1"

1 q = 1,(qi > 0, i = 1, ..., n)←η૒ରੑΛ࢖͏ͱmax EQ [f ] = minQ∈Q

λ>0,η

(ελ + η + λ≈ EPn [f ] +n.
i=1/pi exp& fi − η'+−1λ√2εVPn [f ] + o( ε)標準偏差16 / 28

KL μΠόʔδΣϯεʹ‫ ͮ͘ج‬DRO
min max EQ [f (x, Y)] = minxQ∈Q(ε)

x,λ>0,η(n.

pi exp& fi −η'−1

ελ + η + λi=10 f (x, Y ) − ηi

λ−11+৽ฉചΓࢠ໰୊ͷ DRO

min

λ>0,η,x,fsub.toελ + η + λn!

pi expi=1

λfi ≥ cx − rYi , fi ≥ (c − r)x, i = 1, ..., n,x ≥ 0, (λ > 0).

ϙʔτϑΥϦΦબ୒໰୊ͷ DROn!

minελ + η + λsub.to1" x = 1, x ≥ 0,λ,η,xpi expi=1& exp(−R! x)−η(λ > 0).

λ'−1ϩδεςΟοΫճ‫ؼ‬ͷ DRO

min

λ,η,x,x0

ελ + η + λ exp(− λη − 1)

sub.to(λ > 0).

n!

i=1&&''
pi 1 + exp −bi (a"i x + x0 )17 / 28

RNUOPT ༻ίʔυͰॻ͘ͱʢ৽ฉചΓࢠ໰୊ͷ DRO ͷྫʣ
min

λ>0,η,x,f

sub.toελ + η + λn!

i=1pi exp

" fi −η
λ−1#fi ≥ cx − rYi , fi ≥ (c − r)x, (i = 1, ..., n)x ≥ 0, (λ > 0)nvKL <- function(DmndData,r,c,eps) {Sample <- Set()t <- Element(set=Sample)
Dmnd <- Parameter(index=t,DmndData)x <- Variable()lambda <- Variable()eta <- Variable()loss <- Variable(index=t)s <- Expression(index=t)s[t] ~ (loss[t]-eta)/lambda - 1
drokl <- Objective(type=minimize)drokl ~ eps*lambda + eta + lambda * (Sum(exp(s[t]),t))/length(DmndData)loss[t] >= c*x-r*Dmnd[t]loss[t] >= (c-r)*xx >= 0
lambda >= 0}

18 / 281਺ཧ࠷దԽͱιϧόʔ

2෼෍తϩόετ࠷దԽ (DRO)

3σʔλ‫ۦ‬ಈ‫ܕ‬ͷ DRO

19 / 28ύϥϝʔλ ε ͷνϡʔχϯά

(DRO(ε))minx,λ>0,η(ελ + η + λn.

pi expi=10 f (x, Y ) − ηi

λ1+−1

ε > 0 Λ‫ݻ‬ఆͯ͠ (DRO(ε)) Λιϧόʔʹ౤͛Ε͹ͦͷ࠷దղ xn (ε) ΛಘΔͰ͸Ͳͷ εʢͷ࠷దղʣΛ༻͍Δ΂͖͔ʁ࣮‫͢ݱ‬Δίετ EP [f (xn (ε), Y)] ͕খ͘͞ͳΔΑ͏ʹʁͦ΋ͦ΋ਅͷ෼෍ P ͕Θ͔Βͳ͍ʢख‫͋ʹݩ‬Δͷ͸ Pn ͷΈʣ! ࠶ඪຊ๏Ͱ Pʢor Pn ʹର͢Δ‫౓ײ‬ʣΛγϛϡϨʔτ͢Δϒʔτετϥοϓ๏

֬཰
औΓ͏Δ஋

1
4
Y1

14
Y2

14
Y3

14Y4


 Y4 Y1Y2!
..

.


Y2(1)

Y2
Y4
Y3..
.

Y1Y4
Y1..
.

Y2
Y2
Y1..
.

! x4 (ε)(2)! x4 (ε)(3)! x4 (ε)

Y3

Y2Y2! x4 (ε)͜ΕΛ ε ͷ K ‫ݸ‬ͷީิ ε1 , ..., εK ʹ͍ͭͯ‫܁‬Γฦ͢

(B)! K × B ճͷ࠷దԽ‫ࢉܭ‬
20 / 28

Rnuopt Ͱϒʔτετϥοϓ
N<-nrow(xdata)

EO

for (itr in 1:B) {bs.idx<-sample(1:N,N,replace=TRUE)
x<-xdata[bs.idx,]y<-ydata[bs.idx]
rownames(x) <- c(1:N)
for (delta in delta.set){sys<-System(rob_logreg,x,y,delta)sol<-solve(sys,trace=F)
w0opt<-as.array(current(sys,w0))
wopt<-as.array(current(sys,w))
wopt<-wopt[names(xdata)]}}
21 / 28ϒʔτετϥοϓͷฏ‫ ͮ͘جʹۉ‬δ ͷબ୒
対数尤度= - fの平均

期待効用= - fの平均
SAA-0.974-0.138-0.14

SAA-0.976-0.142-0.978-0.144-0.146-0.98-0.148-0.15-0.982-0.152-0.984-0.154-0.156
00.2

0.4

0.6

0.8(i) ϩδεςΟοΫճ‫ؼ‬ͷ DRO ͷྫ

1δ -0.986 020406080100

δ(ii) ϙʔτϑΥϦΦબ୒ͷྫ஫ҙɿॎ͕࣠ −E[f ]ɼͭ·Γʮେ͖͍΄Ͳྑ͍ʯʹͳ͍ͬͯ·͢

22 / 28

DRO ͷࣄ‫ޙ‬ύϑΥʔϚϯεͷ෼ੳ (Gotoh, Kim, Lim, 2021+)

xn (δ) := arg min max
xcf.

"Q(+1EQ [f (x, Y)] − KL(Q|Pn )δ#$%≈ EPn [f (x,Y)]+δVPn [f (x,Y)]+o(δ)
2

分散6+6min max EQ [f (x, Y)] 6 KL(Q|Pn ) ≤ εxQ√ /√≈ min EPn [f (x, Y)] + 2ε VPn [f (x, Y)] + o( ε)(x標準偏差ࣄલͷ໰୊ (In-sample problem):Y1 , · ·7· , Yn ∼ P: ಠཱʹಉҰͳ෼෍ P ͔ΒಘΒΕͨ n ඪຊxn (0) ≡ SAA!
xn (δ) ≡ DRO for δ > 0ࣄ‫ޙ‬ύϑΥʔϚϯε (Out-of-sample performance):Yn+1 ∼ P: Y1 , · · · , Yn ͱ͸ಠཱʹ P ͷ৽͍͠ඪຊ
7f (xn (0), Yn+1 ) : SAA ͷࣄ‫ޙ‬ίετ!
f (xn (δ), Yn+1 ) : DRO ͷࣄ‫ޙ‬ίετ for δ > 023 / 28ϩόετฏ‫ۉ‬ɾ෼ࢄϑϩϯςΟΞ
(&+'EP [f (xn (δ), Yn+1 )], VP [f (xn (δ), Yn+1 )] : δ ≥ 0δ ͕খ͍͞ +f ͕ x ʹ͍ͭͯ‫ڱ‬ٛತͷͱ͖ࣄ‫ޙ‬෼ࢄͷ‫ݮ‬গޮՌ͕ࢧ഑త: O(δ)ͦͷτϨʔυΦϑͱͯ͠ͷࣄ‫ظޙ‬଴ίετͷ૿Ճ͸খ͍͞: O(δ 2 )ࣄ‫ظޙ‬଴ίετͷ SAA ͔Βͷվળ: ʢ͋ͬͨͱͯ͠΋ʣO(δ/n)- fの平均- fの平均-0.138

SAArSAA-0.974-0.14-0.976-0.142-0.978-0.144-0.146-0.98-0.148-0.15-0.982-0.152-0.984-0.154-0.156
0.1

fの分散

fの分散
-0.9860.150.2(i) ϩδεςΟοΫճ‫ؼ‬ͷ DRO ͷྫ஫ҙɿॎ͕࣠ −E[f ] ʹͳ͍ͬͯ·͢

0.25

00.002

0.004

0.006

0.008

0.01(ii) ϙʔτϑΥϦΦબ୒ͷྫ
25 / 28

DRO ʹ͓͍ͯ͸͹Β͖ͭΛ཈͑Δࢹ఺͕ॏཁϙʔτϑΥϦΦબ୒ͷྫ
期待効用= - fの平均

期待効用= - fの平均-0.974-0.974-0.976-0.976-0.978-0.978

-0.98

-0.98

-0.982-0.982-0.984-0.984-0.986-0.986SAASAAfの分散
0204060(i) ฏ‫ۉ‬ͷΈʹண໨ͨ͠৔߹

80

δ 100

00.002

0.004

0.006

0.008

0.01(ii) ฏ‫ۉ‬ɾ෼ࢄʹண໨ͨ͠৔߹

26 / 28

DRO ʹ͓͍ͯ͸͹Β͖ͭΛ཈͑Δࢹ఺͕ॏཁϩδεςΟοΫճ‫ؼ‬ͷྫ
対数尤度= - fの平均

対数尤度= - fの平均-0.138-0.138

-0.14
SAA

-0.14

-0.142-0.142-0.144-0.144-0.146-0.146-0.148-0.148

-0.15

-0.15

-0.152-0.152-0.154-0.154-0.15600.2

0.4

0.6(i) ฏ‫ۉ‬ͷΈʹண໨ͨ͠৔߹

0.8

δ

1

-0.156
0.1

SAA

fの分散
0.15

0.2

0.25(ii) ฏ‫ۉ‬ɾ෼ࢄʹண໨ͨ͠৔߹

27 / 28

·ͱΊ

DRO ʹ͓͍ͯ෼෍ʹର͢Δෆ࣮֬ੑʹରॲ͢ΔͨΊ࠷ѱͷ෼෍ʹ‫ͮ͘͜ج‬ͱͷҙຯ≈ ίετ f ʢor ใुʣ෼෍ͷ޿͕ΓΛ཈͑Δͨͱ͑͹ɼෆ࣮֬ੑͷαΠζύϥϝʔλ ε/δ ͕খ͍͞ͱ͖ɼKL μΠόʔδΣϯε ↔ ͹Β͖ͭ͸ඪ४ภࠩ/෼ࢄ˞ ҟͳΔμΠόʔδΣϯε΍ෆ࣮֬ੑू߹ʹରͯ͠͸ҟͳΔ͹Β͖ͭͷई౓ (Gotoh, Kim,Lim, 2020, arXiv)ࣄ‫ޙ‬తʹ΋ฏ‫ۉ‬Λվળͤ͞ΔޮՌΑΓ͸ɼ͹Β͖ͭΛ‫ݮ‬গͤ͞ΔޮՌͷํ͕େ͖͍ʢϖφϧςΟʔ൛ͷ෼ੳʣ࠶ඪຊ๏ͳͲͱ૊Έ߹Θͤͨσʔλ‫ۦ‬ಈ‫ܕ‬ͷ࠷దԽ! R ͳͲͷ֤छσʔλղੳύοέʔδ/ϥΠϒϥϦͱιϧόʔΛ૊Έ߹Θͤͨར༻๏͕༗ޮ
Based on
Gotoh, Kim, Lim, Calibration of Distributionally Robust EmpiricalOptimization Models, to appear in Operations Research, 2021+
28 / 28