MATEMATICKÉ OPTIMALIZAČNÍ TECHNOLOGIE

MATEMATICKÉ OPTIMALIZAČNÍ TECHNOLOGIE

Stanislav Míka Ludvík Vlček

Červen 2011 PLZEŇ

3

Motto: Na světě se nestane nic, v čem by nebylo vidět smysl nějakého maxima, nebo minima. . . Leonhard Paul Euler (1707-1783) Náš svět je nejlepší ze všech možných světů a proto lze jeho zákony vyjádřit extremálními principy. . . Gottfried Wilhelm Leibnitz (1646-1716)

Jsme si vědomi toho, že

Předmluva se obvykle nečte. Přesto bychom v těchto úvodních větách chtěli být jakýmsi stručným průvodcem předloženým textem. V úvodní kapitole chceme čtenáře seznámit s klasickými i moderními optimalizačními úlohami. Nezávisle na podrobnějším výkladu v dalších kapitolách, chceme na konkrétních a z velké části klasických úlohách vyložit i principy metod řešení formulovaných optimalizačních úloh. Také zde uvedeme formulaci úloh a shrneme některé podmínky řešitelnosti. Druhá kapitola je shrnutím těch matematických pojmů a poznatků, které umožní srozumitelně popsat principy, metody, postupy k dosažení požadovaného výsledku (tj. řešení úlohy). Další kapitoly jsou poté věnovány několika základním typům optimalizačních úloh a soustřeďujeme se na výklad principů metod a odpovídajících algoritmů, tedy tomu, co si dovolujeme nazývat optimalizačními technologiemi. Optimalizační úlohy byly a stále jsou středem pozornosti matematiků od antiky až po současnost. Klíčové principy formuloval Johannes Kepler (Problém vinných sudů), Johan Bernoulli (Úloha brachystochrony), Leonhard Euler (Variační počet), Lagrange (Princip multiplikátorů). V antice byly formulovány úlohy především geometrického charakteru. V počínajícím novověku byly v popředí zájmu úlohy fyzikálního typu (minimalizace energie, podmínky rovnováhy). Za počátek moderní éry zkoumání optimalizačních úloh lze považovat práce L.V. Kantoroviče a G.B. Dantziga (tzv. lineární programování ). Je příznačné, že během druhé světové války a hlavně po ní, americká a britská armáda investovala velké prostředky do tzv. operačního výzkumu, který byl orientován do vývoje metod řešení optimalizačních úloh. Zde se také pro tyto úlohy poprvé objevuje termín „programování“, používaný ve vojenském žargonu pro úlohy optimálního plánování (= tvorba optimálních plánů).

Plzeň 2011

Stanislav Míka, Ludvík Vlček

4

Obsah Předmluva

3

1 Úvod do optimalizace

13

1.1. Úlohy typu minimalizace vzdálenosti (normy) . . . . . . . . . . . . . . . . . . . 13 1.1.1. Speciální geometrická úloha . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.2. Partikulární řešení soustavy s minimální (euklidovskou) normou . . . . 14 1.1.3. Úloha (ortogonální) projekce na lineární varietu . . . . . . . . . . . . . . 15 1.2. Úlohy typu maximalizace míry (obsahu, objemu) . . . . . . . . . . . . . . . . . 17 1.2.1. Pravoúhelník s největším obsahem vepsaným do daného kruhu . . . . . 17 1.2.2. Kvádr daného povrchu s největším objemem . . . . . . . . . . . . . . . . 19 1.2.3. Kvádr daného objemu s extrémním povrchem . . . . . . . . . . . . . . . 20 1.3. Problémy princezny Didó . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.1. Legenda o založení Kartága . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.2. Izoperimetrické úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.3. Druhá Didonina úloha-technologie variačního počtu . . . . . . . . . . . 21 1.3.4. Střípky dějepisu z Internetu . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.4. Další historické úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.4.1. Keplerův problém vinných sudů . . . . . . . . . . . . . . . . . . . . . . . 24 1.4.2. Bernoulliova úloha o brachystochroně . . . . . . . . . . . . . . . . . . . 25 1.4.3. Fermatova úloha o lomu světla . . . . . . . . . . . . . . . . . . . . . . . 27 1.5. Úlohy tzv. Operační analýzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.5.1. Elementární úlohy optimálního plánování . . . . . . . . . . . . . . . . . 28 1.5.2. Dopravní problém . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.5.3. Problém diety (Úloha velkovýkrmny prasat) . . . . . . . . . . . . . . . . 29 1.5.4. Úloha optimálních strategií . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.6. Úlohy optimálního řízení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2 Optimalizační úlohy a jejich řešitelnost

31

2.1. Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2. Řešitelnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.2.1. Weierstrassova věta

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5

6

OBSAH 2.2.2. Věta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.2.3. Věta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3. Sedlový bod, pojem duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.1. Úlohy minima a maxima . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.2. Slabý vztah duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.3. Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.4. Definice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.5. Příklad 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3.6. Příklad 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3.7. Příklad 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3.8. Poznámka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3.9. Nutná a postačující podmínka sedlovosti . . . . . . . . . . . . . . . . . . 37 2.3.10. Sedlové body a teorie her . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.3.11. Princip dualizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.4. Příklady a cvičení

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.4.1. Řešený příklad 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.4.2. Řešený příklad 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.4.3. Řešený příklad 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.4.4. Řešený příklad 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.4.5. Řešený příklad 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.4.6. Řešený příklad 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.4.7. Cvičení 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.4.8. Cvičení 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.4.9. Cvičení 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.4.10. Cvičení 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3 Hladká optimalizace

47

3.1. Spojitost v hromadném bodě . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.1.1. Spojitost funkcí jedné proměnné . . . . . . . . . . . . . . . . . . . . . . 47 3.1.2. Jednostranná spojitost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.1.3. Polospojitost zdola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.1.4. Obecná věta o existenci minima 3.2. Hladkost v

R1

. . . . . . . . . . . . . . . . . . . . . . 48

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.2.1. Diferencovatelnost v R1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.2. Principy podmínek hladké a nehladké optimalizace . . . . . . . . . . . . 49 3.3. Hladkost v Rn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3.1. Derivace ve směru, Gâteauxův diferenciál . . . . . . . . . . . . . . . . . 50 3.3.2. Druhá derivace ve směru . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.3. Kvadratická funkce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3.4. Silná difrencovatelnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

OBSAH

7 3.3.5. Druhý diferenciál . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3.6. Poznámka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.4. Taylorovy formule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.4.1. Taylorova formule 1. řádu v R1 . . . . . . . . . . . . . . . . . . . . . . . 52 3.4.2. Taylorova formule 2. řádu v R1 . . . . . . . . . . . . . . . . . . . . . . . 53 3.4.3. Taylorova formule 1.řádu v Rn . . . . . . . . . . . . . . . . . . . . . . . 53 3.4.4. Taylorova formule 2.řádu v Rn . . . . . . . . . . . . . . . . . . . . . . . 54 3.4.5. Důsledky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.5. Podmínky optimality v klasické optimalizaci . . . . . . . . . . . . . . . . . . . . 54 3.5.1. Věta (Fermat) Nutná podmínka optimality . . . . . . . . . . . . . . . . 54 3.5.2. Věta Nutná podmínka optimality druhého řádu . . . . . . . . . . . . . . 55 3.5.3. Věta. Postačující podmínka optimality č.1 . . . . . . . . . . . . . . . . . 56 3.5.4. Věta. Postačující podmínka optimality č.2 . . . . . . . . . . . . . . . . . 57 3.5.5. Metody nutných podmínek . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.5.6. Vlastnosti kvadratické formy . . . . . . . . . . . . . . . . . . . . . . . . 58 3.5.7. Ilustrativní příklad 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.5.8. Ilustrativní příklad 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.6. Řešené úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.6.1. Úloha 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.6.2. Úloha 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.6.3. Úloha 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.6.4. Úloha 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.6.5. Úloha 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.6.6. Úloha 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.6.7. Úloha 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.6.8. Úloha 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.6.9. Úloha 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4 Technologie jednorozměrné numerické optimalizace

65

5 Numerické metody nepodmíněné optimalizace

67

6 Úlohy podmíněné optimalizace - rovnostní vazby

69

6.1. Úvodní poznatky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.1.1. Přípustné množiny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.1.2. Lemma Redukce dimenze u lineárních vazeb . . . . . . . . . . . . . . . . 70 6.1.3. Lemma Nutné podmínky optimality na lineární varietě . . . . . . . . . . 71 6.2. Řešené úlohy s lineárními vazbam . . . . . . . . . . . . . . . . . . . . . . . . . . 72 6.2.1. Základní úloha kvadratické optimalizace . . . . . . . . . . . . . . . . . . 73 6.2.2. Obecná úloha kvadratické optimalizace

. . . . . . . . . . . . . . . . . . 74

8

OBSAH 6.3. Lagrangeovy multiplikátory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.3.1. Lemma. Řešitelnost úlohy v R2 . . . . . . . . . . . . . . . . . . . . . . . 78 6.3.2. Geometrický pohled na nutné podmínky . . . . . . . . . . . . . . . . . . 79 6.3.3. Obecná věta o Lagrangeových multiplikátorech . . . . . . . . . . . . . . 82 6.3.4. Geometrický pohled . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

7 Úlohy podmíněné optimalizace - nerovnostní vazby

85

7.1. Formulace úloh a ilustrativní příklady . . . . . . . . . . . . . . . . . . . . . . . 85 7.1.1. Přípustné množiny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 7.1.2. Přípustné směry, aktivní vazby . . . . . . . . . . . . . . . . . . . . . . . 86 7.1.3. Spádové směry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7.1.4. Ilustrace množin D(x, V ), D0 (x), F (x, f ) . . . . . . . . . . . . . . . . . . 87 7.1.5. Příklad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7.1.6. Úloha lineární optimalizace . . . . . . . . . . . . . . . . . . . . . . . . . 88 7.2. Podmínky optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.2.1. Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.2.2. Geometrické nutné podmínky lokální optimality

. . . . . . . . . . . . . 90

7.2.3. Věta o ekvivalenci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.2.4. Věta o nutných podmínkách lokální optimality . . . . . . . . . . . . . . 91 7.2.5. Poznámka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 7.3. Metoda nutných OKKT, KKT podmínek - příklady . . . . . . . . . . . . . . . 92 7.3.1. Příklad-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 7.3.2. Příklad-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 7.3.3. Analýza KKT bodů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 7.4. Lagrangeova funkce a Lagrangeova úloha . . . . . . . . . . . . . . . . . . . . . . 97 7.4.1. Lagrangeova funkce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7.4.2. Lagrangeova úloha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7.5. Lagrangeova metoda (princip) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.5.1. ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 8 Sebrané speciality

101

Seznam obrázků 1.1.1 geometrická interpretace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.2 formalizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.3 minimální euklidovská norma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.1.4 ortogonální projekce v Rn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.5 geometrická interpretace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.2.6 formalizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.7 první Didonina úloha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.8 druhá Didonina úloha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.9 graf funkce y = y(x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.10lD = π , λ = 1.3.11lD < π , λ >

1 2 1 2

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.4.12úloha o brachystochroně. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4.1 sedlový bod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.4.2 graf funkce pro volbu hodnoty y

. . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.4.3 graf funkce pro volbu hodnoty x . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.4.4 reliéf funkce F (x, y) = (x − y)2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.4.5 graf funkce F (x, y) = (x − y)2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.4.6 Sedlový bod (1, 1) funkce F (x, y) = 1 − x + y . . . . . . . . . . . . . . . . . . . . 44 2.4.7 Sedlový bod (1, 1) funkce F (x, y) = 1 − x + y . . . . . . . . . . . . . . . . . . . . 44

2.4.8 maticová hra 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.4.9 maticová hra 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.6.1 Ilustrace úlohy (3.6.1.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.6.2 „Prostorové“ zobrazení funkce z úlohy (3.6.2.) . . . . . . . . . . . . . . . . . . . 62 6.1.1 Báze lineárního prostoru a její ortogonální doplněk . . . . . . . . . . . . . . . . 72 b je bod lokálního minima f na V 6.3.2 Bod x

6.3.3 x není bod minima (extrému) f na V

. . . . . . . . . . . . . . . . . . . . . . 80 . . . . . . . . . . . . . . . . . . . . . . . 81

6.3.4 Bod x není bodem lokálního extrému, f na V . . . . . . . . . . . . . . . . . . . 81

9

10

SEZNAM OBRÁZKŮ

Seznam tabulek 3.5.1 Stacionární body - vlastnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 7.1.1 Sinplexová metoda - výsledky . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

11

12

SEZNAM TABULEK

Kapitola 1

Úvod do optimalizace

1.1. Úlohy typu minimalizace vzdálenosti (normy) Úloha na minimalizaci vzdálenosti je jednou z nejběžnějších optimalizačních úloh. Klíčový je pouze pojem vzdálenosti (dvou bodů). Výběr metriky (normy) ovlivní i škálu vhodných metod.

1.1.1. Speciální geometrická úloha V rovině R2 je dána přímka p. Jsou dány dva různé body A, B, které na ní neleží. Na dané přímce p najděte takový bod X, že součet vzdáleností od daných dvou různých bodů A, B neležících na dané přímce p je minimální, tj. min(|AX| + |BX|) =? B

y

A

p

B = [b, d] A = [0, a]

X X

X = [x, 0]

X

x

A′ = [0, −a]

|AX| + |BX| → min

Obrázek 1.1.2: formalizace

Obrázek 1.1.1: geometrická interpretace

Geometrická metoda: Sestrojíme bod A′ , který je osově symetrický podle dané přímky. Hledaný bod X je průsečíkem přímky A′ B s danou přímkou (zdůvodněte). 13

14

1.1. ÚLOHY TYPU MINIMALIZACE VZDÁLENOSTI (NORMY)

Metoda redukce vazební podmínky: Označíme A = [a1 , a2 ], B = [b1 , b2 ], X = [x1 , x2 ]. Budeme minimalizovat funkci (součet eukleidovských vzdáleností) f (x1 , x2 ) =

q

(x1 − a1 )2 + (x2 − a2 )2 +

q

(x1 − b1 )2 + (x2 − b2 )2 ,

kde hledaný bod X = [x1 , x2 ] leží na dané přímce (tzv. přípustné množině) o rovnici ax1 + bx2 + c = 0 , a, b, c jsou dané koeficienty. Z vazební podmínky vypočteme

−ax1 − c b a dosadíme do funkce f . Dostaneme funkci jedné proměnné x2 =

F (x2 ) = f (x1 , −

ax1 + c ) , x1 ∈ R1 b

a k nalezení minima použijeme standardní metodu diferenciálního počtu. Poznámka: Při vhodné volbě souřadnicového systému (viz obrázek 1.1.2) - danou přímku p zvolíme za osu x, budeme přímo minimalizovat funkci ϕ(x) =

p

x2 + a2 +

q

(x − d)2 + b2 , x ∈ R1 ,

tj. hledáme kořeny rovnice ϕ′ (x) = 0 (nulová podmínka minima).

1.1.2. Partikulární řešení soustavy s minimální (euklidovskou) normou Mějme soustavu lineárních rovnic Bx = C, kde B je daná obdélníková matice typu (p, n), p < n, p = hod(B) a c ∈ Rp je daný sloupec (vektor). Všechna řešení tvoří množinu Vc = {c ∈ Rn : Bx − c = 0} b ∈ VC , které má nejmenší euklidovskou normu, tj. platí Ze všech x ∈ Vc chceme najít takové x b ||2 ≡ x bT x b ≤ x b T x , ∀x ∈ Vc . ||x

Geometricky to znamená, že na lineární varietě Vc hledáme takový bod, který je nejblíže počátku (pata kolmice spuštěné z počátku na množinu Vc ). 1 Je vhodné hledat minimum a bod minima kvadratické funkce f (x) = xT x , x ∈ Vc . 2 Výklad metody se opírá o princip redukce dimenze a o některou podmínku optimality (viz kapitola 6) b: Zaznamenáme pouze „technologii“ výpočtu bodu x

b = (BBT )−1 c ; jediné řešení soustavy BBT v = c s regulární maticí BBT ; 1. stanovíme v řádu p.

b ; obraz vektoru v b ∈ Rp v zobrazení BT : Rp → Rn (je to fakticky b = BT v 2. stanovíme x podmínka nulovosti derivace funkce f ve směru množiny Vc )

1. ÚVOD DO OPTIMALIZACE

15

Konretizace: b1 , x b2 ), Na přímce Vc = {x1 , x2 ∈ R2 : 3x1 + 4x2 = 8} (viz obr.1.1.3) chceme najít takový bod (x který je nejblíže k počátku. Je zřejmé, že: B = [3, 4] ; BT =

"

3 4

8 b= b= ;x v 25

#

"

; BBT = 25 ; (BBT )−1 =

3 4

#

8 1 · = · 25 25

"

#

24 32

1 25

.

x2 Vc [0,2] b = [xˆ1 , xˆ2 ] x V0

y=[2.5,1]

yp x1

[2.66,0]

[0, 0]

X = [x1 , x2 ] wp Obrázek 1.1.3: minimální euklidovská norma

Poznámka: Výše uvedený „vzorečkový“ přístup k úloze nejspíše každého neuspokojí. Je odvozen z principu nutných podmínek minima (metoda redukce dimenze).

1.1.3. Úloha (ortogonální) projekce na lineární varietu Mějme lineární varietu Vc = {x ∈ Rn : Bx − c = 0} , kde Rn je euklidovský prostor se skalárním součinem x T y ; x , y ∈ Rn a normou ||x|| =

√

xT x ,

a standardním pojmem ortogonality. B je daná obdélníková matice typu (p, n), p < n, p = hod(B), c ∈ Rn .

16

1.1. ÚLOHY TYPU MINIMALIZACE VZDÁLENOSTI (NORMY)

Úlohu projekce formulujeme jako optimalizační úlohu takto: je dán prvek y ∈ Rn , y ∈ / Vc . Chceme stanovit takový prvek yp ∈ Vc , že platí ||yp − y|| = inf ||x − y|| . Dále definujeme množinu V0 = {w ∈ Rn : Bw = 0}

Je to lineární prostor všech řešení dané homogenní soustavy. dimenze tohoto lineárního prostoru (počet nezávislých řešení) je dim V0 = n−p (p je počet lineárně nezávislých řádků matice B ≡ sloupců matice BT ). Na obrázku (1.1.4) jsme si Vc a V0 znázornili dvěma rovnoběžnými přímkami. Prvek 0 ∈ V0 , 0 ∈ V ⊥ je také nulovým prvkem prostoru Rn . Vc y V0 x V0⊥

yP

yQ = Qy w p = Py

b x

0

Obrázek 1.1.4: ortogonální projekce v Rn

b ∈ Vc , pro Symbolem V0⊥ označujeme tzv. ortogonální doplněk prostoru V0 . Prvek x ⊥ b ∈ Vc , je partikulárním řešením soustavy Bx − c = 0 s minimální normou. který je také x

Chceme popsat, jak určíme řešení naší úlohy, tj. prvek yp ∈ Vc , který je ortogonálním průmětem prvku y ∈ Rn na Vc a tedy bodem minima vzdálenosti ||x − y||, x ∈ Vc . Popíšeme opět pouze technologii stanovení bodu yp .

b ∈ V0⊥ technologií z odst.1.1.2., tj. 1. Stanovíme x

b = BT (BBT )−1 c = BT (BBT )−1 Bx , ∀x ∈ Vc ; x

2. Stanovíme yQ ∈ V0⊥ , tj. ortogonální průmět prvku y ∈ Rn na V0⊥ : yQ = BT (BBT )−1 By ; 3. Stanovíme xP ∈ V0 , tj. ortogonální průmět prvku y ∈ Rn na V0 : wp = y − yQ = (I − BT (BBT )−1 B)y = Py ;

Matice P je řádu n a je to matice ortogonální projekce z Rn na lineární prostor V0 . Matice Q = BT (BBT )−1 B je řádu n a je to matice ortogonální projekce z Rn na lineární prostor V0⊥ .


17

4. Hledaný průmět yp prvku y ∈ Rn na lineární varietu Vc : b + wp = x b + Py . yp = x

Konkretizace: Na přímce Vc = {x1 , x2 } ∈ R2 : 3x1 + 4x2 = 8 (viz obr.1.1.3) chceme najít bod yp = [y1 , y2 ], který je ortogonálním průmětem bodu y = [2, 1].

Potom

1 b= · Zde, podobně jako v příkladu odst.1.1.2. vypočteme x 25 yQ =

"

3 4

wp =

"

#

1 · · [3, 4] · 25

2 1

#

1 − · 25

"

"

2 1

30 40

b + wp = yp = x

"

#

#

1 = · 25

=

44 25 17 25

"

#

"

20 25 15 − 25

#

30 40 #

"

24 32

#

;

;

;

.

1.2. Úlohy typu maximalizace míry (obsahu, objemu) V tomto odstavci shrneme nejznámější „školské“ optimalizační úvahy, které se vyskytují ve většině matematických učebnic. Naším cílem však bude vyložit principy metod, které budou podrobně studovány v dalších kapitolách. Již před dvěma sty lety formuloval Joseph Louis Lagrange (17366-1813) následující „technologický“ návod, který sehrál klíčovou roli při rozvoji teorie a praxe optimalizačních úloh a metod jejich řešení. V knize Théorie des functions analytiques (Paříž 1813) Lagrange říká: „Lze vyslovit následující princip. Jestliže hledáme minimum, nebo maximum nějaké funkce více proměnných s podmínkou, že mezi těmito proměnnými existuje vazba zadaná jednou, nebo několika rovnicemi, je třeba přičíst k minimalizované (maximalizované) funkci určující rovnice vazby vynásobené neurčitými multiplikátory a pak hledat minimum nebo maximum tohoto součtu tak, jako by byly nezávislé. Získané rovnice spolu s rovnicemi vazeb umožní určit všechny neznámé“.

1.2.1. Pravoúhelník s největším obsahem vepsaným do daného kruhu K matematické formulaci nám pomůže obrázek. Ve zvoleném souřadnicovém systému bude bod X = [x, y] ∈ R2 jedním ze čtyř vrcholů hledaného pravoúhelníka. Vždy můžeme souřadnicové osy takto zvolit. Souřadnice tohoto vrcholu musí splňovat podmínku (bod X leží na kružnici) x2 + y 2 = r 2 , r > 0 .

18

1.2. ÚLOHY TYPU MAXIMALIZACE MÍRY (OBSAHU, OBJEMU)

y

X = [x, y]

x

Obrázek 1.2.6: formalizace

Obrázek 1.2.5: geometrická interpretace chceme maximalizovat obsah čtyřúhelníka f (x, y) = 4xy pro ty rozměry, které patří do množiny

V = {(x, y) ∈ R2 : x2 + y 2 = r 2 , x ≥ 0 , y ≥ 0} . je zřejmé, že pro libovolná nezáporná x, y bude min 4xy = 0 a maximum nebude existovat, tj. min 4xy = 0

(x,y)∈R2+

;

max 4xy = +∞

(x,y)∈R2+

Tecnologie redukce počtu proměnných (redukce dimenze) √ Pro x > 0 bude y = r 2 − x2 > 0 a obsah vyjádříme jako funkci jedné proměnné, tj. f (x, y) = f (x,

p

p

ozn.

r 2 − x2 ) = F (x) = 4x r 2 − x2 , x ∈ (0, +∞) .

b) = 0 pro hledaný rozměr x b > 0. Použijeme podmínku lokálního extrému F ′ (x

Dostaneme

r r b = √ , yb = √ . x 2 2

Hledaným pravoúhelníkem je čtverec o obsahu f (x, y) = 2r 2 . Technologie Lagrangeovy funkce Podle Lagrangeova principu přičteme k maximalizované funkci anulovanou vazební podmínku vynásobenou číselným parametremm tj. sestrojíme funkci L(x, y, v) = 4xy + v(x2 + y 2 − r 2 ) . Z podmínek lokálního maxima (x > 0 , y > 0 , v ∈ R1 ) ∂L = 4y + 2xv = 0 , ∂x

∂L = 4x + 2yv = 0 , ∂y

∂L = x2 + y 2 − r 2 = 0 , ∂v dostaneme 2y = −xv ,

2x = −yv ,

a tedy x = y .

1. ÚVOD DO OPTIMALIZACE Výsledek:

19

r r b = √ , yb = √ , vb = −2 . x 2 2

Technologie penaltové funkce

K maximalizované funkci přičteme kladný násobek mocniny anulované vazební podmínky (tzv. penaltu), tj. sestrojíme funkci F (x, y, p) = 4xy + p(x2 + y 2 − r 2 )2 . Z podmínek lokálního extrému funkce F , (x > 0 , y > 0 , p > 0), tj. podmínek ∂F = 4y + 2(x2 + y 2 − r 2 ) · 2px = 0 , ∂x ∂F = 4x + 2(x2 + y 2 − r 2 ) · 2py = 0 , ∂y dostaneme 1 + p(2x2 − r 2 ) = 0 ,

x=y, odtud

xp = y p = b= Pro p → +∞ bude xp → x

√r 2

, yb =

√r 2

s

1 + p(2y 2 − r 2 ) = 0 .

1 r2 − . 2 2p

.

Metoda penaltové funkce je velmi oblíbená pro řešení složitějších inženýrských úloh, neboť umožňuje jednoduchou numerickou realizaci (viz kapitola. . . ). Je patrné, že z tohoto příkladu není vidět obecný „penaltový princip“, tj. jak se má sestrojovat penaltová funkce pro obecnější úlohy.

1.2.2. Kvádr daného povrchu s největším objemem Označíme-li x, y, z rozměry hledaného kvádru, potom budeme hledat maximum funkce f (x, y, z) = xyz

,

x > 0 ,y : 0 ,z > 0 ,

s podmínkou pro povrch, například ve tvaru xy + yz + xz = 1 . Technologií Lagrangeovy funkce L(x, y, z) = xyz + v(xy + yz + xz − 1) z podmínek lokálního extrému dostáváme yz + v(y + z) = 0 , xz + v(x + z) = 0 , xy + v(x + y) = 0 a pak

Odpověď: je to krychle!

1 1 b = yb = yb = √ , vb = − √ . x 3 2 3

Technologie redukce dimenze, nebo penaltové funkce jsou v tomto případě podstatně pracnější.

20

1.3. PROBLÉMY PRINCEZNY DIDÓ

1.2.3. Kvádr daného objemu s extrémním povrchem Zadání si zjednodušíme úvahou, že nemá smysl (proč ?) uvažovat úlohu na maximální povrch. Budeme tedy hledat minimum funkce f (x, y, z) = xy + yz + yz

,

x>0, y>0, z>0,

s podmínkou pro objem xyz = 1 . Technologií Lagrangeovy funkce L(x, y, z) = xy + yz + xz + v(xyz − 1) a podmínek lokálního extrému dostaneme

Odpověď: je to krychle.

b = yb = zb = 1 , vb = −2 . x

1.3. Problémy princezny Didó 1.3.1. Legenda o založení Kartága Asi v roce 890 př.n.l vládl ve fénickém městě Tyru (jižně od Bejrůtu v dnešním Libanonu) král Muttoial. Po jeho smrti připadl trůn jeho dětem – dceři Didó a synovi Pygmalionovi. Princezna Didó se pravděpodobně provdala za svého strýce Acherbase, nesmírně bohatého muže s vlivným postavením ve státě. Dnes bychom řekli, ře byl vlivným a mocným lobistou. Některé historické prameny uvádějí poněkud odlišné jméno manžela princezny Didó. Uvádí se, že jejím manželem byl Sychaeus, muž stejně mocný a bohatý, jako Acherbas. Bratr princezny Didó, princ Pygmalion, však zatoužil po majetku a postavení svého švagra a tak ho nechal zabít. V té době, příznivci prince Pygmaliona zastoupení ve vládě, požadovali vládu pouze jednoho panovníka. Tak začalo pronásledování princezny Didó. Traduje se, že princezna stačila na poslední chvíli uprchnout s věrnou posádkou na jedné lodi a „vzít“ sebou značnou část státního pokladu. Po poměrně dlouhém a strastiplném putování se posádka utábořila na pobřeží dnešního Tuniska. Díky „zachráněné“ části státního pokladu byla Didó relativně bohatá a tak chtěla od místního vládce koupit pozemek k založení osady. Místní vládce, král Hiarbo, oslněn krásou princezny Didó s prodejem pozemku na mořském pobřeží souhlasil. Vymínil si však, že „ne větší, než jaký lze ohraničit volskou kůží“. Zřejmě ale nepočítal s tím, že krásná princezna Didó může být také chytrá. Rozřezala volskou kůzi na tenké proužky, které svázala a tak získala velmi dlouhý řemen dané délky. Tím pak ohraničila pozemek s maximální výměrou (plochou). Tak přelstila „chytrost“ krále Hiarba. Na takto získaném pozemku pak založila pevnost Byrsu, která se později stala základem mocného města, dnes bychom řekli supervelmoci tehdejšího světa – Kartága.


21

1.3.2. Izoperimetrické úlohy Mezi všemi rovinnými (uzavřenými) křivkami předepsané délky máme najít takovou, jenž ohraničuje plochu s maximálním obsahem. Analogicky, mezi prostorovými uzavřenými plochami předepsaného obsahu máme najít takovou plochu, která ohraničuje největší objem. a) První Didonina úloha Mezi všemi oblouky AB délky L ležícími v polorovině ohraničené přímkou p, pevným koncovým bodem A ∈ p a pohyblivým bodem B ∈ p, najít takový oblouk, který spolu s úsečkou AB ohraničuje obrazec největšího obsahu. b) Druhá Didonina úloha Mezi všemi oblouky délky L ležícími v polorovině ohraničené přímkou p a danými (pevnými) body A, B ∈ p, najít takový oblouk, který spolu s úsečkou AB ohraničuje obrazec největšího obsahu. c) Třetí didonina úloha Mezi všemi oblouky ležícími v polorovině ohraničené přímkou p a danými (pevnými) body A, B ∈ p najít takový oblouk (křivku), který má pro daný obsah spolu s úsečkou AB nejkratší délku. . . . dokreslit obrázek. . .

