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

${\begin{aligned}{\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{aligned}}$

, kde $x\in M\subseteq \mathbb {R} ^{n}$ definujeme Lagrangeovu funkci $L:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\rightarrow \mathbb {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 \mathbb {R}$ a $\nu _{i}\in \mathbb {R}$ se nazývají Lagrangeovy multiplikátory. Vektory $\lambda \in \mathbb {R} ^{m}$ a $\nu \in \mathbb {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 \mathbb {R} ^{p}:g(\lambda ,\nu )\leq P^{*}$

Pokud navíc platí Slaterova podmínka potom taky platí silná dualita, tj. $\max _{\lambda \geq \mathbf {0} ,\ \nu \in \mathbb {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. 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,...,m\}$. Pak dvojice úloh lineárního programování (LP)

minimalizovat $\sum _{i=1}^{n}c_{i}x_{i}$

za podmínek ${\textstyle \sum _{i=1}^{n}A_{i,j}x_{i}\geq b_{j}\forall j\in J_{\geq }}$

$\sum _{i=1}^{n}A_{i,j}x_{i}\leq b_{j}\forall j\in J_{\leq }$

$\sum _{i=1}^{n}A_{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}^{m}b_{j}y_{j}$

za podmínek $\sum _{j=1}^{m}A_{j,i}y_{j}\leq c_{i}\forall j\in I_{\geq }$

$\sum _{j=1}^{m}A_{j,i}y_{j}\geq c_{i}\forall j\in I_{\leq }$

$\sum _{j=1}^{m}A_{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. 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. 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{aligned}&\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{aligned}}$

kde $\mathbf {A} \in \mathbb {R} ^{m\times n},\ \mathbf {x} ,\ \mathbf {c} \in \mathbb {R} ^{m},\ \mathbf {y} ,\ \mathbf {b} \in \mathbb {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ť $\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{aligned}&\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{aligned}}$

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. 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{aligned}&\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{aligned}}$

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. 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}$). 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. 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 ${\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

$minVar(\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. 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ě

$minf(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. Dále označme$f^{*}(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

$maxb^{T}y-{\frac {1}{2}}y^{T}A(\sum )^{-}1A^{T}y={\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 )^{-}1A^{T}}}$. Označme ${\bar {x}}$ řešení původní úlohy a platí $f(x)+f^{*}(A^{T}y)-y\cdot Ax=0$, kde $\cdot$ značí skalární součin. Konečně dostáváme optimální portfolio

${\bar {x}}={\frac {1}{\sum }}A^{T}{\frac {1}{A(\sum )^{-}1A^{T}}}b$.