MOT - Matematické optimalizační technologiehome.zcu.cz/~mika/MO/S_Mika_L_Vlcek_MOT.pdf ·...

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ěja-ké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 jehozá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řed-loženým textem. V úvodní kapitole chceme čtenáře seznámit s klasickými i moderními op-timalizačními úlohami. Nezávisle na podrobnějším výkladu v dalších kapitolách, chceme nakonkrétních a z velké části klasických úlohách vyložit i principy metod řešení formulovanýchoptimalizačních úloh. Také zde uvedeme formulaci úloh a shrneme některé podmínky řešitel-nosti.

Druhá kapitola je shrnutím těch matematických pojmů a poznatků, které umožní sro-zumitelně 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 asoustřeďujeme se na výklad principů metod a odpovídajících algoritmů, tedy tomu, co sidovolujeme 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ů), JohanBernoulli (Úloha brachystochrony), Leonhard Euler (Variační počet), Lagrange (Princip mul-tiplikátorů). V antice byly formulovány úlohy především geometrického charakteru. V počína-jícím novověku byly v popředí zájmu úlohy fyzikálního typu (minimalizace energie, podmínkyrovnová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. Zdese také pro tyto úlohy poprvé objevuje termín „programování“, používaný ve vojenském žar-gonu 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 . . . . . . . . . . . . . . . . . . . . . . 48

3.2. Hladkost v R1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 = π , λ= 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.3.11lD < π , λ > 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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

6.3.2 Bod x je bod lokálního minima f na V . . . . . . . . . . . . . . . . . . . . . . 80

6.3.3 x není bod minima (extrému) f na V . . . . . . . . . . . . . . . . . . . . . . . 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ýchmetod.

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|) =?

p

X

X

X

A

B

|AX|+ |BX| → min

Obrázek 1.1.1: geometrická interpretace

x

y

A = [0, a]

X = [x, 0]

B = [b, d]

A′ = [0,−a]

Obrázek 1.1.2: formalizace

Geometrická metoda:Sestrojíme bod A′, který je osově symetrický podle dané přímky. Hledaný bodX je průsečíkempří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 euklei-dovských vzdáleností)

f(x1,x2) =√

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

(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

x2 =−ax1 − c

b

a dosadíme do funkce f . Dostaneme funkci jedné proměnné

F (x2) = f(x1,−ax1 + c

b) , x1 ∈ R

1

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 zaosu x, budeme přímo minimalizovat funkci

ϕ(x) =√x2 +a2 +

√(x−d)2 + b2 , x ∈ R

1 ,

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

1.1.2. Partikulární řešení soustavy s minimální (euklidovskou) nor-mou

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 ∈ R

p je daný sloupec (vektor). Všechna řešení tvoří množinu

Vc = {c ∈ Rn : Bx − c = 0}

Ze všech x ∈ Vc chceme najít takové x ∈ VC , které má nejmenší euklidovskou normu, tj. platí

||x||2 ≡ xT x ≤ xT x , ∀x ∈ Vc .

Geometricky to znamená, že na lineární varietě Vc hledáme takový bod, který je nejblížepočátku (pata kolmice spuštěné z počátku na množinu Vc).

Je vhodné hledat minimum a bod minima kvadratické funkce f(x) =12

xT x , x ∈ Vc.

Výklad metody se opírá o princip redukce dimenze a o některou podmínku optimality(viz kapitola 6)

Zaznamenáme pouze „technologii“ výpočtu bodu x:

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

2. stanovíme x = BT v ; obraz vektoru v ∈ Rp v zobrazení BT : R

p → Rn (je to fakticky

podmínka nulovosti derivace funkce f ve směru množiny Vc)

1. ÚVOD DO OPTIMALIZACE 15

Konretizace:Na přímce Vc = {x1,x2 ∈ R

2 : 3x1 +4x2 = 8} (viz obr.1.1.3) chceme najít takový bod (x1, x2),který je nejblíže k počátku. Je zřejmé, že:

B = [3,4] ; BT =

[34

]; BBT = 25 ; (BBT )−1 =

125

v =825

; x =

[34

]· 825

=125

·[

2432

].

x1

x2

[0, 0]

[0,2]

[2.66,0]

x = [x1, x2]y=[2.5,1]

yp

wp

X = [x1, x2]

Vc

V0

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 principunutný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

xT 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 ∈ R

n.

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žinuV0 = {w ∈ R

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

n.

V0

V⊥

0

Vc

0

y

x

wp = Py

yQ = Qy

yP

x

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

Symbolem V⊥0 označujeme tzv. ortogonální doplněk prostoru V0. Prvek x ∈ Vc, pro

který je také x ∈ V⊥c , je partikulárním řešením soustavy Bx − c = 0 s minimální normou.

Chceme popsat, jak určíme řešení naší úlohy, tj. prvek yp ∈ Vc, který je ortogonálnímprůmětem prvku y ∈ R

n na Vc a tedy bodem minima vzdálenosti ||x − y||, x ∈ Vc.

Popíšeme opět pouze technologii stanovení bodu yp.

1. Stanovíme x ∈ V⊥0 technologií z odst.1.1.2., tj.

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

2. Stanovíme yQ ∈ V⊥0 , tj. ortogonální průmět prvku y ∈ R

n na V⊥0 :

yQ = BT (BBT )−1By ;

3. Stanovíme xP ∈ V0 , tj. ortogonální průmět prvku y ∈ Rn na V0:

wp = y − yQ = (I − BT (BBT )−1B)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 )−1B je řádu n a je to matice ortogonální projekce z Rn na lineární

prostor V⊥0 .


4. Hledaný průmět yp prvku y ∈ Rn na lineární varietu Vc:

yp = x + wp = x + Py .

Konkretizace:Na přímce Vc = {x1,x2} ∈ R

2 : 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].

Zde, podobně jako v příkladu odst.1.1.2. vypočteme x =125

·[

2432

];

Potom

yQ =

[34

]· 125

· [3,4] ·[

21

]=

125

·[

3040

];

wp =

[21

]− 1

25·[

3040

]=

[2025

−1525

];

yp = x + wp =

[44251725

].

1.2. Úlohy typu maximalizace míry (obsahu, ob-jemu)

V tomto odstavci shrneme nejznámější „školské“ optimalizační úvahy, které se vysky-tují 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 maximumnějaké funkce více proměnných s podmínkou, že mezi těmito proměnnými exis-tuje vazba zadaná jednou, nebo několika rovnicemi, je třeba přičíst k minima-lizované (maximalizované) funkci určující rovnice vazby vynásobené neurčitýmimultiplikátory a pak hledat minimum nebo maximum tohoto součtu tak, jakoby byly nezávislé. Získané rovnice spolu s rovnicemi vazeb umožní určit všechnynezná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 tohotovrcholu musí splňovat podmínku (bod X leží na kružnici)

x2 +y2 = r2 , r > 0 .

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

Obrázek 1.2.5: geometrická interpretace

x

yX = [x, y]

Obrázek 1.2.6: formalizace

chceme maximalizovat obsah čtyřúhelníka

f (x,y) = 4xy

pro ty rozměry, které patří do množiny

V = {(x,y) ∈ R2 : x2 +y2 = r2 , x≥ 0 , y ≥ 0} .

je zřejmé, že pro libovolná nezáporná x,y bude min 4xy = 0 a maximum nebude existovat, tj.

min(x,y)∈R2

+

4xy = 0 ; max(x,y)∈R2

+

4xy = +∞

Tecnologie redukce počtu proměnných (redukce dimenze)

Pro x > 0 bude y =√r2 −x2 > 0 a obsah vyjádříme jako funkci jedné proměnné, tj.

f (x,y) = f (x,√r2 −x2) ozn.= F(x) = 4x

√r2 −x2 , x ∈ (0,+∞) .

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

Dostanemex=

r√2, y =

r√2.

Hledaným pravoúhelníkem je čtverec o obsahu f (x,y) = 2r2 .

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 +y2 − r2) .

Z podmínek lokálního maxima (x > 0 , y > 0 , v ∈ R1)

∂L

∂x= 4y+ 2xv = 0 ,

∂L

∂y= 4x+ 2yv = 0 ,

∂L

∂v= x2 +y2 − r2 = 0 ,

dostaneme2y = −xv , 2x= −yv , a tedy x= y .


Výsledek:x=

r√2, y =

r√2, v = −2 .

Technologie penaltové funkce

K maximalizované funkci přičteme kladný násobek mocniny anulované vazební pod-mínky (tzv. penaltu), tj. sestrojíme funkci

F(x,y,p) = 4xy+p(x2 +y2 − r2)2 .

Z podmínek lokálního extrému funkce F , (x > 0 , y > 0 , p > 0), tj. podmínek

∂F

∂x= 4y+ 2(x2 +y2 − r2) · 2px= 0 ,

∂F

∂y= 4x+ 2(x2 +y2 − r2) · 2py = 0 ,

dostanemex= y , 1+p(2x2 − r2) = 0 , 1+p(2y2 − r2) = 0 .

odtud

xp = yp =

√r2

2− 1

2p.

Pro p→ +∞ bude xp → x= r√2, y = r√

2.

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

x= y = y =1√3, v = − 1

2√

3.

Odpověď: je to krychle!

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

x= y = z = 1 , v = −2 .

Odpověď: je to krychle.

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 Li-banonu) král Muttoial. Po jeho smrti připadl trůn jeho dětem – dceři Didó a synovi Pyg-malionovi. 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ýmlobistou. 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. Bratrprincezny Didó, princ Pygmalion, však zatoužil po majetku a postavení svého švagra a tak honechal zabít. V té době, příznivci prince Pygmaliona zastoupení ve vládě, požadovali vládupouze jednoho panovníka. Tak začalo pronásledování princezny Didó. Traduje se, že princeznastač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íhoTuniska. Díky „zachráněné“ části státního pokladu byla Didó relativně bohatá a tak chtěla odmístního vládce koupit pozemek k založení osady. Místní vládce, král Hiarbo, oslněn krásouprincezny Didó s prodejem pozemku na mořském pobřeží souhlasil. Vymínil si však, že „nevětší, než jaký lze ohraničit volskou kůží“. Zřejmě ale nepočítal s tím, že krásná princeznaDidó může být také chytrá. Rozřezala volskou kůzi na tenké proužky, které svázala a takzí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áklademmocného města, dnes bychom řekli supervelmoci tehdejšího světa – Kartága.


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ýmiplochami předepsaného obsahu máme najít takovou plochu, která ohraničuje největší objem.

a) První Didonina úlohaMezi všemi oblouky AB délky L ležícími v polorovině ohraničené přímkou p, pevnýmkoncový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 úlohaMezi všemi oblouky délky L ležícími v polorovině ohraničené přímkou p a danými (pev-nými) body A,B ∈ p, najít takový oblouk, který spolu s úsečkou AB ohraničuje obrazecnejvětšího obsahu.

c) Třetí didonina úlohaMezi všemi oblouky ležícími v polorovině ohraničené přímkou p a danými (pevnými) bodyA,B ∈ p najít takový oblouk (křivku), který má pro daný obsah spolu s úsečkou ABnejkratší délku.

. . . 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 osyx 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 ∈ 〈0,1〉, splňující podmínky y(0) = 0, y(1) = 0 s konstantní délkou grafu

lD =

1∫

0

√1+ (y′(x))2 dx


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 funkcey = y(x, x ∈ 〈0,1〉). Tento obsah vyjádříme integrálem

f(y) =

1∫

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í

V = {y ∈ C2(〈0,1〉)} : y(0) = 0 , y(1) = 0 ,

1∫

0

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

použijeme myšlenku Lagrangeova principu (viz odst.1.2.) a sestrojíme integrál (tzv. Lagran-gián) tak, že k integrálu f(y) přičteme vazební podmínku

∫ 10

√1+ (y′(x))2 dx− lD = 0 vyná-

sobenou neurčitým multiplikátorem λ ∈ R1, tj.

L(y,λ) =

1∫

0

y(x)dx+λ

1∫

0

√1+ (y′(x))2 dx− lD

, λ ∈ R

1 .

Na Lagrangián L se díváme jako na funkci dvou proměnných a „zvolíme“ nutné podmínkyextrému v optimálním bodě (y, λ) : y = y+αh , λ= λ+βν ;

ddα

L(y,αh,λ)|α=0 = limα→0

1α

[L(y+αh,λ)−L(y,λ)] = 0 ,