. . . dokreslit obrázek. . .

Obrázek 1.3.7: první Didonina úloha

Obrázek 1.3.8: druhá Didonina úloha

1.3.3. Druhá Didonina úloha-technologie variačního počtu Chceme maximalizovat obsah v oblasti R2 omezené úsečkou AB „položenou“ do osy x pravoúhlého souřadného systému (x, y) tak, že A = [0, 0], B = [1, 0] a grafem fumkce y = y(x), x ∈ h0, 1i, splňující podmínky y(0) = 0, y(1) = 0 s konstantní délkou grafu lD =

Z1 q

1 + (y ′ (x))2 dx

0

. . . dokreslit obrázek. . . Obrázek 1.3.9: graf funkce y = y(x) Zde si situaci zjednodušujeme několika předpoklady. Předpokládáme, že křivka dané délky lD je graf funkce. Dále o této funkci předpokládáme, že je hladká (dvakrát spojitě diferencovatelná) a nezáporná. Chceme tedy nalézt maximální obsah oblasti omezené úsečkou AB a grafem funkce y = y(x, x ∈ h0, 1i). Tento obsah vyjádříme integrálem f (y) =

Z1 0

y(x) dx , y(x) ≥ 0 .

22

1.3. PROBLÉMY PRINCEZNY DIDÓ

Maximum integrálu f (y) tedy hledáme na množině funkcí 2

V = {y ∈ C (h0, 1i)} : y(0) = 0 , y(1) = 0 ,

Z1 q

1 + (y ′ (x))2 dx = lD , y(x) ≥ 0

0

použijeme myšlenku Lagrangeova principu (viz odst.1.2.) aR sestrojíme integrál (tzv. Lagranp gián) tak, že k integrálu f (y) přičteme vazební podmínku 01 1 + (y ′ (x))2 dx − lD = 0 vynásobenou neurčitým multiplikátorem λ ∈ R1 , tj. L(y, λ) =

Z1 0

  1 Z q 1 + (y ′ (x))2 dx − lD  , λ ∈ R1 . y(x) dx + λ  0

Na Lagrangián L se díváme jako na funkci dvou proměnných a „zvolíme“ nutné podmínky b : y = yb + αh , λ = λ b + βν ; extrému v optimálním bodě (yb, λ) d 1 L(yb, αh, λ)|α=0 = lim [L(yb + αh, λ) − L(yb, λ)] = 0 , α→0 dα α

