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

Pro primární úlohu matematického programování ve tvaru^[1]

, kde $x\in <!--\; \in \; -->M\subseteq <!--\; \subseteq \; -->R^n$ definujeme Lagrangeovu funkci $L:R^n\times <!--\; \times \; -->R^m\times <!--\; \times \; -->R^p\to <!--\; \to \; -->R$ předpisem

$L(x,\mathrm{\lambda <!--\; \lambda \; -->},\mathrm{\nu <!--\; \nu \; -->}):=f_0\left(x\right)+\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}{\mathrm{\lambda <!--\; \lambda \; -->}}_i{f}_i\left(x\right)+\underset{i=1}{\overset{p}{\sum <!--\; \sum \; -->}}{\mathrm{\nu <!--\; \nu \; -->}}_i{h}_i\left(x\right)$,

proměnné ${\mathrm{\lambda <!--\; \lambda \; -->}}_i\in <!--\; \in \; -->R$ a ${\mathrm{\nu <!--\; \nu \; -->}}_i\in <!--\; \in \; -->R$ se nazývají Lagrangeovy multiplikátory. Vektory $\mathrm{\lambda <!--\; \lambda \; -->}\in <!--\; \in \; -->R^m$ a $\mathrm{\nu <!--\; \nu \; -->}\in <!--\; \in \; -->R^p$ nazveme duální proměnné k původnímu problému.

Duální Lagrangeovu funkci definujeme jako

$g(\mathrm{\lambda <!--\; \lambda \; -->},\mathrm{\nu <!--\; \nu \; -->}):=\underset{x\in <!--\; \in \; -->M}{inf}L(x,\mathrm{\lambda <!--\; \lambda \; -->},\mathrm{\nu <!--\; \nu \; -->})=\underset{x\in <!--\; \in \; -->M}{inf}\left(f_0\right(x)+\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}{\mathrm{\lambda <!--\; \lambda \; -->}}_i{f}_i(x)+\underset{i=1}{\overset{p}{\sum <!--\; \sum \; -->}}{\mathrm{\nu <!--\; \nu \; -->}}_i{h}_i(x\left)\right)$.

Buď $P^{\ast <!--\; \ast \; -->}$ optimální řešení primární úlohy potom platí

$\mathrm{\forall <!--\; \forall \; -->}\mathrm{\lambda <!--\; \lambda \; -->}\ge <!--\; \ge \; -->0,\mathrm{\nu <!--\; \nu \; -->}\in <!--\; \in \; -->R^p:g(\mathrm{\lambda <!--\; \lambda \; -->},\mathrm{\nu <!--\; \nu \; -->})\le <!--\; \le \; -->P^{\ast <!--\; \ast \; -->}$

Pokud navíc platí Slaterova podmínka^[2] potom taky platí silná dualita, tj. $\underset{\mathrm{\lambda <!--\; \lambda \; -->}\ge <!--\; \ge \; -->0,\mathrm{\nu <!--\; \nu \; -->}\in <!--\; \in \; -->R^p}{max}g(\mathrm{\lambda <!--\; \lambda \; -->},\mathrm{\nu <!--\; \nu \; -->})=:D^{\ast <!--\; \ast \; -->}=P^{\ast <!--\; \ast \; -->}$. 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í

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

Nechť je dána matice $A$ s m řádky a n sloupci, m-rozměrný vektor b, n-rozměrný vektor c a disjunktní rozklady množin indexů $I=\{1,2,...,n\}$, $J=\{1,2,...,m\}$. Pak dvojice úloh lineárního programování (LP)

minimalizovat $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{c}_i{x}_i$

za podmínek $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{A}_{i,j}{x}_i\ge <!--\; \ge \; -->b_j\mathrm{\forall <!--\; \forall \; -->}j\in <!--\; \in \; -->J_{\ge <!--\; \ge \; -->}$

$\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{A}_{i,j}{x}_i\le <!--\; \le \; -->b_j\mathrm{\forall <!--\; \forall \; -->}j\in <!--\; \in \; -->J_{\le <!--\; \le \; -->}$

$\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{A}_{i,j}{x}_i=b_j\mathrm{\forall <!--\; \forall \; -->}j\in <!--\; \in \; -->J_{=}$

$x_i\ge <!--\; \ge \; -->0\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->I_{\ge <!--\; \ge \; -->}$

$x_i\le <!--\; \le \; -->0\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->I_{\le <!--\; \le \; -->}$

$x_i\in <!--\; \in \; -->R\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->I_{\in <!--\; \in \; -->}$,

maximalizovat $\underset{j=1}{\overset{m}{\sum <!--\; \sum \; -->}}{b}_j{y}_j$