ddβ

L(y, λ+βν)∣∣∣β=0

= limβ→0

1β

[L(y, λ+βν)−L(y, λ)

]= 0 .

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

Dostaneme soustavu pro neznámé y a λ:

(A)1∫

0

h(x)dx+λ

1∫

0

y′(x)h′(x)√1+ (y′(x))2

dx= 0 ,

(B)1∫

0

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

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

1∫

0

[1−

(λy′(x)√

1+ (y′(x))2

)′]h(x)dx= 0 .

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

ddx

[λy′(x)√

1+ (y′(x))2

]= 1 .

Přímou integrací a dalšími manipulacemi postupně dostáváme

λ · y′

1+ (y′)2= x+C1 , C1 je integrační konstanta.

λ2 · (y′)2

1+ (y′)2= (x+C1)2 ,

λ2 · (y′)2 = (x+C1)2 ·[1+ (y′)2

],


λ2 · (y′)2 = (x2 + 2C1x+C21) ·[1+ (y′)2

],

λ2 · (y′)2 = x2 + 2C1x+C21 + (y′)2x2 + 2C1(y′)2x+C2

1(y′)2 ,

λ2(x′)2 − (y′)2x2 − 2C1(y′)2x−C21(y′)2 = x2 + 2C1x+C2

1 ,

(y′)2 ·[λ2 − (x2 + 2C1x+C2

1)]

= (x2 + 2C1x+C21) ,

(y′)2 ·[λ2 − (x+C1)2

]= (x+C1)2 ,

|y′| =|x+C1|√

λ2 − (x+C1)2, λ2 > (x+C1)2 .

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

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

Z okrajových podmíneky(0) = y(1) = 0

dostaneme

C1 = −12, C2 =

√λ2 − 1

4, λ2 ≥ 1

4,

a (C) vede na systém kružnic s parametrem λ:

(x− 1

2

)2

+

(y−

√λ2 − 1

4

)2

= λ2 .

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

1∫

0

λ√λ2 − (x+ 1

2)2dx= lD .

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


Obrázek 1.3.10: lD = π , λ= 12


Obrázek 1.3.11: lD < π , λ > 12

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á, žebylo 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 znamena-jí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 vestarově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ádlodalší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é spisyve vztahu k čemukoliv kartaginskému používají termín, „punský“. Latinský termín punicusodvozený 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ýmislony 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, kdystál před branami Říma, měl kritický nedostatek skoro všeho vojenského materiálu, zásobamipotravin 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 vedlyk úpadku ekonomické a politické síly Kartága. Úpadek ještě umocnily velmi tvrdé sankceuvalené na Kartágo vítězem, jako podmínka k zastavení bojů. Zda došlo k úpadku Kartágadíky prohraným válkám, nebo zda úpadek města, jeho rozmařilost, způsobila, že díky tomuKartá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íhoměsta vystavěli na jeho rozvalinách Kartágo nové, nyní již ale římské. Téměř všechny kar-taginské památky, buď písemné, či stavební byly po vyhraných válkách Římany metodickyničeny. Není se čemu divit, Řím většího a nebezpečnějšího nepřítele do té doby i od té dobyneměl. Většina z dochovaných záznamů, či překladů původních textů, „pochází“ od římskýchhistoriků. 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 vy-vracejí.

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 knizeNové výpočty vinných sudů („Nova stereometrica doliorum vinariorum“) Kepler píše: „Vroce, kdy jsem se ženil, byla velmi dobrá úroda vinných hroznů a víno bylo levné, a protojsem se chtěl jako dobrý hospodář zásobit vínem. Koupil jsem ho několik soudků. Za nějakoudobu 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 bylvelmi udiven. Zdálo se mu divné, že pomocí jednoho měření lze vyčíslit objem sudů různýchtvarů.

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-


vého geometrického citu vyráběli bednáři sudy takového tvaru, který pro danou délku obrysuzaruč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. Pozna-menejme ještě, že Kepler řešil několik konkrétních extremálních úloh, zejména úlohu o válcinejvětšího objemu, vepsaném do koule.

V současné době se specialisté zabývají úlohami tzv. tvarové optimalizace, v nichž seza 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 solutionemmathematici invitantur“ („Nová úloha, k jejímuž řešení zveme matematiky“) byla formulo-vána úloha: „Ve vertikální rovině jsou dány dva body A a B. Najděte dráhu, po níž se tělesopůsobením vlastní tíže dostane z bodu A do bodu B za nejkratší dobu.“ Tuto úlohu řešilidá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émpodle obrázku 1.4.12

x

y

A = [0, 0]

M = [x, y(x)]

B = [bx, by]

x

y(x)

bx

by

Obrázek 1.4.12: úloha o brachystochroně.

Těleso o hmotnosti m se má pohybovat bez tření vlastní tíží po obloukuAMB. Rychlostv místě M nezávisí na tvaru křivky spojující body A a B (Galileův zákon) a podle zákonaenergetické bilance je kinetická a potenciální energie v každém bodě M = (x,y) v rovnoáze,tj. platí rovnost

(D)12mv2 =mgy, 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 ∈ 〈0,T 〉

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) v(x) ≡ v(t) =ds

dt=

√x2 + y2dt

dt=

√1+ (y′)2dx

dt=√

2gy(x).

Odtud pak úpravou dostaneme

(H) dt=

√1+ (y′)2

2gydx.

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

(I) T =

T∫

0

dt=

bx∫

0

√1+ (y′)2

2gydx.

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

T (y) = minyT (y)

tj. požadujeme splnění nerovnosti

(J) T (y) ≤ T (y)

pro všechny funkce y = y(x) splňující uvedené okrajové podmínky, tj. všechny (hladké) křivkyspojující body A a B.

Závislost (I) času T = T (y) na funkci y = y(x), x ∈ 〈0, bx〉 je funkcionál definovanýnapřípustné množině V funkcí y splňující zřejmé podmínky z obrázku (1.4.12)tj

V = {y ∈ C 1(〈0, bx〉) : y(0) = 0, y(bx) = by, y(x) ≥ 0,

bx∫

0

dx√y(x)

<∞} .

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〈0, bx〉.

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

δT (y,h) =d

dαT (y+αh)

∣∣∣∣α=0

= limα→0

T (y+αh)−T (y)α

= 0 .

Je věcí důvěry čtenáře k autorovi textu, že po určitých manipulacích (technologie variačníhopočtu) dostaneme podmínku

ddx

1√

y (1+ (y′))2

= 0 ,


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 ∈〈0, bx〉.

Substitucí y′ = cotg t2 obdržíme (t he parametr)

y(t) =C

1+ cotg2 t2

=C

2(1− cos t) .

Protožedydx

=dydt

dtdx

,

potomdxdt

= C sin2 t

2a tedy (parametrické vyjádření hledané křivky)

x(t) =C

2(t− sint) , y(t) =

C

2(1− cos t) , t ∈ (0,T ) .

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 T = T (y) vypočteme z okrajových podmínek

x(T ) = bx =C

2(T − sin T ) , y(T ) = by =

C

2(1− cos T ) .

TakžeT = T (y) = min

y∈VT (y) .

1.4.3. Fermatova úloha o lomu světla

Formulace prvního variačního principu pro fyzikální úlohu spojujeme se jménem PierraFermata. Jde o Fermatův variační princip v geometrické optice. Zákon lomu světla byl ex-perimentá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ž vprostř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, žepaprsek světla si „vybírá“ takovou trajektorii, podél které čas vynaložený na překonání cestyz jednoho bodu do druhého je minimální (ve srovnání sjinými trajektoriemi spokujícími tytobody).

Huygens navrh jiné vysvětlení zákona o šíření a lomu světla. Ukázalo se, že mezi Huy-gensovým principem a Fermatovým principem je velmi úzká souvislost. Tyto úvahy se stalyzákladem pro budoucí Hamiltonovu-Jacobiovu teorii a v první polovině minulého století protakzvanou teorii dynamického programování, která je důležitým nástrojem řešení aplikovanýchextremálních úloh.

Záhy po Fermatově principu byla objevena řada dalších variačních principů. Z počátkuv mechanice, poté i ve fyzice.

Formalizací Fermatova variačního principu o trajektorii světelného paprsku v dvojroz-měrném nehomogením prostředí dospějeme opět k úloze minimalizace integrálu T (y)

T =

T∫

0

dt=

bx∫

0

√1+ (y′)2

2gydx.

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 lomusvětla má charakter nutné podmínky minima integrálu T (y).

Napíšeme-li jej ve tvarusinα(x)v(x)

= konst ,

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

sinα(x) =dxds

=dx√

1+ (y′)2 · dx =1√

1+ (y′)2.

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

1√2gy ·

√1+ (y′)2

= konst .

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 t2 obdržíme

y =C

1+ cotg2 t2

=C

2(1− cos t) .

Protožedydx

=dydt

· dtdx

,

potomdxdt

= C sin2 t

2,

a tedy

x(t) =C

2(t− sint) , y(t) =

C

2(1− cos t) , t ∈ (0,T ) .

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

bx =C

2(T − sinT ) , by =

C

2(1− cosT ) .

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í


zboží z každého skladu do každého obchodu a víme, kolik zboží musí být dodáno do každéhoobchodu.

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ýchbodů 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,cijxij - cena přepravy z i-tého skladu do j-tého obchodu.

Vidíme, že je třeba minimalizovat celkovou cenu přepravy

(K)m∑

i=1

n∑

j=1

cijxij

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

j=1xij ≤ ai (nelze odvézt více, než se nachází ve skladu),

m∑i=1

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 + qijxij.

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:Najděte číslo f = inf

x∈Vf (x) a prvek (bod) x ∈ V takový, že f = f (x), že platí:

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

Tuto úlohu budeme zapisovat ve tvaru

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

Úlohu na maximum vzhledem k množině V pro funkci f formulujeme takto:Najděte číslo f = sup

x∈V

f (x) a prvek (bod) x ∈ V takový, že f = f(x), a tedy platí:

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

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 fna množině V. Takovou úlohu budeme zapisovat ve tvaru:

inf {f (x) | x ∈ V } , resp. sup{f (x) | x ∈ V } .

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

Například úloha

sup{arctanx | x ∈ R1} je řešitelná (f =

π

2).

kdežto úlohamax{arctanx | x ∈ R

1} řešitelná není

neboť neexistuje x ∈ R1, pro které f (x) = π

2 .

Bod x ∈ V , pro který je

(C) f = f (x) = minx∈V

f (x) , resp. f = f (x) = maxx∈V

f (x) ,

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:

argminx∈V

f (x) , resp. argmaxx∈V

f (x) .

Symbolemargmin

x∈V

f (x)

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

argmaxx∈V

f (x)

V dalším textu se soustředíme na úlohy minimalizace, neboť vzhledem ke vztahu

maxx∈V

f(x) = −minx∈V

(−f (x))

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řed-poklá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 opti-malizaci 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žinaaritmetický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 ‖ ·‖, případně ještě obecnějilokálně kompaktní Hausdorffův topologický prostor.

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

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

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

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

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

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

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 popisovatmetody řešení optimalizačních úloh.Pro teoretické úvahy někdy potřebujeme smysl definovaných pojmů rozšířit pro případ, že Vje prázdná množina ∅ . Potom klademe

infx∈∅

f (x) = +∞ ; supx∈∅