i 1h d b + βν) b + βν) − L(y, λ) b =0. = lim L(y, λ L(y, λ β=0 β→0 β dβ

K výpočtu uvedených limit musíme použít „rafinované“ techniky ze základního kurzu mateamtické analýzy.

(A)

b Dostaneme soustavu pro neznámé yb a λ: Z1

h(x) dx + λ

0

Z1 0

yb′ (x)h′ (x) p dx = 0 , 1 + (yb′ (x))2

Z1 q

1 + (y ′ (x))2 dx = lD .

(B)

0

Po úpravě rovnice (A) užitím metody per partes dostaneme Z1 " 0

λyb′ (x) 1− p 1 + (yb′ (x))2

!′ #

h(x) dx = 0 .

Zde usoudíme, že výraz v závorce musí být nulový, tj. musí platit #

"

d λyb′ (x) p =1. dx 1 + (yb′ (x))2

Přímou integrací a dalšími manipulacemi postupně dostáváme λ · yb′ = x + C1 , C1 je integrační konstanta. 1 + (yb′ )2 λ2 · (yb′ )2 = (x + C1 )2 , 1 + (yb′ )2 h

i

λ2 · (yb′ )2 = (x + C1 )2 · 1 + (yb′ )2 ,


23 h

i

λ2 · (yb′ )2 = (x2 + 2C1 x + C12) · 1 + (yb′ )2 ,

λ2 · (yb′ )2 = x2 + 2C1 x + C12 + (yb′ )2 x2 + 2C1 (yb′ )2 x + C12 (yb′ )2 , b′ )2 − (yb′ )2 x2 − 2C1 (yb′ )2 x − C12 (yb′ )2 = x2 + 2C1 x + C12 , λ2 (x h

i

(yb′ )2 · λ2 − (x2 + 2C1 x + C12 ) = (x2 + 2C1 x + C12 ) , h

i

(yb′ )2 · λ2 − (x + C1 )2 = (x + C1 )2 ,

|x + C1 | , λ2 > (x + C1 )2 . |yb′ | = p 2 λ − (x + C1 )2

Další přímou integrací dostaneme jednu variantu výsledku ve tvaru q

yb(x) = − λ2 − (x + C1 )2 + C2 , C2 je integrační konstanta.

(C)

Z okrajových podmínek

yb(0) = yb(1) = 0

dostaneme

r

1 1 1 C1 = − , C2 = λ2 − , λ2 ≥ , 2 4 4 a (C) vede na systém kružnic s parametrem λ:

1 x− 2

2

+ y−

r

λ2 −

1 4

!2

= λ2 .

Z vazební podmínky (rovnice B) lze vypočítat (pro dané lD ) λ: Z1 0

q

λ

λ2 − (x + 12 )2

dx = lD .

Výsledky jsou patrné na obrázcích (1.3.10) a (1.3.11). . . . dokreslit obrázek. . .

. . . dokreslit obrázek. . . Obrázek 1.3.10: lD = π , λ =

1 2

Obrázek 1.3.11: lD < π , λ >

1 2

1.3.4. Střípky dějepisu z Internetu Ať je legenda o založení Kartága pravdivá či nikoliv, historickým faktem zůstává, že bylo založeno přibližně v roce 814 př.n.l. féničany jako kolonie Tyru. Podle pověsti byla Didó (některé prameny uvádí jméno „Dídó“, také „Elissar“, či „Alissa“) první královnou Kartága. Stala se mezi svým lidem velmi oblíbeou a kartágo pod její vládou prosperovalo. Jméno Kartágo je odvozené z fénického QRT HDŠT, neboli Qart Hadašt znamenající Nové město. Starověcí féničané pravděpodobně nebyli příliš „tvořiví“ při pojmenovávání svých nových kolonií, jméno Qart Hadašt neslo více jejich zámořských osad. Proslulosti ve starověkém světě však dosáhlo pouze jedno jediné. Postupem času Kartágo vyrostlo v obrovskou eknomickou mocnost ve Středomoří. Shromáždilo obrovské bohatství a získalo dominantní ekonomický vliv. Ve své době vládlo dalším 300 městům kolem západní části Středozemního moře.

24

1.4. DALŠÍ HISTORICKÉ ÚLOHY

Zatímco termín „kartaginský“ je spíše používán současnými autory, starověké spisy ve vztahu k čemukoliv kartaginskému používají termín, „punský“. Latinský termín punicus odvozený od staršího poenicus původně pochází z řeckého θoιυικη, znamenající „Fénicie“. Kartágo bylo ve 2. a 3. stol. př.n.l., řečeno dnešní terminologií, úřadující supervelmocí. Velmi vážného konkurenta ale měla v Římské republice, coby „nastupující“ supervelmoci. S ní soupeřila o nadvládu nad západním Středomořím. Tato rivalita posléze vyústila v sérii válek, které vešly do dějin pod označením punské války. Série tří válek, známých jako punské války měly pro Kartágo zničující dopad. Bohaté Kartágo dokázalo vybudovat mocné armády se schonými vojevudci. Hannibal přešel se svými slony Alpy a po počátečních drtivých vítězstvích nad římskými legiemi stanul před branami Říma. Řečeno dnešní terminologií, však doplatil na hrubé podcenění logistiky. Ve chvíli, kdy stál před branami Říma, měl kritický nedostatek skoro všeho vojenského materiálu, zásobami potravin počínaje a unavenou a vyčerpanou armádou konče. Takže nebyl schopen dobýt žádné větší opevnění římské město. Této šance Římané bezezbytku využili. Podobné „drobnosti“ nakonec vedly k porážkám Kartagiských armád. Prohry vedly k úpadku ekonomické a politické síly Kartága. Úpadek ještě umocnily velmi tvrdé sankce uvalené na Kartágo vítězem, jako podmínka k zastavení bojů. Zda došlo k úpadku Kartága díky prohraným válkám, nebo zda úpadek města, jeho rozmařilost, způsobila, že díky tomu Kartágo prohrálo války dnes pravděpodobně nezjistíme. Třetí a poslední punská válka skončila úplným zničením města Kartága a anektování kartaginského území Římany. Studium historie Kartága je poněkud problematické, Římané po zničení původního města vystavěli na jeho rozvalinách Kartágo nové, nyní již ale římské. Téměř všechny kartaginské památky, buď písemné, či stavební byly po vyhraných válkách Římany metodicky ničeny. Není se čemu divit, Řím většího a nebezpečnějšího nepřítele do té doby i od té doby neměl. Většina z dochovaných záznamů, či překladů původních textů, „pochází“ od římských historiků. Ti svého „úhlavního nepřítele“ neměli nejmenší důvod vychvalovat, či obhajovat. Archeologické výzkumy neustále pokračují na původních kartaginských místech a mnohé z vykopávek některé aspekty tradičního obrazu Kartága potvrzují, mnohé z nich naopak vyvracejí.

1.4. Další historické úlohy 1.4.1. Keplerův problém vinných sudů Až do XVII. století nebyly vypracovány žádné obecné metody řešení extremálních úloh, ale každá úloha se řešila speciálně pro ni vypracovaným postupem. V r.1615 v knize Nové výpočty vinných sudů („Nova stereometrica doliorum vinariorum“) Kepler píše: „V roce, kdy jsem se ženil, byla velmi dobrá úroda vinných hroznů a víno bylo levné, a proto jsem se chtěl jako dobrý hospodář zásobit vínem. Koupil jsem ho několik soudků. Za nějakou dobu přišel prodavač změřit objem soudku a stanovit cenu za víno. Do každého soudku spustil železný prut; a pak, bez nějakých výpočtů, hned oznámil, kolik je v sudu vína.“ Kepler byl velmi udiven. Zdálo se mu divné, že pomocí jednoho měření lze vyčíslit objem sudů různých tvarů. Aby tuto úlohu rozřešil, Kepler buduje základy diferenciálního a integrálního počtu. Současně formuluje první obecná pravidla řešení extremálních úloh. Píše: „Na základě zdra-


25

vého geometrického citu vyráběli bednáři sudy takového tvaru, který pro danou délku obrysu zaručuje největší objem sudu. A jelikož v blízkosti každého maxima bývají změny neznatelné, nemají malé odchylky vliv na objem.“ Přesnější formulace byla dána Fermatem (1629) a pak Newtonem a Leibnitzem. Poznamenejme ještě, že Kepler řešil několik konkrétních extremálních úloh, zejména úlohu o válci největšího objemu, vepsaném do koule. V současné době se specialisté zabývají úlohami tzv. tvarové optimalizace, v nichž se za daných techologických podmínek hledá oblast optimálního tvaru.

1.4.2. Bernoulliova úloha o brachystochroně V roce 1696 v pojednání Johanna Bernoulliho „Problema novum, ad cujus solutionem mathematici invitantur“ („Nová úloha, k jejímuž řešení zveme matematiky“) byla formulována úloha: „Ve vertikální rovině jsou dány dva body A a B. Najděte dráhu, po níž se těleso působením vlastní tíže dostane z bodu A do bodu B za nejkratší dobu.“ Tuto úlohu řešili dále Leibnitz, Jacob Bernoulli, Newton a řada dalších a stala se základem variačního počtu. Pro analýzu úlohy a výklad texhnologie výpočtu opět umístíme souřadnicový systém podle obrázku 1.4.12

A = [0, 0]

bx

x

x

M = [x, y(x)]

y(x)

B = [bx , by ]

by y

Obrázek 1.4.12: úloha o brachystochroně. Těleso o hmotnosti m se má pohybovat bez tření vlastní tíží po oblouku AM B. Rychlost v místě M nezávisí na tvaru křivky spojující body A a B (Galileův zákon) a podle zákona energetické bilance je kinetická a potenciální energie v každém bodě M = (x, y) v rovnoáze, tj. platí rovnost

(D)

1 mv 2 = mgy, 2

g je gravitační zrychlení

kde y = y(x) , v = (x). Nechť hledaná křivka spojující body A a B je grafem funkce y = y(x). Musí proto platit (okrajové) podmínky (E)

y(0) = 0,

y(bx ) = by

26

1.4. DALŠÍ HISTORICKÉ ÚLOHY

Současně můžeme hledanou křivku vyjádřit parametricky (F)

x = x(t), y = y(t), t ∈ h0, T i

kde roli parametru hraje čas t. T je čas potřebný k dosažení bodu B z bodu A (je také hledaným parametrem). Tedy x(0) = 0, x(T ) = bx , y(0) = 0, y(T ) = by Označme s = s(t) délku oblouku hledané křivky opsanou tělesem v okamžiku t. Platí tedy (G)

ds v(x) ≡ v(t) = = dt

p

x˙ 2 + y˙ 2 dt = dt

p

1 + (y ′ )2 dx q = 2gy(x). dt

Odtud pak úpravou dostaneme (H)

dt =

s

1 + (y ′ )2 dx. 2gy

Integrujeme podle t přes interval h0, T i. V proměnné x tomu odpovídá integrace přes interval hx(0), x(T )i ≡ h0, bx i. Takže dostaneme (I)

T=

ZT

dt =

0

Zbxs 0

1 + (y ′ )2 dx. 2gy

Je zřejmé, že čas T pohybu tělesa závisí na tvaru křivky, tj. T = T (y). Chceme stanovit takovou funkci y = yb(x), pro kterou platí T (yb) = min T (y) y

tj. požadujeme splnění nerovnosti (J)

T (yb) ≤ T (y)

pro všechny funkce y = y(x) splňující uvedené okrajové podmínky, tj. všechny (hladké) křivky spojující body A a B. Závislost (I) času T = T (y) na funkci y = y(x), x ∈ h0, bx i je funkcionál definovanýna přípustné množině V funkcí y splňující zřejmé podmínky z obrázku (1.4.12) tj V = {y ∈ C 1 (h0, bx i) : y(0) = 0, y(bx ) = by , y(x) ≥ 0,

Zbx 0

dx < ∞} . y(x)

p

Zde si však technologii výpočtu zjednodušíme tím, že nutnou podmínku minima pro úlohu (J) budeme hledat pro y ∈ C 2 h0, bx i.

Podmínka stacionárnosti funkcionálu T (y) v bodě yb(x) je podmínka nulovosti diferenciálu (rovnice)

T (yb + αh) − T (yb) d δT (yb, h) = = lim T (yb + αh) =0. α→0 dα α α=0

Je věcí důvěry čtenáře k autorovi textu, že po určitých manipulacích (technologie variačního počtu) dostaneme podmínku   d  1 =0, q dx y (1 + (y ′ ))2


27

tj. y(1 + (y ′ ))2 = C ,

C je kladná konstanta.

Tento vztah představuje nelineární diferenciální rovnici pro neznámou funkci y = y(x), x ∈ h0, bx i. Substitucí y ′ = cotg 2t obdržíme (t he parametr) y(t) =

C C t = 2 (1 − cos t) . 2 1 + cotg 2

Protože

dy dt dy = , dx dt dx

potom

dx t = C sin2 dt 2 a tedy (parametrické vyjádření hledané křivky) C C (t − sin t) , yb(t) = (1 − cos t) , t ∈ (0, T ) . 2 2 Křivka, po které těleso dospěje z bodu A do bodu B za nejkratší čas je tedy oblouk cykloidy. Konstantu C a potřebný čas Tb = T (yb) vypočteme z okrajových podmínek b(t) = x

Takže

b(Tb) = bx = x

C C b (T − sin Tb) , yb(Tb) = by = (1 − cos Tb) . 2 2 Tb = Tb (yb) = min T (y) . y∈V

1.4.3. Fermatova úloha o lomu světla

Formulace prvního variačního principu pro fyzikální úlohu spojujeme se jménem Pierra Fermata. Jde o Fermatův variační princip v geometrické optice. Zákon lomu světla byl experimentálně stanoven Snellem. Zanedlouho byl tento zákon teoreticky objasněn Descartem. Podle Descartovy teorie však vychází, že rychlost světla v hustším prostředí je větší než v prostředí řidčím. O této skutečnosti mnozí pochybovali. Fermat podal jiné vysvětlení tohoto jevu. jeho základní myšlenka spočívala v tom, že paprsek světla si „vybírá“ takovou trajektorii, podél které čas vynaložený na překonání cesty z jednoho bodu do druhého je minimální (ve srovnání sjinými trajektoriemi spokujícími tyto body). Huygens navrh jiné vysvětlení zákona o šíření a lomu světla. Ukázalo se, že mezi Huygensovým principem a Fermatovým principem je velmi úzká souvislost. Tyto úvahy se staly základem pro budoucí Hamiltonovu-Jacobiovu teorii a v první polovině minulého století pro takzvanou teorii dynamického programování, která je důležitým nástrojem řešení aplikovaných extremálních úloh. Záhy po Fermatově principu byla objevena řada dalších variačních principů. Z počátku v mechanice, poté i ve fyzice. Formalizací Fermatova variačního principu o trajektorii světelného paprsku v dvojrozměrném nehomogením prostředí dospějeme opět k úloze minimalizace integrálu T (y) T=

ZT 0

dt =

Zbxs 0

1 + (y ′ )2 dx. 2gy

28

1.5. ÚLOHY TZV. OPERAČNÍ ANALÝZY

√ Rychlost paprsku v bodě (x, y) je opět v = 2gy. Dá se ukázat, že známý Snellův zákon lomu světla má charakter nutné podmínky minima integrálu T (y). Napíšeme-li jej ve tvaru

sin α(x) = konst , v(x)

můžeme s jeho pomocí danou úlohu vyřešit. Zde α(x) je úhel mezi tečnou křivky y(x) a osou y (viz obr.1.4.12). Proto sin α(x) =

1 dx dx p = . =p ds 1 + (y ′ )2 · dx 1 + (y ′ )2

Máme tedy Snellův zákon ve tvaru

√

1 = konst . 2gy · 1 + (y ′ )2 p

Tento vztah představuje nelineární diferenciální rovnici pro neznámou funkci y y(1 + (y ′ )2 ) = C ,

C=

1 . 2g · konst2

Substitucí y ′ = cotg 2t obdržíme y= Protože

C C t = 2 (1 − cos t) . 2 1 + cotg 2 dy dt dy = · , dx dt dx

potom

dx t = C sin2 , dt 2

a tedy

C C (t − sin t) , yb(t) = (1 − cos t) , t ∈ (0, T ) . 2 2 Křivka, po které paprsek dospěje z bodu A do bodu B za nejkratší čas je tedy oblouk cykloidy. Konstantu C a potřebný čas T vypočteme z podmínek b(t) = x

bx =

C C (T − sin T ) , by = (1 − cos T ) . 2 2

1.5. Úlohy tzv. Operační analýzy 1.5.1. Elementární úlohy optimálního plánování 1.5.2. Dopravní problém Předpokládejme, že zásoby nějakého zboží jsou uloženy v několika skladech a toto zboží má být distribuováno do několika obchodů. Známe cenu přepravy jednotkového množství


29

zboží z každého skladu do každého obchodu a víme, kolik zboží musí být dodáno do každého obchodu. Dopravní problém spočívá v sestavení optimálního plánu přepravy; je třeba určit, jaké množství zboží máme převést z každého skladu do každého obchodu tak, aby celkové dopravní náklady byly minimální. Na dané přímce najít takový bod, že součet jeho vzdáleností od daných dvou různých bodů neležících na dané přímce je minimální. Formalizace: Zavedeme nejdříve vhodné označení: ai - množství jednotek zboží v i-tém skladu, 1 ≤ i ≤ m, bj - požadavek (ve stejných jednotkách) j-tého obchodu, 1 ≤ j ≤ n, cij - cena přepravy jednotky zboží z i-tého skladu do j-tého obchodu, xij - plánované množství jednotek zboží pro převoz z i-tého skladu do j-tého obchodu, cij xij - cena přepravy z i-tého skladu do j-tého obchodu. Vidíme, že je třeba minimalizovat celkovou cenu přepravy m X n X

(K)

cij xij

i=1 j=1

a přitom dodržet daná omezení: n P

j=1 m P i=1

xij ≤ ai

(nelze odvézt více, než se nachází ve skladu),

xij = bj

(je třeba převézt právě tolik, kolik se požaduje),

xij ≥ 0

(zřejmé).

Jsou-li náklady na přepravu závislé na množství přepravovaného zboží, pak cij = cij (xij ); např. cij = pij + qij xij .

1.5.3. Problém diety (Úloha velkovýkrmny prasat) 1.5.4. Úloha optimálních strategií

1.6. Úlohy optimálního řízení

30

1.6. ÚLOHY OPTIMÁLNÍHO ŘÍZENÍ

Kapitola 2

Optimalizační úlohy a jejich řešitelnost

2.1. Základní pojmy Optimalizační úlohou obvykle rozumíme (a) úlohu na hledání minima nebo maxima (optimalizační úloha v užším smyslu); (b) úlohu hledání sedlového bodu, též také nyzývanou úlohu minimaxu (úlohy teorie her, teorie duality, odhady chyb, teorie aproximace); (c) úlohu hledání kritických (stacionárních) bodů; (d) variační nerovnice; (e) úlohu variačního počtu; (f) úlohu optimálního řízení; Mějme funkci (funkcionál) f : X → R1 a podmnožinu V ⊂ X . Úlohu na minimum vzhledem k množině V pro funkci f formulujeme takto: b ∈ V takový, že fb = f (x b ), že platí: Najděte číslo fb = inf f (x) a prvek (bod) x x∈V

(A)

b ) ≤ f (x) , ∀x ∈ V . f (x

Tuto úlohu budeme zapisovat ve tvaru

min {f (x) | x ∈ V } . Úlohu na maximum vzhledem k množině V pro funkci f formulujeme takto: b ∈ V takový, že fb = f (x b ), a tedy platí: Najděte číslo fb = sup f (x) a prvek (bod) x x∈V

(B)

b ) ≥ f (x) , ∀x ∈ V . f (x

Tuto úlohu budeme zapisovat ve tvaru:

max {f (x) | x ∈ V } . 31

32

2.1. ZÁKLADNÍ POJMY

Někdy je vhodné omezit se na úlohu najít pouze infimum resp. supremum funkce f na množině V. Takovou úlohu budeme zapisovat ve tvaru: inf {f (x) | x ∈ V } ,

resp.

sup {f (x) | x ∈ V } .

b , f (x b )) v závislosti na konkrétní formulaci Řešením této úlohy je číslo fb nebo dvojice (x b , f (x b ))) řekneme, že úloha je řešitelná. úlohy. Existuje-li řešení úlohy (tj. číslo fb nebo dvojice (x

Například úloha

sup {arctan x | x ∈ R1 } je řešitelná (fb =

kdežto úloha

π ). 2

max {arctan x | x ∈ R1 } řešitelná není

b ∈ R1 , pro které f (x b ) = π2 . neboť neexistuje x b ∈ V , pro který je Bod x

b ) = min f (x) , fb = f (x

(C)

x∈V

b ) = max f (x) , resp. fb = f (x x∈V

se nazývá bod globálního minima (resp. bod globálního maxima) funkce f na množině V . Také jej označujeme jako globální minimizátor (resp. globální maximizátor) funkce f na množině V a označujeme jej: argmin f (x) , resp. argmax f (x) . x∈V

x∈V

Symbolem argmin f (x) x∈V

se v literatuře označuje množina všech (globálních) minimizátorů funkce f na množině V . Analogický význam má symbol argmax f (x) x∈V

V dalším textu se soustředíme na úlohy minimalizace, neboť vzhledem ke vztahu max f (x) = − min(−f (x)) x∈V

x∈V

můžeme úlohu maximalizace převést na úlohu minimalizace pro funkci (−f ). Množina V se nazývá přípustná množina nebo množina přípustných bodů (prvků), neboť každý její bod (prvek) se nazývá přípustný bod (prvek). Funkce f se v optimalizačních úlohách nazývá účelová (cílová, kriteriální ) funkce. Předpokládá se její spojitost, v obecnějších případech polospojitost (zdola, shora). Je-li V ≡ X , pak se optimalizační úloha nazývá úlohou bez omezení. Hovoříme také o nepodmíněné optimalizaci nebo o optimalizaci bez vazeb. Je-li V ⊂ X určena souborem podmínek typu rovnosti či nerovnosti, hovoříme o optimalizaci s vazbami. Je-li X ≡ Rn , hovoříme o konečnědimenzionální optimalizaci.

Je-li množina V konečná, hovoříme o kombinatorické optimalizaci, je-li V množina aritmetických vektorů, jejichž složky jsou celá čísla, hovoříme o celočíselné nebo diskrétní optimalizaci. Obecně množina X může být Banachův prostor s normou k · k, případně ještě obecněji lokálně kompaktní Hausdorffův topologický prostor.

2. OPTIMALIZAČNÍ ÚLOHY A JEJICH ŘEŠITELNOST

33

b ∈ V se nazývá bod lokálního minima (lokální minimizátor) funkce f na množině Bod x b ) bodu x b , že platí V , existuje-li takové okolí U(x

(D)

b ) ≤ f (x) , ∀x ∈ V ∩ U(x b) ; V ⊂ X . f (x

b ∈ V se nazývá bod lokálního maxima (lokální maximizátor) funkce f na množině Bod x b ) bodu x b , že platí V , existuje-li takové okolí U(x

(E)

b ) ≥ f (x) , ∀x ∈ V ∩ U(x b) ; V ⊂ X . f (x

b ostrá nerovnost, potom x b je ostrý Jestliže v nerovnosti (C), resp. (D), je pro x 6= x minimizátor (globální, resp. lokální ). Analogicky, požadujeme-li ostré nerovnosti v (C), (E) b 6= x b , je x b ostrý maximizátor (globální, resp. lokální ). pro x

V dalších kapitolách budeme vyšetřovat podmínky (nutné nebo postačující) řešitelnosti, případně jednoznačné řešitelnosti, formulované optimalizační úlohy. Také budeme popisovat metody řešení optimalizačních úloh. Pro teoretické úvahy někdy potřebujeme smysl definovaných pojmů rozšířit pro případ, že V je prázdná množina ∅ . Potom klademe inf f (x) = +∞ ; sup f (x) = −∞ .

x∈∅

x∈∅

2.2. Řešitelnost 2.2.1. Weierstrassova věta Nechť X je kompaktní množina v Rn a funkce f je spojitá na X . Potom existuje bod b ∈ X takový, že: x b ) = min f (x) tj. existuje globální minimum f (x x∈X

b b b) = b ∈ X takový, že f (x To znamená, že úloha minimalizace je řešitelná. Analogicky existuje x max f (x). x∈X

Důkaz

Pro n = 1; skripta [3], odst. 5.2. Pro n > 1 je důkaz analogický.

2.2.2. Věta Nechť X je uzavřená množina v Rn a funkce f je spojitá na X . Když pro některé x ∈ X b ∈ X takovým, je množina x ∈ X : f (x) ≤ f (x) neprázdná a omezená, potom existuje bod x b ) = min f (x). že f (x x∈X

Důkaz

Plyne z předcházející věty.

34

2.3. SEDLOVÝ BOD, POJEM DUALITY

2.2.3. Věta Věta Nechť X je Banachův prostor a f : X → R1 je zdola polospojitá na X . Potom funkce f (obecně funkcionál) dosahuje minima na každé (sekvenciálně) kompaktní podmnožině prostoru X . Viz ([5]).

2.3. Sedlový bod, pojem duality 2.3.1. Úlohy minima a maxima Nechť Rn , Y ⊂ Rm jsou dané množiny (např. také X ≡ Rn , Y ≡ Rm ) a nechť F : X ×Y → R1 je spojitá na X × Y funkce (n + m) proměnných; F (x, y) = F (x1 , x2 , . . . , xn , y1 , y2 , . . . , ym )). Označme

   x∈X    max ϕ(y) = max min F (x, y).   Předpokládáme existenci y∈Y y∈Y x∈X  všech minim a maxim, o max F (x, y) , ∀x ∈ X ;   y∈Y   kterých je řeč.  min f (x) = min max F (x, y). 

ϕ(y) = min F (x, y) , ∀y ∈ Y ; β =

f (x) = α =

x∈X

x∈X y∈Y

Předpokládejme, že úlohy najít (stanovit) α, β, f (x), ϕ(y) jsou řešitelné (o jednoznačnosti b b b , takové, že b, y b, y b, x nehovoříme), tj. existují body (nemusí být jediné) x (F)

b ) = min f (x) = max F (x b , y) = F (x b, y b ), α = f (x

(G)

b b b b b ) = max ϕ(y) = min F (x, y b ) = F (x b, y b ). β = ϕ(y

x∈X

y∈Y

y∈Y

x∈X

2.3.2. Slabý vztah duality

Nechť úlohy z odst. (2.3.1.) jsou řešitelné a f (x), ϕ(y), α, β jsou příslušná řešení. Potom platí (H) (I)

min F (x, y) ≤ max F (x, y) , x∈X

y∈Y

tj.

ϕ(y) ≤ f (x) ; ∀x ∈ X , ∀y ∈ Y ,

a tedy (J)

max ϕ(y) ≤ min f (x) , y∈Y

resp. (K)

x∈X

b b ) ≤ f (x b ). tj. ϕ(y

max min F (x, y) ≤ min max F (x, y). y∈Y x∈X

Vztahu (K) se říká slabý vztah duality.

x∈X y∈Y

2. OPTIMALIZAČNÍ ÚLOHY A JEJICH ŘEŠITELNOST Důkaz

35

Pro každé pevné x ∈ X platí nerovnost F (x, y) ≤ max F (x, y) y∈Y

a pro každé pevné y ∈ Y platí

min F (x, y) ≤ F (x, y) , x∈X

tj. min F (x, y) ≤ F (x, y) ≤ max F (x, y) , x∈X

y∈Y

a tedy ϕ(y) ≤ f (x) , ∀x ∈ X , ∀y ∈ Y . Odkud pak vidíme, že spojitá funkce f je omezená zdola libovolnou hodnotou ϕ(y) a spojitá funkce ϕ je omezená shora libovolnou hodnotou funkce f (x). Takže max ϕ(y) ≤ min f (x) . y∈Y

x∈X

Poznámka. Pokud úlohy formulujeme obecněji, tj. jako inf sup F (x, y), sup inf F (x, y) ,

x∈A y∈B

y∈B x∈A

b b b, y b, x b, y b pak lemma 2.3.2. zůstává v platnosti, pouze v důkazu nemůžeme zmiňovat body x b b b ), ϕ(y b ) pak bereme pouze f , ϕ. b (nemusí existovat) a místo f (x

2.3.3. Lemma

Nechť funkce F (x, y) je spojitá na kartézském součinu A × B kompaktních množin A ⊂ X , B ⊂ Y . Potom úlohy maximinu a minimaxu jsou řešitelné a platí slabý vztah duality (2.3.4.). Důkaz Oproti lemmatu (2.3.2.), zde předpokládáme platnost postačující podmínky existence řešení (spojitost F a kompaktnost A, B). Tvrzení pak už plyne (je důsledkem) z předchozího lemmatu a Weierstrasovy věty. Poznámka. Lemmata (2.3.2.), (2.3.3.) lze formulovat i pro Banachovy prostory X , Y . Musí se však obecněji definovat jednotlivé pojmy: spojitost, kompaktnost, uzavřenost, omezenost.

2.3.4. Definice Nechť F : X × Y → R1 je spojitá, X ∈ Rn , Y ∈ Rn . Bod (x, y) ∈ X × Y je (globální) sedlový bod funkce F na X × Y , platí-li (L)

F (x, y) ≤ F (x, y) ≤ F (x, y) , ∀x ∈ X , ∀y ∈ Y .

resp. (M)

F (x, y) ≥ F (x, y) ≥ F (x, y) , ∀x ∈ X , ∀y ∈ Y .

Platí-li uvedené nerovnosti pouze v okolí bodu (x, y), pak tento bod je lokálním sedlovým bodem.

36

2.3. SEDLOVÝ BOD, POJEM DUALITY

2.3.5. Příklad 1 Mějme funkci F (x, y) = x2 − y 2 , x ∈ h−1, 1i , y ∈ h−1, 1i Bod (0, 0) splňuje podmínky (nerovnosti) (L) F (0, y) ≤ F (0, 0) ≤ F (x, 0) tj. −y 2 ≤ 0 ≤ x2 ; ∀x ∈ h−1, 1i , ∀y ∈ h−1, 1i. Je tedy (globálním) vnitřním sedlovým bodem funkce F na daném uzavřeném čtverci. Je patrné, že bod (0, 0) je sedlovým bodem funkce F uvažované na celé množině R1 × R1 .

2.3.6. Příklad 2 Mějme funkci F (x, y) = x2 + y 2 , x ∈ R1 , y ∈ R1 Protože F (0, y) = y 2 , F (0, 0) = 0 , F (x, 0) = x2 a nerovnosti typu (L) y 2 ≤ 0 ≤ x2 , resp. y 2 ≥ 0 ≥ x2 platí pouze pro y = 0 (nikoliv pro všechna y ∈ R1 ), ∀x ∈ R1 , resp. x = 0 , ∀y ∈ R1 , není bod (0, 0) sedlovým bodem na R1 × R1 .

V dalším ukázkovém příkladu dáme odpověď na otázku, zda úloha na sedlový bod pro danou funkci F může být (resp. je) řešitelná na nějaké podmnožině A × B ⊂ R1 × R1 .

2.3.7. Příklad 3 Mějme funkci F (x, y) = x2 + y 2 , x ∈ h0, 1i , y ∈ h0, 1i. Všimneme si, že definiční obor je ve srovnání s příkladem (2.3.6.) výrazně odlišný. Lze proto konstatovat, že funkce F splňuje pro bod (0, 1) podmínky F (0, y) ≤ F (0, 1) ≤ F (x, 1) tj. y 2 ≤ 1 ≤ x2 + 1 , ∀x ∈ h0, 1i , ∀y ∈ h0, 1i. Bod (0, 1) je tedy sedlovým bodem dané funkce na množině h0, 1i × h0, 1i. Všimneme si, že bod (0, 1) je bodem maxima, bod (1, 1) je bodem maxima, bod (1, 0) je sedlovým bodem ve smyslu (M), tj. platí 1 + y 2 ≥ 1 ≥ x2 . K této úloze se ještě vrátíme v odst. (2.4.1.).


37

2.3.8. Poznámka Pomocí podmínky (L) můžeme ověřit, zda vybraný bod je či není sedlovým bodem. Nedává nám však (zatím) návod, jak sedlový bod najít. Ukážeme si, že vhodným nástrojem b b, y= b=x jsou úlohy minimaxu a maximinu. Z odst. (2.3.1.) bezprostředně plyne pro x = x b b , že b=y y b , y) ≤ F (x b, y b ) = min max F (x, y) = F (x, y) = α F (x x∈X y∈Y

b b b b, y b ) ≤ F (x, y b ) = β. F (x, y) = max min F (x, y) = F (x y∈Y x∈X

2.3.9. Nutná a postačující podmínka sedlovosti

Nechť F : X × Y → R1 , Rn , Y ⊂ Rm a nechť úlohy minimaxu a maximinu jsou řešitelné. Bod (x, y) ∈ X × Y je (globální) sedlový bod funkce F právě tehdy, když platí (N)

max min F (x, y) = F (x, y) = min max F (x, y). y

x

x∈X y∈Y

Vztahu (N) říkáme silný vztah duality . Důkaz 1. Nechť (x, y) ∈ X × Y je sedlový bod funkce F typu (L), tj. platí F (x, y) ≤ F (x, y) ≤ F (x, y) ; ∀x ∈ X , ∀y ∈ Y . Odtud pak plynou implikace F (x, y) ≤ F (x, y) ⇒ f (x) = max F (x, y) ≤ F (x, y), y∈Y

F (x, y) ≤ F (x, y) ⇒ F (x, y) ≤ min F (x, y) = ϕ(y). x∈X

Samozřejmě platí min f (x) ≤ f (x), x∈X

ϕ(y) ≤ max ϕ(y). y∈Y

Spojením uvedených nerovností dostaneme min x∈X

f (x) | {z }

≤ f (x) ≤ F (x, y) ≤ ϕ(y) ≤ max y∈Y

max F (x, y) y∈Y

ϕ(y)

| {z }

,

min F (x, y) x∈X

takže min max F (x, y) ≤ F (x, y) ≤ max min F (x, y). x∈X y∈Y

y∈Y x∈X

ze slabého vztahu duality (K) (který platí vždy za předpokladu řešitelnosti uvažovaných úloh) dostaneme max min F (x, y) ≤ min max F (x, y) y∈Y x∈X

dostáváme pak rovnost (N).

x∈X y∈Y

38

2.3. SEDLOVÝ BOD, POJEM DUALITY 2. Nyní dokážeme, že ze silného vztahu duality (N) plyne podmínka sedlovosti (L). Nechť v nějakém bodě (x, y) ∈ X × Y platí (O)

max min F (x, y) = F (x, y) = min max F (x, y). y∈Y x∈X

x∈X y∈Y

Potom (chceme dokázat) (P)

F (x, y) ≤ F (x, y) ≤ F (x, y) ; ∀x ∈ X , ∀y ∈ Y .

Vztah (N) lze upravit na tvar F (x, y) = max [min F (x, y)] = min F (x, y), y

y. . . bod maxima funkce ϕ ϕ(y) = F (x, y). . . hodnota maxima

x

|

{z

ϕ(y)

|

}

x

{z

ϕ(y)

}

Poznámka: Maximalizujeme funkci ϕ(y) = min F (x, y) = F (x, y). x

a také F (x, y) = min [max F (x, y)] = max F (x, y), x

x. . . bod minima funkce f f (x) = F (x, y). . . hodnota minima

|

y

{z

f (x)

}

|

y

{z

f (x)

}

Poznámka: Minimalizujeme funkci f (x) = max F (x, y) = F (x, y). Takže spojime-li obě rovnosti

y

max F (x, y) = F (x, y) = min F (x, y) Klíčova rovnost – y x ekvivalentní s (P). a dostaneme F (x, y) ≤ max F (x, y) = F (x, y) = min F (x, y) ≤ F (x, y). y

x

2.3.10. Sedlové body a teorie her Předpokládáme „hru“ dvou stejně inteligentních hráčů: X . . . množina strategií hráče H1 Y . . . množina strategií hráče H2 F (x, y) . . . zisk (cena, výhra) hráče H1 G(x, y) . . . zisk (cena, výhra) hráče H2 Když F (x, y) < 0, pak hráč H1 má ztrátu (záporný zisk) Když G(x, y) < 0, pak hráč H2 má ztrátu (záporný zisk)


39

Každé x ∈ X je nějaké rozhodnutí hráče H1 Každé y ∈ Y je nějaké rozhodnutí hráče H2 Z pohledu hráče H1 : min F (x, y) : . . . hráč H2 volí takovou strategii yb, aby minimalizoval y∈Y

b ∈ X , aby maximalizoval svojí minimální zisk hráče H1 ⇒ hráč H1 musí volit takovou strategii x výhru (zisk). H1 řeší tedy tuto úlohu

v1 = max min F (x, y) x∈X y∈Y

Z pohledu hráče H2 : . . . analogické úvahy v2 = max min G(x, y) y∈Y x∈X

Nejjednodušší hra: hra dvou hráčů s nulovým součtem: F (x, y) + G(x, y) = 0 , ∀(x, y) ∈ X × Y Hrou rozumíme trojici {X , Y , F (x, y)}

b, yb), kde x b je optiŘešením hry která je sedlovým bodem funkce F (x, y) je dvojice (x mální strategie H1 a yb je optimální strategie H2 .

2.3.11. Princip dualizace

Dualizací optimalizační úlohy min{f (x) | x ∈ X } rozumíme přiřazení (nalezení) funkce F (x, y) , x ∈ X , y ∈ Y (určení Y ) k funkci f (x) vztahem f (x) = max F (x, y) y∈Y

a stanovení funkce ϕ(y) = min F (x, y) x∈X

b ) = ϕ(y b ) = F (x b, y b ). tak, že f (x

Existuje-li taková funkce F (x, y), potom 

b ) = min f (x) = min max F (x, y) = F (x b, y b)  f (x x∈X

x∈X y∈Y

b ) = max ϕ(y) = max min F (x, y) = F (x b, y b)  ϕ(y y∈Y

y∈Y x∈X

b ,y b ) je sedlový bod (x nemusí být jediný!!

b ) ≤ f (x b ) ≤ f (x). Silný vztah duality píšeme ve Slabý vztah duality píšeme ve tvaru ϕ(y) ≤ ϕ(y b b tvaru ϕ(y) = f (x).

Poznámka: V některých speciálních případech (viz později) popíšeme konstrukci F (x, y) a stanovíme jiné podmínky existence sedlového bodu.

2.4. Příklady a cvičení 2.4.1. Řešený příklad 1 Mějme funkci F (x, y) = x2 + y 2 , x ∈ h0, 1i , y ∈ h0, 1i.

40

2.4. PŘÍKLADY A CVIČENÍ

Posuďme řešitelnost úlohy sedlového bodu, tj. řešitelnost úloh max min F (x, y) , min max F (x, y). y∈Y x∈X

x∈X y∈Y

Označíme-li f (x) = max F (x, y) = max (x2 + y 2 ) = x2 + 1 = F (x, 1) ; y

y∈h0,1i

ϕ(y) = min F (x, y) = min (x2 + y 2 ) = y 2 = F (0, y) . x

x∈h0,1i

Pak α = min max F (x, y) = min (x2 + 1) = 1 = F (0, 1) = f (0) , x

y

x∈h0,1i

β = max min F (x, y) = max y 2 = 1 = F (0, 1) = ϕ(1) . y

x

y∈h0,1i

A je patrné, že F (0, y) ≤ F (0, 1) ≤ F (x, 1) , (x, y) = (0, 1) je sedlový bod y2 ≤ 1 ≤ x2 + 1 , ∀x ∈ h0, 1i , ∀y ∈ h0, 1i Viz odst. (2.3.7.). Úloha sedlového bodu je řešitelná. Situace je patrná z obr. (2.4.1).

x2 + 1 = z maxy F (x, y) = = f (x) 1

0

y2 + 1

[1, 0] x 1

0

[0, 1] y

x2 [1, 1]

1

y 2 = maxx F (x, y) = ϕ(y) Obrázek 2.4.1: sedlový bod

2.4.2. Řešený příklad 2 Mějme funkci F (x, y) = x2 − y 2 , x ∈ h−1, 1i , y ∈ h−1, 1i . Posuďme řešitelnost úloh max min F (x, y) ; min max F (x, y) . y

x

x

y


41

Podle definice stanovíme f (x) =

max (x2 − y 2 ) = x2 = F (x, 0) ,

y∈h−1,1i

α = min max(x2 − y 2 ) = min f (x) = min x2 = 0 = F (0, 0) , x

ϕ(y) =

y

x

x∈h−1,1i

2

2

2

min (x − y ) = −y = F (0, y) ,

x∈h−1,1i

β = max min(x2 − y 2 ) = max ϕ(y) = max(−y 2 ) = 0 = F (0, 0) . y

x

y

y∈h−1,1i

Obě úlohy jsou řešitelné a platí α = β, tedy úloha sedlového bodu je řešitelná a (0, 0) je sedlový bod, jak bylo ukázáno v odst. (2.3.5.).

2.4.3. Řešený příklad 3 Mějme funkci F (x, y) = (x − y)2 ≡ (y − x)2 ; x ∈ h0, 1i , y ∈ h0, 1i . Posuďme řešitelnost úloh max min F (x, y) ; min max F (x, y) . y

x

x

y

Znázorníme si grafy funkcí F (x, y) = (x − y)2 pro jednotlivé volby y ∈ h0, 1i, např: F (x, 0) 1 F (x, ) 4 1 F (x, ) 2 3 F (x, ) 4 F (x, 1) Pro 0 ≤ x ≤

pro

1 2

1 2

je max(x − y)2 = (x − 1)2 , y

≤ x ≤ 1 je max(x − y)2 = x2 , tj. y

f (x) =

Potom zřejmě

Takže

= (x − 0)2 ; 1 = (x − )2 ; 4 1 2 = (x − ) ; 2 3 2 = (x − ) ; 4 = (x − 1)2 .

   (x − 1)2   x2

1 ,0 ≤ x ≤ , 2 1 , ≤x≤1. 2  1   F ( , 0) ,

1 1 2 f ( ) = min f (x) = = 1 2 4  x∈h0,1i  F ( , 1) . 2 min max(x − y)2 = x

y

1 . 4

42


y y=0

1

0.5

0 0

0.5

y=

1 4

y=

1 2

y=

3 4

x

1

Obrázek 2.4.2: graf funkce pro volbu hodnoty y Znázorníme si nyní na obr. (2.4.2) grafy funkci F (x, y) = (x−y)2 pro jednotlivé volby x ∈ h0, 1i, např. F (0, y) 1 F ( , y) 4 1 F ( , y) 2 3 F ( , y) 4 F (1, y)

= (0 − y)2 ; 1 = ( − y)2 ; 4 1 = ( − y)2 ; 2 3 = ( − y)2 ; 4 = (1 − y)2 .

y 1

x=0

0.5

0 0

0.5

1

x=

1 4

x=

1 2

x=

3 4

x

Obrázek 2.4.3: graf funkce pro volbu hodnoty x Na obrázku (2.4.3) jsou formálně stejné paraboly jako na předchozím obrázku (2.4.2),


43

zde jsou to funkce proměnné y ∈ h0, 1i. Protože def

ϕ(y) = min (x − y)2 = 0 , x∈h0,1i

tj. max min(x − y)2 = 0 , y

x

b b b b b. b=y b ), v němž x b, y (nabývá v libovolném bodě (x

Tedy

0 = max min(x − y)2 < min max(x − y)2 = y

x

x

y

1 . 4

Závěr: Úlohy minimaxu a maximinu jsou řešitelné, ale úloha sedlového bodu řešitelná není ! z

y 1

1

f (0, 1) = 1

f=

1 4

f =0

0.5

0 0

f= 0

0

0.5

1

x

1 4

f (1, 0) = 1 x 1

Obrázek 2.4.4: reliéf funkce F (x, y) = (x − y)2 .

y

1

Obrázek 2.4.5: graf funkce F (x, y) = (x − y)2 .

Poznámka: Metodami diferenciálního počtu posuďte řešitelnost úloh na extrém pro danou funkci. Viz také odst. (1.7) těchto skript.

2.4.4. Řešený příklad 4 Mějme funkci F (x, y) = 1 − x + y , x ∈ h0, 1i , y ∈ h0, 1i . Posuďme řešitelnost úloh max min F (x, y) ; min max F (x, y) . y

x

x

y

44


Protože F (x, y) je lineární v obou proměnných, budou naše úvahy podstatně jednodušší. f (x) = min f (x) =

x∈h0,1i

ϕ(y) = max ϕ(y) =

y∈h0,1i

max (1 − x + y) = 2 − x = F (x, 1) ,

y∈h0,1i

min (2 − x) = 1 = f (1) = F (1, 1) = min max F .

x∈h0,1i

min (1 − x + y) = y = F (1, y) ,

x∈h0,1i

max (y) = 1 = F (1, 1) = max min F .

y∈h0,1i

Obě úlohy jsou řešitelné a navíc platí rovnost (silná podmínka duality). Také úloha na sedlový bod je řešitelná a bod (1, 1) je sedlový bod a tedy platí F (1, y) ≤ F (1, 1) ≤ F (x, 1) tj. y ≤ 1 ≤ 2 − x , x ∈ h0, 1i , y ∈ h0, 1i . z

y 1

1 f=

3 2

F1 (x)

f =1

0.5

0

f= 0

0

1 2

1

x

F2 (y)

0

0.5

x

1

y

Obrázek 2.4.6: Sedlový bod (1, 1) funkce F (x, y) = 1 − x + y

1

Obrázek 2.4.7: Sedlový bod (1, 1) funkce F (x, y) = 1 − x + y

max F2 (y) ≤ min F1 (x) (dokonce platí rovnost) y

x

2.4.5. Řešený příklad 5 Je dána diskrétní funkce F (i, j) maticí aij = F (i, j), kde (aij ) =

"

5 1 3 7

#

.

Posuďme opět úlohy min max Fij ; max min Fij ; i

j

[1, 1]

j

i


45

a úlohu sedlového bodu. Máme: f (i) = max F (i, j) : f (1) = max F (1, j) = max{5, 1} = 5 , j

j

f (2) = max F (2, j) = max{3, 7} = 7 . j

ϕ(j) = min F (i, j) : ϕ(1) = min F (i, 1) = min{5.3} = 3 , i

i

ϕ(2) = min F (i, 2) = min{1, 7} = 1 . i

Takže max min F (i, j) = max ϕ(j) = max{3, 1} = 3 , j

i

j

min max F (i, j) = min f (i) = min{5, 7} = 5 . i

j

i

Nutná a postačující podmínka sedlovosti splněná není ! Uvedená úloha se nazývá maticová hra . Stručně "

#

max

5 1 −→ 5 max 3 7 −→ 7 ↓ ↓ min 3 | {z 1} max

−→ 3

)

min

−→ 5

→ 3 6= 5

Obrázek 2.4.8: maticová hra 1

2.4.6. Řešený příklad 6 Pro diskretní funkci F (i, j) = aij , pro jinou matici, stručné schéma vypadá takto: "

#

max

3 1 −→ 3 max 5 7 −→ 7 ↓ ↓ min 3 | {z 1} max

−→ 3

)