za podmínek $\underset{j=1}{\overset{m}{\sum <!--\; \sum \; -->}}{A}_{j,i}{y}_j\le <!--\; \le \; -->c_i\mathrm{\forall <!--\; \forall \; -->}j\in <!--\; \in \; -->I_{\ge <!--\; \ge \; -->}$

$\underset{j=1}{\overset{m}{\sum <!--\; \sum \; -->}}{A}_{j,i}{y}_j\ge <!--\; \ge \; -->c_i\mathrm{\forall <!--\; \forall \; -->}j\in <!--\; \in \; -->I_{\le <!--\; \le \; -->}$

$\underset{j=1}{\overset{m}{\sum <!--\; \sum \; -->}}{A}_{j,i}{y}_j=c_i\mathrm{\forall <!--\; \forall \; -->}j\in <!--\; \in \; -->I_{\in <!--\; \in \; -->}$

$y_j\ge <!--\; \ge \; -->0\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->J_{\ge <!--\; \ge \; -->}$

$y_j\le <!--\; \le \; -->0\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->J_{\le <!--\; \le \; -->}$

$y_j\in <!--\; \in \; -->R\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->J_{=}$

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 $M$, tj. množinu všech $x\in <!--\; \in \; -->R^n$, která splňují výše uvedené podmínky, a množinu všech jejich optimálních řešení symbolem $M^{\ast <!--\; \ast \; -->}$. Množinu přípustných řešení úlohy maximalizace označíme jako $N$, tj. množinu všech $y\in <!--\; \in \; -->R^m$, která splňují výše uvedené podmínky, a množinu všech jejich optimálních řešení symbolem $N^{\ast <!--\; \ast \; -->}$.

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 $A\in <!--\; \in \; -->R^{m\times <!--\; \times \; -->n},x,c\in <!--\; \in \; -->R^m,y,b\in <!--\; \in \; -->R^n$. 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 $M$ a množinu přípustných řešení duální úlohy označíme $N$. Ú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

Nechť $x\in <!--\; \in \; -->M,y\in <!--\; \in \; -->N$ jsou libovolná, pak platí

$c^{T}x\ge <!--\; \ge \; -->b^{T}y$

přičemž rovnost nastane, právě když jsou splněny podmínky komplementarity

Důkaz

Tvrzení stačí ukázat pro dvojici symetrických duálních úloh, jak bylo zmíněno výše. Pro libovolné $x\in <!--\; \in \; -->M,y\in <!--\; \in \; -->N$ , tj. pro přípustné řešení úlohy minimalizace a pro přípustné řešení úlohy maximalizace, platí

$c^{T}x\ge <!--\; \ge \; -->(A^{T}y{)}^{T}x=y^{T}Ax\ge <!--\; \ge \; -->y^{T}b=b^{T}y$.

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

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í

$\underset{x\in <!--\; \in \; -->M}{min}{c}^{T}x=\underset{y\in <!--\; \in \; -->N}{max}{b}^{T}y$

Jedním z důsledků silné věty o dualitě v LP je například Farkasová věta.

Duální bazické řešení

Pro lineární optimalizační úlohu a bázi $L$ definujeme $y\left(L\right)\in <!--\; \in \; -->R^m$, které je jednoznačně určené podmínkou $\left(A_L{)}^{T}y\right(L)=c_L$. Vektor $y\left(L\right)$ nazveme duální bazické řešení příslušné k bázi $L$.

Aplikace duality

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 $m+p\le <!--\; \le \; -->2$ a zároveň dimenze primární proměnné je $n>2$. 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

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 $\mathrm{\theta <!--\; \theta \; -->}=({\mathrm{\theta <!--\; \theta \; -->}}^1,{\mathrm{\theta <!--\; \theta \; -->}}^2,\dots <!--\; \dots \; -->,{\mathrm{\theta <!--\; \theta \; -->}}^m,)\in <!--\; \in \; -->R^{m+1}$, jehož člen ${\mathrm{\theta <!--\; \theta \; -->}}_i$ reprezentuje podíl jehož i-tého aktiva (s cenou v čase t reprezentovanou pomocí $S_t^i$). Hodnota portfolia $\mathrm{\theta <!--\; \theta \; -->}$ v čase t je rovna $t\cdot <!--\; \cdot \; -->S_t$, kde $\cdot <!--\; \cdot \; -->$ 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

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 $\stackrel{^<!--\; ^\; -->}{S}=(S^1\dots <!--\; \dots \; -->S^m)$ jako cenu rizikových aktiv, $\mathrm{\theta <!--\; \theta \; -->}=({\mathrm{\theta <!--\; \theta \; -->}}^1,\dots <!--\; \dots \; -->,{\mathrm{\theta <!--\; \theta \; -->}}^m)$ portfolio. Nechť $r_0$ je dána očekávaná výplata, $w_0$ počáteční kapitál. Pak formulujeme úlohu

