Dualita (optimalizace)

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

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, t.j. . 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ýka dvojice úloh lineárního programování (LP), která je dána společnými vstupními daty, to jest maticou 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, t.j. 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ýva dvojice duálních úloh lineárního programování (LP). Množinu přípustných řešení úlohy minimalizace označíme jako , t.j. 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 , t.j. 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áklade řešeného problému. Zbylou úlohu, pak nazývame úlohou k ní duální. V případě, že je optimalizační problém lineární, teda úlohu lineárního prgramování (LP) ve standradní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é , t.j. pro příspustné ř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 investcici, 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 otimální řešení duální úlohy nazýva stínové ceny nebo duální ceny.

Finanční portfolio[editovat | editovat zdroj]

Jednou z nejzákladnejší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 podiel 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ůznymi 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. Obecne, zajíma nás portfolio s vysokým očekávaným výnosem a zároveň s mnimální variací. 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ásledovne

.

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éhle úlohy duální k zadané je . Označme řešení původní úlohy a platí , kde značí skalární součin. Konečně dostávame optimálni portfolio

.

Reference[editovat | editovat zdroj]

  1. 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. (anglicky) 
  2. SLATER, Morton. Lagrange Multipliers Revisited. Cowles Commission Discussion Paper. 1950. Dostupné online. (anglicky) 
  3. DUPAČOVÁ, Jitka; LACHOUT, Petr. Úvod do optimalizace. Praha: Matfyzpress, 2011. 10 s. ISBN 978-80-7378-176-7. S. 31.