min

−→ 5

→ 3=3

Obrázek 2.4.9: maticová hra 2

2.4.7. Cvičení 1 Pro funkci F (x, y) = x2 −y 2 +4x−2y +1 , x ∈ R1 ; y ∈ R1 řešte úlohy max min F (x, y) , min max F (x, y)

a rozhodněte o existenci sedlového bodu.

y

x

x

[Návod: min F (x, y) = −y 2 −2y −3 ; max F (x, y) = x2 +4x+2 ; (−2, −1) je sedlový bod;max min F (x, y) = x

y

F (−2, −1) = min max F (x, y) .] x

y

y

x

y

46


2.4.8. Cvičení 2 Nechť F : X × Y → R1 , X ⊂ Rn , Y ⊂ Rm . Potom platí max min F (x, y) ≤ min max F (x, y) . y∈Y x∈X

x∈X y∈Y

Dokažte.

[Návod: Pro každé pevné y ∈ Y platí nerovnost min F (x, y) ≤ F (x, y) ; pro každé pevné x ∈ X platí x∈X

nerovnost F (x, y) ≤ max F (x, y). Tudíž pro každé x ∈ X , y ∈ Y platí, že min F (x, y) ≤ y∈Y

x∈X

max F (x, y).] y∈Y

2.4.9. Cvičení 3 Nechť F : X × Y → R1 , X ⊂ Rn , Y ⊂ Rm . Potom platí b, y b ) = min max F (x, y) právě tehdy, když (x b, y b ) je sedlový bod funkce max min F (x, y) = F (x y∈Y x∈X

x∈X y∈Y

F. Dokažte.

[ Návod: b, y b ) je sedlový bod, potom max F (x b , y) ≤ F (x b, y b ) ≤ min ∈ XF (x, y b ) , min max F (x, y) ≤ Když (x y∈Y

x

x∈X y∈Y

b , y) ; min F (x, y b) ≤ max F (x y∈Y

x∈X

≤ max min F(x, y) ; užijte cvičení (2.4.8.); když platí max min = min max , pak využitím uvey∈Y x∈X

dených nerovností dostaneme (F).]

2.4.10. Cvičení 4 Sedlový bod funkce F definovaný v odst. (2.3.1.) se nazývá sedlový bod typu minimaxu. Platí-li pro funkci G : ; X × Y → R1 nerovnosti b , y) ≥ G(x b, y b ) ≥ G(x, y b ) , ∀x ∈ X , ∀y ∈ Y , G(x

b, y b ) ∈ X × Y je sedlový bod typu maximinu. Posuďte platnost poznatků z předchozích pak (x odstavců i pro sedlový bod typu maximinu.

Kapitola 3

Hladká optimalizace V úvodu (kap.1, odst.1.4.1.) jsme uvedli, že v roce 1615 řeší J.Kepler optimalizační úlohu vinných sudů a buduje si k tomuto účelu novou metodu. Dnes tuto metodu nazýváme diferenciální počet. Johanes Bernoulli, Isaac Newton, Leibnitz a další tuto metodu dále rozvíjeli a používali ji k řešení složitějších úloh. Obecnější verze této metody se nazývá variační počet. Nebude jistě na škodu si připomenout souhrn poznatků, nazývané „diferenciální minimum“.

3.1. Spojitost v hromadném bodě Okolí hromadného bodu budeme označovat b = {t ∈ R1 : |t − t| b < δ} , Uδ (t)

b ) = {x ∈ Rn : kx − x b k < δ} . Uδ (x

3.1.1. Spojitost funkcí jedné proměnné Mějme funkci g : Uδ → R1 ,

Uδ = Uδ (tb) ⊂ R1 .

Vlastnost lim g(t) = g(tb) , tj. „spojitost v bodě“ definujeme ekvivalentními výroky: t→b t

b t → t, b n → +∞ , posloupnost funkčních hodnot {g(tn )} konverguje V1 : ∀{tn } ⊂ Uδ (t), b , tj. g(tn ) → g(t), b n → +∞ . k číslu g(t) b b − ǫ < g(t) < g(t) b +ǫ . V2 : ∀ǫ > 0 , ∃δ(ǫ) > 0 , (t − δ) < t < (tb+ δ) ⇒ g(t)

3.1.2. Jednostranná spojitost b ∈ R1 . Mějme funkci g : Uδ → R1 , Uδ = Uδ (t)

b = g(t) b , „spojitost zprava“ definujeme ekvivalentními výroky: Vlastnost lim g(t) = g(t+) t→b t+

47

3.2. HLADKOST V R1

48

b , tn > tb, t → tb, n → +∞ ; posloupnost funkčních hodnot {g(tn )} V1+ : ∀{tn } ⊂ Uδ (t) b „zprava“, tj. g(tn ) → g(t) b , n → +∞ . konverguje k číslu g(t) + b − ǫ) < g(t) < (g(t) b + ǫ) . V2 : ∀ǫ > 0 ∃δ(ǫ) > 0, takové, že 0 < t < (tb+ δ) ⇒ (g(t)

b = g(t) b , „spojitost zleva“ definujeme ekvivalentními výroky: Vlastnost lim g(t) = g(t−) t→b t− − b , tn < tb, V1 : ∀{tn } ⊂ Uδ (t)

V2− Důkaz

t → tb, n → +∞ , posloupnost funkčních hodnot {g(tn )} , b b , n → +∞ . konverguje k číslu g(t) „zleva“, tj. g(tn ) → g(t) b b b − ǫ) < g(t) < (g(t) b + ǫ) . : ∀ǫ > 0 ∃δ(ǫ) > 0 , takové, že (t − δ) < t < t ⇒ g(t)

Lze najít v každé podrobnější učebnici matematické analýzy

3.1.3. Polospojitost zdola b ∈ R1 . Mějme funkci g : Uδ → R1 , Uδ = Uδ (t)

b , „polospojitost zdola“ definujeme ekvivalentními výroky: Vlastnost lim inf g(t) ≥ g(t)

Důkaz

b , tn → tb , tn 6= tb , n → +∞ , platí lim inf g(tn ) ≥ g(t) b . W1 : ∀{tn } ⊂ Uδ (t) b b b W2 : ∀ǫ > 0 ∃ δ(ǫ) > 0 , takové, že (t − δ) < t < (t + δ) ⇒ g(t) − ǫ < g(t) .

Nelze už najít v každé učebnici matematické analýzy

3.1.4. Obecná věta o existenci minima Nechť I ⊂ R1 je uzavřený interval. Je-li g : I → R1 zdola polospojitá na I , potom existuje bod tb ∈ I takový, že: b = min g(t) g(t) t∈I

Důkaz

Viz ??

3.2. Hladkost v R1 3.2.1. Diferencovatelnost v R1 Funkce g : Uδ → R1 diferencovatelná v t ∈ Uδ má tuto vlastnost:

Existuje lineární funkce a ∆t v proměnné ∆t = t − t taková, že platí: g(t) − g(t) = a∆t + ω(∆t) , t ∈ Uδ kde pro nelineární (zbytkovou) funkci ω(∆t) platí lim

∆t→0

ω(∆t) =0. ∆t

Pak lineární funkce dg(t, ∆t) = a∆t se nazývá diferenciál funkce g v bodě t a číslo a = g ′ (t) = lim

∆t→0

g(t) − g(t) ∆t

3. HLADKÁ OPTIMALIZACE

49

se nazývá derivace v bodě funkce g v bodě t. Je-li funkce ψ : Uδ → R1 , ψ(t) = g ′ (t)

diferencovatelná, potom říkáme, že funkce g je dvakrát diferencovatelná a její diferenciál dψ(t, ∆t) nazýváme druhým diferenciálem funkce g , tj. platí dψ(t, ∆t) = d2 g(t, ∆t) ψ ′ (t) = g ′′ (t) Funkce, u nichž existují vyšší derivace a diferenciály se nazývají hladké.

3.2.2. Principy podmínek hladké a nehladké optimalizace Nutnými podmínkami eistence minima rozumíme takové podmínky, které jsou důsledkem existence minima. Postačujícími podmínkami existence minima rozumíme takové podmínky, které zaručují existenci minima. Například, nechť spojitá funkce jedné proměnné g : Uδ → R1 má v bodě tb ∈ Uδ ⊂ R1 lokální minimum, tj. platí Pak nutně platí nerovnosti

b ≤ g(t) , t ∈ (tb− δ , tb+ δ) g(t)

b g(t) − g(t) ≥ 0 , t − tb > 0 , t ∈ (tb , tb+ δ) . t − tb

b g(t) − g(t) ≤ 0 , t − tb < 0 , t ∈ (tb , tb+ δ) . t − tb Jestliže limity uvedených podílů existují, pak máme nutné podmínky ve tvaru b ≥ 0 , g ′ (t−) b ≤0. g ′ (t+)

Jedná se o elementární příklad nutných podmínek nehladké optimalizace. Jsou-li si uvedené limity rovny, pak máme nutnou podmínku ve tvaru b =0 g ′ (t)

Což je elementární případ nutné podmínky minima hladké optimalizace.

3.3. Hladkost v Rn Mějme funkci f : X → R1 , X ⊂ Rn , kde Rn je Eukleidovský prostor s normou k · k , Uδ (x) ⊂ X je okolí bodu x.

50

3.3. HLADKOST V RN

3.3.1. Derivace ve směru, Gâteauxův diferenciál Mějme x ∈ Uδ , x + td ∈ Uδ , d ∈ X , kdk = 1 , t ∈ R1 .

Limita (číslo, pokud existuje)

f (x + td) − f (x) d = f (x + td) t=0 t→0 t dt

(A)

δf (x, d) = lim

se nazývá derivace funkce f v bodě x ve směru d. Je-li d = ei i-tý fázový vektor v Rn , pak ∂f (x) δf (xi , ei ) = ∂xi def

se nazývá

(

− derivace ve směru ei − parciální derivace podle xi

Je-li funkce (v proměnné h) δf : h → δf (x, h) která každému h ∈ X ⊂ Rn přiřazuje číslo δf (x, h) lineární a spojitá, nazývá se tato funkce Gâteauxův první diferenciál. Lineární funkce v Rn se dá zapsat ve tvaru skalárního součinu δf (x, h) = aT h = hT a .

(B) Vektor

a = grad f (x) = f ′ (x) se nazývá derivace, nebo gradient funkce f v bodě x. Když h =

n P

hi ei , pak

i=1

δf (x,

n X

hi ei ) =

i=1

n X

hi δf (xi , ei ) =

i=1

n X ∂f (x) i=1

∂xi

hi

3.3.2. Druhá derivace ve směru Pro pevné d1 je δf (x; d1 ) = ψ(x) funkcí proměnné x ∈ Uδ ∈ X . Limita (pokud existuje) ψ(x + td2 ) − δf (x) = t δf (x + td2 , d1 ) − δf (x, d1 ) = lim = t→0 t

δψ(x, d2 ) = lim

t→0

(C)

def

= δ2 f (x, d2 , d1 )

se nazývá druhá (smíšená) derivace funkce f v bodě x ve směrech d1 , d2 . Je to bilineární forma v d1 , d2 . V Rn lze tuto bilineární formu psát ve tvaru (D)

δ2 f (x, d2 , d1 ) = d2 H(x)d1


51

kde Hessova matice H(x) =

∂ 2 f (x) ∂xi ∂xj

!

, i = 1, 2, . . . , n

je symetrická.

3.3.3. Kvadratická funkce Pro kvadratickou funkci f : Rn → R1 určenou předpisem 1 f (x) = xT Ax − bT x + γ 2 je

d f (x + td) t=0 dt δf (x, d) = dT (Ax − b), grad f (x) = Ax − b

δf (x, d) = dT grad f (x) =

δ2 f (x, d) = dT H(x) d =

3.3.4. Silná difrencovatelnost

d2 f (x + td) t=0 ; H(x) = A 2 dt

Funkce f : Uδ → R1 , Uδ ⊂ X ⊂ Rn , x ∈ Uδ je diferencovatelná (silně diferencovatelná, Fréchetovsky diferencovatelná) v bodě x , existuje-li lineární forma v Rn , ϕ(h) = DT h , h ∈ Rn , D ∈ Rn , taková, že existuje limita kf (x + h) − f (x) − DT hk = 0 , ∀h ∈ Rn . khk khk

(E)

lim

Lineární funkci proměnné h značíme

df (x, h) = DT h

(F)

a nazývá se diferenciál (silný, Fréchetův). Lze snadno ukázat, že D = grad f (x). V matematické analýze se ukazuje, že z F-diferencovatelnosti plyne spojitost funkce f (z Gdiferencovatelnosti však nikoliv). Ekvivalentní definice ∀ǫ > 0 , ∃ δ > 0 (∀ h ∈ X : khk < δ) ⇒ kf (x + h) − f (x) − DT hk

Když pro každou posloupnost {xn ∈ X } platí implikace

xn → x ⇒ df (xn , h) → df (x, h) , ∀ h ∈ X ,

říkáme, že funkce f je spojitě diferencovatelná v bodě x.

3.3.5. Druhý diferenciál Je-li funkce df (x, h) : Uδ → R1 proměnné x ∈ Uδ F-diferencovatelná ve smyslu definice (E), potom (podobně jako v odstavci 3.3.2.) kvadratická forma (v proměnné h) (G)

d2 f (x, h) = hT H(x)h

se nazývá druhý F-diferenciál. H(x) je opět Hessova matice.

52

3.4. TAYLOROVY FORMULE

3.3.6. Poznámka Je třeba náležitě zdůraznit, že pro laika nejsou žádné formální rozdíly mezi G-diferenciálem a F-diferenciálem, případně G-derivací a F-derivací viditelné. Z pohledu teorie jsou však rozdíly podstatné. Toto naznačuje i následující implikace.

F-diferencovatelnost

⇒

spojitost v bodě

⇓ G-diferencovatelnost ⇓ Existence derivace ve směru

3.4. Taylorovy formule 3.4.1. Taylorova formule 1. řádu v R1 Nechť pro funkci g : Uδ → R1 , Uδ ⊂ R1 existuje spojitá g ′ . Potom pro každé t ∈ Uδ (t) , t = t + ∆t , existuje τ = τ (t) takové, že platí g(t) − g(t) = g ′ (τ )(t − t) = dg(τ, ∆t) = = g ′ (t)(t − t) + ω(∆t) =

(H)

= dg(t, ∆t) + ω(∆t) kde

ω(∆t) =0 ∆t→0 ∆t lim

Komentář místo důkazu V uvedeném tvrzení se koncentrují základní poznatky matematické analýzy diferencovatených funkcí jedné proměnné. Jednak samotná definice z odstavce 2.2.1. a především pak věta o střední hodnotě diferenciálního počtu. Funkci ω(∆t) s vlastností lim

∆t→0

ω(∆t) ∆t

= 0 zapisujeme často symbolem

o(∆t) . Obecně symbol o(hn )) znamená, že