$minVar(\mathrm{\theta <!--\; \theta \; -->}\cdot <!--\; \cdot \; -->{\stackrel{^<!--\; ^\; -->}{S}}_1)$

$s.t.E[\stackrel{^<!--\; ^\; -->}{\mathrm{\theta <!--\; \theta \; -->}}\cdot <!--\; \cdot \; -->{\stackrel{^<!--\; ^\; -->}{S}}_1]=r_0$

$\stackrel{^<!--\; ^\; -->}{\mathrm{\theta <!--\; \theta \; -->}}\cdot <!--\; \cdot \; -->{\stackrel{^<!--\; ^\; -->}{S}}_0=w_0$,

kde $\stackrel{^<!--\; ^\; -->}{S}$ je řádkový vektor, $\stackrel{^<!--\; ^\; -->}{\mathrm{\theta <!--\; \theta \; -->}}$ je řádkový vektor a platí $E\left[{\stackrel{^<!--\; ^\; -->}{S}}_1\right]=\left[E\left[{\stackrel{^<!--\; ^\; -->}{S}}_1^1\right],\dots <!--\; \dots \; -->,E\left[{\stackrel{^<!--\; ^\; -->}{S}}_1^m\right]\right]$. Předpisem $E\left[X\right]$ rozumíme střední hodnotu náhodné veličiny X. Maticovým zápisem $A=(\frac{E\left[{\stackrel{^<!--\; ^\; -->}{S}}_1\right]}{{\stackrel{^<!--\; ^\; -->}{S}}_0})$, $b=(\frac{r_0}{w_0})$ lze danou úlohu přepsat následovně

$minf\left(x\right)=\frac{1}{2}{x}^T\sum <!--\; \sum \; -->x$

$s.t.Ax=b$ .

Zde platí, že $x={\stackrel{^<!--\; ^\; -->}{\mathrm{\theta <!--\; \theta \; -->}}}^T$, $\sum <!--\; \sum \; -->=E\left[\right({\stackrel{^<!--\; ^\; -->}{S}}_1-<!--\; -\; -->E\left[\stackrel{^<!--\; ^\; -->}{S_1}\right]{)}^T({\stackrel{^<!--\; ^\; -->}{S}}_1-<!--\; -\; -->E[\stackrel{^<!--\; ^\; -->}{S_1}\left]{)}^T\right]=\left(E\right[({\stackrel{^<!--\; ^\; -->}{S}}_1^i-<!--\; -\; -->E[\stackrel{^<!--\; ^\; -->}{S_1^i}\left]{)}^T\right({\stackrel{^<!--\; ^\; -->}{S}}_1^j-<!--\; -\; -->E\left[\stackrel{^<!--\; ^\; -->}{S_1^j}\right]{)}^T\left]\right)$,$i,j=1,\dots <!--\; \dots \; -->m$. Zjevně $\sum <!--\; \sum \; -->$ je symetrická, pozitivně definitní matice. Dále označme$f^{\ast <!--\; \ast \; -->}\left(y\right)=\frac{1}{2}{y}^T\frac{y}{\sum <!--\; \sum \; -->}$. Jelikož $b\in <!--\; \in \; -->rangeA$, je splněná podmínka silné věty o dualitě a tedy úloha je duální k úloze

$max{b}^{T}y-<!--\; -\; -->\frac{1}{2}{y}^{T}A(\sum <!--\; \sum \; -->{)}^{-<!--\; -\; -->}1A^{T}y=\frac{1}{2}{b}^T\frac{1}{A(\sum <!--\; \sum \; -->{)}^{-<!--\; -\; -->}1A^t}b$.

Optimálním řešením této úlohy duální k zadané je $\stackrel{¯<!--\; ¯\; -->}{y}=\frac{b}{A(\sum <!--\; \sum \; -->{)}^{-<!--\; -\; -->}1A^T}$. Označme $\stackrel{¯<!--\; ¯\; -->}{x}$ řešení původní úlohy a platí $f\left(x\right)+f^{\ast <!--\; \ast \; -->}\left(A^{T}y\right)-<!--\; -\; -->y\cdot <!--\; \cdot \; -->Ax=0$, kde $\cdot <!--\; \cdot \; -->$ značí skalární součin. Konečně dostáváme optimální portfolio

$\stackrel{¯<!--\; ¯\; -->}{x}=\frac{1}{\sum <!--\; \sum \; -->}{A}^T\frac{1}{A(\sum <!--\; \sum \; -->{)}^{-<!--\; -\; -->}1A^T}b$.

Reference