f (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

x ∈ X takový, že:

f (x) = minx∈X

f (x) tj. existuje globální minimum

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

f (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

je množina x ∈ X : f (x) ≤ f (x) neprázdná a omezená, potom existuje bod x ∈ X takovým,že f (x) = min

x∈Xf (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ě pro-storu 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 ≡R

n,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

ϕ(y) = minx∈X

F(x,y) , ∀y ∈ Y ;

β = maxy∈Y

ϕ(y) = maxy∈Y

minx∈X

F(x,y).

f (x) = maxy∈Y

F(x,y) , ∀x ∈ X ;

α = minx∈X

f (x) = minx∈X

maxy∈Y

F(x,y).

Předpokládáme existencivšech minim a maxim, okterých je řeč.

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

(F) α= f (x) = minx∈X

f (x) = maxy∈Y

F(x,y) = F(x, y),

(G) β = ϕ(y) = maxy∈Y

ϕ(y) = minx∈X

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

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í. Potomplatí

minx∈X

F(x,y) ≤ maxy∈Y

F(x,y) , tj.(H)

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

a tedy

(J) maxy∈Y

ϕ(y) ≤ minx∈X

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

resp.

(K) maxy∈Y

minx∈X

F(x,y) ≤ minx∈X

maxy∈Y

F(x,y).

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


Důkaz Pro každé pevné x ∈ X platí nerovnost

F(x,y) ≤ maxy∈Y

F(x,y)

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

F (x,y) ≤ F(x,y) ,

tj.minx∈X

F(x,y) ≤ F(x,y) ≤ maxy∈Y

F(x,y) ,

a tedyϕ(y) ≤ f (x) , ∀x ∈ X , ∀y ∈ Y .

Odkud pak vidíme, že spojitá funkce f je omezená zdola libovolnou hodnotou ϕ(y) aspojitá funkce ϕ je omezená shora libovolnou hodnotou funkce f (x). Takže

maxy∈Y

ϕ(y) ≤ minx∈X

f (x) .

Poznámka. Pokud úlohy formulujeme obecněji, tj. jako

infx∈A

supy∈B

F(x,y), supy∈B

infx∈A

F(x,y) ,

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

2.3.3. Lemma

Nechť funkce F(x,y) je spojitá na kartézském součinu A × B kompaktních množinA ⊂ 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 exis-tence řešení (spojitost F a kompaktnost A,B). Tvrzení pak už plyne (je důsledkem) z před-chozí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, ome-zenost.

2.3.4. Definice

Nechť F : X × Y → R1 je spojitá, X ∈ R

n,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ýmbodem.


2.3.5. Příklad 1

Mějme funkciF(x,y) = x2 −y2 , x ∈ 〈−1,1〉 , y ∈ 〈−1,1〉

Bod (0,0) splňuje podmínky (nerovnosti) (L)

F(0,y) ≤ F(0,0) ≤ F(x,0)

tj.−y2 ≤ 0 ≤ x2 ; ∀x ∈ 〈−1,1〉 , ∀y ∈ 〈−1,1〉.

Je tedy (globálním) vnitřním sedlovým bodem funkce F na daném uzavřeném čtverci. Jepatrné, že bod (0,0) je sedlovým bodem funkce F uvažované na celé množině R

1 ×R1.

2.3.6. Příklad 2

Mějme funkciF(x,y) = x2 +y2 , x ∈ R

1 , y ∈ R1

ProtožeF(0,y) = y2 , F(0,0) = 0 , F(x,0) = x2

a nerovnosti typu (L)y2 ≤ 0 ≤ x2,

resp.y2 ≥ 0 ≥ x2

platí pouze pro y = 0 (nikoliv pro všechna y ∈ R1), ∀x ∈ R

1, resp. x = 0 , ∀y ∈ R1, není bod

(0,0) sedlovým bodem na R1 ×R

1.

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

1 ×R1.

2.3.7. Příklad 3

Mějme funkciF(x,y) = x2 +y2 , x ∈ 〈0,1〉 , y ∈ 〈0,1〉.

Všimneme si, že definiční obor je ve srovnání s příkladem (2.3.6.) výrazně odlišný. Lze protokonstatovat, že funkce F splňuje pro bod (0,1) podmínky

F(0,y) ≤ F(0,1) ≤ F(x,1)

tj.y2 ≤ 1 ≤ x2 + 1 , ∀x ∈ 〈0,1〉 , ∀y ∈ 〈0,1〉.

Bod (0,1) je tedy sedlovým bodem dané funkce na množině 〈0,1〉 × 〈0,1〉. Všimneme si, žebod (0,1) je bodem maxima, bod (1,1) je bodem maxima, bod (1,0) je sedlovým bodem vesmyslu (M), tj. platí 1+y2 ≥ 1 ≥ x2. K této úloze se ještě vrátíme v odst. (2.4.1.).


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ástrojemjsou úlohy minimaxu a maximinu. Z odst. (2.3.1.) bezprostředně plyne pro x = x = x , y =y = y , že

F(x,y) ≤ F(x, y) = minx∈X

maxy∈Y

F(x,y) = F(x,y) = α

F(x,y) = maxy∈Y

minx∈X

F(x,y) = F(x, y) ≤ F(x, y) = β.

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

Nechť F : X × Y → R1 , Rn , Y ⊂ R

m 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) maxy

minx

F(x,y) = F(x,y) = minx∈X

maxy∈Y

F(x,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) = maxy∈Y

F(x,y) ≤ F(x,y),

F(x,y) ≤ F(x,y) ⇒ F(x,y) ≤ minx∈X

F(x,y) = ϕ(y).

Samozřejmě platíminx∈X

f (x) ≤ f (x),

ϕ(y) ≤ maxy∈Y

ϕ(y).

Spojením uvedených nerovností dostaneme

minx∈X

f (x)︸︷︷︸maxy∈Y

F(x,y)

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

ϕ(y)︸︷︷︸minx∈X

F(x,y)

,

takžeminx∈X

maxy∈Y

F(x,y) ≤ F(x,y) ≤ maxy∈Y

minx∈X

F(x,y).

ze slabého vztahu duality (K) (který platí vždy za předpokladu řešitelnosti uvažovanýchúloh) dostaneme

maxy∈Y

minx∈X

F(x,y) ≤ minx∈X

maxy∈Y

F(x,y)

dostáváme pak rovnost (N).


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) maxy∈Y

minx∈X

F(x,y) = F(x,y) = minx∈X

maxy∈Y

F(x,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) = maxy

[minx

F(x,y)]︸︷︷︸

ϕ(y)

= minx

F(x,y)︸︷︷︸

ϕ(y)

,

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

Poznámka: Maximalizujeme funkci

ϕ(y) = minx

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

a takéF(x,y) = min

x[max

yF(x,y)]

︸︷︷︸f (x)

= maxy

F(x,y)︸︷︷︸

f (x)

,

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

Poznámka: Minimalizujeme funkci f (x) = maxy

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

Takže spojime-li obě rovnosti

maxy

F(x,y) = F(x,y) = minx

F(x,y)}

Klíčova rovnost –ekvivalentní s (P).

a dostaneme

F(x,y) ≤ maxy

F(x,y) = F(x,y) = minx

F(x,y) ≤ F(x,y).

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)


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áčeH1: miny∈Y

F(x,y) : . . . hráčH2 volí takovou strategii y, aby minimalizoval

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

v1 = maxx∈X

miny∈Y

F(x,y)

Z pohledu hráče H2: . . . analogické úvahy

v2 = maxy∈Y

minx∈X

G(x,y)

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)}Řešením hry která je sedlovým bodem funkce F(x,y) je dvojice (x, y), kde x je opti-

mální strategie H1 a y 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í) funkceF(x,y) , x ∈ X , y ∈ Y (určení Y ) k funkci f (x) vztahem

f (x) = maxy∈Y

F(x,y)

a stanovení funkceϕ(y) = min

x∈XF(x,y)

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

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

f (x) = minx∈X

f (x) = minx∈X

maxy∈Y

F(x,y) = F(x, y)

ϕ(y) = maxy∈Y

ϕ(y) = maxy∈Y

minx∈X

F(x,y) = F(x, y)

(x,y) je sedlový bod

nemusí být jediný!!

Slabý vztah duality píšeme ve tvaru ϕ(y) ≤ ϕ(y) ≤ f (x) ≤ f (x). Silný vztah duality píšeme vetvaru ϕ(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 funkciF(x,y) = x2 +y2 , x ∈ 〈0,1〉 , y ∈ 〈0,1〉.

40 2.4. PŘÍKLADY A CVIČENÍ

Posuďme řešitelnost úlohy sedlového bodu, tj. řešitelnost úloh

maxy∈Y

minx∈X

F(x,y) , minx∈X

maxy∈Y

F(x,y).

Označíme-li

f (x) = maxy

F(x,y) = maxy∈〈0,1〉

(x2 +y2) = x2 + 1 = F(x,1) ;

ϕ(y) = minx

F(x,y) = minx∈〈0,1〉

(x2 +y2) = y2 = F(0,y) .

Pak

α = minx

maxy

F(x,y) = minx∈〈0,1〉

(x2 + 1) = 1 = F(0,1) = f(0) ,

β = maxy

minx

F(x,y) = maxy∈〈0,1〉

y2 = 1 = F(0,1) = ϕ(1) .

A je patrné, že

F(0,y) ≤ F(0,1) ≤ F(x,1) , (x,y) = (0,1) je sedlový body2 ≤ 1 ≤ x2 + 1 , ∀x ∈ 〈0,1〉 , ∀y ∈ 〈0,1〉

Viz odst. (2.3.7.). Úloha sedlového bodu je řešitelná. Situace je patrná z obr. (2.4.1).

x

y

z

0 10

1

0

1

[1, 1]

[0, 1]

[1, 0]

y2 = maxx F (x, y) = ϕ(y)

x2

y2 + 1x2 + 1 =

maxy F (x, y) == f(x)

Obrázek 2.4.1: sedlový bod


Mějme funkciF(x,y) = x2 −y2 , x ∈ 〈−1,1〉 , y ∈ 〈−1,1〉 .

Posuďme řešitelnost úloh

maxy

minx

F(x,y) ; minx

maxy

F(x,y) .


Podle definice stanovíme

f (x) = maxy∈〈−1,1〉

(x2 −y2) = x2 = F(x,0) ,

α = minx

maxy

(x2 −y2) = minx∈〈−1,1〉

f (x) = minxx2 = 0 = F(0,0) ,

ϕ(y) = minx∈〈−1,1〉

(x2 −y2) = −y2 = F(0,y) ,

β = maxy

minx

(x2 −y2) = maxy∈〈−1,1〉

ϕ(y) = maxy

(−y2) = 0 = F(0,0) .

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.).


Mějme funkci

F(x,y) = (x−y)2 ≡ (y−x)2 ; x ∈ 〈0,1〉 , y ∈ 〈0,1〉 .


maxy

minx

F(x,y) ; minx

maxy

F(x,y) .

Znázorníme si grafy funkcí F(x,y) = (x−y)2 pro jednotlivé volby y ∈ 〈0,1〉, např:

F(x,0) = (x− 0)2 ;

F(x,14

) = (x− 14

)2 ;

F(x,12

) = (x− 12

)2 ;

F(x,34

) = (x− 34

)2 ;

F(x,1) = (x− 1)2 .

Pro 0 ≤ x≤ 12 je max

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

pro 12 ≤ x≤ 1 je max

y(x−y)2 = x2, tj.

f (x) =

(x− 1)2 ,0 ≤ x≤ 12,

x2 ,12

≤ x≤ 1 .

Potom zřejmě

f (12

) = minx∈〈0,1〉

f (x) =14

=

F(12,0) ,

F(12,1) .

Takže

minx

maxy

(x−y)2 =14.


x

y

0 0.5 10

0.5

1 y = 0

y = 1

4

y = 1

2

y = 3

4

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∈ 〈0,1〉,např.

F(0,y) = (0−y)2 ;

F(14,y) = (

14

−y)2 ;

F(12,y) = (

12

−y)2 ;

F(34,y) = (

34

−y)2 ;

F(1,y) = (1−y)2 .

x

y

0 0.5 10

0.5

1 x = 0

x = 1

4

x = 1

2

x = 3

4

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),


zde jsou to funkce proměnné y ∈ 〈0,1〉. Protože

ϕ(y) def= minx∈〈0,1〉

(x−y)2 = 0 ,

tj.

maxy

minx

(x−y)2 = 0 ,

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

Tedy

0 = maxy

minx

(x−y)2 <minx

maxy

(x−y)2 =14.

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

x

y

0 0.5 10

0.5

1

f = 1

4

f = 0

f = 1

4

f(0, 1) = 1

f(1, 0) = 1

Obrázek 2.4.4:

reliéf funkce F(x,y) = (x−y)2.

x

y

z

0 10

1

0

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 prodanou funkci. Viz také odst. (1.7) těchto skript.


Mějme funkci

F(x,y) = 1−x+y , x ∈ 〈0,1〉 , y ∈ 〈0,1〉 .


maxy

minx

F(x,y) ; minx

maxy

F(x,y) .


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

f(x) = maxy∈〈0,1〉

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

minx∈〈0,1〉

f(x) = minx∈〈0,1〉

(2−x) = 1 = f(1) = F(1,1) = minmaxF .

ϕ(y) = minx∈〈0,1〉

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

maxy∈〈0,1〉