o(hn ) =0 h→0 hn lim


53

3.4.2. Taylorova formule 2. řádu v R1 Nechť pro funkci g : Uδ (t) → R1 , Uδ ⊂ R1 existuje spojitá g ′′ . Potom pro každé t ∈ Uδ (t) , t = t + ∆t existuje τ = τ (t) takové, že platí g(t) − g(t) = g ′ (t)∆t + g ′′ (τ )

1 2 d g(τ, ∆t) = 2 1 = dg(t, ∆t) + d2 g(t, ∆t) + O(∆t2 ) 2

(I)

Důkaz

∆t2 = 2

= dg(t, ∆t) +

Stejně jako v odstavci (3.4.1.), tak i pro uvedené předpoklady platí

g(t) − g(t) =

Zt

g ′ (ξ) dξ

t

Navíc můžeme použít následující úpravy Zt t

(

′

g (ξ) dξ =

   ξ = t − z

dξ = − dz   ht, ti → ht − t, 0i

′ ′′ g ′ = dg dz = u , u = −g = 1 = v′ , v = z

=

(

(

=

(

t−t R 0

g ′ (t − z) dz

[zg ′ (t − z)]t−t 0 +

t−t R 0

=

zg ′′ (t − z) dz

=

Rt

= (t − t)g ′ (t) + (t − ξ)g ′′ (ξ) dξ t

A nyní již stačí užít větu o střední hodnotě.

3.4.3. Taylorova formule 1.řádu v Rn Nechť pro funkci f : Uδ (x) → R1 , Uδ ⊂ Rn , existuje spojitý F-diferenciál df (x, h). Potom pro každé x ∈ Uδ (x) , x = x + h , existuje z ∈ Uδ , resp. funkce ω1 (x, h) , taková, že platí (J)

f (x + h) − f (x) = hT grad f (x) + ω1 (x, h) |ω1 (x, h)| ≤ ε1 (khk) , lim = ǫ1 (khk) = 0 ; khk khk→0

resp. existuje z ∈ Uδ takové, že (K)

f (x + h) − f (x) = df (z, h) ≡ hT grad f (z) .

54

3.5. PODMÍNKY OPTIMALITY V KLASICKÉ OPTIMALIZACI

3.4.4. Taylorova formule 2.řádu v Rn Nechť pro funkci f : Uδ (x) → R1 , Uδ ⊂ Rn , existuje spojitý druhý F-diferenciál d f (x, h). Potom pro každé x ∈ Uδ (x) existuje funkce ω2 (x, h) , taková, že platí 2

1 f (x + h) − f (x) = hT grad f (x) + hT H(x)h + ω(x, h) , 2

(L)

resp. existuje z ∈ Uδ takové, že

1 f (x + h) − f (x) = hT grad f (x) + hT H(z)h 2

(M)

|ω2 (x, h)| ≤ ε2 (khk) , lim ε2 (khk) = 0 khk2 khk→0

Podrobnější výklad tvrzení z odst. (3.4.3.) a (3.4.4.) je třeba hledat např v [4].

3.4.5. Důsledky (A) Nechť funkce f : Uδ (x) → R1 , Uδ ⊂ Rn , je G-diferencovatelná v bodě x ve směru přímky x = x + td , kdk = 1 , t ∈ R1 . Potom platí (N)

f (x + td) − f (x) = t grad f (x) +o(t) |

{z

tδf (x,d)

}

(B) Nechť funkce f : Uδ (x) → R1 , Uδ ⊂ Rn , je dvakrát G-diferencovatelná v bodě x , ve směru přímky x = x + td , kdk = 1 , t ∈ R1 . Potom platí (O)

1 f (x + td) − f (x) = t dT grad f (x) + t2 dT H(x)d + o(t2 ) 2

3.5. Podmínky optimality v klasické optimalizaci 3.5.1. Věta (Fermat) Nutná podmínka optimality b ∈ X. Nechť funkce f : X → R1 , X ⊂ Rn , je spojitě diferencovatelná ve vnitřním bodě x b bodem lokálního minima funkce f , potom platí Je-li bod x

resp. (P)

b) = 0 , grad f (x

b , h) = 0 , ∀h ∈ Rn df (x

b ) 6= 0. Zvolme takový směr h = Důkaz (Sporem) Nechť v bodě minima platí grad f (x b ) . Potom − grad f (x b ) = −k grad f (x b )k2 < 0 hT grad f (x


55

ve zvolém směru h platí b + h) < f (x b) f (x

b memůže být bodem lokálního minima. Spor s předpokladem. a tudíž bod x

Poznámka Detailní důkaz Fermatovy věty, viz 3.5.2. na straně 55

3.5.2. Věta Nutná podmínka optimality druhého řádu Nechť funkce f : X → R1 , X ⊂ Rn , je dvakrát spojitě diferencovatelná ve vnitřním b ∈ X. bodě x (Q)

b bodem lokálního minima funkce f , potom platí Je-li bod x b , h) = 0 , ∀h ∈ Rn df (x b , h) ≥ 0 , ∀h ∈ Rn d2 f (x

resp.

b) = 0 grad f (x b )h ≥ 0 , ∀h ∈ Rn hT H(x

(R) kde

"

je Hessova matice funkce f . Důkaz platí

Zvolíme

b) ∂ 2 f (x b) = H(x ∂xi ∂xj

#

)

)

, i, j = 1, 2, . . . , n

b ) = 0 (důsledek Fermatovy věty) plyne, že Z Taylorovy formule a podmínky grad f (x

1 b )h + o(khk2 ) . b + h) − f (x b ) = hT H(x f (x 2 h = td , kdk2 = 1 ,

V bodě lokálního minima platí b + td) ≥ f (x b) , f (x

pro dostatečně malé t (tj. existuje takové δ > 0, že uvedená nerovnost platí pro t ∈ (0, δ)). Musí proto platit 1 2 T b )d + o(t2 ) ≥ 0 . t d H(x 2 Kdybychom totiž připustili, že v bodě minima platí ostrá nerovnost b )d < 0 , dT H(x

pak pro dostatečně malá t bude (opět díky spojitosti g ′′ (τ ) = 1 2 T b )d + O(t2 ) < 0 . t d H(x 2

Poznámka (detailní důkaz Fermatovy věty)

Každý vnitřní bod x ∈ Uδ (x) ⊂ X můžeme vyjádřit ve tvaru b + td , x=x

d dt2

b + τ d)) f (x

56


kde t je reálné číslo a d ∈ Rn je jednotkový vektor, tj. kdk = 1. Tudíž b + td) f (x) = f (x

a podle předpokladu je (S)

b ) ≤ f (x + td) , pro | t | < δ f (x

Označíme

b + td) g(t) = f (x

a nerovnost (S) píšeme ve tvaru (T)

g(0) ≤ g(t) , ∀t : | t | < δ

Na uzavřeném intervalu h0, ti píšeme větu o střední hodnotě g(t) − g(0) = g ′ (τ ) · t , τ = Θt , 0 < Θ < 1 Předpokládáme-li, že g ′ (0) > 0 , pak ze spojitosti derivace g ′ plyne, že existuje ε > 0 takové, že g ′ (αt) > 0 , ∀α ∈ (0, 1) a ∀ t : | t | < δ Můžeme tedy najít takové t < 0 , že | t | < δ a platí

g(0) > g(t). To je však ve sporu s (T) Předpokládáme-li nyní g ′ (0) < 0 , dostaneme analogickou úvahou opět spor s (T) Takže nutně musí být d b + td) t=0 = dT grad f (x) = 0 g ′ (0) = f (x dt

3.5.3. Věta. Postačující podmínka optimality č.1

Nechť funkce f : X → R1 , X ⊂ Rn , je dvakrát spojitě diferencovatelná pro x ∈ Uδ (x) ⊂ X . (U)

b ∈ X platí Jestliže ve vnitřním bodě x

b ) = 0, grad f (x

a pro každé d ∈ Rn platí (V)

b) dT H(x)d ≥ 0 , ∀x ∈ Uδ (x

b je bod lokálního minima. potom x

Platí-li místo (V) ostrá nerovnost

(W)

b ) , x 6= x b dT H(x)d > 0 , ∀d ∈ Rn , d 6= 0 , ∀x ∈ Uδ (x

b je bodem ostrého lokálního minima potom x

b není bod lokálního minima. Potom existuje bod x ∈ Uδ (x b) Důkaz Nechť platí (U) a (V), ale x takový, že platí nerovnost b ) > f (x) f (x


57

Pro napíšeme Taylorovu formuli

Pak musí být

b + td , kdk = 1 x=x

1 b + td) = f (x b ) + tdT grad f (x b ) + t2 dT H(x b + Θtd)d f (x) = f (x 2 0<Θ<1. b + Θtd)d < 0, dT H(x

b není bod lokálního minima. což je spor! Nemůžeme proto připustit, že x

3.5.4. Věta. Postačující podmínka optimality č.2 a platí (X)

b ∈X Nechť f : X → R1 , X ⊂ Rn , je dvakrát spojitě diferencovatelná ve vnitřním bodě x b) = 0 grad f (x

b )d > 0 dT H(x

(Y)

b je bodem ostrého lokálního minima. pro každý nenulový vektor d ∈ Rn . Potom bod x

Důkaz

b ) takový, že f (x) < f (x b ). Z Taylorova rozvoje Nechť existuje bod x ∈ Uδ (x 1 b ) + (x − x b )T grad f (x b ) + (x − x b )T H(x b )(x − x b )+ f (x) = f (x 2 b k2 ω(x b, x − x b) +kx − x

b potom plyne nerovnost využijeme-li vztahu h = x − x 1 T b )h + khk2 ω(x b , h) < 0. h H(x 2

3.5.5. Metody nutných podmínek

Metodami nutných podmínek se rozumí ty metody, které se opírají o výše uvedené podmínky optimality. Pro diferencovatelnou funkci f stanovíme stacionární body, tj.všechna řešení rovnice grad f (x) = 0. Ty z nich, v nichž je Hessova matice pozitivně definitní (viz. odstavec 3.3.2.) jsou body minima. Ty z nich, v nichž je Hessova matice negativně definitní jsou body maxima funkce f . Tímto způsobem nerozhodnutelné případy vyžadují další (hlubší) analýzu. Schéma metody 1. Stanoví se stacionární body funkcef . Úskalí: Řešitelnost rovnice grad f (x) = 0 (praktická i teoretická) nemusí být vždy jednoduchá záležitost. 2. V každém stacionárním bodě funkce f se prověří znaménko (signum) druhého diferenciálu d2 f (x, h) = hT H(x)h , ∀h ∈ Rn

kde H(x) je Hessova matice v bodě x

Protože druhý difernciál funkce f je kvadratická forma, používáme kritéria uvedená v (následujícím) odstavci (3.5.6.).

58


3.5.6. Vlastnosti kvadratické formy Je praktické si připomenout užitečné ekvivalentní výroky pro symetrickou matici A = (aij ) , i, j = 1, 2, . . . , n a k ní přiřazenou kvadratickou formu xT Ax =

n X

j=1

aij xi xj , x ∈ Rn .

1. Matice A je pozitivně definitní: (a) xT Ax > 0 pro každý nenulový vektor x ∈ Rn ,

(b) všechna vlastní čísla matice A jsou kladná,

(c) všechny hlavní minory M1 , M2 , . . . , Mn matice A jsou kladné. 2. Matice A je pozitivně semidefinitní: (a) xT Ax ≥ 0 pro každý vektor x ∈ Rn a existuje nenulový vektor y ∈ Rn takový, že yT Ay = 0, (b) vlastní čísla matice A jsou nezáporná, některá z nich jsou nulová, (c) některé hlavní minory matice A jsou kladné, zbývající jsou nulové. 3. Matice A negativně definitní: (a) xT Ax < 0 pro každý vektor x ∈ Rn ,

(b) všechna vlastní čísla matice A jsou záporná, (c) M1 < 0, M2 > 0, M3 < 0, . . . , (−1)n Mn > 0. 4. Matice A je negativně semidefinitní: (a) xT Ax ≤ 0 pro každý vektor y ∈ Rn a existuje nenulový vektor y ∈ Rn takový, že yT Ay = 0, (b) vlastní čísla matice A jsou nekladná, některá z nich jsou nulová, (c) pro hlavní minory matice A platí M1 ≤ 0, M2 ≥ 0, M3 ≤ 0, . . . , (−1)n Mn ≥ 0 a některé nerovnosti jsou ostré. 5. Matice A je indefinitní: (a) existují vektory x, y ∈ Rn takové, že xT Ax > 0 , yT Ay < 0,

(b) matice A má kladná i záporná vlastní čísla,

(c) pro hlavní minory matice A neplatí žádná z předchozích možností.

3.5.7. Ilustrativní příklad 1 Je dána funkce f (x1 , x2 ) = x31 + x32 − 3x1 x2 , (x1 , x2 ) ∈ R2 Řešme tyto optimalizační úlohy a) min{f (x1 , x2 ) | (x1 , x2 ) ∈ R2 }


59

b) max{f (x1 , x2 ) | (x1 , x2 ) ∈ R2 } c) úlohu na sedlový bod Použijeme metodu (technologii) klasické optimalizace. 1. Stanovíme stacionární body funkce grad f (x1 , x2 ). . . grad f (x1 , x2 ) =

"

3x21 − 3x2

3x22 − 3x1

#

=

" #

0 0

Je zřejmé, že řešením uvedené soustavy rovnice je dvojice stacionárních bodů S1 = [1 , 1] , S2 = [0 , 0] . 2. Stanovíme Hessovu matici H(x1 , x2 ) . . . H(x1 , x2 ) =





∂2f 2 ∂x  21 ∂ f ∂x1 ∂x2

∂2f ∂x1 ∂x2  ∂2f ∂x22

#

"

6x1 −3 . = −3 6x2

Pro stacionární body S1 a S2 jsou příslušné Hessovy matice . . . "

#

"

#

6 −3 0 −3 H(S1 ) = , H(S2 ) = −3 6 −3 0 3. Vlastní čísla matice H(S1 ) , (označme jako H1 ) λ1 (H1 ) = 9 > 0 , λ2 (H1 ) = 3 > 0 Matice H1 je tedy pozitivně definitní, tudíž platí dT H1 d > 0 , ∀d ∈ Rn , d 6= 0

a podle postačující podmínky optimality z odst. ?? je S1 = [1, 1] bod ostrého lokálního minina min f = f (x1 , x2 ) = −1 4. Vlastní čísla matice H(S2 ) , (označme jako H2 ) λ1 (H2 ) = 3 > 0 , λ2 (H2 ) = −3 < 0 Matice H2 je tedy indefinitní, je tedy vyloučeno, aby v bodě S2 = [0, 0] byl extrém. Posoudíme tedy, zda stacionární bod S2 není sedlovým bodem. Vyšetříme znaménko kvadratické formy dT H2 d v závislosti na směrech d. Budeme tedy vlastně vyšetřovat průběh dané funkce na přímkách procházející stacionárním bodem S2 . (a) zvolíme d = e1 , tj. x1 = t , x2 = 0 Máme tedy „novou“ funkci f (t, 0) = t3 : funkce f je v bodě S2 ve směru osy x1 ostře rostoucí. (b) zvolíme d = e2 , tj. x1 = 0 , x2 = t Máme tedy „jinou novou“ funkci f (0, z) = t3 : funkce f je bodě S2 ve směru osy x2 ostře rostoucí.

60

3.5. PODMÍNKY OPTIMALITY V KLASICKÉ OPTIMALIZACI (c) zvolíme d = v1 = [1, −1]T tj. vlastní vektor příslušejícímu vlastnímu číslu λ1 = 3 Máme „další“ funkci f (t, −t) = 3t2 : funkce f má v bodě S2 a ve směru vektoru v1 ostré minimum. (d) zvolíme d = v2 = [1, 1]T tj. vlastní vektor příslušejícímu vlastnímu číslu λ2 = −3 Máme „další“ funkci f (t, t) = 2t3 − 3t2 : funkce f má v bodě S2 a ve směru vektoru v2 ostré maximum. Aniž bychom sledovanou funkci f dále vyšetřovali, můžeme konstatovat, že daná funkce f má v bodě S2 lokální sedlový bod.

Je patrné, že optimalizační metoda je poměrně pracná na manuální výpočty (je nutné prověřit poměrně značné množství variant) i pro relativně velmi jednoduché funkce.

3.5.8. Ilustrativní příklad 2 Je dána funkce f (x1 , x2 ) = x31 + x32 + 2x21 + 4x22 + 6 . Rozhodněme o charakteru stacinárních bodů této funkce. Technologie výpočtů: "

#

x (3x + 4) grad f (x1 , x2 ) = 1 1 , x2 (3x2 + 8) "

#

6x1 + 4 0 H(x1 , x2 ) = , 0 6x2 + 8

!

M1 = 6x1 + 4

M2 = (6x1 + 4)(6x2 + 8)

.

Výsledky seřadíme do tabulky Stacionární bod (0, 0) (0, − 83 ) (− 43 , 0) (− 43 , − 83 )

Vlastní čísla H λ1 = 4 λ2 = 8 λ1 = 4 λ2 = −8 λ1 = −4 λ2 = 8 λ1 = −4 λ2 = −8

Minory M1 = 4 M3 = 32 M1 = 4 M2 = −32 M1 = −4 M2 = −32 M= − 4 M2 = 32

Vlastnost H pozitivně definitní

charakter stac. bodu ostré lokální minimum

indefinitní

sedlový bod

418 27

indefinitní

sedlový bod

194 27

negativně definitní

ostré lokální maximum

50 3

f 6

Tabulka 3.5.1: Stacionární body - vlastnosti

O charakteru bodů (0, − 83 ) a (− 43 , 0) lze rozhodnout podle chování funkce f (x1 , x2 ) na přímkách procházejícími těmito body.


61

3.6. Řešené úlohy 3.6.1. Úloha 1 Vyšetřete úlohu n o x2 3 min f (x1 , x2 ) | (x1 , x2 ) ∈ R2 , kde f (x1 , x2 ) = (x22 − x1 )2 − 1 2 4

Odpověď Jediným stacionárním bodem je S = (0, 0 ) (prověřte). • Hessova matice funkce f je v bodě S pozitivně semidefinitní (λ1 = 2 , λ2 = 0), • f (0, 0) = 0 , proto f (x1 , x2 ) = f (0, 0) = f (x1 , x2 ), • pro body (x1 , x2 ) 6= (0, 0) na parabole o rovnici x22 − 32 x1 < f (0, 0) a pro body (x1 , x2 ) 6= (0, 0) na ose x2 je f (x1 , x2 ) > f (0, 0). Takže daná funkce f nemá v bodě S lokální extrém. ovšem na každé přímce x2 = kx1 má funkce f (x1 , kx1 ) = 2x21 − 3k2 x31 + k4 x41 ostré lokální minumum v bodě S.

Závěr Daná funkce má v bodě S extrém v libovolném směru, ale lokální extrém v bodě S nemá. Nezpochybňuje tento příklad větu 3.6.?

6

x 10 4

osa z

3 2

50

1 40 0 30

−1 45

40

20 35

30

25

20

osa x2

10 15

10

5

osa x1 0

0

Obrázek 3.6.1: Ilustrace úlohy (3.6.1.)

62

3.6. ŘEŠENÉ ÚLOHY

3.6.2. Úloha 2 Stanovme všechna řešení optimalizační úlohy pro funkci f (x1 , x2 ) = min f (x1 , x2 ) = x41 + x42 − (x1 + x2 )2 , (x1 , x2 ) ∈ R2 . Odpověď Stacionární body jsou S1 = (1, 1) , S2 = (−1, −1) , a S3 = (0, 0). • f (S1 ) = min f (x1 , x2 ) = −2 • f (S2 ) = min f (x1 , x2 ) = −2 • H(S3 ) je negativně semidefinitní (λ1 = 0 , λ2 = −4), tj. S3 je sedlovým bodem.

180 160 140 120 100 80 60 40 20 0 −20 −20 0 20 40 60 80

50

60

70

40

30

20

10

0

−10

osa x1

osa x2

Obrázek 3.6.2: „Prostorové“ zobrazení funkce z úlohy (3.6.2.)

3.6.3. Úloha 3 b ∈ R1 a x b je ostrý lokální Nechť funkce f : R1 → R1 má derivace všech řádů v bodě x (k) b ) 6= 0 alespoň pro jedno k ? minimizátor funkce f . Plyne odtud, že f (x

Odpověď Neplyne, vyšetřete funkci

f (x) =

(

1

e− x2 , pro x 6= 0 0 , pro x = 0

3.6.4. Úloha 4 b je je ostrý minimizátor funkce f : R1 → R1 . Plyne odtud, že v nějakém leNechť x b funkce klesá a v nějakém pravostranném okolí bodu x b funkce roste? vostranném okolí bodu x


63

Odpověď Neplyne, vyšetřete funkci f (x) =

(

2x2 + x2 sin x1 , pro x 6= 0 0 , pro x = 0

3.6.5. Úloha 5 Přesvědčte se o tom, že funkce f (x1 , x2 ) = x1 ex1 − (1 + ex1 ) cos x2 má v R2 nekonečně mnoho lokálních minimizátorů, ale žádný lokální maximizátor v R2 .

3.6.6. Úloha 6 Uveďte příklady hladkých funkcí jedné, nebo dvou proměnných, které splňují níže uvedené požadavky. a) globální minimum i maximum nybývá funkce v nekonečně mnoha bodech b) funkce je omezená a má globální maximum, ale minimum nikoliv c) funkce je omezená, ale globální extrémy nemá d) funkce je omezená, ale má pouze lokální extrémy e) funkce má nekonečně mnoho lokálních maxim, ale ani jedno lokální minimum Odpověď a) X = R1 ,

f (x) = sin x

b) X = R1 ,

f (x) =

c) X = R1 ,

f (x) = arctan x

d) X = R1 ,

f (x) = (arctan x)(sin x)

e) X = R2 ,

f (x1 , x2 ) = sin x2 − x21

1 1+x2

3.6.7. Úloha 7 Mějme úlohu na minimum pro funkci f (x1 , x2 ) = x21 − x1 x2 + 2x2 − 2x1 + ex1 +x2 • Uveďte nutné podmímky optimality. Jsou postačující ? • Je x = (0, 0)T minimizátor ? Pokud nikoliv, stanovte nějaký směr spádu d.

