Obsah Předmluva vii 1 Úvod 1 1.1 Základní pojmy............................ 1 1.2 Základní pojmy z konvexní analýzy a teorie optimalizace...... 3 1.3 Základní pojmy z numerické minimalizace.............. 3 2 Konvexní množiny 5 2.1 Základní pojmy............................ 5 2.2 Oddělování konvexních množin ................... 13 2.3 Krajní body konvexních množin................... 19 2.4 Kombinatorické a topologické vlastnosti konvexních množin .... 21 2.5 Cvičení................................ 24 3 Konvexní funkce 27 3.1 Základní vlastnosti konvexních funkcí................ 27 3.2 Kritéria konvexnosti diferencovatelných funkcí........... 36 3.3 Spojitost a směrová derivace konvexních funkcí........... 40 3.4 Další vlastnosti konvexních funkcí.................. 43 3.5 Subgradient a subdiferenciál..................... 44 3.6 Fenchelova transformace....................... 48 3.7 Systémy konvexních a afinních nerovností.............. 55 3.8 Cvičení................................ 58 4 Nutné a dostatečné podmínky optimality 61 4.1 Extrémy konvexních funkcí...................... 62 4.2 Lagrangeův princip a Kuhnovy-Tuckerovy podmínky........ 63 4.3 Dualita v úlohách matematického programování........... 69 4.4 Závislost řešení úlohy matematického programování na parametrech 80 iii 4.5 Cvičení................................ 89 5 Numerické metody jednorozmerné minimalizace 91 5.1 Minimalizace unimodálních funkcí.................. 92 5.1.1 Algoritmus prostého dělení intervalu............. 92 5.1.2 Metoda půlení intervalu ................... 93 5.1.3 Fibonacciova metoda..................... 93 5.1.4 Metoda zlatého řezu..................... 96 5.2 Minimalizace mnohoextremálních funkcí.............. 97 5.2.1 Metoda prosté minimalizace................. 98 5.2.2 Metoda lomených čar...................... 98 5.3 Závěrečné poznámky a cvičení.................... 99 5.3.1 Další minimalizační algoritmy................ 99 5.3.2 Optimálni algoritmy..................... 100 5.3.3 Cvičení............................ 100 6 Numerické metody nepodmíněné minimalizace 101 6.1 Základní pojmy............................ 101 6.2 Gradientní metody .......................... 104 6.2.1 Metoda nejrychlejšího spádu................. 104 6.2.2 Gradientní metoda s modifikovaným drobením kroku .... 107 6.3 Metoda sdružených směrů ...................... 108 6.3.1 Metoda sdružených gradientů pro minimalizaci kvadratických funkcí.......................... 110 6.3.2 Metoda sdružených gradientů pro nekvadratické funkce . . 114 6.3.3 Metoda sdružených směrů nultého řádu........... 114 6.4 Newtonova metoda.......................... 116 6.5 Metoda proměnné metriky...................... 119 7 Lineárni a kvadratické programování 123 7.1 Lineární programování........................ 124 7.1.1 Teoretické základy...................... 124 7.1.2 Jeden krok simplexové metody................ 127 7.2 Úloha kvadratického programování ................. 130 7.2.1 Kuhnovy-Tuckerovy podmínky pro úlohu kvadratického programování .......................... 130 7.2.2 Duální úloha v kvadratickém programování......... 132 7.3 Metoda Hildrethova a ďEsopova................... 133 7.3.1 Předpoklady ......................... 133 IV 7.3.2 Algoritmus.......................... 134 7.3.3 Ilustrační příklad....................... 136 7.4 Metoda Theila a van de Panneho................... 138 7.4.1 Základy metody ....................... 138 7.4.2 Postup výpočtu........................ 141 7.4.3 Ilustrační príklad....................... 142 7.5 Wolfeho metoda............................ 146 7.5.1 Princip metody........................ 146 7.5.2 Krátky tvar metody...................... 147 7.5.3 Dlouhý tvar metody ..................... 149 7.5.4 Ilustrační příklad....................... 152 8 Numerické metody podmíněné minimalizace 157 8.1 Metoda přípustných směrů...................... 157 8.1.1 Základní pojmy........................ 158 8.1.2 Případ lineárních ohraničení................. 159 8.1.3 Normalizace směru...................... 162 8.1.4 Případ nelineárních ohraničení................ 163 8.1.5 Algoritmus.......................... 164 8.1.6 Ilustrační příklad....................... 165 8.2 Metoda penalizačních funkcí..................... 169 8.2.1 Základy metody ....................... 169 8.2.2 Konvergence metody..................... 170 8.2.3 Regularita a penalizační teorie optimality.......... 172 8.3 Metoda projekce gradientu...................... 177 Literatura 181 Rejstřík 184 v