ϕ(y) = maxy∈〈0,1〉

(y) = 1 = F(1,1) = maxminF .

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 ∈ 〈0,1〉 , y ∈ 〈0,1〉 .

x

y

0 0.5 10

0.5

1

f = 3

2

f = 1

f = 1

2

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

x

y

z

0 10

1

0

1

F1(x)

F2(y)

[1, 1]

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

maxy

F2(y) ≤ minx

F1(x) (dokonce platí rovnost)


Je dána diskrétní funkce F(i,j) maticí aij = F(i,j), kde

(aij) =

[5 13 7

].

Posuďme opět úlohymin

imax

jFij ; max

jmin

iFij ;


a úlohu sedlového bodu.

Máme:

f (i) = maxj

F(i,j) : f (1) = maxj

F(1, j) = max{5,1} = 5 ,

f(2) = maxj

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

ϕ(j) = mini

F(i,j) : ϕ(1) = mini

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

ϕ(2) = mini

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

Takže

maxj

mini

F(i,j) = maxjϕ(j) = max{3,1} = 3 ,

mini

maxj

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

Nutná a postačující podmínka sedlovosti splněná není !

Uvedená úloha se nazývá maticová hra . Stručně[

5 13 7

]max−→ 5max−→ 7

}min−→ 5

↓ ↓ min3 1︸︷︷︸

max−→ 3 → 3 6= 5

Obrázek 2.4.8: maticová hra 1


Pro diskretní funkci F(i,j) = aij, pro jinou matici, stručné schéma vypadá takto:[

3 15 7

]max−→ 3max−→ 7

}min−→ 5

↓ ↓ min3 1︸︷︷︸

max−→ 3 → 3 = 3

Obrázek 2.4.9: maticová hra 2

2.4.7. Cvičení 1

Pro funkci F(x,y) =x2 −y2+4x−2y+1 , x∈R1 ; y ∈R

1 řešte úlohy maxy

minx

F(x,y) , minx

maxy

F(x,y)

a rozhodněte o existenci sedlového bodu.

[Návod:min

xF(x,y) = −y2 −2y−3 ; max

yF(x,y) =x2 +4x+2 ; (−2,−1) je sedlový bod;max

ymin

xF(x,y) =

F (−2,−1) = minx

maxy

F(x,y) .]


2.4.8. Cvičení 2

Nechť F : X × Y → R1 , X ⊂ R

n , Y ⊂ Rm . Potom platí

maxy∈Y

minx∈X

F(x,y) ≤ minx∈X

maxy∈Y

F(x,y) .

Dokažte.

[Návod:Pro každé pevné y ∈ Y platí nerovnost min

x∈XF(x,y) ≤ F(x,y) ; pro každé pevné x ∈ X platí

nerovnost F(x,y) ≤ maxy∈Y

F(x,y). Tudíž pro každé x ∈ X , y ∈ Y platí, že minx∈X

F(x,y) ≤maxy∈Y

F(x,y).]

2.4.9. Cvičení 3

Nechť F : X × Y → R1 , X ⊂ R

n , Y ⊂ Rm . Potom platí

maxy∈Y

minx∈X

F(x,y) = F(x, y) = minx∈X

maxy∈Y

F(x,y) právě tehdy, když (x, y) je sedlový bod funkce

F .Dokažte.

[ Návod:Když (x, y) je sedlový bod, potom max

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

x∈ XF(x, y) , min

x∈Xmaxy∈Y

F(x,y) ≤maxy∈Y

F(x,y) ; minx∈X

F(x, y) ≤≤ max

y∈Y

minx∈X

F(x,y) ; užijte cvičení (2.4.8.); když platí maxmin = minmax , pak využitím uve-

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 → R

1 nerovnosti

G(x,y) ≥ G(x, y) ≥ G(x, y) , ∀x ∈ X , ∀y ∈ Y ,

pak (x, y) ∈ X × Y je sedlový bod typu maximinu. Posuďte platnost poznatků z předchozíchodstavců 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ámediferenciální počet.

Johanes Bernoulli, Isaac Newton, Leibnitz a další tuto metodu dále rozvíjeli a používaliji 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í mini-mum“.

3.1. Spojitost v hromadném bodě

Okolí hromadného bodu budeme označovat

Uδ(t) = {t ∈ R1 : |t− t|< δ} ,

Uδ(x) = {x ∈ Rn : ‖x − x‖< δ} .

3.1.1. Spojitost funkcí jedné proměnné

Mějme funkci g : Uδ → R1 , Uδ = Uδ(t) ⊂ R

1.

Vlastnost limt→t

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

V1 : ∀{tn} ⊂ Uδ(t), t → t,n → +∞ , posloupnost funkčních hodnot {g(tn)} konvergujek číslu g(t) , tj. g(tn) → g(t),n → +∞ .

V2 : ∀ǫ > 0 , ∃δ(ǫ)> 0 , (t− δ)< t < (t+ δ) ⇒ g(t)− ǫ < g(t)< g(t)+ ǫ .

3.1.2. Jednostranná spojitost

Mějme funkci g : Uδ → R1 , Uδ = Uδ(t) ∈ R

1 .

Vlastnost limt→t+

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

47

48 3.2. HLADKOST V R1

V +1 : ∀{tn} ⊂ Uδ(t) , tn > t , t→ t , n→ +∞ ; posloupnost funkčních hodnot {g(tn)}

konverguje k číslu g(t) „zprava“, tj. g(tn) → g(t) , n→ +∞ .

V +2 : ∀ǫ > 0 ∃δ(ǫ)> 0, takové, že 0< t < (t+ δ) ⇒ (g(t)− ǫ)< g(t)< (g(t)+ ǫ) .

Vlastnost limt→t−

g(t) = g(t−) = g(t) , „spojitost zleva“ definujeme ekvivalentními výroky:

V −1 : ∀{tn} ⊂ Uδ(t) , tn< t , t→ t , n→ +∞ , posloupnost funkčních hodnot {g(tn)} ,

konverguje k číslu g(t) „zleva“, tj. g(tn) → g(t) , n→ +∞ .

V −2 : ∀ǫ > 0 ∃δ(ǫ)> 0 , takové, že (t− δ)< t < t⇒ g(t)− ǫ)< g(t)< (g(t)+ ǫ) .

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

3.1.3. Polospojitost zdola

Mějme funkci g : Uδ → R1 , Uδ = Uδ(t) ∈ R

1 .

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

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

Důkaz 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 → R

1 zdola polospojitá na I , potomexistuje bod t ∈ I takový, že:

g(t) = mint∈I

g(t)

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)∆t

= 0 .

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δ → R

1 , ψ(t) = g′(t)

diferencovatelná, potom říkáme, že funkce g je dvakrát diferencovatelná a její diferenciáldψ(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ůsled-kem 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ě t ∈ Uδ ⊂ R1 lokální minimum, tj. platí

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

Pak nutně platí nerovnosti

g(t)− g(t)t− t

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

g(t)− g(t)t− t

≤ 0 , t− t < 0 , t ∈ (t , t+ δ) .

Jestliže limity uvedených podílů existují, pak máme nutné podmínky ve tvaru

g′(t+) ≥ 0 , g′(t−) ≤ 0 .

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

g′(t) = 0

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

3.3. Hladkost v Rn

Mějme funkci f : X →R1 , X ⊂R

n , kde Rn je Eukleidovský prostor s normou ‖ · ‖ , Uδ(x) ⊂ Xje 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 , ‖d‖ = 1 , t ∈ R1.

Limita (číslo, pokud existuje)

(A) δf (x,d) = limt→0

f (x + td)− f (x)t

=ddt

f (x + td)∣∣t=0

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 (xi,ei)def=

∂f (x)∂xi

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

(B) δf (x,h) = aT h = hT a .

Vektora = grad f (x) = f ′(x)

se nazývá derivace, nebo gradient funkce f v bodě x.

Když h =n∑

i=1hiei , pak

δf (x,n∑

i=1

hiei) =n∑

i=1

hiδf (xi , ei) =n∑

i=1

∂f (x)∂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)

(C)

δψ(x,d2) = limt→0

ψ(x + td2)− δf (x)t

=

= limt→0

δf (x + td2,d1)− δf (x,d1)t

=

def= δ2f (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) δ2f (x,d2,d1) = d2H(x)d1


kde Hessova matice

H(x) =

(∂2f (x)∂xi∂xj

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

je symetrická.

3.3.3. Kvadratická funkce

Pro kvadratickou funkci f : Rn → R

1 určenou předpisem

f(x) =12

xT Ax − bT x + γ

je

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

f (x + td)∣∣t=0

δf (x,d) = dT (Ax − b), grad f (x) = Ax − b

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

dt2f (x + td)

∣∣t=0

; H(x) = A

3.3.4. Silná difrencovatelnost

Funkce f : Uδ → R1 , Uδ ⊂ X ⊂ R

n , x ∈ Uδ je diferencovatelná (silně diferencovatelná,Fréchetovsky diferencovatelná) v bodě x , existuje-li lineární forma v R

n , ϕ(h) = DT h , h ∈R

n , D ∈ Rn , taková, že existuje limita

(E) lim‖h‖

‖f (x + h)− f (x)− DT h‖‖h‖ = 0 , ∀h ∈ R

n .

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

(F) df (x,h) = DT h

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 G-diferencovatelnosti však nikoliv).

Ekvivalentní definice

∀ǫ > 0 , ∃δ > 0 (∀h ∈ X : ‖h‖ < δ) ⇒ ‖f (x + h)− f (x)− DT h‖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álema F-diferenciálem, případně G-derivací a F-derivací viditelné. Z pohledu teorie jsou však roz-dí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δ ⊂ R

1 existuje spojitá g′. Potom pro každé t ∈Uδ(t) , t= t+ ∆t , existuje τ = τ(t) takové, že platí

(H)

g(t)− g(t) = g′(τ)(t− t) = dg(τ,∆t) =

= g′(t)(t− t)+ω(∆t) =

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

kde

lim∆t→0

ω(∆t)∆t

= 0

Komentář místo důkazu

V uvedeném tvrzení se koncentrují základní poznatky matematické analýzy diferenco-vatených funkcí jedné proměnné. Jednak samotná definice z odstavce 2.2.1. a především pakvě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ě symbolo(hn))

znamená, že

limh→0

o(hn)hn

= 0


3.4.2. Taylorova formule 2. řádu v R1

Nechť pro funkci g : Uδ(t) → R1 , Uδ ⊂ R

1 existuje spojitá g′′. Potom pro každét ∈ Uδ(t) , t= t+ ∆t existuje τ = τ(t) takové, že platí

(I)

g(t)− g(t) = g′(t)∆t+ g′′(τ)∆t2

2=

= dg(t,∆t)+12

d2 g(τ,∆t) =

= dg(t,∆t)+12

d2 g(t,∆t)+ O(∆t2)

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

g(t)− g(t) =

t∫

t

g′(ξ) dξ

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

t∫

t

g′(ξ) dξ =

ξ = t− z

dξ = −dz

〈t, t〉 → 〈t− t,0〉=