64

3.6. ŘEŠENÉ ÚLOHY

3.6.8. Úloha 8 Uvažte úlohu minimalizovat kAx − bk2 , kde A je obdélníková matice typu (m, n) , b je vektor o m složkách. • interpretujte úlohu geometricky • zapište nutné podmínky optimaity. Jsou postačující ? • má úloha jediné řešení ? Své tvrzení zdůvodněte. • řešte úlohu pro

   

A=



1 −1 0 0 2 1   , 0 1 0  1 0 1

   

b=

2 1 1 0

    

3.6.9. Úloha 9 Stanovte řešení úlohy min{f (x, y, z) | (x, y, z) ∈ R3 } , kde f (x, y, z) = 5x2 + 5y 2 + z 2 + 2xy − 2xz − 2yz − 4x − 4y Odpověď b, y b, b b, y b, b z) = 0. (x z) = ( 12 , 12 , 1); f (x

Návod Stanovíme všechny body, v nichž grad f (x, y, z) = 0. Dostaneme tak soustavu lineárních rovnic 



10x + 2y − 2z − 4 = 0    10y + 2x − 2z − 4 = 0  2z − 2x − 2y = 0

a jediným řešením této soustavy je trojice ( 12 , 12 , 1). Hessova matice fukce f pak je 



10 2 −2   H =  2 10 −2  −2 −2 2

je podle kritéria 1 z odst. 3.5.6. pozitivně definitní, tj. stacionární bod je bod ostrého minima. V kapitole »5« bude ukázáno (odst. »?«), že daná kvadratická funkce je ostře konvexní na R3 , a proto minimum je globální.

Kapitola 4

Technologie jednorozměrné numerické optimalizace

65

66

Kapitola 5

Numerické metody nepodmíněné optimalizace

67

68

Kapitola 6

Úlohy podmíněné optimalizace - rovnostní vazby

6.1. Úvodní poznatky Budeme se zabývat úlohou na minimum (A)

min{f (x) | x ∈ V } ,

nebo úlohou na maximum (B)

max{f (x) | x ∈ V } ,

kde f : X → R1 , X ⊂ Rn je daná diferencovatelná účelová funkce. Přípustná množina V ⊂ X je dána souborem vazebních podmínek typu rovností.

6.1.1. Přípustné množiny Přípustnou množinou s lineárními vazbami definujeme jako množinu (tzv. lineární varieta) (C)

V = {x ∈ X : Bx − c = 0} ⊂ Rn ,

kde matice B je obdélníková typu (p, n) s prvky (bij ) a x ∈ Rp .

Každý přípustný bod x ∈ V je tedy řešením soustavy lineárních rovnic

(D)

bj1 x1 + bj2 x2 + · · · + bjn xn = cj , j = 1, 2, . . . , p

Všechna tato řešení lze vyjádřit ve tvaru (E)

x = x+

n−h X i=1

αi wi , αi ∈ R1 ,

kde x ∈ V je partikulární řešení soustavy Bx = c (pevný bod lineární variety V ) a vektory wi ∈ R , i = 1, 2, . . . , n − h jsou lineárně nezávislá řešení homogenní soustavy Bw = 0 , h = h(B) 69

70

6.1. ÚVODNÍ POZNATKY

je hodnost matice B. Číslo n − h = dimV je dimenze lineární variety V , které se definuje jako dimenze lineárního prostoru (tzv. nulový prostor matice B ≡ lineární obal vektorů wi ) N (B) = {w ∈ Rn : Bw = 0} ,

(F)

Přípustnou množinu z (C) lze proto ekvivalentně definovat jako množinu (G)

V = {x ∈ X : x = x + N (B)} ; Bx= c.

Obecné nelineární vazební podmínky (H)

hj (x) = 0 , j = 1, 2, . . . , p ,

definujeme funkcemi hj : X → R1 , j = 1, 2, . . . , p a přípustnou množinu označujeme (I)

V {x ∈ X : hj (x) = 0 , j = 1, 2, . . . , p}

nebo (J)

V = {x ∈ X : h(x) = 0} ,

kde h : X → Rp , h(x) = [h1 (x), h2 (x), . . . , hp (x), ]T .

6.1.2. Lemma Redukce dimenze u lineárních vazeb b je bod lokálního minima funkce f : X → R1 na přípustné množině (C), resp Nechť x (G), tj. b ) = min f (x) , x b = x+ f (x

n−h X i=1

b i wi ; Bwi = 0 . α

b + N (B) x∈x

b = [α b1 , α b2 , . . . , α b n−h ]T je bod lokálního minima funkce g : Rn−h → R1 dané předpisem Potom α

g(α1 , α2 , . . . , αn−h ) = f (x +

n−h X

αi wi ) .

i=1

a platí b ) = g(x b) . f (x

Důkaz je evidentní.

b ) ≤ f (x) ∀x ∈ V ≡ x + N (B) , pak také Když f (x

f

x+

n−h X i=1

tj.

!

b i wi ≤ f α

x+

n−h X i=1

αi wi

!

b ≤ g(α) , ∀α ∈ Rn−h . g(α)

∀αi ∈ R1 ,

Poznámka: Úloha na minimum funkce f na lineární varietě x + N (B) se na základě tohoto lemmatu převede na úlohu na volný extrém funkce g na (v??) prostoru Rn−h , kde h > 0 je hodnost matice B .

6. ÚLOHY PODMÍNĚNÉ OPTIMALIZACE - ROVNOSTNÍ VAZBY

71

6.1.3. Lemma Nutné podmínky optimality na lineární varietě b = x+ Je-li x

n−h X i=1

b i wi bod (lokálního) minima funkce f : X → R1 na přípustné množině α

V = x + N (B)

určené lineárními vazbovými podmínkami Bx − c = 0 ; h(B) = p , potom platí d f dαi

(K)

x+

n−h X i=1

! αi wi

Tuto podmínku lze ekvivalentně vyjádřit takto: a) (L)

b)

=0. αi =α bi

b ) = 0 , i = 1, 2, . . . , n − h , wTi grad f (x

b jsou ve všech směrech lineární variety nulové ! tj. derivace funkce f v bodě x b ∈ Rp , v b = [vb1 , vb2 , . . . , vbp ]T (ne všechna nulová!) ∃v b≡ b ) = BT v − grad f (x

(M)

p X

j=1

vbj bj

b ) je lineární kombinace sloupců matice BT , tj. vektor grad f (x

tj. lineárně nezávislých řádků matice B.

c)

(N)

b ∈ Rp , v b = [vb1 , vb2 , . . . , vbp , ]T (ne všechna nulová!) ∃v

grad[f (x) + vT (Bx − c)] x=bx = 0 ; b

v=v

grad (bTj x − cj ) = bj , zřejmě j = 1, 2, . . . , p . |

{z

}

j−tá složka vektoru Bx−c

d) (O)

b ) ∈ (span wi )T ≡ span(bj ) , grad f (x

i = 1, 2, . . . , n − p ;

j = 1, 2, . . . , p ,

tj. gradient funkce f v bodě minima je ortogonální ke všem směrovým vektorům lineární variety V . Důkaz a) n−h X d f (x + αi wi ) = wTi grad f (x) . dαi i=1

b ) > 0 , potom Modifikace standardního důkazu sporem. Připustíme-li například, že wTi grad f (x b + twi ) < (x b ) pro dostatečně malé t > 0. z Taylorovy formule dostaneme nerovnost f (x

72

6.2. ŘEŠENÉ ÚLOHY S LINEÁRNÍMI VAZBAM

b) b ) , i = 1, 2, . . . , n − h říkají, že grad f (x b ) ∈ Rn v bodě Podmínky ortogonality wi ⊥ grad f (x n b) ∈ minima je ortogonální k bázi lineárního prostoru N (B) ⊂ R , tedy grad f (x / N (B), dob )⊥N (B). Jinak řečeno, grad f (x b ) musí patřit ortogonálnímu doplňku k prostoru konce grad f (x N (B), tj. do lineárního prostoru dimenze p:

[N (B)]⊥ ≡ H(BT ) = {z ∈ Rn : z = BT v ,

∀v ∈ Rp } .

Bazí z1 , z2 , . . . , zp jsou tedy lineárně nezávislé obrazy prvků v ∈ Rp v zobrazení BT , což jsou sloupce matice BT .

⊥

[N (B)] = H (BT )

R n = N (B) ⊕ H (BT )

N (B) 0

Obrázek 6.1.1: Báze lineárního prostoru a její ortogonální doplněk Pak (M) je zápisem faktu, že b ) ∈ H(BT ) . grad f (x

c) (N) je pouze jiný zápis (M). d)

span(wi ) = N (B) ; span(bj ) = [N (B)]⊥ ≡ H(BT ) ;

