Cesko.wiki Dualita (optimalizace)
Author
Albert FloresDualita 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
\begin{align} \text{minimalizovat } &f_0(x) \\ \text{za podmínek } &f_i(x) \leq 0,\ \forall i \in \left \{1,\ldots,m \right \} \\ &h_i(x) = 0,\ \forall i \in \left \{1,\ldots,p \right \} \end{align}
, kde x \in M \subseteq \R^n definujeme Lagrangeovu funkci L: \R^n \times \R^m \times \R^p \rightarrow \R předpisem
L(x,\lambda,\nu):=f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x),
proměnné \lambda_i \in \R a \nu_i \in \R se nazývají Lagrangeovy multiplikátory. Vektory \lambda \in \R^m a \nu \in \R^p nazveme duální proměnné k původnímu problému.
Duální Lagrangeovu funkci definujeme jako
g(\lambda,\nu):=\inf_{x \in M } L(x,\lambda,\nu)=\inf_{x \in M} (f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x)).
Buď P^* optimální řešení primární úlohy potom platí
\forall \lambda \geq \mathbf 0,\ \nu \in \R^p : g(\lambda,\nu) \leq P^*
Pokud navíc platí Slaterova podmínka potom taky platí silná dualita, t. j. +more \max_{\lambda \geq \mathbf 0,\ \nu \in \R^p} g(\lambda,\nu)=:D^*=P^*. 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. +more 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 \mathrm{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,. +more,m\}. Pak dvojice úloh lineárního programování (LP).
minimalizovat \sum_{i=1}^nc_{i}x_{i}
za podmínek \sum_{i=1}^nA_{i,j}x_{i}\geq b_{j} \forall j\in J_{\geq}
\sum_{i=1}^nA_{i,j}x_{i}\leq b_{j} \forall j\in J_{\leq}
\sum_{i=1}^nA_{i,j}x_{i}= b_{j} \forall j\in J_{=}
x_{i}\geq 0 \forall i\in I_{\geq}
x_{i}\leq 0 \forall i\in I_{\leq}
x_{i}\in R \forall i\in I_{\in},
maximalizovat \sum_{j=1}^mb_{j}y_{j}
za podmínek \sum_{j=1}^mA_{j,i}y_{j}\leq c_{i} \forall j \in I_{\geq}
\sum_{j=1}^mA_{j,i}y_{j}\geq c_{i} \forall j \in I_{\leq}
\sum_{j=1}^mA_{j,i}y_{j}= c_{i} \forall j \in I_{\in}
y_{j}\geq 0 \forall i\in J_{\geq}
y_{j}\leq 0 \forall i\in J_{\leq}
y_{j}\in R \forall i\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 \mathrm{M}, tj. +more množinu všech x\in R^{n}, která splňují výše uvedené podmínky, a množinu všech jejich optimálních řešení symbolem \mathrm{M}^{*}. Množinu přípustných řešení úlohy maximalizace označíme jako \mathrm{N}, tj. množinu všech y\in R^{m}, která splňují výše uvedené podmínky, a množinu všech jejich optimálních řešení symbolem \mathrm{N}^{*}.
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. +more 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.
\begin{align} &\min \{\mathbf{c}^{\mathsf T} \mathbf{x}\ :\ \mathbf{A}\mathbf{x} \geq \mathbf{b},\ \mathbf x \geq \mathbf 0 \}, \\ &\max \{\mathbf{b}^{\mathsf{T}}\mathbf{y}\ : \ \mathbf{A}^{\mathsf{T}}\mathbf{y} \leq \mathbf{c},\ \mathbf{y} \geq \mathbf 0 \}, \end{align}
kde \mathbf{A} \in \R^{m \times n},\ \mathbf{x}, \ \mathbf{c} \in \R^m,\ \mathbf{y},\ \mathbf{b} \in \R^n. V tomto případě minimalizační úlohu nazveme primární a maximalizační úlohu, úlohou k ní duální. +more 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ť \mathbf x \in M,\ \mathbf y \in N jsou libovolná, pak platí
\mathbf{c}^{\mathsf{T}} \mathbf{x} \geq \mathbf{b}^{\mathsf{T}} \mathbf{y}
přičemž rovnost nastane, právě když jsou splněny podmínky komplementarity
\begin{align} &\forall j \in \{1,\dots,m \}: \text{ buď } y_j=0\ \text{ nebo } \sum_{i=1}^n A_{ij}x_i=b_j, \\ &\forall i \in \{1,\dots,n \}: \text{ buď } x_i=0\ \text{ nebo } \sum_{j=1}^m A_{ij}y_j=c_i. \end{align}
Důkaz
Tvrzení stačí ukázat pro dvojici symetrických duálních úloh, jak bylo zmíněno výše. Pro libovolné \mathbf x \in M,\ \mathbf y \in N , tj. +more pro přípustné řešení úlohy minimalizace a pro přípustné řešení úlohy maximalizace, platí.
\mathbf{c}^{\mathsf{T}} \mathbf{x} \geq (\mathbf{A}^{\mathsf{T}} \mathbf{y})^{\mathsf{T}} \mathbf{x}= \mathbf{y}^{\mathsf{T}} \mathbf{A} \mathbf{x} \geq \mathbf{y}^{\mathsf{T}} \mathbf{b}= \mathbf{b}^{\mathsf{T}} \mathbf{y}.
Rovnost v předcházejícím výrazů nastává, právě tehdy když
\begin{align}
&\mathbf{y}^{\mathsf T} (\mathbf{A} \mathbf{x} - \mathbf{b})=0,\\
&(\mathbf{c}-\mathbf{A}^{\mathsf T}\mathbf{y})^{\mathsf T} \mathbf{x}=0,
\end{align}
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í
\min_{\mathbf x \in M} \mathbf{c}^{\mathsf T} \mathbf{x}= \max_{\mathbf y \in N} \mathbf{b}^{\mathsf{T}} \mathbf{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(L)\in R^{m}, které je jednoznačně určené podmínkou (A_{L})^{T}y(L)=c_{L}. Vektor y(L) 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 \leq 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. +more 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 \theta=(\theta^1,\theta^2,\ldots,\theta^m)\in R^{m+1}, jehož člen \theta_i reprezentuje podíl jehož i-tého aktiva (s cenou v čase t reprezentovanou pomocí S_t^i). +more Hodnota portfolia \theta v čase t je rovna t\cdot S_t, kde \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. +more Obecně, zajímá nás portfolio s vysokým očekávaným výnosem a zároveň s minimální variací. Tahle teorie přímo vychází teorie optimalizace. Označme \widehat{S}= (S^1\ldots S^m) jako cenu rizikových aktiv, \theta=(\theta^1,\ldots,\theta^m) portfolio. Nechť r_0 je dána očekávaná výplata, w_0 počáteční kapitál. Pak formulujeme úlohu.
min Var(\theta\cdot\widehat{S}_1)
s.t. \mathsf{E}[\widehat{\theta}\cdot\widehat{S}_1]=r_0
\widehat{\theta}\cdot\widehat{S}_0=w_0,
kde \widehat{S} je řádkový vektor, \widehat{\theta} je řádkový vektor a platí \mathsf{E[\widehat{S}_1]}=[\mathsf{E[\widehat{S}_1^1],\ldots,E[\widehat{S}_1^m]}]. Předpisem \mathsf{E}[X] rozumíme střední hodnotu náhodné veličiny X. +more Maticovým zápisem A=\binom{\mathsf{E}[\widehat{S}_1]}{\widehat{S}_0}, b=\binom{r_0}{w_0} lze danou úlohu přepsat následovně.
min f(x)=\frac{1}{2}x^T\sum x
s.t.Ax=b .
Zde platí, že x=\widehat{\theta}^T, \sum=\mathsf{E}[(\widehat{S}_1-\mathsf{E}[\widehat{S_1}])^T(\widehat{S}_1-\mathsf{E}[\widehat{S_1}])^T]=(\mathsf{E}[(\widehat{S}_1^i-\mathsf{E}[\widehat{S_1^i}])^T(\widehat{S}_1^j-\mathsf{E}[\widehat{S_1^j}])^T]),i,j=1,\ldots m. Zjevně \sum je symetrická, pozitivně definitní matice. +more Dále označmef^*(y)=\frac{1}{2}y^T\frac{y}{\sum}. Jelikož b\in rangeA, je splněná podmínka silné věty o dualitě a tedy úloha je duální k úloze.
max b^Ty-\frac{1}{2}y^TA(\sum)^-1 A^Ty=\frac{1}{2}b^T\frac{1}{A(\sum)^-1A^t}b.
Optimálním řešením této úlohy duální k zadané je \bar{y}=\frac{b}{A(\sum)^-1 A^T}. Označme \bar{x} řešení původní úlohy a platí f(x)+f^*(A^Ty) - y\cdot Ax=0, kde \cdot značí skalární součin. +more Konečně dostáváme optimální portfolio.
\bar{x}=\frac{1}{\sum}A^T\frac{1}{A(\sum)^-1A^T}b.