{t−t∫0

g′(t− z) dz =

=

{g′ = dg

dz= u , u′ = −g′′

1 = v′ , v = z=

{[zg′(t− z)]t−t

0 +t−t∫0zg′′(t− z)dz =

=

{(t− t)g′(t)+

t∫

t

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

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δ ⊂ R

n , 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á, žeplatí

(J) f(x + h)−f(x) = hT gradf(x)+ω1(x,h)

|ω1(x,h)|‖h‖ ≤ ε1(‖h‖) , lim

‖h‖→0= ǫ1(‖h‖) = 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δ ⊂ R

n , existuje spojitý druhý F-diferenciáld2 f(x,h). Potom pro každé x ∈ Uδ(x) existuje funkce ω2(x,h) , taková, že platí

(L) f (x + h)− f (x) = hT grad f (x)+12

hT H(x)h +ω(x,h) ,

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

(M) f (x + h)− f (x) = hT grad f (x)+12

hT H(z)h

|ω2(x,h)|‖h‖2

≤ ε2(‖h‖) , lim‖h‖→0

ε2(‖h‖) = 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δ ⊂R

n , je G-diferencovatelná v bodě x ve směru přímkyx = x + td , ‖d‖ = 1 , t ∈ R

1. Potom platí

(N) f (x + td)− f (x) = t grad f (x)︸︷︷︸tδf (x,d)

+o(t)

(B) Nechť funkce f : Uδ(x) → R1 , Uδ ⊂ R

n , je dvakrát G-diferencovatelná v bodě x , vesměru přímky x = x + td , ‖d‖ = 1 , t ∈ R

1. Potom platí

(O) f (x + td)− f (x) = tdT grad f (x)+12t2dT H(x)d + o(t2)

3.5. Podmínky optimality v klasické optimali-zaci

3.5.1. Věta (Fermat) Nutná podmínka optimality

Nechť funkce f : X →R1 , X ⊂R

n , je spojitě diferencovatelná ve vnitřním bodě x ∈ X .

Je-li bod x bodem lokálního minima funkce f , potom platí

grad f (x) = 0 ,

resp.

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

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

hT grad f (x) = −‖grad f (x)‖2 < 0


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

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

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 ⊂ R

n , je dvakrát spojitě diferencovatelná ve vnitřnímbodě x ∈ X .

Je-li bod x bodem lokálního minima funkce f , potom platí

(Q)df (x,h) = 0 , ∀h ∈ R

n

d2 f (x,h) ≥ 0 , ∀h ∈ Rn

}

resp.

(R)grad f (x) = 0

hT H(x)h ≥ 0 , ∀h ∈ Rn

}

kde

H(x) =

[∂2f (x)∂xi∂xj

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

je Hessova matice funkce f .

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

f (x + h)− f (x) =12

hT H(x)h + o(‖h‖2) .

Zvolímeh = td , ‖d‖2 = 1 ,

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

pro dostatečně malé t (tj. existuje takové δ > 0, že uvedená nerovnost platí pro t ∈ (0,δ)).Musí proto platit

12t2dT H(x)d + o(t2) ≥ 0 .

Kdybychom totiž připustili, že v bodě minima platí ostrá nerovnost

dT H(x)d< 0 ,

pak pro dostatečně malá t bude (opět díky spojitosti g′′(τ) = ddt2 f (x + τd))

12t2dT H(x)d + O(t2)< 0 .

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

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

x = x + td ,


kde t je reálné číslo a d ∈ Rn je jednotkový vektor, tj. ‖d‖ = 1. Tudíž

f(x) = f (x + td)

a podle předpokladu je

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

Označímeg(t) = f (x + td)

a nerovnost (S) píšeme ve tvaru

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

Na uzavřeném intervalu 〈0, t〉 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ženutně musí být

g′(0) =ddt

f (x + td)∣∣t=0

= dT grad f (x) = 0

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

Nechť funkce f : X →R1 , X ⊂R

n , je dvakrát spojitě diferencovatelná pro x ∈ Uδ(x) ⊂ X .

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

(U) grad f (x) = 0,

a pro každé d ∈ Rn platí

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

potom x je bod lokálního minima.

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

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

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

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

f (x)> f (x)


Prox = x + td , ‖d‖ = 1

napíšeme Taylorovu formuli

f (x) = f (x + td) = f (x)+ tdT grad f (x)+12t2dT H(x + Θtd)d

0<Θ< 1 .

Pak musí býtdT H(x + Θtd)d< 0,

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

3.5.4. Věta. Postačující podmínka optimality č.2

Nechť f : X →R1 , X ⊂R

n , je dvakrát spojitě diferencovatelná ve vnitřním bodě x ∈ Xa platí

(X) grad f (x) = 0

(Y) dT H(x)d> 0

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

Důkaz Nechť existuje bod x ∈ Uδ(x) takový, že f (x)< f (x). Z Taylorova rozvoje

f (x) = f (x)+ (x − x)T grad f (x)+12

(x − x)T H(x)(x − x)+

+‖x − x‖2ω(x,x − x)

využijeme-li vztahu h = x − x potom plyne nerovnost12

hT H(x)h + ‖h‖2ω(x,h) < 0.

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 jedno-duchá záležitost.

2. V každém stacionárním bodě funkce f se prověří znaménko (signum) druhého diferenciálu

d2f(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ásle-dujícím) odstavci (3.5.6.).


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∑

j=1

aijxixj , 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 ∈ R

n takový, žeyT 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)nMn > 0.

4. Matice A je negativně semidefinitní:

(a) xT Ax ≤ 0 pro každý vektor y ∈ Rn a existuje nenulový vektor y ∈ R

n takový, žeyT 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)nMn ≥ 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 +x3

2 − 3x1x2 , (x1,x2) ∈ R2

Řešme tyto optimalizační úlohy

a) min{f (x1,x2) | (x1,x2) ∈ R2}


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) =

[3x2

1 − 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

∂x21

∂2f∂x1∂x2

∂2f∂x1∂x2

∂2f

∂x22

=

[6x1 −3

−3 6x2

].

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

H(S1) =

[6 −3

−3 6

], H(S2) =

[0 −3

−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 H1d> 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íhominina

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 kva-dratické formy dT H2d v závislosti na směrech d. Budeme tedy vlastně vyšetřovat průběhdané funkce na přímkách procházející stacionárním bodem S2.

(a) zvolíme d = e1 , tj. x1 = t , x2 = 0Máme tedy „novou“ funkci f (t,0) = t3 : funkce f je v bodě S2 ve směru osy x1 ostřerostoucí.

(b) zvolíme d = e2 , tj. x1 = 0 , x2 = tMáme tedy „jinou novou“ funkci f (0,z) = t3 : funkce f je bodě S2 ve směru osy x2

ostře rostoucí.


(c) zvolíme d = v1 = [1,−1]T

tj. vlastní vektor příslušejícímu vlastnímu číslu λ1 = 3Má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 = −3Má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 fmá 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ěřitpomě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 +x3

2 + 2x21 + 4x2

2 + 6 .

Rozhodněme o charakteru stacinárních bodů této funkce.

Technologie výpočtů:

grad f (x1,x2) =

[x1(3x1 + 4)x2(3x2 + 8)

],

H(x1,x2) =

[6x1 + 4 0

0 6x2 + 8

],

(M1 = 6x1 + 4

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

).

Výsledky seřadíme do tabulky

Stacionárníbod

Vlastníčísla H Minory Vlastnost H

charakter stac.bodu f

λ1 = 4 M1 = 4 pozitivně ostré lokální(0,0)

λ2 = 8 M3 = 32 definitní minimum6

λ1 = 4 M1 = 4(0,−8

3 )λ2 = −8 M2 = −32

indefinitní sedlový bod 41827

λ1 = −4 M1 = −4(−4

3 ,0)λ2 = 8 M2 = −32

indefinitní sedlový bod 19427

λ1 = −4 M= − 4 negativně ostré lokální(−4

3 ,−83)

λ2 = −8 M2 = 32 definitní maximum503

Tabulka 3.5.1: Stacionární body - vlastnosti

O charakteru bodů (0,−83 ) a (−4

3 ,0) lze rozhodnout podle chování funkce f(x1,x2) napřímkách procházejícími těmito body.


3.6. Řešené úlohy

3.6.1. Úloha 1

Vyšetřete úlohu

min{

f (x1,x2) | (x1,x2) ∈ R2}, kde f (x1,x2) = (x2

2 − 32x1)2 − x2

1

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 − 3

2x1 < 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) = 2x2

1 − 3k2x31 +k4x4

1 ostré lokální minumum v bodě S.

ZávěrDaná 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.?

0

10

20

30

40

50

05

1015

2025

3035

4045

−1

0

1

2

3

4

x 106

osa x1

osa x2

osa

z

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 +x4

2 − (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.

−10010203040506070

−20

0

20

40

60

80

−20

0

20

40

60

80

100

120

140

160

180

osa x1osa x2

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

3.6.3. Úloha 3

Nechť funkce f : R1 → R

1 má derivace všech řádů v bodě x ∈ R1 a x je ostrý lokální

minimizátor funkce f . Plyne odtud, že f (k)(x) 6= 0 alespoň pro jedno k ?

OdpověďNeplyne, vyšetřete funkci

f (x) =

{e− 1

x2 , pro x 6= 00 , pro x= 0

3.6.4. Úloha 4

Nechť x je je ostrý minimizátor funkce f : R1 → R

1. Plyne odtud, že v nějakém le-vostranném okolí bodu x funkce klesá a v nějakém pravostranném okolí bodu x funkce roste?


OdpověďNeplyne, vyšetřete funkci

f (x) =

{2x2 +x2 sin 1

x, 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) = x1ex1 − (1+ ex1)cosx2

má v R2 nekonečně mnoho lokálních minimizátorů, ale žádný lokální maximizátor v R

2.

3.6.6. Úloha 6

Uveďte příklady hladkých funkcí jedné, nebo dvou proměnných, které splňují níže uve-dené 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) = sinx

b) X = R1 , f (x) = 1

1+x2

c) X = R1 , f (x) = arctanx

d) X = R1 , f (x) = (arctanx)(sinx)

e) X = R2 , f (x1,x2) = sinx2 −x2

1

3.6.7. Úloha 7

Mějme úlohu na minimum pro funkci

f (x1,x2) = x21 −x1x2 + 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 ‖Ax − b‖2 , 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 00 2 10 1 01 0 1

, b =

2110

3.6.9. Úloha 9

Stanovte řešení úlohy min{f (x,y,z) | (x,y,z) ∈ R3} , kde

f(x,y,z) = 5x2 + 5y2 + z2 + 2xy− 2xz− 2yz− 4x− 4y

Odpověď(x, y, z) = (1

2 ,12 ,1); f (x, y, z) = 0.

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

10x+ 2y− 2z− 4 = 010y+ 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

H =

10 2 −22 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í naR

3 , 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 ⊂ R

n je daná diferencovatelná účelová funkce. Přípustná množina V ⊂ Xje 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í va-rieta)

(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) bj1x1 + bj2x2 + · · ·+ bjnxn = cj , j = 1,2, . . . ,p

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

(E) x = x +n−h∑

i=1

αiwi , αi ∈ R1 ,

kde x ∈ V je partikulární řešení soustavy Bx = c (pevný bod lineární variety V ) a vektorywi ∈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 jakodimenze lineárního prostoru (tzv. nulový prostor matice B ≡ lineární obal vektorů wi)

(F) N (B) = {w ∈ Rn : Bw = 0} ,

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

Nechť x je bod lokálního minima funkce f : X → R1 na přípustné množině (C), resp

(G), tj.

f (x) = min f (x) , x = x +n−h∑

i=1

αiwi ; Bwi = 0 .

x ∈ x + N (B)

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

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

i=1

αiwi) .

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

Důkaz je evidentní.

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

f

(x +

n−h∑

i=1

αiwi

)≤ f

(x +

n−h∑

i=1

αiwi

)∀αi ∈ R

1 ,

tj.g(α) ≤ g(α) , ∀α ∈ R

n−h .

Poznámka: Úloha na minimum funkce f na lineární varietě x + N (B) se na základě tohotolemmatu převede na úlohu na volný extrém funkce g na (v??) prostoru R

n−h , kde h > 0 jehodnost matice B .

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

6.1.3. Lemma Nutné podmínky optimality na lineární varietě

Je-li x = x +n−h∑

i=1

αiwi 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í

(K)d

dαif

(x +

n−h∑

i=1

αiwi

)∣∣∣∣∣αi=αi

= 0 .

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

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

tj. derivace funkce f v bodě x jsou ve všech směrech lineární variety nulové !

b)∃ v ∈ R

p , v = [v1, v2, . . . , vp]T (ne všechna nulová!)

(M) − grad f (x) = BT v ≡p∑

j=1

vjbj

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

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

c)∃ v ∈ R

p , v = [v1, v2, . . . , vp, ]T (ne všechna nulová!)

(N) grad[f (x)+ vT (Bx − c)]x=x

v=v

= 0 ;

grad(bTj x − cj)

︸︷︷︸j−tá složka

vektoru Bx−c

= bj , zřejmě j = 1,2, . . . ,p .

d)

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

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)d

dαif (x +

n−h∑

i=1

αiwi) = wTi grad f (x) .

Modifikace standardního důkazu sporem. Připustíme-li například, že wTi grad f (x)> 0 , potom

z Taylorovy formule dostaneme nerovnost f (x + twi)< (x) pro dostatečně malé t > 0.

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

b)

Podmínky ortogonality wi⊥grad f (x) , i = 1,2, . . . ,n− h říkají, že grad f (x) ∈ Rn v bodě