span(bj ) je lineární obal řádků matice B , tj. lineární prostor tvořený všemi lineárními kombinacemi sloupců matice BT . Jestliže přípustnou množinu V = x+N (B) určenou vazbami Bx = c , tedy geometricky jako průnik nadrovin bTj x − cj = 0 , j = 1, 2, . . . , p , potom podmínka b )⊥span(wi ) grad f (x

b ) leží v prostoru všech normál uvedených nadrovin. říká, že vektor grad f (x

Poznámka: Výrok span(bj ) = [N (B)]⊥ pouze říká, že bj ⊥w , resp. bTj w = 0 , a to je ekvivalentní výroku Bw = 0.

j = 1, 2, . . . , p ;

6.2. Řešené úlohy s lineárními vazbam Opíráme se o poznatky z odstavců (6.1.2.) a (7.2.4.), tj. o vyjádření nutných podmínek optimality.


73

6.2.1. Základní úloha kvadratické optimalizace Stanovme řešení úloh min{f (x1 , x2 ) | (x1 , x2 ) ∈ V } , max{f (x1 , x2 ) | (x1 , x2 ) ∈ V } ,

kde

f (x1 , x2 ) = x21 + x22 , (x1 , x2 ) ∈ R2 ,

V = {(x1 , x2 ) ∈ R2 : x1 + x2 − 1 = 0} . Technologie derivování ve směru množiny V : Všechny přípustné body lze vyjádřit: "

#

" #

| {z }

#

| {z }

|{z}

x

rozepsáno složkově

"

x1 0 1 = = x + αw , α ∈ R1 . +α x2 1 −1 w

x

x1 = 0 · x1 + α · (+1) x2 = 1 · x2 + α · (−1)

Funkci f dvou proměnných x1 , x2 převedeme na funkci jedné proměnné α (restrikce funkce f na V ) g(α) = f (x + αw) = f (α, 1 − α) = 2α2 − 2α + 1 . prostým dosazením x1 = α , x2 = 1 − α. b musí být V bodě minima (maxima) α b = g ′ (α)

d b w) = 0 . [f (α, 1 − α)]α=αb = wT grad f (x + α dα

Je zřejmé, že g ′ (α) = (2α2 + 2α + 1)′ = 4α − 2 , odtud již plyne

Protože

1 b= , α 2 b = g ′′ (α)

" #

"

#

0 1 1 b= x + = 1 2 −1

" # 1 2 1 2

.

d2 b )w = , [f (α, 1 − α)]α=αb = wT H(x dα2 "

# "

#

20 1 = [1, −1] · · =4>0, 02 −1

b ∈ V bodem minima. Úloha na maximum není řešitelná. je x

Technologie přímé redukce dimenze:

Z vazební podmínky vyjádříme x2 = 1 − x1 a stanovíme funkci jedné proměnné ozn.

f (x1 , 1 − x1 ) = F (x1 ) = x21 + (1 − x1 )2 = 2x21 + 2x1 + 1 . Původní úlohy min{f (x1 , x2 ) | (x1 , x2 ) ∈ V } ,

74


tak převedeme na úlohy

max{f (x1 , x2 ) | (x1 , x2 ) ∈ V } , min{F (x1 ) | x1 ∈ R1 } ,

Z druhé podmínky

b1 = dostaneme x

Protože

b= je x

" # 1 2 1 2

1 . 2

max{F (x1 ) | x1 ∈ R1 } ,

dF (x1 ) = (2x21 − 2x1 + 1)′ = 0 dx1 x1 =bx1

d2 F (x1 ) = (2x21 − 2x1 + 1)′′ = 4 > 0 , dx21 x =bx 1 1

bodem minima, f (x1 , x2 ) =

1 . 2

6.2.2. Obecná úloha kvadratické optimalizace Chceme najít řešení úlohy min{f (x) | x ∈ V } , kde

a předpokládáme

1 f (x) = xT Ax − bT x , x ∈ Rn , 2 V = {x ∈ Rn : Bx − c = 0} , c ∈ Rp

A je symetrická, pozitivně definitní matice řádu n ; b ∈ Rn ;

B je obdélníková matice typu (p, n) s plnou hodností, tj. h(B) = p < n. Znamená to, že řádky matice B bTj = [bj1 , bj2 , . . . , bjn , ] , j = 1, 2, . . . , p , jsou lineárně nezávislé. Jednotlivé vazební nerovnosti mají tvar bTj x − c =

n X

k=1

bjk xk − cj = 0 ,

j = 1, 2, . . . , p .

Jak již bylo řečeno v odst. (7.2.4.), každé x ∈ V lze vyjádřit ve tvaru součtu x = x+w , kde vektor x je partikulární řešení nehomogení (vazební) soustavy, tj. platí Bx = c a w ∈ N (B) ⊂ Rn , což je lineární prostor všech řešení této homogení soustavy.

b ∈ V lze stanovit využitím některé z nutných podmínek z odst. Jediný bod minima x (7.2.4.). Přesněji řečeno: stanovíme řešení soustavy nutných podmínek a dodatečně prověříme, že jde o bod minima.


75

Technologie stanovení partikulárního řešení x Ze všech řešení soustavy Bx = c stanovíme takové, které má nejmenší normu √ kxk2 = xT x . Řešíme tedy pomocnou otimalizační úlohu 1 min{ xT x : BX − c = 0} 2 Z nutné podmínky (M) dostaneme −x = BT v , tj. Bx = −BBT v = c . Takže v = −(BBT )−1 c ,

a tedy

x = BT (BBT )−1 c . Technologie stanovení báze prostoru N (B)

Sestrojíme pomocnou maticovou rovnici e ·W = D , B

kde     ..   .       p              e = B   ···             n-p            |

..



.

0 ···

..

.

B ..

···

0

. ··· ··· ··· ··· ··· 1 0 1 .. .

          , ···         

1

{z n

}



..

 .          D=   ···   1       |

..

.

0

0 .. .

···

···

1

.. {z

n−p

.

                        . .   .   n  ···                     1    } 

Zde B je již upravená původní matice B na lichoběžníkový tvar. Sloupce matice W typu (n, n − p) jsou hledané bázové vektory w1 , w1 , . . . , wn−p , prostoru N (B) , tj. Bwi = 0 , i = 1, 2, . . . , n − p . Metoda redukce dimenze Každý přípustný bod x ∈ V vyjádříme ve tvaru x = x+u , kde u = y1 w1 + y1 w1 + · · · yn−p wn−p ≡ Wy ,

76


a y = [y1 , y2 , . . . , yn−p ]T ∈ Rn−p je vektor nových (neredukovaných) proměnných. Definujeme funkci 1 g(y) = f (x + Wy) = (x + Wy)T A(x + Wy) − bT (x + Wy) 2 V bodě minima: b ) ≤ g(y) , g(y

z nutné podmínky optimality

∀y ∈ Rn−p ,

b) = 0 , zT grad g(y

∀y ∈ Rn−p

b ze soustavy lineárních rovnic stanovíme y

WT AWy = −WT Ax − WT b .

Potom b. b = +Wy x

a

b ) = min (x) = min g(y) = g(y b) . f (x y∈Rn−p

x∈V

(A) Konkrétní vstupy a výstupy 1 1 f (x) = (xT x) = (x21 + x22 + x23 + x24 ) ; n = 4 ; 2 2 

B=

"

  

A= 1 5 3 2 1 6 5 2



1 1 1 1 #

;

c=

"

  ; 

1 0 1 5

   

b= #

;

0 0 0 0



  ; 

h(B) = 2 , p = 2 .

Algoritmus metody redukce dimenze Vstup: 1. Stanovit: 2. Stanovit: Určit: Výstup:

A : Rn → Rn , B : Rn → Rp , p = h(B) , b ∈ Rn , c ∈ Rp , 1 f (x) = xT Ax − bT x ; V = {x ∈ Rn : Bx − c = 0} . 2 v ∈ Rp : BBT v = c , x ∈ Rn : x = BT v . bázi prostoru N (B) , tj. matici W typu (n, n − p) e řešením pomocné maticové rovnice BW = D ; n − p bázových vektorů n−p T T T b∈R y : W AWy = −W Ax − W b (lze užít metodu sdružených gradientů). b , f (x b ) = g(y b ) = f (x + Wy b ). b = x + Wy x


BBT =

"

#

39 50 50 66

5  −   74   60  −0, 0675676     0, 810811    74 =   155   2, 0945952     74  −0, 1351352  10  − 74 

   

x = BT (BBT )−1 c = 

;

77

Pomocná maticová rovnice     

Takže

1 0 0 0

5 1 0 0

3 2 1 0

2 0 0 1

e BW = D , tj.

      ·  

w11 w21 w31 w41

w12 w22 w32 w42





0 0 1 0

    =  

0 0 0 1



  . 

w1 = [w11 , w21 , w31 , w41 , ]T = [7, −2, 1, 0]T , w2 = [w12 , w22 , w32 , w42 , ]T = [−2, 0, 0, 1]T , WT A =

"

7 −2 1 0 −2 0 0 1

Z nutné podmínky

#

.    

WT AWy = −WT Ax − WT b =  b = [0, 0, 0, 0]T . Dostaneme y

0 0 0 0

    

b=x. Takže x

(B) Konkrétní vstupy a výstupy 1 f (x) = x21 + x22 + x23 + x2 + x3 ; n = 3 ; 2 







" # " # 3 0 0 0 1 2 −1 4     A= 0 2 1  ; b= 0  ; B= ; c= ; h(B) = 1 , p = 2 . 1 −1 1 2 0 1 2 0

BBT =

"

6 −2 −2 3

#

; v : BBT v = c ; v =  

w ∈ R3−2 ; jeden bázový vektor w =  e ·W = D B

:



− 13 2 3

1

"

8 7 10 7



#

 

; x = BT v = 

18 7 5 7 2 7



 .

  ; jako řešení soustavy pro výpočet báze 









0 1 2 −1 w1       2  ·  w2  =  0  ;  0 −3 1 w3 0 0 1

78

6.3. LAGRANGEOVY MULTIPLIKÁTORY  

x = x + yw = 

18 7 6 7 2 7

f (x + yw) = g(y) =





   +y 

− 31 2 3

1

  

575 41 2 4 y + y+ ; 18 21 49

g ′ (y) = 0 : yb = 0, 0418118 ;

b = x + ybw = [2, 5853658; 0, 8292268; 0, 243902]T . x

6.3. Lagrangeovy multiplikátory V knize Théorie des functions analytiques (Paříž 1813) Lagrange říká: „Lze vyslovit následující princip. Jestliže hledáme minimum, nebo maximum nějaké funkce více proměnných s podmínkou, že mezi těmito proměnnými existuje vazba zadaná jednou, nebo několika rovnicemi, je třeba přičíst k minimalizované (maximalizované) funkci určující rovnice vazby vynásobené neurčitými multiplikátory a pak hledat minimum nebo maximum tohoto součtu tak, jako by byly nezávislé. Získané rovnice spolu s rovnicemi vazeb umožní určit všechny neznámé“. Důkazy vět v tomto odstavci a ve svém důsledku metoda Lagrangeových multiplikátorů se opírá opět o pricip redukce dimenze a tedy o teorii řešitelnosti funkcionálních rovnic (tzv. věta o implicitní funkci) – viz např. [2].

6.3.1. Lemma. Řešitelnost úlohy v R2 Mějme funkci f : X → R1 , h : X → R1 , X ⊂ R2 , které jsou spojitě diferencovatelné b ) ⊂ X . Předpokládáme, že x b = (x b1 , x b2 ) je bod lokálního minima (nebo maxima) v okolí Uδ (x funkce f , který je lokálním řešením rovnice h(x1 , x2 ) = 0. Potom existuje číslo vb ∈ R1 takové, že platí

(P)

b1 , x b2 ) + v b grad h(x b1 , x2 ) = 0. grad f (x

b1 , x b2 ) = 0 a znaménka Důkaz. Ze spojitosti a diferencovatelnosti funkce h a z rovnosti h(x ∂h(x1 , x2 ) 6= 0 plyne, že existuje jediná diferencovatelná funkce ∂x2 (x1 ,x2 )=(b x1 ,b x2 ) b1 ) → R1 , x2 = ϕ(x1 ), ϕ : Uδ (x

která je lokálním řešením funkcionální rovnice h(x1 , x2 ) = 0 , tj platí rovnosti b1 ) , h(x1 , ϕ(x1 )) = 0 ∀x1 ∈ Uδ (x b2 = ϕ(x b1 ) , x


b1 ) = ϕ′ (x

(Q)

79

∂h(b x1 ,b x2 )

dx2 . = − ∂x1 ∂h(b x1 ,b x2 ) dx1 bx1 ∂x2

Sestrojíme (složenou) funkci (myšlenka redukce proměnných)

b1 ) F (x1 ) = f (x1 , ϕ(x1 )) , x1 ∈ Uδ (x

Podmínka minima

b1 , x b2 ) ≤ f (x1 , x2 ) , ∀(x1 , x2 ) ∈ V = {(x1 , x2 ) ∈ R2 : h(x1 , x2 ) = 0} f (x

lze tedy také psát

a nutnou podmínku optimality (R)

b1 ) ≤ F (x1 ) , ∀x1 ∈ Uδ (x b1 ) , F (x

dF (x1 ) ∂f ∂f dx2 0= = + · . dx1 bx1 ∂x1 ∂x1 dx1 Xb1

Z rovností (Q) a (R) plyne dokazované tvrzení

b1 , x b2 ) b1 , x b2 ) ∂h(x ∂f (x + vb · =0, ∂x1 ∂x1 b1 , x b2 ) b1 , x b2 ) ∂h(x ∂f (x + vb · =0. ∂x2 ∂x2

6.3.2. Geometrický pohled na nutné podmínky Výsledek z odstavce (6.3.1.) říká, že nutnou podmínkou minima (maxima) v bodě b1 , x b2 ) jsou vektory (x b1 , x b2 ) , grad h(x b1 , x b2 ) grad f (x

a jsou kolineární s koeficientem kolineárnosti vb. b1 , x b2 ) ke křivce Tečný vektor v bodě (x

V = {(x1 , x2 ) ∈ R2 : h(x1 , x2 ) = 0}

je w=

∂h(b x1 ,b x2 ) # ∂x2 x2 ) 1 ,b − ∂(bx∂x 1

"

"

#

"

#

dx1 dx1 = ′ = b1 ) dx1 ϕ (x dx2 (bx ,bx ) 1 2

b1 , x b2 ) je neboť rovnice tečny ke křivce V v bodě (x

a

b1 , x b2 ) b1 , x b2 ) ∂h(x ∂h(x b1 ) + b2 ) = 0 · (x1 − x · (x2 − x ∂x1 ∂x2 b1 ) = − ϕ′ (x

∂h(b x1 ,b x2 ) ∂x1 ∂h(b x1 ,b x2 ) ∂x2

Proto také z (6.3.1.) vyplývají podmínky ortogonality

b1 , x b2 ) , w⊥ grad h(x b1 , x b2 ) , w⊥ grad f (x

80

6.3. LAGRANGEOVY MULTIPLIKÁTORY

tj. podmínky

b1 , x b2 ) = 0 wT grad f (x

b1 , x b2 ) = 0 wT grad h(x

Geometrická interpretace nutné podmínky: kolineárnost vektorů (grad f ) a (grad h) v bodě b1 , x b2 ). (x

x2

f
f =c grad h(b x1 , x b2 ) hladiny f f >c růst f

b x

x b2

h(x1 , x2 ) = 0 w grad f (b x1 , x b2 )

V 0

x b1

x1

b je bod lokálního minima f na V Obrázek 6.3.2: Bod x


x2

81

-grad f (x) f >c hladiny f

b x

x2

grad h(x)

h(x) = 0 x

f =c -grad f (e x) V f
e x

grad h(e x)

růst f

0

x2

x1

x1

Obrázek 6.3.3: x není bod minima (extrému) f na V b je bod lokálního minima f na V x e je bod lokálního maxima f na V x f >c hladiny f grad f (x) f =c h(x) = 0 w

x2

x

f
V grad h(x)

0

x1

x1

Obrázek 6.3.4: Bod x není bodem lokálního extrému, f na V avšak grad f (x), grad h(x) jsou kolineární (závislé). Pozorování: Podmínka kolineárnosti vektorů grad f a grad h není postačující podmínkou

82


extrému (minima, nebo maxima), je to pouze podmínka nutná !

6.3.3. Obecná věta o Lagrangeových multiplikátorech Mějme funkce f : X → R1 , hj : X → R1 , X ⊂ Rn , j = 1, 2, . . . , p, které jsou spojitě b) ⊂ X . diferencovatelné v okolí Uδ (x

b je bod lokálního minima (nebo maxima) funkce f , který je lokálPředpokládáme, že x ním řešením rovnic hj (x1 , x2 , . . . , xn ) = 0 , j = 0, 2, . . . , p .

Dále předpokládáme, že vektory b ) , j = 1, 2, . . . , p grad hj (x

jsou lineárně nezávislé, tj. Jacobiova matice typu (p, n)

b) ∂hj (x D(h) D(h1 , h2 , . . . , hp ) b) = = = grad h(x D(x) D(x1 , x2 , . . . , xn ) ∂xi

b hodnost (p < n). má v bodě x

(S)

Potom existují reálná čísla vb1 , vb2 , . . . , vbp taková, ne všechna nulová, že platí b) + grad f (x

p X

j=1

b) = 0 vbj grad h(x

Číslům vbj , j = 1, 1, 2, . . . , p říkáme Lagrangeovy multiplikátory. Při označení

  

h(x) =   

h1 (x) h2 (x) .. .

hp (x)





     ; v=    

v1 v2 .. . vp





     ; grad h(x) =     

grad h1 (x) grad h2 (x) .. . grad hp (x)

lze tvrzení (S) psát ve vektorově-maticovém tvaru



  D(h) =  D(x) 

b ) + gradT h(x b) v = 0 grad f (x

(T)

kde gradT h je matice typu (m, n) se sloupci grad hj .

Důkaz: Budeme sledovat „technologii důkazu“ z odstavce (6.3.1.). Z věty o existenci lokálního řešení vazbových rovnic plyne existence diferencovatelných funkcí

při označení

b 1 ) → R1 , Uδ (x1 ) ⊂ Rn−p , i = 1, 2, . . . , p ϕi : Uδ (x

je zobrazení z Rn−p do Rp

b = (x bp+1 , . . . , x bn ) b1 , x b2 , . . . , x bp , x x |



  Φ=  

{z b x2

ϕ1 (x1 ) ϕ2 (x1 ) .. . ϕp (x1 )

} |



{z b x1

}

   , x2 = Φ(x1 )  


83

řešením vazbové rovnice h(x) ≡ h(x1 , x2 ) = 0;

tj. platí

b 1 ) ⊂ Rn−p ; h (Φ(x1 ), x1 ) = 0 , ∀x1 ∈ Uδ (x b 2 = Φ(x b 1 ). x

Beze ztráty obecnosti předpokládáme, že čtvercová regulární část Jacobiovy matice řádu (p)

Potom

D(h) D(h) . = D(x) D(x2 ) bx

D(Φ) D(h) −1 D(h) =− · D(x) bx1 D(x2 ) bx D(x1 ) bx

Sestrojíme funkci F : Rn−p → R1 (redukce dimenze)

b1) . F (x1 ) = f (Φ(x1 ), x1 ) , x1 ∈ Uδ (x

Z požadavku

b 1 ) ≤ F (x1 ) , ∀x1 ∈ Uδ (x b 1 ) ⊂ Rn−p F (x

plyne (nutné podmínky optimality)

b1) ∂F (x = 0 , j = p + 1, p + 2, . . . , n . ∂xj

tj.

p

b1) b ) ∂ϕi (x ∂f (x) X ∂f (x + · = 0 , j = p + 1, p + 2, . . . , n . ∂xj ∂xi ∂xj i=1

(U) Derivace

∂ϕi , i = 1, 2, . . . , p ; j = p + 1, p + 2, . . . , n ∂xj

vyjádříme také z rovností h(Φ(x1 ), x1 ) = 0: (V)

p X b) b ) ∂ϕi (x ∂hk (x i=1

∂ϕi

·

∂xj

+

b) ∂hk (x = 0 , k = 1, 2, . . . , p ; j = p + 1, p + 2, . . . , n . ∂xj

Pomocná soustava regulární maticí

(W)



 D(h) ·v = −  D(x2 )

∂f ∂x1

.. .

∂f ∂xp



p X  ∂hk ∂f ↔ , k = 1, 2, . . . , p vi =  ∂x ∂x i=1

i

k

b ∈ Rp . Zde jsme vzali jen těch p rovnic, jejichž matice odpovídá lineárně má jediné řešení v nezávislým sloupcům Jacobiovy matice D(h) D(x) typu (p, n) , p < n.

Každou z p rovností vztahu (V) vynásobíme postupně čísly vb1 , vb2 , . . . , vbp ze vztahu (W) a přičteme k n − p rovnostem vztahu (U). Po úpravě dostaneme n − p rovností   p p p X b ) X ∂hj (x b 1 ) ∂f (x b) b) b ) X ∂hj (x ∂ϕi (x ∂f ( x   + + = 0 , k = p + 1, p + 2, . . . , n + · vbj vbj i=1

∂xi

j=1

∂xi

∂xk

∂xk

j=1

∂xk

Výrazy v hranaté závorce jsou díky vztahu (W) nulové. odtud pak spolu se vztahem (W) dostaneme tvrzení (6.3.2.)

84


6.3.4. Geometrický pohled Přípustnou množinu V {x ∈ X ⊂ Rn : hj (x) = 0, j = 1, 2, . . . , p} jako průnik nadplochou v Rn . Označíme b ), grad h2 (x b ), . . . , grad hp (x b )} S = span{grad h1 (x

lineární obal vektorů normál k nadplochám hj (x) = 0.

b ∈ V označíme Tečný prostor k nelineární varietě V v bodě x

b ) = 0 , j = 1, 2, . . . , p}. T = {w ∈ Rn : wT grad hj (x

b ∈ V bod minima funkce f : X → R1 , potom musí být bodem dotyku tečného prostoru Je-li x b ). T k hladině funkce f o rovnici f (x) = f (x

Potom prostory S a T jsou navzájem ortogonální, tj. S⊥T

musí být a tedy také (X)

b )⊥T grad f (x b) ∈ S grad f (x

b ) , j = 1, 2, . . . , p lineárně nezávislé, pak tvoří bázi prostoru S a každý jsou-li vektory grad hj (x další vektor tohoto prostoru se dá vyjádřit jako lineární kombinace této báze, tj. existují čísla vb1 , vb2 , . . . , vbp (ne všechna nulová) taková, že platí

(Y)

b) = − grad f (x

p X

j=1

b) . vbj · grad hj (x

Geometricky řečeno T je ortogonální doplněk prostoru S, tj. T ⊕ S = Rn .

b ) , j = 1, 2, . . . , p lineárně závislé, pak (6.3.3.) pouze říká, že vektory Jsou-li vektory grad hj (x b ), grad h1 (x b ), grad h2 (x b ), . . . , grad hp (x b) grad f (x

jsou lineárně závislé, tj, existují čísla vb0 , vb1 , vb2 , . . . , vbp (ne všechna nulová) taková, že platí

(Z)

b) + vb0 grad f (x

p X

j=1

b) = 0 . vbj grad hj (x

Kapitola 7

Úlohy podmíněné optimalizace - nerovnostní vazby

7.1. Formulace úloh a ilustrativní příklady 7.1.1. Přípustné množiny Je dána funkce f : X → R1 , žina V ⊂ X .

X ⊂ Rn (spojitá, resp. diferencovatelná) a přípustná mno-

Úloha na minimum: b ∈ V , f (x b ) ∈ R1 , takové, že f (x b ) ≤ f (x), ∀x ∈ V . Najít x

Úloha na maximum:

b ∈ V , f (x b ) ∈ R1 , takové, že f (x b ) ≥ f (x), ∀x ∈ V . Najít x

Zápis uvedených úloh: (A)

min{f (x) | x ∈ V ⊂ Rn } ;

(B)

max{f (x) | x ∈ V ⊂ Rn } ;

Pokud požadujeme splnění podmínky b ) ≤ f (x) [f (x b ) ≥ f (x)] f (x

b ), hovoříme o úloze na lokální minimum, resp. lokální maximum. pro všechna x ∈ V ∩ Uδ (x

b ∈ V je lokálním řešením dané úlohy, jestliže existuje δ > 0 takové, Přesněji: Přípustný bod x b ). že platí požadovaná nerovnost pro všechna x ∈ V ∩ Uδ (x

V této kapitole se soustředíme na úlohy, v nichž přípustné množiny budou definovány pomocí vazbových podmínek typu nerovnosti, případně smíšenými podminkami. Typickou přípustnou množinou (především v úlohách operační analýzy) je: (C)

V = {x ∈ X : Bx − c ≤ 0}, 85

86

7.1. FORMULACE ÚLOH A ILUSTRATIVNÍ PŘÍKLADY

kde matice B je obdélníková typu (m, n), m je počet řádků, n je počet sloupců, c ∈ Rm .

Lineární vazbové podmínky v rozepsané podobě:

b11 x1 + b12 x2 + · · · + b1n xn − c1 ≤ 0, b21 x1 + b22 x2 + · · · + b2n xn − c2 ≤ 0, ......................................... bm1 x1 + bm2 x2 + · · · + bmn xn − cm ≤ 0 . V obecných úlohách se vazbové podmínky zapisují pomocí nelineárních funkcí

1

n

gi : X → R , i = 1, 2, . . . m ; g : R → R

m

Takže: (D)



  ; g=  

g1 g2 .. . gm



  .  

V = {x ∈ X : g(x) ≤ 0},

resp. ve složkách: V = {x ∈ X : gi (x) ≤ 0 i = 1, 2, . . . , m}.

Někdy je účelné registrovat samostatně rovnostní a nerovnostní vztahy. Pak označujeme (E)

V = {x ∈ X : h(x) = 0, g(x) ≤ 0},

kde h : Rm → Rp ; g : Rn → Rm .

Typickým případem jsou tzv. úlohy operační analýzy s přípustnými množinami typu (F)

V = {x ∈ X : Bx − c = 0, x ≥ 0},

7.1.2. Přípustné směry, aktivní vazby Jednotkový vektor p ∈ Rn , kpk = 1 je přípustným směrem v přípustném bodě x ∈ V , existuje-li okolí Uτ (x) ⊂ X bodu x takové, že platí implikace x ∈ V ⇒ x + tp ∈ V ∩ Uτ (x) . . . obrázek . . . pro dostatečně malé t, tj. pro t ∈ (0, τ ).

Pro vazební podmínky (D) to znamená, že platí implikace: gi (x) ≤ 0 ⇒ gi (x + tp) ≤ 0, i = 1, 2, . . . , m. Množinu přípustných směrů v bodě x ∈ V označíme D(x, V ) = {p ∈ Rm : q x + tp ∈ V ∩ Uδ (x); kpk = 1, t ∈ (0, τ )}

7. ÚLOHY PODMÍNĚNÉ OPTIMALIZACE - NEROVNOSTNÍ VAZBY

87

Množinu indexů vazeb aktivních v bodě x ∈ V označíme:

I (x) = {i : g(x) = 0}.

Ilustrace obrázkem . . . , také říkáme, že bod x je aktivní vzhledem k vazbám (někerým). Dále označíme Do (x) = {p ∈ Rm : pT grad gi (x) < 0, i ∈ I (x), kpk = 1}.

otevřený kužel přípustných směrů v aktivním bodě x Množinu:

D o (x) = {p ∈ Rm : pT grad gi (x) ≤ 0, i ∈ I (x), kpk = 1}.

nazveme uzavřený kužel přípustných směrů v aktivním bodě x.

7.1.3. Spádové směry Množinu spádových směrů v přípustném bodě x vzhledem k funkci f označíme S(x, f ) = {d ∈ R: f (x + td) < f (x), t ∈ (0, δ), kdk = 1} Kužel spádových směrů v přípustném bodě x vzhledem k funkci f označíme F (x, f ) = {d ∈ Rm : dT grad f (x) < 0, kdk = 1}. Při výkladu spádových metod v kapitole 3 jsme ukázali, že platí inkluze F (x, f ) ⊂ S(x, f ),

neboť pro hladkou funkci f a pro dostatečně malé t > 0 z nerovnosti dT grad f (x) < 0 plyne nerovnost f (x + td) < f (x).

7.1.4. Ilustrace množin D(x, V ), D0(x), F (x, f ) Předpokládáme, že gi (x) < 0, x ∈ V . . . obrázek. . .

přípustná množina V určená vazovými podmínkami g1 (x) ≤ 0, g2 (x) ≤ 0, g3 (x) ≤ 0 a množiny D přípustných směrů I (x) = {2, 3}, I (x) = {2}, I (x) = {1, 3} . . . obrázek. . .

Množiny F spádových směrů a množiny D přípustných směrů. V optimálním bodě b ∈ V je F (x, f ) ∩ D(x, V ) = ∅, v neoptimálním bodě x je F (x, f ) ∩ D(x, V ) 6= ∅. . . . ostatní x obrázky, zatím na nich pracuji. . .

7.1.5. Příklad Mějme úlohu kde

min{f (x1 , x2 )|(x1 , x2 ) ∈ V }, f (x1 , x2 ) = (x1 − 2)2 + x22 ,

V = {(x1 , x2 ) ∈ R2 : −x1 ≤ 0, −x2 ≤ 0, −1 + x21 + x2 ≤ 0} ...

|{z} g1

|{z} g2

|

{z g3

}

88

7.1. FORMULACE ÚLOH A ILUSTRATIVNÍ PŘÍKLADY

7.1.6. Úloha lineární optimalizace Na jednoduchém příkladu vyložíme základní principy přístupu k úlohám lineární optimalizace (tzv. „lineární programování“). a) Formulace úlohy (úloh) - příklad (

(G)

min{f (x) | x ∈ V ⊂ R2 },

max{f (x) | x ∈ V ⊂ R2 }.

kde f (x) = aT x = x1 + 3x2 (lineární funkce), " #

"

#

1 x1 a= . ; x= 3 x2 Přípustná množina V je v obou případech dána nerovnostními podmínkami (vazbami): −x1 + 2x2 x1 + x2 x1 x2

≤ ≤ ≥ ≥

6, 5, 0, 0,

        

   

maticově 

−1 2 1 1 −1 0 0 −1



  . 

"

x1 x2

#

   

≤ 

6 5 0 0



  . 

b) Geometrická ilustrace množin V , D(x, V ), D0 (x), S(x, f ), F (x, f ) . . . obrázek. . . obrázková metoda: je vidět, že max f (x1 , x2 ) = f V

4 11 , 3 3

=

37 , 3

min f (x1 , x2 ) = f (0, 0) = 0. V

c) Reformulace úlohy - převod na kanonický tvar Cílem je ukázat převod úlohy z (G) na tvar s novou přípustnou množinou    

W = {x ∈ R4 : Bx − c = 0, x ≥ 0}, x = 

x1 x2 x3 x4



  ; 

kde matici B vytvoříme tak, abychom z původních nerovnostních vazeb dostali rovnostní vazby přidáním nových proměnných x3 ≥ 0, x4 ≥ 0 takto: −x1 + 2x2 + x3 = 6, x1 + x2 + x4 = 5, f (x) = f (x1 , x2 , x3 , x4 ) = x2 + 3x2 + 0x3 + 0x4 .

B=

"

−1 2 1 0 1 1 0 1

#

; c=

"

6 5

#


89

d) Princip simplexové metody V soustavě Bx − c = 0 máme dvě rovnice pro čtyři neznámé x1 , x2 , x3 , x4 . Budeme postupně volit dvě neznámé a zbývající dopočítávat. Budeme kontrolovat nezápornost (přípustnost) a vypočítávat f .

4! Počet voleb je dán číslem 42 = 4·3·2·1 1·2 = 2! = 6. Proměnné, které volíme nazýváme nebazické proměnné, proměnné, které dopočítáváme, nazýváme bazické proměnné.

x3 = 0 x4 = 0

x2 = 0 x4 = 0

x2 = 0 x3 = 0

x1 = 0 x4 = 0

x1 = 0 x3 = 0

x1 = 0 x2 = 0

x1 = x2 =

4 3 11 3

x1 = 5 x3 = 11

x1 = −6 x4 = 11

x2 = 5 x3 = −4 x2 = 3 x4 = 2

x3 = 6 x4 = 5

    

4 3 11 3









   0 

0 5  0    11 0  −6  0    0 11  0  5    −4 0  0  3    0 2  0  0    6 5 

   

         

   

             









       

   

1 3 − 13



   1 

0 −1 1 −3 0 2 1 0 −3 1 −1 3 0 1

    

− 32 1  0    1 −1

   

    

   

    

   



   0  1 2

   

   

    

   

− 23 − 13 0 1 −1 0 −1 1 1 0 1 −1 0 −1 2 1 0 − 12 1 1 2

0 1 −2 −1

f (x)

nezápornost bazického řešení

nebazické řešení

bazické (parikulární) řešení

dopočítávané proměnné soustavy Bx-c=0

volitelné proměnné (= 0)

Partikulární řešení soustavy Bx − c = 0 se u simplexové metody nazývá bazické řešení. Řešení homogení soustavy Bw = 0 se zde nazývá nebazické řešení.



ano

f = 37 3 (Max)



ano

f =5



ne

—



ne

—



ano

f =9



ano

f =0 (Min)

   

   

   

   

   

   

Tabulka 7.1.1: Sinplexová metoda - výsledky e) Algoritmus simplexové metody je třeba ještě doplnit strategií v jakém pořadí volit nebazické proměnné (1.sloupec). Strategie je založena na výběru tzv. pivota (klíčového prvku).

90

7.2. PODMÍNKY OPTIMALITY

7.2. Podmínky optimality 7.2.1. Lemma Nechť x ∈ V je aktivní bod. Potom platí inkluze (včetně případu, že D0 (x) je prázdná množina) D0 (x) ⊂ D(x, V ) ⊂ D0 (x) navíc platí F (x, f ) ∪ D0 (x) = Rn tj. každý vektor z Rn patří alespoň do jedné z množin F , D0 . ...

7.2.2. Geometrické nutné podmínky lokální optimality b ∈ V bod lokálního minima funkce f , potom Je-li x

