Share
Embed
Transcript
23 slides
-
ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ ͖͟·ͭ ػցγεςϜίʔεɹम࢜ 1 February 10, 2023
͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 1 / 23 -
࣍ 1 Property of Convex 2 Convex Optimization 3 DC
Optimization ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 2 / 23 -
Property of Convex ࣍ 1 Property of Convex 2 Convex
Optimization 3 DC Optimization ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 3 / 23 -
Property of Convex ತू߹ Definition (ತू߹: convex set) ͋Δू߹ C
Λఆٛ͢ΔɽC ⊂ Rn ͕ತू߹Ͱ͋Δͱɼ x1, x2 ∈ C, θ ∈ [0, 1] ⇒ (1 − θ)x1 + θx2 ∈ C ͕Γཱͭ͜ͱΛݴ͏ɽ ײతʹɼx1 ͱ x2 Λ݁Μͩઢͷ͕ू߹ C ʹଘࡏ͢Δ͜ͱɽ ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 4 / 23 -
Property of Convex ತؔ Definition (ತؔ) ͋Δ࣮ؔΛ f ͱ͢Δɽf ͷΤϐάϥϑ͕ತू߹ͷͱ͖ɼf
ತؔͰ͋Δɽ Definition (Τϐάϥϑ) ҎԼͷू߹ɼf ͷΤϐάϥϑͰ͋Δɽ epi f ≜ {(x, y) ∈ Rn × R : y ≥ f(x)} ఆٛͷ؆୯ͳղऍͷํͱͯ͠ɼ • ؔͷ্ଆ͕Τϐάϥϑ • ؔͷ্ଆ͕ԜΜͩΓ͍ͯ͠ͳ͚ΕɼತؔʢԼʹತʣ ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 5 / 23 -
Property of Convex ತؔ Ҏ্ 2 ͭͷఆٛΑΓɼತؔҰൠతʹҎԼͷΑ͏ʹද͞ΕΔɽ (1 − θ)f(x1)
+ θf(x2) ≥ f ((1 − θ)x1 + θx2) (1) ਤ 2: ತؔͱඇತؔ ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 6 / 23 -
Property of Convex ͪͳΈʹ ʮತ͕͋ΔͳΒɼԜ͋ΔͷͰʁ ʁʯˠɹ͋Γ·͢ɽ͑͐ɼ͋Γ·͢ͱɽ Definition (Ԝؔ) ͋Δ࣮ؔΛ g
ͱ͢Δɽg ͷූ߸స͕ತؔͰ͋Δ࣌ɼg ԜؔͰ͋Δɽ (1 − θ)f(x1) + θf(x2) ≤ f ((1 − θ)x1 + θx2) (2) Ԝؔͷྫ • ରؔ g(x) = log x • ਖ਼ݭؔ g(x) = sin x (0 ≤ x ≤ π) • ೋ࣍ؔ g(x) = −x2 • ฏํؔ g(x) = √ x ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 7 / 23 -
Convex Optimization ࣍ 1 Property of Convex 2 Convex Optimization
3 DC Optimization ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 8 / 23 -
Convex Optimization ৭Μͳ࠷దԽ ઢܗܭը త͕ؔҰ࣍ࣜͱͯ͠ද͞Εɼ੍݅ͷू߹͕Ұ࣍ํఔࣜɾҰ࣍ෆࣜʹΑͬ ͯఆٛ͞Ε͍ͯΔɽ ܭը ઢܗܭըͷதͰɼ֤มͷ͕ʹ੍ݶ͞Ε͍ͯΔɽ ೋ࣍ਲ਼ܭը ࣮ߦՄೳྖҬ͕ೋ࣍ਲ਼ʢԁਲ਼ʣͰ͋ΔΑ͏ͳɽ
ਖ਼ఆܭը ਖ਼ఆߦྻΛมͱ͢Δತܭըɽ ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 9 / 23 -
Convex Optimization ತ࠷దԽ (Convex Optimization) ͱ ؔ f
: Rn → R ∪ {∞} ͕ϓϩύʔͳತؔɼ͔ͭू߹ C ⊂ Rn ͕ดತू߹Ͱ͋Δͱ ͖ɼx ⊂ C ͷதͰ f(x) Λ࠷খʹ͢Δ x ΛٻΊΔɽ f(x) < ∞ ͱͳΔΑ͏ͳ x ͕ҰͭͰଘࡏ͢Δʢdom f ̸= ∅ʣͱ͖ɼؔ f ϓϩύʔͰ ͋Δͱ͍͏ɽ Definition (dom fʢ࣮ޮఆٛҬʣ) ؔ f ͷఆٛҬͷ͏ͪɼf(x) ͕࣮ΛऔΔΑ͏ͳ x ͷू߹Λ f ͷ࣮ޮఆٛҬͱݺͿɽ dom f ≜ {x ∈ R : f(x) < ∞} ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 10 / 23 -
Convex Optimization ತ࠷దԽͷԿ͕خ͍͠ͷ͔ େҬతͳ࠷దΛಘΔ͜ͱ͕Ͱ͖Δ ҰൠʹɼޯใΛར༻ͨ͠࠷దԽख๏Ͱɼہॴతͳ࠷దʹऩଋ͢Δ͜ͱ͕ଟ ͍ɽತ࠷దԽͰɼධՁؔͷತੑ͕୲อ͞Ε͍ͯΔͨΊɼେҬతͳ࠷దΛಘΔ ͜ͱ͕Ͱ͖Δɽ ࠷దԽܭࢉͷ͕͍ ತ࠷దԽಛ༗ͷ࠷దԽख๏Λ༻͍Δ͜ͱͰɼ൚༻ͷ࠷దԽख๏ΑΓܭࢉ࣌ؒΛॖ ͢Δ͜ͱ͕Ͱ͖ΔɽԿ͔ɼ࠷ۙͰߋʹߴԽΛࢦͨ͠ख๏͕͋Δͱ͔ͳΜͱ͔ɽ
͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 11 / 23 -
Convex Optimization ತ࠷దԽͷදతͳख๏ʢΞϧΰϦζϜʣ • ࠷খೋ๏ • ෮ແ͠χϡʔτϯ๏ • ༗ޮ੍๏ •
๏ • ۙޯ๏ • ަޓํ๏ ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 12 / 23 -
Convex Optimization ΞϧΰϦζϜͷҰྫɿۙޯ๏ ҎԼͷΑ͏ʹఆࣜԽ͞ΕΔ࠷దԽΛߟ͑Δɽ minimize ω f(ω) ≜
g(ω) + h(ω) (3) ͜͜Ͱɼg ඍՄೳͳತؔɼh ඞͣ͠ඍՄೳͰͳ͍ತؔͰ͋Δͱ͢Δɽ (3) ʹର͢Δۙޯ๏ɼҎԼͷߋ৽ࣜʹΑͬͯ ω Λߋ৽͢ΔΞϧΰϦζϜͰ ͋Δɽ ωk+1 = proxγh (ωk − γ∇g(ωk)) proxγh (v) ≜ argminω { h(ω) + 1 2γ ∥ω − v∥2 2 } ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 13 / 23 -
Convex Optimization ۙޯ๏ͷײ֮ ࠷ϧʔτͰͳ͍͚ͲɼͦΕͳΓʹ͍ʢ࠷దղʹ͍ۙʣϧʔτΛͨͲͬͯਐΉɽ ਤ 3: ۙ࡞༻ૉͷಇ͖ ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1
) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 14 / 23 -
Convex Optimization ತ࠷దԽɹ·ͱΊ • ತ࠷దԽͱɼత͕ؔತؔͰදݱ͞ΕΔ࠷దԽͷ͜ͱɽ • ತ࠷దԽͰɼޯใΛར༻ͯ͠େҬతͳ࠷దղΛٻΊΕΔɽ • ಛ༗ͷ࠷దԽख๏ʹΑͬͯɼܭࢉΛ͘ߦ͏͜ͱ͕Ͱ͖Δɽ ▶
࠷্ೋ๏ ▶ ๏ ▶ ۙޯ๏ ▶ ަޓํ๏ ͳͲͳͲ etc ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 15 / 23 -
DC Optimization ࣍ 1 Property of Convex 2 Convex Optimization
3 DC Optimization ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 16 / 23 -
DC Optimization DC ࠷దԽʹ͍ͭͯ DC ࠷దԽͱ త͕ؔ 2 ͭͷತؔͷࠩ (Difference
of Convex Function) Ͱදݱ͞ΕΔඇತ࠷దԽ ʹ͍ͭͯɼ࠷খԽΛߦ͏ࡍʹ͏ख๏ɽ 2 ͭͷತؔ g, h : Rn → R ∪ {∞} ΛͬͯɼҎԼͷΑ͏ʹදݱ͞ΕΔɽ minimize ω g(ω) − h(ω) (4) ؔ f : Rn → R ∪ {∞} ʹରͯ͠ɼ2 ͭͷดತؔ g, h ʹ͍ͭͯ f(ω) = g(ω) − h(ω), ∀ω ∈ Rn (5) ͕Γཱͭͱ͖ɼf Λ DC ؔͱ͍͍ɼ(5) ͷදݱΛ f ͷ DC දݱͱݺͿɽ ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 17 / 23 -
DC Optimization DC ࠷దԽʹ͍ͭͯ ͳͥඇತ࠷దԽʹͳΔͷ͔ • ತؔͷತؔͰ͋Δɽ •
ತؔͷࠩತؔʹͳΒͳ͍߹͕͋Δɽ ತؔͷࠩΛऔΔ࠷దԽҰൠʹඇತ࠷దԽͱͳΓɼେہత࠷దղΛٻΊΔ ͷࠔͰ͋Δɽ ͦ͜ͰɼDCA Λ༻͍Δ͜ͱͰɼDC ࠷దԽΛತ࠷దԽʹม͢Δ͜ͱ͕Ͱ͖ɼ ತ࠷దԽͷख๏ʹΑͬͯ࠷దղΛٻΊΔ͜ͱ͕Ͱ͖Δɽ ͳ͓ɼ2 ֊ඍ͕ՄೳͳҙͷؔͳͲɼଟ͘ͷ͕ؔ DC ؔͱͳ͍ͬͯΔɽ ˠɹ༷ʑͳΫϥεͷ࠷దԽ͕ DC ࠷దԽʹΑͬͯදݱͰ͖Δɽ ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 18 / 23 -
DC Optimization DC Algorithm Algorithm 1 Calculate Problem (4) with
DCA 1: దͳॳظ ω0 ΛͱΔɽ 2: for k = 0, 1, 2, . . . do 3: ݱࡏͷ෮ ωk ʹ͓͚Δ h ͷྼޯ sk ∈ ∂h(ωk) Λܭࢉ͢Δɽ 4: ωk+1 = argminω ( g(ω) − s⊤ k ω ) 5: end for ∂h(x[k])ɿ࣌ࠁ k ʹ͓͚Δ x[k] ·ΘΓͷྼඍ ∂h(x[k]) ≜ {s ∈ Rn : h(x) ≥ h(x[k]) + s⊤(x − x[k])} ඍͷ֓೦ΛɼඍෆՄೳؔʹରͯ͠ద༻ͨ͠ͷʢઈରؔͱ͔ʣ ɽ ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 19 / 23 -
DC Optimization DC Algorithm ͷ ω[k + 1] ∈ argminω
( g(ω) − s[k]⊤ω ) (6) ࠷దԽͷதʹɼࢠͱͯ͠ತ࠷దԽ (6) ؚ͕·Ε͓ͯΓɼ֤෮Ͱ (6) ͷ࠷ద ղΛٻΊΔඞཁ͕͋Δɽ ͦͷͨΊɼେنͳෳࡶͳͰɼലେͳܭࢉίετʹͳΔՄೳੑ͕͋Δɽ ਤ 4: DCA ͷྲྀΕ ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 20 / 23 -
DC Optimization pDCAε ࠷ۙͰͷߏΛ׆͔͠ɼ֤෮ͰͷܭࢉΛܰ͘͢Δख๏͕ఏҊ͞Ε͍ͯΔɽ pDCAε DCA ʹରͯ͠ɼۙޯ๏ͱ Nesterov
ͷ֎ૠΛࢪͨ͠վྑ൛ΞϧΰϦζϜɽ Algorithm 2 Calculate Problem (4) with pDCAe 1: supk βk < 1 ͱͳΔ βk ⊂ [0, 1) ΛఆΊɼω−1 = ω0 ͱ͢Δɽ 2: for k = 0, 1, 2, . . . do 3: ݱࡏͷ෮ ω[k] ʹ͓͚Δ h ͷྼޯ sk ∈ ∂h(ωk) Λܭࢉ͢Δɽ 4: yk = ωk + βk(ωk − ωk−1) 5: ωk+1 = argminy { (∇f(yk) − sk)⊤ + L 2 ∥y − yk∥2 2 + g(y) } 6: end for ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 21 / 23 -
DC Optimization ತ࠷దԽɹ·ͱΊ • త͕ؔ 2 ͭͷತؔͷࠩͰදݱ͞ΕΔඇತ࠷దԽʹର͢Δख๏ɽ • DCA ʹΑͬͯɼඇತ࠷దԽΛತ࠷దԽʹม͢Δ͜ͱ͕Ͱ͖Δɽ
• ଟ͘ͷ͕ؔ DC ؔͱͳ͍ͬͯͯɼ༷ʑͳΫϥεͷ࠷దԽΛ DC ࠷దԽ ͰදݱՄೳɽ • ͨͩɼʹΑͬͯେنͳܭࢉίετ͕ඞཁɽ • ࠷ۙͰɼܭࢉͷܰྔԽΛࢦͨ͠ख๏͕ఏҊ͞Ε͍ͯΔɽ ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 22 / 23 -
References References • פળത, ୩ོ, ”౦ژେֶֶڭఔ جૅܥ ֶ ࠷దԽͱม๏”, ؙળग़൛,
2014. • Ӭݪਖ਼ষ, ”εύʔεϞσϦϯάʔجૅ͔ΒಈతγεςϜͷԠ༻ʔ”, ίϩφࣾ, 2017. • ҏ౻উ, ”ತ࠷దԽʹର͢ΔҰ࣍๏ͱͦͷཧ : Ճޯ๏ͱͦͷपล”, ΦϖϨʔγϣϯζɾϦαʔν = Communications of the Operations Research Society of Japan : ܦӦͷՊֶ, 64, 6, pp.326-334, 2019. • খफ़༎, ”ۙΞϧΰϦζϜͱͦͷԠ༻: ৴߸ॲཧɾը૾ॲཧత؍͔Β”, ΦϖϨʔγϣϯζɾϦαʔ ν= Communications of the Operations Research Society of Japan: ܦӦͷՊֶ, 64, 6, pp.316-325, 2019. • খफ़༎, ”ۙʹΑΔࢄತ࠷దԽʕަޓํ๏ʹجͮ͘ΞϓϩʔνΛத৺ͱͯ͠ʕ”, ܭଌͱ੍ޚ, 55, 11, pp.954-959, 2016. • ాதະདྷ, Ԟو೭, ”DC ࠷దԽͷཧͱԠ༻”, Ԡ༻ཧ, 29, 6, pp.14-23, 2019. • ޙ౻ॱ࠸, ా࿕ࢠ, ”DC Ξϓϩʔνʹجͮ͘εύʔε࠷దԽ”, ΦϖϨʔγϣϯζɾϦαʔν= Communications of the Operations Research Society of Japan: ܦӦͷՊֶ, 64, 6, pp.352-359, 2019. • Wen, Bo and Chen, Xiaojun and Pong, Ting Kei, ”A proximal difference-of-convex algorithm with extrapolation”, Computational optimization and applications, 69, pp.297-324, 2018. ͖͟·ͭ (ػցγεςϜίʔεɹम࢜ 1 ) ತ࠷దԽ͔Β DC ࠷దԽ·Ͱ February 10, 2023 23 / 23