minima je ortogonální k bázi lineárního prostoru N (B) ⊂ Rn, tedy grad f (x) /∈ N (B), do-

konce grad f (x)⊥N (B). Jinak řečeno, grad f (x) musí patřit ortogonálnímu doplňku k prostoruN (B), tj. do lineárního prostoru dimenze p:

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

p} .

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

sloupce matice BT .

N (B)

[N (B)]⊥= H (BT )

Rn = N (B)⊕ H (BT )

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

grad f (x) ∈ H(BT ) .

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 kom-binacemi sloupců matice BT .

Jestliže přípustnou množinu V = x+N (B) určenou vazbami Bx = c , tedy geometrickyjako průnik nadrovin bT

j x − cj = 0 , j = 1,2, . . . ,p , potom podmínka

grad f (x)⊥span(wi)

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

Poznámka: Výrok span(bj) = [N (B)]⊥ pouze říká, že bj⊥w , resp. bTj w = 0 , j = 1,2, . . . ,p ;

a to je ekvivalentní výroku Bw = 0.

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ínekoptimality.


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 +x2

2 , (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:[x1

x2

]

︸︷︷︸x

=

[01

]

︸︷︷︸x

+α

[1

−1

]

︸︷︷︸w

= x +αw , α ∈ R1 .

rozepsáno složkověx1 = 0 ·x1 +α · (+1)

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

Funkci f dvou proměnných x1,x2 převedeme na funkci jedné proměnné α (restrikce funkcef na V )

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

prostým dosazením x1 = α , x2 = 1−α.

V bodě minima (maxima) α musí být

g′(α) =d

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

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

α=12, x =

[01

]+

12

[1

−1

]=

[1212

].

Protože

g′′(α) =d2

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

= [1,−1] ·[2 00 2

]·[

1−1

]= 4> 0 ,

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

Technologie přímé redukce dimenze:

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

f (x1,1−x1) ozn.= F(x1) = x21 + (1−x1)2 = 2x2

1 + 2x1 + 1 .

Původní úlohymin{f (x1,x2) | (x1,x2) ∈ V } ,


max{f (x1,x2) | (x1,x2) ∈ V } ,tak převedeme na úlohy

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

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

Z druhé podmínkydF(x1)

dx1

∣∣∣∣x1=x1

= (2x21 − 2x1 + 1)′ = 0

dostaneme x1 =12

.

Protožed2 F(x1)

dx21

∣∣∣∣∣x1=x1

= (2x21 − 2x1 + 1)′′ = 4> 0 ,

je x =

[1212

]bodem minima, f (x1,x2) =

12

.

6.2.2. Obecná úloha kvadratické optimalizace

Chceme najít řešení úlohy

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

kdef (x) =

12

xT Ax − bT x , x ∈ Rn ,

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

p

a předpokládáme

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∑

k=1

bjkxk − 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) ⊂ R

n , což je lineární prostor všech řešení této homogení soustavy.

Jediný bod minima x ∈ V lze stanovit využitím některé z nutných podmínek z odst.(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.


Technologie stanovení partikulárního řešení x

Ze všech řešení soustavy Bx = c stanovíme takové, které má nejmenší normu

‖x‖2 =√

xT x .

Řešíme tedy pomocnou otimalizační úlohu

min{12

xT x : BX − c = 0}

Z nutné podmínky (M) dostaneme

−x = BT v , tj. Bx = −BBT v = c .

Takžev = −(BBT )−1c ,

a tedyx = BT (BBT )−1c .

Technologie stanovení báze prostoru N (B)

Sestrojíme pomocnou maticovou rovnici

B · W = D ,

kde

B =

p

n-p

. . .. . .

0. . . B

. . .· · · · · · · · · · · · · · · · · · · · · · · · · · ·

1 00 1

. . .1

︸︷︷︸n

, D =

. . .. . . 0

0. . .

. . .· · · · · · · · · · · ·1

1. . .

1

︸︷︷︸n−p

n

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 ,

kdeu = y1w1 +y1w1 + · · ·yn−pwn−p ≡ Wy ,


a

y = [y1,y2, . . . ,yn−p]T ∈ Rn−p

je vektor nových (neredukovaných) proměnných.

Definujeme funkci

g(y) = f (x + Wy) =12

(x + Wy)T A(x + Wy)− bT (x + Wy)

V bodě minima:

g(y) ≤ g(y) , ∀y ∈ Rn−p ,

z nutné podmínky optimality

zT gradg(y) = 0 , ∀y ∈ Rn−p

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

WT AWy = −WT Ax − WT b .

Potom

x = +Wy .

af (x) = min

x∈V(x) = min

y∈Rn−pg(y) = g(y) .

(A) Konkrétní vstupy a výstupy

f (x) =12

(xT x) =12

(x21 +x2

2 +x23 +x2

4) ; n= 4 ;

A =

11

11

; b =

0000

;

B =

[1 5 3 21 6 5 2

]; c =

[1 01 5

]; h(B) = 2 , p= 2 .

Algoritmus metody redukce dimenze

Vstup: A : Rn → R

n , B : Rn → R

p , p= h(B) , b ∈ Rn , c ∈ R

p ,

f (x) =12

xT Ax − bT x ; V = {x ∈ Rn : Bx − c = 0} .

1. Stanovit: v ∈ Rp : BBT v = c ,

x ∈ Rn : x = BT v .

2. Stanovit: bázi prostoru N (B) , tj. matici W typu (n,n−p)řešením pomocné maticové rovnice BW = D ; n−p bázových vektorů

Určit: y ∈ Rn−p : WT AWy = −WT Ax − WT b

(lze užít metodu sdružených gradientů).Výstup: x = x + Wy , f (x) = g(y) = f (x + Wy).


BBT =

[39 5050 66

]; x = BT (BBT )−1c =

−0,06756760,8108112,0945952

−0,1351352

=

− 5746074

15574

−1074

Pomocná maticová rovniceBW = D , tj.

1 5 3 20 1 2 00 0 1 00 0 0 1

·

w11 w12

w21 w22

w31 w32

w41 w42

=

0 00 01 00 1

.

Takžew1 = [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 =

0000

Dostaneme y = [0,0,0,0]T .

Takže x = x .

(B) Konkrétní vstupy a výstupy

f (x) =12x2

1 +x22 +x2

3 +x2 +x3 ; n= 3 ;

A =

3 0 00 2 10 1 2

; b =

000

; B =

[1 2 −11 −1 1

]; c =

[42

]; h(B) = 1 , p= 2 .

BBT =

[6 −2

−2 3

]; v : BBT v = c ; v =

[87

107

]; x = BT v =

1875727

.

w ∈ R3−2 ; jeden bázový vektor w =

−13231

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

B · W = D :

1 2 −10 −3 20 0 1

·

w1

w2

w3

=

001

;

78 6.3. LAGRANGEOVY MULTIPLIKÁTORY

x = x +yw =

1876727

+ y

−13231

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

421y+

57549

;

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

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

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 maximumnějaké funkce více proměnných s podmínkou, že mezi těmito proměnnými exis-tuje vazba zadaná jednou, nebo několika rovnicemi, je třeba přičíst k minima-lizované (maximalizované) funkci určující rovnice vazby vynásobené neurčitýmimultiplikátory a pak hledat minimum nebo maximum tohoto součtu tak, jakoby byly nezávislé. Získané rovnice spolu s rovnicemi vazeb umožní určit všechnyneznámé“.

Důkazy vět v tomto odstavci a ve svém důsledku metoda Lagrangeových multiplikátorů seopí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 → R

1 , X ⊂ R2 , které jsou spojitě diferencovatelné

v okolí Uδ(x) ⊂ X . Předpokládáme, že x = (x1, x2) je bod lokálního minima (nebo maxima)funkce f , který je lokálním řešením rovnice

h(x1,x2) = 0.

Potom existuje číslo v ∈ R1 takové, že platí

(P) grad f (x1, x2)+ vgradh(x1,x2) = 0.

Důkaz. Ze spojitosti a diferencovatelnosti funkce h a z rovnosti h(x1, x2) = 0 a znaménka∂h(x1,x2)

∂x2

∣∣∣∣(x1,x2)=(x1,x2)

6= 0 plyne, že existuje jediná diferencovatelná funkce

ϕ : Uδ(x1) → R1 , x2 = ϕ(x1),

která je lokálním řešením funkcionální rovnice h(x1,x2) = 0 , tj platí rovnosti

h(x1,ϕ(x1)) = 0 ∀x1 ∈ Uδ(x1) ,

x2 = ϕ(x1) ,


(Q) ϕ′(x1) =dx2

dx1

∣∣∣∣x1

= −∂h(x1,x2)

∂x1

∂h(x1,x2)∂x2

.

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

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

Podmínka minima

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

lze tedy také psátF(x1) ≤ F(x1) , ∀x1 ∈ Uδ(x1) ,

a nutnou podmínku optimality

(R) 0 =dF (x1)

dx1

∣∣∣∣x1

=[∂f∂x1

+∂f∂x1

· dx2

dx1

]

X1

.

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

∂f (x1, x2)∂x1

+ v · ∂h(x1, x2)∂x1

= 0 ,

∂f (x1, x2)∂x2

+ v · ∂h(x1, x2)∂x2

= 0 .

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ě(x1, x2) jsou vektory

grad f (x1, x2) , gradh(x1, x2)

a jsou kolineární s koeficientem kolineárnosti v.

Tečný vektor v bodě (x1, x2) ke křivce

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

je

w =

[ ∂h(x1,x2)∂x2

−∂(x1,x2)∂x1

]=

[dx1

ϕ′(x1)dx1

]=

[dx1

dx2

]

(x1,x2)

neboť rovnice tečny ke křivce V v bodě (x1, x2) je

∂h(x1, x2)∂x1

· (x1 − x1)+∂h(x1, x2)

∂x2· (x2 − x2) = 0

a

ϕ′(x1) = −∂h(x1,x2)

∂x1

∂h(x1,x2)∂x2

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

w⊥grad f (x1, x2) , w⊥gradh(x1, x2) ,


tj. podmínky

wT grad f (x1, x2) = 0

wT gradh(x1, x2) = 0

Geometrická interpretace nutné podmínky: kolineárnost vektorů (grad f ) a (gradh) v bodě(x1, x2).

x1

x2

0

f < c

f = c

f > c

hladiny f

růst fx

V

h(x1, x2) = 0

w

grad f(x1, x2)

grad h(x1, x2)

x2

x1

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


x1

x2

0

f < c

f = c

f > c

hladiny f

V

h(x) = 0

x

x

x

-grad f(x)

grad h(x)

grad h(x)

-grad f(x)

růst f

x1

x2

Obrázek 6.3.3: x není bod minima (extrému) f na Vx je bod lokálního minima f na Vx je bod lokálního maxima f na V

x1

x2

0

f < c

f = c

f > c

hladiny f

V

h(x) = 0

x

grad f(x)

grad h(x)

w

x1

x2

Obrázek 6.3.4: Bod x není bodem lokálního extrému, f na Vavšak grad f (x), gradh(x) jsou kolineární (závislé).

Pozorování: Podmínka kolineárnosti vektorů grad f a gradh není postačující podmínkou


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 ⊂ R

n , j = 1,2, . . . ,p, které jsou spojitědiferencovatelné v okolí Uδ(x) ⊂ X .

Předpokládáme, že x je bod lokálního minima (nebo maxima) funkce f , který je lokál-ním řešením rovnic

hj(x1,x2, . . . ,xn) = 0 , j = 0,2, . . . ,p .

Dále předpokládáme, že vektory

gradhj(x) , j = 1,2, . . . ,p

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

D(h)D(x)

=D(h1,h2, . . . ,hp)D(x1,x2, . . . ,xn)

=[∂hj(x)∂xi

]= gradh(x)

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

Potom existují reálná čísla v1, v2, . . . , vp taková, ne všechna nulová, že platí

(S) grad f (x)+p∑

j=1

vj gradh(x) = 0

Číslům vj , 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

; gradh(x) =

gradh1(x)gradh2(x)

...gradhp(x)

=D(h)D(x)

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

(T) grad f (x)+(gradT h(x)

)v = 0

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

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

ϕi : Uδ(x1) → R1 , Uδ(x1) ⊂ R

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

při označeníx = (x1, x2, . . . , xp︸︷︷︸

x2

, xp+1, . . . , xn)︸︷︷︸x1

je zobrazení z Rn−p do R

p

Φ =

ϕ1(x1)ϕ2(x1)

...ϕp(x1)

, x2 = Φ(x1)


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

tj. platíh(Φ(x1),x1) = 0 , ∀x1 ∈ Uδ(x1) ⊂ R

n−p ;

x2 = Φ(x1).

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

D(h)D(x)

=D(h)D(x2)

∣∣∣∣x

.

PotomD(Φ)D(x)

∣∣∣∣x1

= −[

D(h)D(x2)

]−1

x

·[

D(h)D(x1)

]

x

Sestrojíme funkci F : Rn−p → R

1 (redukce dimenze)

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

Z požadavkuF(x1) ≤ F(x1) , ∀x1 ∈ Uδ(x1) ⊂ R

n−p

plyne (nutné podmínky optimality)

∂F(x1)∂xj

= 0 , j = p+ 1,p+ 2, . . . ,n .

tj.

(U)∂f (x)∂xj

+p∑

i=1

∂f (x)∂xi

· ∂ϕi(x1)∂xj

= 0 , j = p+ 1,p+ 2, . . . ,n .

Derivace∂ϕi

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

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

(V)p∑

i=1

∂hk(x)∂ϕi

· ∂ϕi(x)∂xj

+∂hk(x)∂xj

= 0 , k = 1,2, . . . ,p ; j = p+ 1,p+ 2, . . . ,n .

Pomocná soustava regulární maticí

(W)[

D(h)D(x2)

]· v = −

∂f∂x1

...∂f

∂xp

↔

p∑

i=1

∂hk

∂xivi =

∂f∂xk

, k = 1,2, . . . ,p

má jediné řešení v ∈ Rp. Zde jsme vzali jen těch p rovnic, jejichž matice odpovídá lineárně

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 v1, v2, . . . , vp ze vztahu (W)a přičteme k n−p rovnostem vztahu (U). Po úpravě dostaneme n−p rovností

p∑

i=1

∂f (x)∂xi

+p∑

j=1

vj∂hj(x)∂xi

· ∂ϕi(x1)

∂xk

+∂f (x)∂xk

+p∑

j=1

vj∂hj(x)∂xk

= 0 , k = p+ 1,p+ 2, . . . ,n

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


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

S = span{gradh1(x),gradh2(x), . . . ,gradhp(x)}

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

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

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

Je-li x ∈ V bod minima funkce f : X → R1, potom musí být bodem dotyku tečného prostoru

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ýtgrad f (x)⊥T

a tedy také

(X) grad f (x) ∈ S

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

(Y) grad f (x) = −p∑

j=1

vj · gradhj(x) .

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

T ⊕ S = Rn .

Jsou-li vektory gradhj(x) , j = 1,2, . . . ,p lineárně závislé, pak (6.3.3.) pouze říká, že vektory

grad f (x),gradh1(x),gradh2(x), . . . ,gradhp(x)

jsou lineárně závislé, tj, existují čísla v0, v1, v2, . . . , vp (ne všechna nulová) taková, že platí

(Z) v0 grad f (x)+p∑

j=1

vj gradhj(x) = 0 .

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, X ⊂ R

n (spojitá, resp. diferencovatelná) a přípustná mno-žina V ⊂ X .

Úloha na minimum:

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

Úloha na maximum:

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

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

f (x) ≤ f (x) [f (x) ≥ f (x)]

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

Přesněji: Přípustný bod x ∈ V je lokálním řešením dané úlohy, jestliže existuje δ > 0 takové,ž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řípustnoumnož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ě:

b11x1 + b12x2 + · · ·+ b1nxn − c1 ≤ 0 ,b21x1 + b22x2 + · · ·+ b2nxn − c2 ≤ 0 ,. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .bm1x1 + bm2x2 + · · ·+ bmnxn − cm ≤ 0 .

V obecných úlohách se vazbové podmínky zapisují pomocí nelineárních funkcí

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

n → Rm ; g =

g1

g2...gm

.

Takže:

(D) 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},

kdeh : Rm → R

p; 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, ‖p‖ = 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); ‖p‖ = 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 gradgi(x)< 0, i ∈ I (x), ‖p‖ = 1}.

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

