Název:
Metody řešení dvouúrovňových optimalizačních úloh
Překlad názvu:
Solving methods for bilevel optimization problems
Autoři:
Lžičař, Jiří ; Kopa, Miloš (vedoucí práce) ; Branda, Martin (oponent) Typ dokumentu: Diplomové práce
Rok:
2019
Jazyk:
eng
Abstrakt: [eng][cze] The presented thesis discusses bilevel programming problems with the focus on solution algorithms. Bilevel programming problem is a hierarchical programming problem, where constraints contain another programming problem. We formulate basic bilevel optimization theory and describe three types of so- lution algorithms for bilevel programming problems: Algorithms based on KKT reformulation where the lower level is replaced by its KKT conditions, algorithms based on optimal value function where the bilevel programming problem is re- duced to a single level problem using the optimal value function of the lower level problem, and algorithms solving linear bilevel programming problems. Using real data for portfolio optimization bilevel programming problems, we compare ability to solve the problems and computing time of some of the pre- sented algorithms. 1Předložená práce se zabývá dvouúrovňovými optimalizačními úlohami se za- měřením na řešící algoritmy. Úloha dvouúrovňového programování je hierarchická optimalizační úloha, jejíž omezení obsahují další optimalizační úlohu. Práce formuluje základní teorii k dvouúrovňové optimalizaci a popisuje tři typy algoritmů řešících dvouúrovňové optimalizační úlohy: Algoritmy založené na KKT reformulaci, kdy je úloha na dolní úrovni nahrazena jejími KKT podmín- kami; algoritmy založené na reformulaci pomocí funkce optimální hodnoty, kdy je dvouúrovňová úloha redukována na jednoúrovňovou za pomoci funkce optimální hodnoty; a algoritmy řešící úlohy lineárního dvouúrovňového programování. S použitím reálných dat v dvouúrovňových úlohách optimalizace portfolia je porovnána rychlost některých z uvedených algoritmů a jejich schopnost vyřešit danou úlohu. 1
Klíčová slova:
algoritmy; aplikace na reálné problémy; dvouúrovňové optimalizační úlohy; KKT reformulace; mean-risk model; optimalizace; algorithms; applications to real-life problems; bilevel optimization problems; KKT reformulation; mean-risk model; optimization