Dualita (optimalizace)
Dualita v teorií optimalizace znamená, že optimalizační problém může být interpretován dvěma způsoby, skrz úlohu primární, nebo k ní úlohu duální. Vztah těchto dvou úloh se liší v závislosti na vlastnostech řešeného problému. Obecně, optimální řešení duální úlohy tvoří spodní mez pro optimální řešení primární úlohy. V konkrétních případech mají tyto dvě úlohy velmi příjemné vlastnosti jakou je například silná dualita.
Obecná formulace
[editovat | editovat zdroj]Pro primární úlohu matematického programování ve tvaru[1]
, kde definujeme Lagrangeovu funkci předpisem
,
proměnné a se nazývají Lagrangeovy multiplikátory. Vektory a nazveme duální proměnné k původnímu problému.
Duální Lagrangeovu funkci definujeme jako
.
Buď optimální řešení primární úlohy potom platí
Pokud navíc platí Slaterova podmínka[2] potom taky platí silná dualita, tj. . V takovém případe se tedy optimální řešení primární a duální úlohy shodují.
Dualita v úloze lineárního programování
[editovat | editovat zdroj]Dualita se týká dvojice úloh lineárního programování (LP), která je dána společnými vstupními daty, to jest maticí A s m řádky a n sloupci, m-rozměrným vektorem b a n-rozměrným vektorem c. Kromě daných koeficientů je každá úloha lineárního programování (LP) určena také druhem optimalizace, tj. jestli se daný problém týče minimalizace neboli maximalizace, dále tvarem omezení, jestli se v problému vyskytuje rovnost nebo nerovnost, přítomností či absencí podmínek nezápornosti. Obecná dvojice duálních úloh v matematice vypadá následovně.
Definice
[editovat | editovat zdroj]Nechť je dána matice s m řádky a n sloupci, m-rozměrný vektor b, n-rozměrný vektor c a disjunktní rozklady množin indexů , . Pak dvojice úloh lineárního programování (LP)
minimalizovat
za podmínek
,
maximalizovat
za podmínek
se nazývá dvojice duálních úloh lineárního programování (LP). Množinu přípustných řešení úlohy minimalizace označíme jako , tj. množinu všech , která splňují výše uvedené podmínky, a množinu všech jejich optimálních řešení symbolem . Množinu přípustných řešení úlohy maximalizace označíme jako , tj. množinu všech , která splňují výše uvedené podmínky, a množinu všech jejich optimálních řešení symbolem .
Někdy také hovoříme o úloze primární a k ní úloze duální. Jako primární označujeme tu úlohu, která vznikla na základě řešeného problému. Zbylou úlohu, pak nazýváme úlohou k ní duální. V případě, že je optimalizační problém lineární, tedy úlohu lineárního programování (LP) ve standardním tvaru, dvojici duálních symetrických úloh lineárního programování (LP) můžeme zapsat ve tvaru[3]
kde . V tomto případě minimalizační úlohu nazveme primární a maximalizační úlohu, úlohou k ní duální. Množinu přípustných řešení primární úlohy budeme značit a množinu přípustných řešení duální úlohy označíme . Úlohy lineárního programování lze převádět na zvolený tvar. Stačí se proto zabývat pouze jedním typem dvojice duálních úloh. Dokázaná tvrzení jsou potom platná i pro libovolnou dvojici duálních úloh, nejen pro ty ve standardním tvaru. Pro tuhle dvojici úloh pak platí následující tvrzení.
Slabá věta o dualitě pro případ LP
[editovat | editovat zdroj]Nechť jsou libovolná, pak platí
přičemž rovnost nastane, právě když jsou splněny podmínky komplementarity
Důkaz
[editovat | editovat zdroj]Tvrzení stačí ukázat pro dvojici symetrických duálních úloh, jak bylo zmíněno výše. Pro libovolné , tj. pro přípustné řešení úlohy minimalizace a pro přípustné řešení úlohy maximalizace, platí
.
Rovnost v předcházejícím výrazů nastává, právě tehdy když
tedy když jsou obě nerovnosti splněny jako rovnosti. Po rozepsáni předcházejících výrazů dostaneme přímo podmínky komplementarity.
Silná věta o dualitě pro případ LP
[editovat | editovat zdroj]Primární úloha má optimální řešení, právě tehdy když duální úloha má optimální řešení. V takovém případě navíc platí
Jedním z důsledků silné věty o dualitě v LP je například Farkasová věta.
Duální bazické řešení
[editovat | editovat zdroj]Pro lineární optimalizační úlohu a bázi definujeme , které je jednoznačně určené podmínkou . Vektor nazveme duální bazické řešení příslušné k bázi .
Aplikace duality
[editovat | editovat zdroj]Nejzákladnější aplikace duality nastává pro případ, kdy jsou splněny podmínky pro silnou dualitu a součet dimenzí duálních proměnných je a zároveň dimenze primární proměnné je . V tomto případě lze složitější primární problém řešit pomocí často jednoduššího duálního problému. Zatím co k řešení primárního problému by byly zapotřebí pokročilejší výpočetní techniky, například simplexový algoritmus, duální problém může být řešitelný graficky a k jeho vyřešení (zejména, jestli se jedná o úlohu LP) může stačit jednoduše jeho nakreslení na papír. Jednoduchou interpretací dvojice duálních úloh je predikce vývoje po investici, jinými slovy, uvažujeme maximální zisk výroby v daném podniku, který je dán optimalizační úlohou. V ekonomické literatuře se optimální řešení duální úlohy nazývá stínové ceny nebo duální ceny.
Finanční portfolio
[editovat | editovat zdroj]Jednou z nejzákladnějších aplikací z praxe je maximalizace výnosu akcí finančního portfolia. Z matematického pohledu rozumíme pod pojmem portfolio vektor , jehož člen reprezentuje podíl jehož i-tého aktiva (s cenou v čase t reprezentovanou pomocí ). Hodnota portfolia v čase t je rovna , kde značí skalární součin. V praxi se můžeme setkat s různými typy portfolií. Podstatným příkladem je Markowitzovo portfolio.
Markowitzovo portfolio
[editovat | editovat zdroj]Markowitz ve své teorii uvažuje jenom riziková aktiva. Pro pevný výnos je zapotřebí volit portfolia s minimální variací, která také slouží jako míra rizika. Obecně, zajímá nás portfolio s vysokým očekávaným výnosem a zároveň s minimální variancí. Tahle teorie přímo vychází teorie optimalizace. Označme jako cenu rizikových aktiv, portfolio. Nechť je dána očekávaná výplata, počáteční kapitál. Pak formulujeme úlohu
,
kde je řádkový vektor, je řádkový vektor a platí . Předpisem rozumíme střední hodnotu náhodné veličiny X. Maticovým zápisem , lze danou úlohu přepsat následovně
.
Zde platí, že , ,. Zjevně je symetrická, pozitivně definitní matice. Dále označme. Jelikož , je splněná podmínka silné věty o dualitě a tedy úloha je duální k úloze
.
Optimálním řešením této úlohy duální k zadané je . Označme řešení původní úlohy a platí , kde značí skalární součin. Konečně dostáváme optimální portfolio
.
Reference
[editovat | editovat zdroj]- ↑ BOYD, Stephen; VANDENBERGHE, Lieven. Convex Optimization. https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf#page=230: Cambridge University Press, 2004. ISBN 978-0-521-83378-3.
- ↑ SLATER, Morton. Lagrange Multipliers Revisited. Cowles Commission Discussion Paper. 1950. Dostupné online.
- ↑ DUPAČOVÁ, Jitka; LACHOUT, Petr. Úvod do optimalizace. Praha: Matfyzpress, 2011. 10 s. ISBN 978-80-7378-176-7. S. 31.