Množinu:Do(x) = {p ∈ R

m : pT gradgi(x) ≤ 0, i ∈ I (x), ‖p‖ = 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,δ), ‖d‖ = 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 gradf(x) < 0, ‖d‖ = 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 gradf(x) < 0 plynenerovnost 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 amnož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ěx ∈ V je F(x, f ) ∩ D(x,V ) = ∅, v neoptimálním bodě x je F(x, f ) ∩ D(x,V ) 6= ∅. . . . ostatníobrázky, zatím na nich pracuji. . .

7.1.5. Příklad

Mějme úlohumin{f (x1,x2)|(x1,x2) ∈ V },

kdef (x1,x2) = (x1 − 2)2 +x2

2,

V = {(x1,x2) ∈ R2 : −x1︸︷︷︸

g1

≤ 0, −x2︸︷︷︸g2

≤ 0, −1+x21 +x2︸︷︷︸

g3

≤ 0}

. . .

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í opti-malizace (tzv. „lineární programování“).

a) Formulace úlohy (úloh) - příklad

(G)

{min{f (x) | x ∈ V ⊂ R

2},max{f (x) | x ∈ V ⊂ R

2}.

kdef (x) = aT x = x1 + 3x2 (lineární funkce),

a =

[13

]; x =

[x1

x2

].

Přípustná množina V je v obou případech dána nerovnostními podmínkami (vazbami):

−x1 + 2x2 ≤ 6,x1 +x2 ≤ 5,

x1 ≥ 0,x2 ≥ 0,

maticově

−1 21 1

−1 00 −1

.[x1

x2

]≤

6500

.

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

maxV

f (x1,x2) = f(

43,113

)=

373,

minV

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

c) Reformulace úlohy - převod na kanonický tvarCí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,

B =

[−1 2 1 0

1 1 0 1

]; c =

[65

]

f (x) = f (x1,x2,x3,x4) = x2 + 3x2 + 0x3 + 0x4.


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 .

Počet voleb je dán číslem(4

2

)= 4·3·2·1

1·2 = 4!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é.

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í.

volit

elné

prom

ěnné

(=0)

dop

očít

ávan

épr

oměn

néso

usta

vyB

x-c=

0

bazi

cké

(par

ikul

ární

)ře

šení

neba

zick

éře

šení

nezá

por

nost

bazi

ckéh

oře

šení

f(x

)

x3 = 0x4 = 0

x1 = 43

x2 = 113

43

11300

13

−1310

−23

−1301

ano f = 37

3(Max)

x2 = 0x4 = 0

x1 = 5x3 = 11

50

110

−11

−30

−10

−11

ano f = 5

x2 = 0x3 = 0

x1 = −6x4 = 11

−600

11

210

−3

101

−1

ne —

x1 = 0x4 = 0

x2 = 5x3 = −4

05

−40

1−1

30

0−1

21

ne —

x1 = 0x3 = 0

x2 = 3x4 = 2

0302

1120

−32

0−1

2112

ano f = 9

x1 = 0x2 = 0

x3 = 6x4 = 5

0065

101

−1

01

−2−1

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 neba-zické 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) = R

n

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

Je-li x ∈ V bod lokálního minima funkce f , potom

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

F(x, f ) ∩ D(x,V ) = ∅ ,

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

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

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

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) gradf(x)+∑

i∈I(x)

ui · gradgi(x) = 0,

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


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

(J)

gradf(x)+m∑

i=1

ui · gradgi(x) = 0,

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

(podmínky komplementarity)

. . .

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}a nechť funkce f ,gi , i= 1,2, . . . ,m jsou spojitě diferencovatelné v uδ(x) ⊂ X .

1. Potom existují nezáporná čísla u0 ≥ 0 , ui ≥ 0 , i ∈ I (x), ne všechna nulová, taková, žeplatí(OKKT) u0 grad f (x)+

∑

i∈I(x)

ui · gradgi(x) = 0

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

(OKKT)

u0 grad f (x)+m∑

i=1

ui · gradgi(x) = 0

ui · gi(x) = 0 , i= 1,2, . . . ,m (podmínky komplementarity)

.

3. Když navíc gradgi(x) , i ∈ I (x) jsou lineárně nezávislé (podmínka regularity), potomexistují nezáporná čísla ui ≥ 0 , i ∈ I (x), ne všechna nulová, taková, že platí

(KKT)

grad f (x)+∑

I∈(x)

ui · gradgi(x) = 0 ,

uigi(x) = 0 , i= 1,2, . . . ,m (podmínky komplementarity)

.

respektive

(KKT)

grad f (x)+m∑

i=1

ui · gradgi(x) = 0 ,

uigi(x) = 0 , i= 1,2, . . . ,m (podmínky komplementarity)

.

. . . obrázek. . .

Komentář k obrázku: v bodě minima x vektory −gradg1(x) , −gradg3(x) směřují dovnitřpřípustné množiny V , lze z nich tedy sestavit lineární kombinaci s nezápornými koeficientyu1 ≥ 0 ,u3 ≥; takovou, že

gradf(x) = −u1 gradg1(x)− u2 gradg2(x).

. . . obrázek. . .

Komentář: Také zde je vidět. že gradf(x) se dá v bodě minima vyjádřit jako lineární kom-binace vektorů −gradg2(x) , −gradg3(x). Naproti tomu v bodě maxima x se gradf(x) dávyjádřit jako lineární kombinace vektorů +gradg1(x) , gradg3(x).

V případě dalšího obrázku (. . . ) jsou gradg3(x) , gradg2(x) lineárně závislé a neplatí zdepodmínka (3), ale pouze podmínka (1).

. . .

92 7.3. METODA NUTNÝCH OKKT, KKT PODMÍNEK - PŘÍKLADY

7.2.5. Poznámka

Když pro x ∈ V (bod minima, bod maxima) platí gi(x) < 0 pro i = 1,2, . . . ,m, pakvzhledem k x není žádná vazební podmínka aktivní, tj. I (x) = ∅ (prázdná množina), potomz podmínek komplementarity plyne

u1 = 0 , u2 = 0 , . . . , um = 0.

Musí proto být u0 6= 0 a nutná podmínka (1) se redukuje na

gradf(x) = 0.

To také odráží poznatek, že možina (kužel) spádových směrů S(x,V ) , F(x, f ) je v bodě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︸︷︷︸

g1

≤ 0 , −x2︸︷︷︸g2

≤ 0 , −1+x21 +x2︸︷︷︸

g3

≤ 0}.

V odstavci (7.1.5.) jsme ukázali princip analýzy řešitelnosti dané úlohy na minimum. Kon-kré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í soustavynutných podmínek.

Přípravné výpočty:

gradf =

[2(x1 − 2)

2x2

], gradg1 =

[−10

], gradg2 =

[0

−1

], gradg3 =

[2x1

1

].

Chceme tedy stanovit takové x1 , x2 , u0 , u1 , u2 , u2 , aby platila soustava (OKKT), resp.(KKT) podmínek:

(S) u1 · gradf(x1,x2)+u1 · gradg1(x1,x2)+u2 · gradg2(x1,x2)+u3 · gradg3(x1,x2) = 0 ;

podmínky komplementarity

(K) u1 · g1(x1,x2) = 0 , u2 · g2(x1,x2) = 0 , u3 · g3(x1,x2) = 0 ,


znaménkové podmínky (Z)

(Z1) u1 ≥ 0 , u2 ≥ 0 , u3 ≥ 0 ; pro minimum

(Z2) u1 ≤ 0 , u2 ≤ 0 , u3 ≤ 0 ;pro maximun

a podmínky řešitelnosti (P)

(P) −x1︸︷︷︸g1

≤ 0 , −x2︸︷︷︸g2

≤ 0 , −1+x21 +x2︸︷︷︸

g3

≤ 0}

Takže konkrétně máme:

(S)

