Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
非線形最適化の基礎〜KKT条件〜
Search
miruca
March 19, 2019
Science
3
5k
非線形最適化の基礎〜KKT条件〜
非線形最適化問題に対する最も代表的な最適性の必要条件(KKT条件)に関するスライド
miruca
March 19, 2019
Tweet
Share
More Decks by miruca
See All by miruca
非線形最適化の基礎〜射影・錐・凸関数〜
mirucacule
2
2.1k
非線形最適化の基礎〜カラテオドリの定理〜
mirucacule
2
3k
Other Decks in Science
See All in Science
データマイニング - コミュニティ発見
trycycle
PRO
0
130
LayerXにおける業務の完全自動運転化に向けたAI技術活用事例 / layerx-ai-jsai2025
shimacos
2
1.4k
SciPyDataJapan 2025
schwalbe10
0
250
Lean4による汎化誤差評価の形式化
milano0017
1
280
統計学入門講座 第3回スライド
techmathproject
0
120
Cross-Media Information Spaces and Architectures (CISA)
signer
PRO
3
31k
データベース03: 関係データモデル
trycycle
PRO
1
240
「美は世界を救う」を心理学で実証したい~クラファンを通じた新しい研究方法
jimpe_hitsuwari
1
140
生成AIと学ぶPythonデータ分析再入門-Pythonによるクラスタリング・可視化をサクサク実施-
datascientistsociety
PRO
4
1.7k
メール送信サーバの集約における透過型SMTP プロキシの定量評価 / Quantitative Evaluation of Transparent SMTP Proxy in Email Sending Server Aggregation
linyows
0
970
ド文系だった私が、 KaggleのNCAAコンペでソロ金取れるまで
wakamatsu_takumu
2
980
機械学習 - DBSCAN
trycycle
PRO
0
950
Featured
See All Featured
Automating Front-end Workflow
addyosmani
1370
200k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
26
3k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.8k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
21
1.4k
Fireside Chat
paigeccino
38
3.6k
Designing Experiences People Love
moore
142
24k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
Into the Great Unknown - MozCon
thekraken
40
2k
Measuring & Analyzing Core Web Vitals
bluesmoon
7
540
Build The Right Thing And Hit Your Dates
maggiecrowley
37
2.8k
The Language of Interfaces
destraynor
158
25k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
234
17k
Transcript
ඇઢܗ࠷దԽͷجૅ – KKT condition – miruca Graduate School of Informatics,
Kyoto University March 19, 2019
͜ͷεϥΠυͷత ʰඇઢܗ࠷దԽͷجૅʱ(ౡ, 2001) ͷୈ 3 ষʹؔͯ͠ • ๏ઢਲ਼Λ༻͍ͨ࠷దੑ݅ʹ͍ͭͯཧղ͢Δ • ෆ੍ࣜΛؚΉ࠷దԽʹର͢Δ
KKT ݅Λཧղ͢Δ • KKT ݅ͷԾఆͰ͋Δ੍ఆʹ͍ͭͯཧղ͢Δ ˞ҙ • ຊεϥΠυͷఆཧͷ൪߸ʰඇઢܗ࠷దԽͷجૅʱʹ४ͣΔ • ਤͳ͍ͷͰదٓखΛಈ͔͠ͳ͕Βཧղ͢Δ͜ͱΛਪ • (ԋश) ͱॻ͍ͨͷʹղΛͨ͠
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ Today’s Topic 1. ਲ਼ͱ࠷దੑ݅ 2. KKT
݅ 3. ੍ఆ 3 / 21
1. ਲ਼ͱ࠷దੑ݅ 2. KKT ݅ 3. ੍ఆ
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ ࠷దԽ ࣍ͷ࠷దԽΛߟ͑Δɿ minimize x∈Rn f(x) subject
to x ∈ S. (1) ͜͜ʹɼؔ f : Rn → R ͱू߹ S ⫅ Rn ॴ༩Ͱ͋Δɽ • ੍݅ x ∈ S Λຬͨ͢ϕΫτϧ x Λ࣮ޮՄೳղͱ͍͍ɼ࣮ ޮՄೳղશମͷू߹Λ࣮ޮՄೳྖҬͱ͍͏ɽ • S = Rn ͷ߹ɼ (1) ੍ͳ͠࠷దԽͱݺΕΔɽ • ؔ f ͕ತؔͰɼू߹ S ͕ತू߹Ͱ͋Δͱ͖ɼ (1) ತ ܭը (convex programming problem) ͱݺΕΔɽ 5 / 21
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ ࠷దղͷछྨ • ࣮ޮՄೳղ x ∈ S
ʹରͯ͠ɼ͋Δ ε > 0 ͕ଘࡏͯ͠ f(x) ≧ f(x) (∀x ∈ S ∩ B(x, ε)) (2) ཱ͕͢Δͱ͖ɼx Λ (1) ͷہॴత࠷దղͱ͍͏ *1)ɽ • ҙͷ ε > 0 ʹରͯࣜ͠ (2) ཱ͕͢Δɼ͢ͳΘͪ f(x) ≧ f(x⋆) (∀x ∈ ε) (3) Ͱ͋Δͱ͖ɼx⋆ ΛେҬత࠷దղͱ͍͏ɽ ˞ େҬత࠷దղ ⇒ ہॴత࠷దղ (ٯඞͣ͠Γཱͨͳ͍) *1)த৺͕ x ∈ Rn Ͱܘ͕ r > 0 ͷٿΛ B(x, r) = {y ∈ Rn | ∥y − x∥ < r} ͱॻ͖ɼ ։ٿͱݺͿɽ 6 / 21
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ ತܭըʹ͓͚Δ࠷దղ ʮہॴత࠷దղ ⇒ େҬత࠷దղʯΛอূͰ͖Δ߹͕͋Δɽ ఆཧ 3.1
࠷దԽ (1) ʹ͓͍ͯɼf ತؔɼS ತू߹ͱ͢Δɽͦͷͱ ͖ɼ (1) ͷҙͷہॴత࠷దղେҬత࠷దղͰ͋Δɽ • ূ໌ɼہॴత࠷దղͰ͋Δ͕େҬత࠷దղͰͳ͍Α͏ͳ x ∈ S ͷଘࡏੑΛԾఆͯ͠ໃ६Λಋ͚Α͍ɽ(ԋश) • ࠷దղશମͷू߹͕ತू߹Ͱ͋Δ͜ͱࣔ͢͜ͱ͕Ͱ͖Δɽ • ತܭըͰͳ͍߹ɼҰൠʹ͍ͭ͘ͷہॴత࠷దղ͕ଘࡏ ͢ΔͷͰɽେҬత࠷దղΛٻղ͢Δ͜ͱࠔͰ͋Δɽ → ತੑΛԾఆ͠ͳ͍ʹ͓͍ͯɼہॴత࠷దղ͕ղੳͷରͱ ͳΔ߹͕΄ͱΜͲͰ͋Δɽ 7 / 21
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ ਲ਼ (1) ʹର͢Δ࠷దੑ݅Λಋͨ͘ΊʹඞཁͱͳΔ֓೦Λड़Δɽ ఆٛ: ਲ਼
(tangent cone) x ∈ S ʹऩଋ͢Δྻ {xk} ⫅ S Λߟ͑Δɽ͜ͷͱ͖ɼ͋Δඇෛ ྻ {αk} Λ༻͍ͯఆٛ͞ΕΔྻ {αk(xk − x)} ͕ऩଋ͠ɼͦͷ ۃݶ͕ y ∈ Rn ͱͳΔͱ͖ɼy Λू߹ S ͷ x ʹ͓͚ΔϕΫτϧ (tangent vector) ͱݺͿɽ·ͨɼS ͷ x ʹ͓͚ΔϕΫτϧશମ ͷू߹Λ Ts(x) ͱද͠ɼू߹ S ͷ x ʹ͓͚Δਲ਼ (tangent cone) ͱݺͿɽ • ਲ਼ Ts(x) ྻΛ༻͍ͯ࣍ͷΑ͏ʹදݱ͞ΕΔ: Ts(x) := { y ∈ Rn | lim k→∞ αk(xk − x) = y, lim k→∞ xk = x, xk ∈ S, αk ≧ 0 (k = 1, 2, . . .) } . 8 / 21
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ ๏ઢਲ਼ ਲ਼ͷۃਲ਼ʹ͍ͭͯߟ͑Δɽ ఆٛ: ๏ઢਲ਼ (normal cone)
ਲ਼ Ts(x) ͷۃਲ਼ Ts(x)⋆ Λ S ͷ x ʹ͓͚Δ๏ઢਲ਼ (normal cone) ͱݺͼɼNs(x) ͱද͢ɽNs(x) ʹଐ͢ΔϕΫτϧΛ x ʹ͓͚Δ S ͷ๏ઢϕΫτϧ (normal vector) ͱ͍͏ɽ • ๏ઢਲ਼࣍ͷΑ͏ʹදݱ͞ΕΔ: Ns(x) = {z ∈ Rn | ⟨z, y⟩ ≦ 0 (∀y ∈ Ts(x))} (4) • ಛʹɼू߹ S ͕ತू߹Ͱ͋Δͱ͖࣍ͷΑ͏ʹදݱ͞ΕΔ: Ns(x) = {z ∈ Rn | ⟨z, x − x⟩ ≦ 0 (∀x ∈ S)} (5) • ๏ઢਲ਼ Ns(x) ۭͰͳ͍ดತਲ਼Ͱ͋Δ *2)ɽ *2)ҙͷਲ਼ C ʹର͢Δۃਲ਼ C⋆ ดತਲ਼Ͱ͋ΔͨΊ (ఆཧ 2.12)ɽ 9 / 21
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ ࠷దੑ݅ ๏ઢਲ਼Λ༻͍Δ͜ͱʹΑΓɼ (1) ʹର͢Δ࠷جຊతͳ࠷దੑ ݅Λ༩͑Δ͜ͱ͕Ͱ͖Δɽ ఆཧ
3.3 ؔ f : Rn → R x ∈ S ʹ͓͍ͯඍՄೳͱ͢Δɽͦͷͱ͖ɼ x ͕ (1) ͷہॴత࠷దղͳΒ࣍ͷ͕ؔΓཱͭɿ − ∇f(x) ∈ Ns(x). (6) • ࣜ (6) Λຬͨ͢ (1) ͷఀཹ (stationary point) ͱݺ ΕΔɽ • ࣜ (6) x ͕ (1) ͷہॴత࠷దղͰ͋ΔͨΊͷඞཁ݅ Ͱ͋Δ͕े݅Ͱͳ͍ɽ • ತܭըͷ߹ɼࣜ (6) ͕࠷దੑͷඞཁे݅ͱͳΔɽ 10 / 21
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ ತܭըʹ͓͚Δ࠷దੑ݅ ఆཧ 3.4 S ⫅ Rn
ۭͰͳ͍ತू߹ɼf : Rn → R x ∈ S ʹ͓͍ͯඍ Մೳͳತؔͱ͢Δɽ͜ͷͱ͖ɼࣜ (6) x ͕ (1) ͷେҬత࠷ దղͰ͋ΔͨΊͷඞཁे݅Ͱ͋Δɽ ূ໌ ඞཁੑ໌Β͔ͳͷͰेੑ͚ͩࣔͤΑ͍ɽ(ԋश) 11 / 21
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ ತܭըʹ͓͚Δ࠷దੑ݅ ఆཧ 3.4 ΑΓ࣍ͷܥ͕Γཱͭɽ ܥ 3.1
ू߹ S ⫅ Rn ͷ෦ۭͰͳ͘ɼؔ f : Rn → R x ∈ int S*3) ʹ͓͍ͯඍՄೳͱ͢Δɽͦͷͱ͖ɼx ͕ (1) ͷہ ॴత࠷దղͳΒ ∇f(x) = 0 ཱ͕͢Δɽ͞Βʹɼf ͕ತؔɼS ͕ತू߹ͳΒɼ∇f(x) = 0 x ͕ (1) ͷେҬత࠷దղͰ͋ ΔͨΊͷඞཁे݅Ͱ͋Δɽ ূ໌ ɹ x ∈ int S Ͱ͋Δͱ͖ɼTs(x) = Rn Ͱ͋Δ͔Βɼ Ns(x) = {0} ͱͳΔɽΑͬͯɼࣜ (6) ∇f(x) = 0 ʹؼண͞ΕΔɽ *3)ू߹ S ⫅ Rn ͱ x ∈ Rn ʹରͯ͠ɼB(x, r) ⫅ S ͱͳΔΑ͏ͳ r > 0 ͕ଘࡏ͢Δͱ ͖ɼx Λ S ͷͱ͍͍ɼS ͷશମͷू߹Λ S ͷ෦ͱ͍͍ɼint S Ͱද͢ɽ 12 / 21
1. ਲ਼ͱ࠷దੑ݅ 2. KKT ݅ 3. ੍ఆ
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ ෆࣜΛؚΉ࠷దԽ ࣍ͷ࠷దԽΛߟ͑Δɿ minimize x∈Rn f(x) subject
to gi(x) ≦ 0 (i = 1, . . . , m). (7) ͜͜Ͱɼؔ f ͓Αͼ gi (i = 1, . . . , m) ඍՄೳͰ͋Δͱ͢Δɽ • (7) ͷ੍݅ɼ (1) ͷ࣮ޮՄೳྖҬ S ͕ S = {x ∈ Rn | gi(x) ≦ 0 (i = 1, . . . , m)} (8) ͱද͞ΕΔ߹ʹଞͳΒͳ͍ɽ • (7) ͷ࣮ޮՄೳղ x ʹ͓͍ͯɼgi(x) = 0 ͕Γ੍ཱͭ ݅Λ༗ޮ੍݅ͱݺͼɼͦͷఴࣈू߹ΛҎԼͰද͢ɿ I(x) = {i ∈ N | gi(x) = 0} ⫅ {1, 2, . . . , m}. 14 / 21
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ ઢܗԽਲ਼ ࣮ޮՄೳྖҬ S ͕ࣜ (8) Ͱ༩͑ΒΕΔͱ͖ɼਲ਼ʹมΘΔ֓೦ͱ͠
ͯઢܗԽਲ਼ͱݺΕΔਲ਼Λߟ͑Δ͜ͱ͕Ͱ͖Δɽ ఆٛ: ઢܗԽਲ਼ (linearizing cone) ू߹ S ͕ࣜ (8) Ͱ༩͑ΒΕ͍ͯΔͱ͖ɼ x ∈ S ʹ͓͚Δ༗ޮ੍ ݅ʹରԠ͢Δ੍ؔͷޯ ∇gi(x) (i ∈ I(x)) ͱ 90◦ Ҏ্ͷ֯ Λͳ͢ϕΫτϧશମͷू߹ΛઢܗԽਲ਼ͱݺͼɼCs(x) Ͱද͢ɽ • ઢܗԽਲ਼ Cs(x) ࣍ͷΑ͏ʹද͞ΕΔ: Cs(x) := {y ∈ Rn | ⟨∇gi(x), y⟩ ≦ 0 (∀i ∈ I(x))} (9) • ਲ਼ Ts(x) ू߹ S ͔Βఆٛ͞ΕΔͷʹର͠ɼઢܗԽਲ਼ Cs(x) ؔ gi ʹґଘͯ͠ఆ·Δ͜ͱʹҙ͢Δɽ • ਲ਼ͱઢܗԽਲ਼ඞͣ͠Ұக͢ΔͱݶΒͳ͍͕ɼแؚؔ Ts(x) ⫅ Cs(x) ৗʹཱ͢Δɽ(ิ 3.3) 15 / 21
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ Lagrange ؔ Lagrange ؔͱݺΕΔؔΛఆٛ͢Δɽ ఆٛ: Lagrange
ؔ (Lagragian) (7) ʹରͯ͠ɼ࣍ࣜͰఆٛ͞ΕΔؔ L0 : Rn+m → [−∞, ∞] Λ Lagrange ؔͱ͍͏ɽ L0(x, λ) = f(x) + m ∑ i=1 λigi(x) (λ ≧ 0) −∞ (λ ≧̸ 0) (10) ͜͜ʹɼλ = (λ1, . . . , λm)⊤ ∈ Rm Λ Lagrange ͱݺͿɽ • ࣜ (10) ʹ͓͍ͯɼλ ≧̸ 0 ͷͱ͖ L0(x, λ) = −∞ ͱఆٛͨ͠ ͷɼରΛఆٛ͢Δࡍʹ߹͕Α͍ͨΊͰ͋Δɽ • Lagrange ؔʹΑͬͯ (7) ʹର͢Δ࠷దੑͷඞཁ݅Λ ༩͑Δ͜ͱ͕Ͱ͖Δɽ 16 / 21
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ KKT ݅: ࠷దੑͷඞཁ݅ (7) ʹର͢Δ࠷దੑͷඞཁ݅ʹ͍ͭͯड़Δɽ
ఆཧ 3.5 x Λ (7) ͷہॴత࠷దղͱ͢Δɽͦͷͱ͖ɼแؚؔ Cs(x) ⫅ co Ts(x) ͕ΓཱͭͳΒɼ࣍ࣜ: ∇xL0(x, λ) = ∇f(x) + m ∑ i=1 λi∇gi(x) = 0 λi ≧ 0, gi(x) ≧ 0, λigi(x) = 0 (i = 1, . . . , m) (11) Λຬ͢Δ Lagrange λ ∈ Rm ͕ଘࡏ͢Δɽ • ࣜ (11) Ұൠʹ KKT ݅ (KKT condition) ͱݺΕΔɽ • ఆཧ 3.5 x ͕ (7) ͷہॴత࠷దղͰ͋ΔͨΊͷे ݅Ͱ͋Δ͜ͱอূ͍ͯ͠ͳ͍ɽ 17 / 21
ਲ਼ͱ࠷దੑ݅ KKT ݅ ੍ఆ ࠷దੑͷे݅ ತܭըʹ͓͍ͯɼKKT ͕݅࠷దੑͷे݅ʹͳΔɽ ఆཧ 3.6
(7) ʹ͓͍ͯɼతؔ f ͱ੍ؔ gi ඍՄೳͳತؔͱ ͢Δɽͦͷͱ͖ɼ͋Δ x ∈ Rn ͱ λ ͕ࣜ (11) Λຬ͢ΔͳΒɼx (7) ͷେҬత࠷దղͰ͋Δɽ • ఆཧ 3.5 ͱఆཧ 3.6 ΑΓɼತܭըͷͱ͖ KKT ͕݅େ Ҭత࠷దੑͷඞཁे݅ͱͳΔɽͭ·Γɼ ∃ (x, λ) s.t. ࣜ (11) ⇔ x (7) ͷେҬత࠷దղ • େҬత࠷దղͰ͋Δ͜ͱΛอূͰ͖Δͷɼತܭըʹ͓͍ ͯʮہॴత࠷దղͳΒେҬత࠷దղʯ͕ΓཱͭͨΊͰ͋ Δɽ(ఆཧ 3.1) • ূ໌Ұܦݧ͓ͯ͘͠ͱΑ͍ɽ(ԋश) 18 / 21
1. ਲ਼ͱ࠷దੑ݅ 2. KKT ݅ 3. ੍ఆ
੍ఆ (7) ʹର͢Δදతͳ੍ఆͱͯ͠ҎԼͷͷ͕͋Δɽ ओͳ੍ఆ • Ұ࣍ಠ੍ཱఆ: ϕΫτϧ ∇gi(x) (∀i
∈ I(x)) Ұ࣍ಠཱͰ ͋Δɽ • Slater ੍ఆ: ؔ gi (∀i ∈ I(x)) ತؔͰ͋Γɼ gi(x) < 0 (i = 1, . . . , m) ͳΔ x0 ͕ଘࡏ͢Δɽ • Cottle ੍ఆ: ⟨∇g(x), y⟩ < 0 (∀i ∈ I(x)) Λຬͨ͢ϕΫτ ϧ y ∈ Rn ͕ଘࡏ͢Δɽ • Abadie ੍ఆ: Cs(x) ⫅ Ts(x) • Guignard ੍ఆ: Cs(x) ⫅ co Ts(x) • Guignard ੍ఆఆཧ 3.5 ͰԾఆ੍ͨ͠ఆͰ͋Δɽ
੍ఆͷ૬ޓؔ ੍֤ఆʹ͍ͭͯ࣍ͷ͕ؔΓཱͭɽ ఆཧ • Ұ࣍ಠ੍ཱఆ ⇒ Cottle ੍ఆ • Slater
੍ఆ ⇒ Cottle ੍ఆ • Cottle ੍ఆ ⇒ Abadie ੍ఆ • Abadie ੍ఆ ⇒ Guignard ੍ఆ • 5 छྨͷ੍ఆͷ͏ͪ Guignard ੍ఆ͕࠷ऑ͍ԾఆͰ ͋Δ͕ɼ༩͑ΒΕͨ࠷దԽʹରͯ͠ Cs(x) ⫅ co Ts(x) Ͱ ͋Δ͜ͱΛఆ͢Δ͜ͱࠔͰ͋Γɼ࣮༻తͰͳ͍ɽ • Ұ੍࣍ఆɼSlater ੍ఆɼCottle ੍ఆݕূ͕ൺֱ త༰қͰ͋ΔͨΊɼ࣮ࡍʹΑ͘ΘΕΔɽ
4.
ఆཧ 3.1 ࠷దԽ (1) ʹ͓͍ͯɼf ತؔɼS ತू߹ͱ͢Δɽͦͷͱ ͖ɼ (1) ͷҙͷہॴత࠷దղେҬత࠷దղͰ͋Δɽ
ূ໌ ہॴత࠷దԽͰ͋Δ͕େҬత࠷దղͰͳ͍Α͏ͳ x ∈ S ͷ ଘࡏΛԾఆ͢Δɽ͢ͳΘͪɼf(y) < f(x) Λຬͨ͢Α͏ͳ y ∈ S ͕ଘࡏ͢Δɽ͍·ɼू߹ S ತؔΑΓҙͷ α ∈ (0, 1) ʹର͠ ͯɼ(1 − α)x + αy ∈ S Ͱ͋Δɽ·ͨɼؔ f ತؔΑΓ f((1 − α)x + αy) ≦ (1 − α)f(x) + αf(y) < (1 − α)f(x) + αf(x) = f(x) ͕Γཱͭɽ্ࣜͰ α → 0 ͷۃݶΛߟ͑Δͱɼx ͷҙͷۙͷத ʹ x ΑΓਅʹখ͍͞తؔΛ࣮ͭޮՄೳղ͕ଘࡏ͢Δ͜ͱ ͕ݴ͑Δɽ͜Εɼx ͕ہॴత࠷దղͰ͋Δ͜ͱʹ͢Δɽ(ূ ໌ऴ)
ఆཧ 3.4 S ⫅ Rn ۭͰͳ͍ತू߹ɼf : Rn → R
x ∈ S ʹ͓͍ͯඍ Մೳͳತؔͱ͢Δɽͦͷͱ͖ɼࣜ (6) x ͕ (1) ͷେҬత࠷ దղͰ͋ΔͨΊͷඞཁे݅Ͱ͋Δɽ ূ໌ ඞཁੑఆཧ 3.3 ΑΓ໌Β͔ͳͷͰेੑͷΈࣔ͢ɽ͍·ɼ −∇f(x) ∈ Ns(x) ΑΓɼҙͷ x ∈ S ʹରͯ͠ ⟨−∇f(x), x − x⟩ ≦ 0 ⇔ ⟨∇f(x), x − x⟩ ≧ 0 (12) ͕Γཱͭ *4)ɽ·ͨɼҙͷ x ∈ S ʹରͯ͠ f(x) ≧ (f ͷತੑ) f(x) + ⟨∇f(x), x − x⟩ ≧ (ࣜ (12)) f(x) ͕ΓཱͭɽΏ͑ʹɼx (1) ͷେҬత࠷దղͰ͋Δɽ(ূ໌ऴ) *4)ू߹ S ͕ತू߹Ͱ͋Δͱ͖๏ઢਲ਼ࣜ (5) Ͱ༩͑ΒΕΔ͜ͱΛ༻͍ͨɽ
ఆཧ 3.6 (7) ʹ͓͍ͯɼతؔ f ͱ੍ؔ gi ඍՄೳͳತؔͱ ͢Δɽͦͷͱ͖ɼ͋Δ
x ∈ Rn ͱ λ ͕ࣜ (11) Λຬ͢ΔͳΒɼx (7) ͷେҬత࠷దղͰ͋Δɽ ূ໌ λ Λݻఆͯ͠ɼؔ ℓ : Rn → R Λ࣍ࣜͰఆٛ͢Δɿ ℓ(x) = f(x) + m ∑ i=1 λigi(x). ͍·ɼf, gi ͱʹತؔͰ λ ≧ 0 Ͱ͋Δ͔Β ℓ ತؔͰ͋ Δ *5)ɽ݅ΑΓɼx ∈ Rn ͱ λ ࣜ (11) Λຬͨ͢ͷͰ ∇f(x) + m ∑ i=1 λi∇gi(x) = 0
͕Γཱͭɽఆཧ 3.4 ΑΓ ℓ x ʹ͓͍ͯେҬతʹ࠷খͱͳΔɽ Αͬͯɼҙͷ x ∈
Rn ʹରͯ͠ɼℓ(x) ≦ ℓ(x), i.e., f(x) + m ∑ i=1 λigi(x) =0 ≦ f(x) + m ∑ i=1 λigi(x) ͕Γཱͭɽ݅ΑΓ λigi(x) = 0 (i = 1, . . . , m) ͔ͭ λ ≧ 0 Ͱ͋ Δ͔Βɼgi(x) ≦ 0 (i = 1, . . . , m) Λຬͨ͢ҙͷ x ʹରͯ͠ *6) f(x) + 0 ≦ f(x) + m ∑ i=1 λigi(x) ≦0 ≦ f(x) ͕Γཱͭɽ͕ͨͬͯ͠ɼx େҬత࠷దղͰ͋Δɽ(ূ໌ऴ) *5)ʰඇઢܗ࠷దԽͷجૅʱఆཧ 2.26 Λࢀরɽ *6)͢ͳΘͪɼ (7) ͷҙͷ࣮ޮՄೳղʹରͯ͠