b , f ) ∩ D(x b, V ) = ∅ , S(x

b , f ) ∩ D(x b, V ) = ∅ , F (x b , f ) ∩ D0 (x b) = ∅ , S(x

b , f ) ∩ D0 (x b) = ∅ , F (x

b neexistuje přípustný směr, který by byl spádový. tj. v bodě x

Důkaz:. . . ...

7.2.3. Věta o ekvivalenci Nechť x ∈ X je aktivní bod vzhledem k vazbám gi (x) ≤ 0 , i ∈ I (x). Potom následující výroky jsou ekvivalentní. 1. (H)

F (x, f ) ∩ D0 (x) = ∅

2. existují nezáporná čísla ui ≥ 0 , i ∈ I (x) taková, že platí (I)

grad f (x) +

X

i∈I (x)

ui · grad gi (x) = 0,

tj. vektor grad f (x) je lineární kombinací gradientů vazbových funkcí aktivních v bodě x.


91

3. existují nezáporná čísla ui ≥ 0 , i = 1, 2, . . . , m taková, že platí (J)

      

grad f (x) +

(podmínky komplementarity)

m X i=1

ui · grad gi (x) = 0,

ui · gi (x) = 0 , i = 1, 2, . . . , m .

...

7.2.4. Věta o nutných podmínkách lokální optimality Nechť x ∈ V je aktivní bod lokálního minima funkce f : X → R1 na přípustné množině V = {x ∈ X : gi (x) ≤ 0 , i = 1, 2, . . . , m}

b) ⊂ X . a nechť funkce f , gi , i = 1, 2, . . . , m jsou spojitě diferencovatelné v uδ (x

b ), ne všechna nulová, taková, že c0 ≥ 0 , ubi ≥ 0 , i ∈ I (x 1. Potom existují nezáporná čísla u platí X b) + b) = 0 c0 grad f (x (OKKT) u ubi · grad gi (x i∈I (b x)

c0 ≥ 0 , i = 1, 2, . . . , m, ne všechna nulová, taková, že platí 2. Potom existují nezáporná čísla u 

(OKKT)

m X   u b) = 0 b) + c0 grad f (x ubi · grad gi (x i=1   ub · g (x b ) = 0 , i = 1, 2, . . . , m i i

.


b ) , i ∈ I (x b ) jsou lineárně nezávislé (podmínka regularity), potom 3. Když navíc grad gi (x b ), ne všechna nulová, taková, že platí existují nezáporná čísla ubi ≥ 0 ,X i ∈ I (x  b b b) = 0 , grad f ( x ) + u ·  i grad gi (x  I ∈(b x) (KKT) .   b ) = 0 , i = 1, 2, . . . , m (podmínky komplementarity) bi gi (x u respektive 

(KKT)

. . . obrázek. . .

m X   grad f (x b) + b) = 0 , ubi · grad gi (x i=1   u b ) = 0 , i = 1, 2, . . . , m bi gi (x

.


b ) , − grad g3 (x b ) směřují dovnitř b vektory − grad g1 (x Komentář k obrázku: v bodě minima x přípustné množiny V , lze z nich tedy sestavit lineární kombinaci s nezápornými koeficienty u1 ≥ 0 , u3 ≥; takovou, že

. . . obrázek. . .

b ) − u2 grad g2 (x b ). b ) = −u1 grad g1 (x grad f (x

b ) se dá v bodě minima vyjádřit jako lineární komKomentář: Také zde je vidět. že grad f (x b b b ) dá b se grad f (x b b binace vektorů − grad g2 (x) , − grad g3 (x). Naproti tomu v bodě maxima x b b b ). b ) , grad g3 (x vyjádřit jako lineární kombinace vektorů + grad g1 (x

b ) , grad g2 (x b ) lineárně závislé a neplatí zde V případě dalšího obrázku (. . . ) jsou grad g3 (x podmínka (3), ale pouze podmínka (1).

...

92

7.3. METODA NUTNÝCH OKKT, KKT PODMÍNEK - PŘÍKLADY

7.2.5. Poznámka b ∈ V (bod minima, bod maxima) platí gi (x b ) < 0 pro i = 1, 2, . . . , m, pak Když pro x b není žádná vazební podmínka aktivní, tj. I (x b ) = ∅ (prázdná množina), potom vzhledem k x z podmínek komplementarity plyne b1 = 0 , u b2 = 0 , . . . , u bm = 0. u

b0 6= 0 a nutná podmínka (1) se redukuje na Musí proto být u b ) = 0. grad f (x

b , V ) , F (x b , f ) je v bodě To také odráží poznatek, že možina (kužel) spádových směrů S(x minima prázdná.

Dále mesmíme zapomínat, že podmínky (KKT) jsou nutné, nikoliv však postačující ! . . .

7.3. Metoda nutných OKKT, KKT podmínek příklady 7.3.1. Příklad-1 Chceme stanovit řešení úloh min{f (x1 , x2 ) | (x1 , x2 ) ∈ V } , min{f (x1 , x2 ) | (x1 , x2 ) ∈ V } ,

kde

f (x1 , x2 ) = (x1 − x2 )2 + x22 ,

V = {(x1 , x2 ) ∈ R2 : −x1 ≤ 0 , −x2 ≤ 0 , −1 + x21 + x2 ≤ 0}. |{z}

|{z}

g1

g2

{z

|

g3

}

V odstavci (7.1.5.) jsme ukázali princip analýzy řešitelnosti dané úlohy na minimum. Konkrétní poznatky pak byly zobecněny v odstavcích (7.2.2.), (7.2.3.) a (7.2.4.). Nyní se budeme „tvářit“, že neznáme výsledek a chceme pouze stanovit řešení soustavy nutných podmínek. Přípravné výpočty: "

#

"

#

"

#

"

#

2(x1 − 2) −1 0 2x1 grad f = , grad g1 = , grad g2 = , grad g3 = . 2x2 0 −1 1 Chceme tedy stanovit takové x1 , x2 , u0 , u1 , u2 , u2 , aby platila soustava (OKKT), resp. (KKT) podmínek: (S)

u1 · grad f (x1 , x2 ) + u1 · grad g1 (x1 , x2 ) + u2 · grad g2 (x1 , x2 ) + u3 · grad g3 (x1 , x2 ) = 0 ;

podmínky komplementarity (K)

u1 · g1 (x1 , x2 ) = 0 , u2 · g2 (x1 , x2 ) = 0 , u3 · g3 (x1 , x2 ) = 0 ,


93

znaménkové podmínky (Z) (Z1 )

u 1 ≥ 0 , u 2 ≥ 0 , u 3 ≥ 0 ; pro minimum

(Z2 ) a podmínky řešitelnosti (P)

u1 ≤ 0 , u2 ≤ 0 , u3 ≤ 0 ;pro maximun

−x ≤ 0 , −x2 ≤ 0 , −1 + x21 + x2 ≤ 0}

(P)

|{z}1

|{z}

g1

Takže konkrétně máme:

(

(S)

|

g2

{z

}

g3

[u0 2(x1 − 2)] − u1 + u3 · 2x1 = 0 , [u0 2x2 ] − u2 + u3 = 0 ,

u1 x1 = 0 , u2 x2 = 0 , u3 (−1 + x21 + x2 ) = 0 .

(K)

Máme zde 5 rovnic (nelineárních) a 6 nerovnic pro 6 neznámých x1 , x2 , u0 , u1 , u2 , u3 ; také musíme požadovat, že ui nesmí být všechna nulová ! Strategie: Volíme buď u0 = 0 (viz OKKT), nebo u0 = 1 (viz KKT), pak postupně prošetřujeme možnosti splnění podmínek (K); volíme buď xi , nebo ui . Je zřejmé, že tato strategie je vhodná (proveditelná) pouze pro úlohy s malým počtem vazebních podmínek. Pro složitější úlohy je metoda přímého využití nutných podmínek optimality mimo realitu. Volba u0 = 0 - nabízí se další volby a jejich důsledky: (

(S)

−u1 + u3 · 2x1 = 0 ,

−u2 + u3 = 0 ,

u1 x1 = 0 , u2 x2 = 0 , u3 (−1 + x21 + x2 ) = 0 .

(K) znaménkové podmínky (Z) (Z1 )

u 1 ≥ 0 , u 2 ≥ 0 , u 3 ≥ 0 ; pro minimum

(Z2 ) a podmínky řešitelnosti (P)

u1 ≤ 0 , u2 ≤ 0 , u3 ≤ 0 ;pro maximun

−x ≤ 0 , −x2 ≤ 0 , −1 + x21 + x2 ≤ 0}

(P)

|{z}1

|{z}

g1

(S)

g2 (S)

|

{z g3

}

a) x1 6= 0 , x2 6= 0 : −−→ u1 = 0 , u2 = 0 −−→ u3 = 0 ; ⇒ neřešitelná soustava, ∀ ui = 0 ! (S)

(K)

b) x1 = 0 , x2 6= 0 : −−→ u2 = 0 −−→ u3 = 0 , u1 = 0 ; ⇒ neřešitelná ! (S)

(K)

(S)

(K)

c) x1 6= 0 , x2 = 0 : −−→ u1 = 0 , −−→ , u3 = 0 , u2 = 0 ; ⇒ neřešitelná !

d) x1 = 0 , x2 = 0 : −−→ u3 = 0 , −−→ , u2 = 0 , u1 = 0 ; ⇒ neřešitelná !

Závěr: Při volbě u0 = 0 nejsou podmínky (S), (K), (Z), (P) současně splnitelné. Volba u0 = 1 Nyní máme (S)

(K)

(

2(x1 − 2) − u1 + 2x1 u3 = 0 ,

2x2 − u2 + u3 = 0 ,

u1 x1 = 0 , u2 x2 = 0 , u3 (−1 + x21 + x2 ) = 0 .

94

7.3. METODA NUTNÝCH OKKT, KKT PODMÍNEK - PŘÍKLADY

(Z1 )

u1 ≥ 0 , u2 ≥ 0 , u3 ≥ 0 ;

(Z2 )

u1 ≤ 0 , u2 ≤ 0 , u3 ≤ 0 .

x1 ≥ 0 , x2 ≥ 0 , −1 + x21 + x2 ≤ 0

(P)

A opět postupně prověříme nám již známe možnosti a)

x1 6= 0 , x2 6= 0 : musi být: (K)

−−→

b)

(S)

(K)

−−→ u1 = 0 , u2 = 0 , −−→ 2x2 + u3 = 0 , 2x1 − 4 + 2x1 u3 = 0 , x1 (2 + 2u3 ) = 4 x1 > 0 , x2 > 0 (plyne z (P)), u3 6= 0 (požadavek nenulovosti) −1 + x21 + x2 = 0

(Z1 ) →

u3 > 0 je v rozporu s požadavkem 2x2 + u3 = 0 takže podmínky nezápornosti nejsou splněny !

(Z2 ) →

u3 < 0 , −−→ x2 = − u23 , x1 =

x1 = 0 , x2 6= 0 : (S)

−−→ (Z1 ) → (Z2 ) →

(S)

2 1+u3 , → u3 > −1 −1 + x21 + x2 = 0 dostaneme

Po dosazení do podmínky u33 + 4u23 + 5u3 − 6 = 0. Tato rovnice nemá v intervalu (−1, 0) kořen ! Podmínky nekladnosti také nejsou splněny !

u2 = 0 , u3 (−1 + x2 ) = 0 , z (P) : x2 > 0 , volba u3 = 0 nepřipadá v úvahu, protože je v rozporu s podmínkou x2 6= 0 ; pak musí být: x2 = 1 2(−2) − u1 = 0 → u1 = −4 2 + u3 = 0 → u3 = −2 neřešitelné v bodě (0, 1) jsou splněny podmínky nekladnosti a podmínka grad f (0, 1) + u1 · grad g1 (0, 1) + u3 · grad g3 (0, 1) = 0 má tvar "

#

"

#

" #

" #

−4 −1 0 0 + (−4) + (−2) = . 2 0 1 0

c)

x1 6= 0 , x2 = 0 :

(Z1 ) →

(Z2 ) → d)

x1 = 0 , x2 = 0 :

u1 = 0 , u3 (−1 + x21 ) = 0 ; z (P) : x1 > 0 , 2(x1 − 2) + 2x1 u2 = 0 , −u2 + u3 = 0 ; varianta u3 = 0 nepřipadá v úvahu u3 6= 0 vede k hodnotě x1 = 1 (kořen x1 = −1 není přípustný) u3 = 1 , u2 = 1 a (K)má tvar "

#

"

#

" #

" #

−2 0 2 0 +1· +1· = . 0 −1 1 0 neřešitelné Pozor ! Zjistíme, že pro: u1 = −4 , u2 = 0 , u3 = 0 jsou podmínky (S) splněny, ale bod (0, 0) nemůže být bodem minima ani maxima.

7.3.2. Příklad-2 Chceme stanovit řešení úloh min{f (x1 , x2 ) | (x1 , x2 ) ∈ V } ,


95

min{f (x1 , x2 ) | (x1 , x2 ) ∈ V } ,

kde

f (x1 , x2 ) = (x1 − 2)2 + x22 ,

V = {(x1 , x2 ) ∈ R2 : −x1 ≤ 0 , −x2 ≤ 0 , x2 − (1 − x1 )3 ≤ 0}. |{z}

|{z} g1

. . . bude obrázek. . .

{z

|

g2

}

g3

Přípravné výpočty: "

#

"

#

"

#

"

#

2(x1 − 2) −1 0 3(1 − x1 )2 grad f = , grad g1 = , grad g2 = . , grad g3 = 2x2 0 1 −1 Chceme tedy stanovit takové x1 , x2 , u0 , u1 , u2 , u2 , aby platily (OKKT) podmínky: #

"

"

"

#

" #

#

2(x1 − 2) −1 0 0 + u1 u0 + u2 + u3 3(1 − x)2 = , 2x2 0 −1 0

(S)

podmínky komplementarity

u1 (−x1 ) = 0 , u2 (−x2 ) = 0 , u3 x2 − (1 − x1 )3 = 0 .

(K) Buď

u1 ≥ 0 , u2 ≥ 0 , u3 ≥ 0 ;

(Z1 ) nebo (Z2 )

u1 ≤ 0 , u2 ≤ 0 , u3 ≤ 0 ;

a podmínky

x1 ≥ 0 , x2 ≥ 0 , x2 − (1 − x1 )3 ≤ 0 .

(P)

Postupujeme podle stejné strategie jako v odst. (7.3.1.). Volba u0 = 0 a) b) c)

d)

(K)

(S)

x1 6= 0 , x2 6= 0 :

−−→ u1 = 0 , u2 = 0 , −−→ u3 = 0 neřešitelné !

x1 = 0 , x2 6= 0 :

−−→ u2 = 0 , −−→ u3 = 0 , u1 = 0 neřešitelné !

x1 6= 0 , x2 = 0 : možnost: možnost:

x= 0 , x2 = 0 :

(K)

(S)

??

−→ u1 = 0 , u3 = −(1 − x1 )3 ; u3 = 0 vede k neřešitelným (1) podmínkám; u3 6= 0 vede k x1 = 1. Pouze konstatujme, že v bodě (1, 0) jsou grad g1 , grad g2 kolineární. Nelze rozhodnout, zda jde o bod minima. (K)

(S)

−−→ u3 = 0 , −−→ u2 = 0 , u1 = 0 neřešitelné !

Volba u0 = 1 (

(S)

a)

x1 6= 0 , x2 6= 0 :

2(x1 − 2) − u1 + 3u3 (1 − x1 )2 = 0

2x2 − u2 + u3 = 0

 

(S)

u3 6= 0 , −−→ x2 − (1 − x1 )3 = 0 −−→ u1 = 0 , u2 = 0 , u = 0 , neřešitelné 3 (K)

96

7.3. METODA NUTNÝCH OKKT, KKT PODMÍNEK - PŘÍKLADY 2(x1 − 2) + 3u3 (1 − x1 )2 = 0 2x+ u3 = 0 , → u3 = −2x2 Protože x1 > 0 , x2 > 0 (podmínka řešitelnosti), potom je u3 ≤ 0 a muselo by být x1 − 2 = − 23 u3 (1 − x1 )2 ≥ 0 , což je ve sporu s přípustností ! Podle (S):

b)

c)

x1 = 0 , x2 6= 0 :

x1 6= 0 , x2 = 0 :

 (K) u = 0 , − −→ x2 = 0 , spor ! 3 −−→ u2 = 0 , (S) (K)  (K)

u3 6= 0 , −−→ x2 = 1 , −−→ u2 = −2 , → u1 = 10 v bodě (0, 1) je možné maximum ! (K)

−−→ u1 = 0 ,

 

(K)

(S)

u3 6= 0 , −−→ x1 = 1 , −−→ −2 = 0 ! u = 0 , neřešitelné ! 3

V bodě (1, 0) nelze všechny požadavky splnit. d)

x1 = 0 , x2 = 0 :

opět vede ke sporu s řešitelností podmínek (S)a (K).

Závěr: v bodě (1, 0) lze splnit pouze podmínky (OKKT), nikoliv však (KKT).

7.3.3. Analýza KKT bodů V úlohách odstavce (7.3.1.) a (7.3.2.) jsme se snažili najít řešení soustavy nutných podmínek optimality. Nyní se na tentýž problém podíváme z pohledu poznatků odstavce (7.2.2.). Pro úlohy z odstavce (7.3.2.) (viz obrázek) jsme našli dva body (x1 , x2 ) = (1, 0) , (x1 , x2 ) = (0, 1) , v nichž jsou splněny nutné podmínky (OKKT) a (KKT) V bodě x = (0, 1) bychom zjistili, že FA D0 6= 0 (jde zřejmě o bod maxima).

Kužel spádových směrů v bodě x = (1, 0) b , f ) = {d ∈ R2 , dT grad f (x) < 0 , kdk = 1} : d = [d1 , d2 ]T , d21 + d22 = 1. F (x "

#

2(x1 − 2) grad f (x) = 2x2 "

(1,0)

"

#

−2 = , 0

#

−2 d ∈ F ⇔ [d1 , d2 ] · < 0 ⇒ d1 > 0 , d2 libovolné. 0 Otevřený kužel přípustných směrů v bodě x = (1, 0) b ) = {p ∈ R2 : pT grad gi (x b ) < 0 , i ∈ I (x b ) , I (x b ) = {2, 3}. D0 (x "

#

"

0 −3(1 − x1 )2 b) = b) = grad g2 (x , grad g3 (x −1 1 "

#

0 p ∈ D0 ⇒ [p1 , p2 ] · <0 : −1 " #

0 [p1 , p2 ] · <0 1

:

p1 libovolné p2 > 0 p1 libovolné p2 < 0

Závěr: F ∩ D0 = ∅ , ale (KKT) podmínky nejsou splněny.

   ,      , 

#

(1,0)

⇒

=

" #

0 . 1

b) = ∅ D0 (x


97

Uzavřený kužel přípustných směrů v bodě x = (1, 0) b ) = {s ∈ R2 : sT grad gi (x b ) ≤ 0 , i ∈ I (x b )} , I (x b ) = {2, 3}. D 0 (x "

#

0 s ∈ D 0 ⇒ [s1 , s2 ] · ≤0 −1 " #

:

0 [s1 , s2 ] · ≤0 1

:



s1 libovolné     s2 ≥ 0 , 

 s1 libovolné     s2 ≤ 0 ,

b ) = {s1 libovolné , s2 = 0} ⇒ D 0 (x

Závěr: F ∩ D 0 6= ∅ , ale (OKKT) podmínky jsou splněny, neboť jde zřejmě o bod minima.

7.4. Lagrangeova funkce a Lagrangeova úloha 7.4.1. Lagrangeova funkce Pro optimalizační úlohy z odstavce (7.1.) definujeme standardní Lagrangeovu funkci L : X × Rm → R1 předpisem (Ka)

L(x, u) = f (x) +

m X i=1

ui gi (x) , x ∈ X ⊂ Rn , u ∈ Rm ,

tj.

(Kb)

  

L(x, u) = f (x) + uT g(x) , u =   

u1 u2 .. . um





     , g(x) =     

g1 (x) g2 (x) .. . gm (x)



  .  

Obecnou Lagrangeovu funkci L : X × R1 × Rm → R1 definujeme předpisem (La)

L(x, u) = f (x) +

m X

ui gi (x) ,

i=1

tj. (Lb)

L(x, u) = f (x) + uT g(x) ,

Užíváme stejné názvosloví, jako v odst. (4.5.2). Pouze didaktické důvody nás vedou k vytvoření samostatného výkladu pro rovnostní vazby (odst. 4.5) a nerovnostní vazby (odst. 7.4.).

7.4.2. Lagrangeova úloha (S) (K) (P)

Pro u0 = 1, resp. u0 = 0 chceme stanovit x ∈ X ⊂ Rn , u ∈ Rm takové, že platí gradx L(y, u) = 0 , (soustava KKT, příp. OKKT),

ui gi (x) = 0 , i ∈ I (x) , (komplementarita), u1 ne všechny nulové gradu L(x, u) ≤ 0 , (přípustnost),

98

7.5. LAGRANGEOVA METODA (PRINCIP)

a požadavek znaménka multiplikátorů (

(Z)

buď u ≥ 0 pro úlohu na minimum, nebo u ≤ 0 pro úlohu na maximum.

Lagrangeova úloha je fakticky formalizací úlohy stanovit řešení soustavy nutných podmínek optimality. Hledáme tedy taková řešení soustavy (S), která splňují podmínky komplementarity (K), podmínky přípustnosti (P) a požadavek znaménka (Z). Řešení Lagrangeovy úlohy se často nazývá KKT-body (příp. OKKT-body). Říkat těmto bodům stacionární body Lagrangeovy funkce není vhodné u úloh s nerovnostními vazbami.

7.5. Lagrangeova metoda (princip) V tomto odstavci budeme ilustrovat Lagrangeovu metodu na konkrétních optimalizačních úlohách. K finálnímu rozhodnutí o výsledku je ještě potřeba nějaká podoba postačující podmínky optimality. Držíme se strategie výpočtů z odst.(7.3.).

7.5.1. ? Mějme úlohu minimaliazce (maximalizace) funkce f (x1 , x2 ) = x21 + x2 na přípustné množině V = {(x1 , x2 ) ∈ R2 : x21 + x22 − 9 ≤ 0 , x1 + x2 − 1 ≤ 0}. Zde máme L(x1 , x1 , u0 , u1 , u2 ) = u0 (x21 + x22 ) + u1 (x21 + x22 − 9) + u2 (x1 + x2 − 1) "

#

"

#

" #

" #

(S)

2x1 2x1 1 0 + u1 u0 = , + u2 1 2x2 1 0

(K)

u1 (x21 + x22 − 9) = 0 , u2 (x1 + x2 − 1) = 0 .

Volba u0 = 0 a)

x1 6= 0 , x2 6= 0 :

volba u1 6= 0 , u2 = 0 → vede ke sporu (S) a (K) ; volba u1 = 0 , u2 = 6 0 → neřešitelná (S) a (K) .

b)

x1 = 0 , x2 6= 0 :

neřešitelná (S) pro nenulové ui ;

c)

x1 6= 0 , x2 = 0 :

neřešitelná (S) pro nenulové ui ;

d)

x1 = 0 , x2 = 0 :

neřešitelná (S) pro nenulové ui .

Volba u0 = 1

7. ÚLOHY PODMÍNĚNÉ OPTIMALIZACE - NEROVNOSTNÍ VAZBY a) u1 6= 0 , u2 6= 0 :

√ √ √ √ 1 − 17 1 + 17 1 + 17 1 − 17 Z (K) dostáváme x1 = , x2 = , x1 = , x2 = , 2 2 2 √ √2 1 1 −1 − 17 17 − 1 > 0 , u1 = − < 0 , u2 = <0 Z (S) vyjde u1 = − < 0 , u2 = 2 1 2 2 (x1 , x2 ) není KKT bod ; (x1 , x2 ) je KKT bod.

b) u1 = 0 , u2 6= 0 :

Z (S)máme u1 = −1 , x1 =

1 1 ; Z (K) x2 = ; 2 2

(x1 , x2 ) je KKT bod. c) u1 6= 0 , u2 = 0 :

√ 1 35 Z (S)máme u1 = −1 , x3 = ; z (K) x1 = − ; 2 2 (x1 , x2 ) je KKT bod, nebo x1 = 0 , z (K) x3 = −3 ; (x1 , x2 ) je také KKT bod.

d) u1 6= 0 , u2 = 0 : (S) není řešitelná. Závěr:

Pozor:

! √ 35 1 , = 9 = max f ; f − 2 2 f (0, −3) = −3 = min f ;

Ne každý KKT bod je bodem extrému !

99

100

7.5. LAGRANGEOVA METODA (PRINCIP)

Kapitola 8

Sebrané speciality

101

102

Literatura [1] Míka, S.: Matematická optimalizace. ZČU Plzeň, 1997. [2] Míka, S.: Numerické metody algebry. Praha, SNTL 1982. [3] Drábek P. - Míka, S.: Matematická analýza I. ZČU Plzeň, 4. vydání, 1998. [4] Drábek P. - Míka, S.: Matematická analýza II. ZČU Plzeň, 3. vydání, 1997. [5] Alexejev, V.M. - Tichomirov, V.M. - Fomin, S.V.: Matematická teorie optimálních procesů. Praha, Academia 1991. [6] Alexejev, V.M. - Galejev, E.M. - Tichomirov, V.M.: Sbornik zadač po optimizacii. Moskva, Nauka 1984 (v ruštině). [7] Aoki, M.: Introduction to optimization techniques, University of California, Los Angeles The Millan Company, New York Collier - Mac Millan Limited, London, 1975 (Překlad do ruštiny: Moskva, Nauka 1977). [8] Avriel, M.: Nonlinear programming: Analysis and Methods New Jersey Prentice-Hall, Englewood Cliffs, 1976. [9] Bazaraa, M.S. - Sheety, C.M.: Nonlinear Programming. Theory and Algorithms. New York, 1979. (Překlad do ruštiny: Moskva, Mir 1982). [10] Lukšan, L.: Numerické optimalizační metody. Nepodmíněná optimalizace. UI AVČR, Technical report No.1058, Praha 2009. [11] Bartoňková, K.: Numerická optimalizace v ekonomii. Diplomová práce, PřF UP Olomouc, 2008. Komentář: [1] Nedokonalost této učebnice a její jistá tématická „přeplněnost“ byla hlavní inspirací pro vznik předloženého textu. [2] Určuje rozsah nutných poznatků z numerické matematiky. [3],[4] Potřebné poznatky z matematické analýzy lze ovšem čerpat i z dalších standardních zdrojů. [5],[6] Také další knihy autorů byly inspirací pro zpracování našeho textu. [7] Inspirace nejen pro název našeho textu [8],[9] Asi nejzdařilejší knihy věnované optimalizaci. Nevyčerpatelná inspirace. Lepší výklad asi nelze vymyslet. [10] Shrnutí současných výsledků numerických metod nepodmíněné optimalizace. Vhodný základ pro studium v rámci doktorského studia. [11] Vhodný doplňující text využívající Mathlab. Také pro informace o ekonomických optimalizačních úlohách. 103

MATEMATICKÉ OPTIMALIZAČNÍ TECHNOLOGIE

Recommend Documents