{[u0 2(x1 − 2)]−u1 +u3 · 2x1 = 0 ,

[u0 2x2] −u2 +u3 = 0 ,

(K) u1x1 = 0 , u2x2 = 0 , u3(−1+x21 +x2) = 0 .

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žnostisplně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 vazeb-ních podmínek. Pro složitější úlohy je metoda přímého využití nutných podmínek optimalitymimo realitu.

Volba u0 = 0 - nabízí se další volby a jejich důsledky:

(S)

{−u1 +u3 · 2x1 = 0 ,

−u2 +u3 = 0 ,

(K) u1x1 = 0 , u2x2 = 0 , u3(−1+x21 +x2) = 0 .

znaménkové podmínky (Z)

(Z1) u1 ≥ 0 , u2 ≥ 0 , u3 ≥ 0 ; pro minimum

(Z2) u1 ≤ 0 , u2 ≤ 0 , u3 ≤ 0 ;pro maximun

a podmínky řešitelnosti (P)

(P) −x1︸︷︷︸g1

≤ 0 , −x2︸︷︷︸g2

≤ 0 , −1+x21 +x2︸︷︷︸

g3

≤ 0}

a) x1 6= 0 , x2 6= 0 :(S)−−→ u1 = 0 , u2 = 0

(S)−−→ u3 = 0 ; ⇒ neřešitelná soustava, ∀ ui = 0 !

b) x1 = 0 , x2 6= 0 :(S)−−→ u2 = 0

(K)−−→ u3 = 0 , u1 = 0 ; ⇒ neřešitelná !

c) x1 6= 0 , x2 = 0 :(S)−−→ u1 = 0 ,

(K)−−→ , u3 = 0 , u2 = 0 ; ⇒ neřešitelná !

d) x1 = 0 , x2 = 0 :(S)−−→ u3 = 0 ,

(K)−−→ , 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)

{2(x1 − 2)−u1 + 2x1u3 = 0 ,

2x2 −u2 +u3 = 0 ,

(K) u1x1 = 0 , u2x2 = 0 , u3(−1+x21 +x2) = 0 .


(Z1) u1 ≥ 0 , u2 ≥ 0 , u3 ≥ 0 ;

(Z2) u1 ≤ 0 , u2 ≤ 0 , u3 ≤ 0 .

(P) x1 ≥ 0 , x2 ≥ 0 , −1+x21 +x2 ≤ 0

A opět postupně prověříme nám již známe možnosti

a) x1 6= 0 , x2 6= 0 :(S)−−→ u1 = 0 , u2 = 0 ,

(K)−−→ 2x2 +u3 = 0 ,2x1 − 4+ 2x1u3 = 0 , x1(2+ 2u3) = 4

musi být: x1 > 0 , x2 > 0 (plyne z (P)),u3 6= 0 (požadavek nenulovosti)

(K)−−→ −1+x21 +x2 = 0

(Z1) → u3 > 0 je v rozporu s požadavkem 2x2 +u3 = 0takže podmínky nezápornosti nejsou splněny !

(Z2) → u3 < 0 ,(S)−−→ x2 = −u3

2 , x1 = 21+u3

, → u3 >−1

Po dosazení do podmínky −1+x21 +x2 = 0 dostaneme

u33 + 4u2

3 + 5u3 − 6 = 0.Tato rovnice nemá v intervalu (−1,0) kořen !Podmínky nekladnosti také nejsou splněny !

b) x1 = 0 , x2 6= 0 : 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

(S)−−→ 2(−2)−u1 = 0 → u1 = −42+u3 = 0 → u3 = −2

(Z1) → neřešitelné(Z2) → v bodě (0,1) jsou splněny podmínky nekladnosti a podmínka

grad f (0,1) +u1 · gradg1(0,1) +u3 · gradg3(0,1) = 0 má tvar[−42

]+ (−4)

[−10

]+ (−2)

[01

]=

[00

].

c) x1 6= 0 , x2 = 0 : u1 = 0 , u3(−1+x21) = 0 ; z (P) : x1 > 0 ,

2(x1 − 2)+ 2x1u2 = 0 , −u2 +u3 = 0 ; variantau3 = 0 nepřipadá v úvahuu3 6= 0 vede k hodnotě x1 = 1 (kořen x1 = −1 není přípustný)

(Z1) → u3 = 1 , u2 = 1 a (K)má tvar[−20

]+ 1 ·

[0

−1

]+ 1 ·

[21

]=

[00

].

(Z2) → neřešitelné

d) x1 = 0 , x2 = 0 : Pozor ! Zjistíme, že pro: u1 = −4 , u2 = 0 , u3 = 0jsou podmínky (S) splněny, ale bod (0,0) nemůže být bodem minimaani maxima.

7.3.2. Příklad-2

Chceme stanovit řešení úloh

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


min{f (x1,x2) | (x1,x2) ∈ V } ,kde

f (x1,x2) = (x1 − 2)2 +x22 ,

V = {(x1,x2) ∈ R2 : −x1︸︷︷︸

g1

≤ 0 , −x2︸︷︷︸g2

≤ 0 , x2 − (1−x1)3

︸︷︷︸g3

≤ 0}.

. . . bude obrázek. . .

Přípravné výpočty:

gradf =

[2(x1 − 2)

2x2

], gradg1 =

[−10

], gradg2 =

[0

−1

], gradg3 =

[3(1−x1)2

1

].

Chceme tedy stanovit takové x1 , x2 , u0 , u1 , u2 , u2 , aby platily (OKKT) podmínky:

(S) u0

[2(x1 − 2)

2x2

]+u1

[−10

]+u2

[0

−1

]+u33(1−x)2 =

[00

],

podmínky komplementarity

(K) u1(−x1) = 0 , u2(−x2) = 0 , u3

(x2 − (1−x1)3

)= 0 .

Buď

(Z1) u1 ≥ 0 , u2 ≥ 0 , u3 ≥ 0 ;

nebo

(Z2) u1 ≤ 0 , u2 ≤ 0 , u3 ≤ 0 ;

a podmínky

(P) x1 ≥ 0 , x2 ≥ 0 , x2 − (1−x1)3 ≤ 0 .

Postupujeme podle stejné strategie jako v odst. (7.3.1.).

Volba u0 = 0

a) x1 6= 0 , x2 6= 0 :(K)−−→ u1 = 0 , u2 = 0 ,

(S)−−→ u3 = 0 neřešitelné !

b) x1 = 0 , x2 6= 0 :(K)−−→ u2 = 0 ,

(S)−−→ u3 = 0 , u1 = 0 neřešitelné !

c) x1 6= 0 , x2 = 0 : ??−→ u1 = 0 , u3 =(−(1−x1)3

);

možnost: u3 = 0 vede k neřešitelným (1) podmínkám;možnost: u3 6= 0 vede k x1 = 1.

Pouze konstatujme, že v bodě (1,0) jsou gradg1, gradg2 kolineární. Nelzerozhodnout, zda jde o bod minima.

d) x=0 , x2 = 0 :(K)−−→ u3 = 0 ,

(S)−−→ u2 = 0 , u1 = 0 neřešitelné !

Volba u0 = 1

(S)

{2(x1 − 2)−u1 + 3u3(1−x1)2 = 0

2x2 −u2 +u3 = 0

a) x1 6= 0 , x2 6= 0 :(K)−−→ u1 = 0 , u2 = 0 ,

u3 6= 0 ,

(S)−−→ x2 − (1−x1)3 = 0

u3 = 0 , neřešitelné


Podle (S): 2(x1 − 2)+ 3u3(1−x1)2 = 02x+u3 = 0 , → u3 = −2x2

Protože x1 > 0 , x2 > 0 (podmínka řešitelnosti), potom je u3 ≤ 0a muselo by být x1 − 2 = −3

2u3(1−x1)2 ≥ 0 , což je ve sporu s přípustností !

b) x1 = 0 , x2 6= 0 :(K)−−→ u2 = 0 ,

u3 = 0 ,

(K)−−→ x2 = 0 , spor !

u3 6= 0 ,(S)−−→ x2 = 1 ,

(K)−−→ u2 = −2 , → u1 = 10v bodě (0,1) je možné maximum !

c) x1 6= 0 , x2 = 0 :(K)−−→ u1 = 0 ,

u3 6= 0 ,

(K)−−→ x1 = 1 ,(S)−−→ −2 = 0 !

u3 = 0 , neřešitelné !

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ýchpodmí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 FAD0 6= 0 (jde zřejmě o bod maxima).

Kužel spádových směrů v bodě x = (1,0)F(x, f ) = {d ∈ R

2 , dT gradf(x)< 0 , ‖d‖ = 1} : d = [d1,d2]T , d21 +d2

2 = 1.

grad f (x) =

[2(x1 − 2)

2x2

]

(1,0)

=

[−20

],

d ∈ F ⇔ [d1,d2] ·[−20

]< 0 ⇒ d1 > 0 , d2 libovolné.

Otevřený kužel přípustných směrů v bodě x = (1,0)D0(x) = {p ∈ R

2 : pT gradgi(x)< 0 , i ∈ I (x) , I (x) = {2,3}.

gradg2(x) =

[0

−1

], gradg3(x) =

[−3(1−x1)2

1

]

(1,0)

=

[01

].

p ∈ D0 ⇒ [p1,p2] ·[

0−1

]< 0 :

p1 libovolnép2 > 0

,

[p1,p2] ·[01

]< 0 :

p1libovolnép2 < 0

,

⇒ D0(x) = ∅

Závěr: F ∩ D0 = ∅ , ale (KKT) podmínky nejsou splněny.


Uzavřený kužel přípustných směrů v bodě x = (1,0)D0(x) = {s ∈ R

2 : sT gradgi(x) ≤ 0 , i ∈ I (x)} , I (x) = {2,3}.

s ∈ D0 ⇒ [s1,s2] ·[

0−1

]≤ 0 :

s1 libovolnés2 ≥ 0 ,

[s1,s2] ·[01

]≤ 0 :

s1 libovolnés2 ≤ 0 ,

⇒ D0(x) = {s1 libovolné , s2 = 0}

Závěr: F ∩ D0 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 funkciL : X ×R

m → R1 předpisem

L(x,u) = f (x)+m∑

i=1

uigi(x) , x ∈ X ⊂ Rn , u ∈ R

m ,(Ka)

tj.

L(x,u) = f (x)+ uT g(x) , u =

u1

u2...um

, g(x) =

g1(x)g2(x)

...gm(x)

.(Kb)

Obecnou Lagrangeovu funkci L : X ×R1 ×R

m → R1 definujeme předpisem

L(x,u) = f (x)+m∑

i=1

uigi(x) ,(La)

tj.

L(x,u) = f (x)+ uT g(x) ,(Lb)

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

Pro u0 = 1, resp. u0 = 0 chceme stanovit x ∈ X ⊂ Rn , u ∈ R

m takové, že platí

(S) gradx L(y,u) = 0 , (soustava KKT, příp. OKKT),

(K) uigi(x) = 0 , i ∈ I (x) , (komplementarita), u1 ne všechny nulové

(P) 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 pod-mí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 nerov-

nostní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 : x2

1 +x22 − 9 ≤ 0 , x1 +x2 − 1 ≤ 0}.

Zde máme

L(x1,x1,u0,u1,u2) = u0(x21 +x2

2)+u1(x21 +x2

2 − 9)+u2(x1 +x2 − 1)

(S) u0

[2x1

1

]+u1

[2x1

2x2

]+u2

[11

]=

[00

],

(K) u1(x21 +x2

2 − 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


a) u1 6= 0 , u2 6= 0 :

Z (K) dostáváme x1 =1−

√17

2, x2 =

1+√

172

, x1 =1+

√17

2, x2 =

1−√

172

,

Z (S) vyjde u1 = −12< 0 , u2 =

√17 − 1

1> 0 , u1 = −1

2< 0 , u2 =

−1−√

172

< 0

(x1,x2) není KKT bod ; (x1,x2) je KKT bod.

b) u1 = 0 , u2 6= 0 :

Z (S)máme u1 = −1 , x1 =12

; Z (K) x2 =12

;

(x1,x2) je KKT bod.

c) u1 6= 0 , u2 = 0 :

Z (S)máme u1 = −1 , x3 =12

; z (K) x1 = −√

352

;

(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: f

(−

√352,12

)= 9 = max f ;

f (0,−3) = −3 = min f ;

Pozor: Ne každý KKT bod je bodem extrému !

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íchprocesů. 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 AngelesThe Millan Company, New York Collier - Mac Millan Limited, London, 1975 (Překladdo 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. NewYork, 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 Olo-mouc, 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íchzdrojů.

[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ýchoptimalizačních úlohách.

103

Date post:	25-Feb-2020
Category:	Documents
Upload:	others
View:	3 times
Download:	0 times

MOT - Matematické optimalizační technologiehome.zcu.cz/~mika/MO/S_Mika_L_Vlcek_MOT.pdf ·...

Documents