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{array}{cc}\text{minimalizovat }& f_0(x)\\ \text{za podmínek }& f_i(x)\le 0,\mathrm{\forall }i\in \{1,\dots ,m\}\\ & h_i(x)=0,\mathrm{\forall }i\in \{1,\dots ,p\}\end{array}$

, kde $x\in M\subseteq {ℝ}^n$ definujeme Lagrangeovu funkci $L:{ℝ}^n\times {ℝ}^m\times {ℝ}^p\to ℝ$ 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 ℝ$ a ${\nu }_i\in ℝ$ se nazývají Lagrangeovy multiplikátory. Vektory $\lambda \in {ℝ}^m$ a $\nu \in {ℝ}^p$ nazveme duální proměnné k původnímu problému.

Duální Lagrangeovu funkci definujeme jako

$g(\lambda ,\nu ):=\underset{x\in M}{\inf }L(x,\lambda ,\nu )=\underset{x\in M}{\inf }(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í

$\mathrm{\forall }\lambda \ge \mathrm{𝟎},\nu \in {ℝ}^p:g(\lambda ,\nu )\le P^{*}$

Pokud navíc platí Slaterova podmínka potom taky platí silná dualita, tj. $\underset{\lambda \ge \mathrm{𝟎},\nu \in {ℝ}^p}{\max }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 ${\sum }_{i=1}^n{A}_{i,j}{x}_i\ge b_j\mathrm{\forall }j\in J_{\ge }$

$\sum _{i=1}^n{A}_{i,j}{x}_i\le b_j\mathrm{\forall }j\in J_{\le }$

$\sum _{i=1}^n{A}_{i,j}{x}_i=b_j\mathrm{\forall }j\in J_{=}$

$x_i\ge 0\mathrm{\forall }i\in I_{\ge }$

$x_i\le 0\mathrm{\forall }i\in I_{\le }$

$x_i\in R\mathrm{\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\le c_i\mathrm{\forall }j\in I_{\ge }$

$\sum _{j=1}^m{A}_{j,i}{y}_j\ge c_i\mathrm{\forall }j\in I_{\le }$

$\sum _{j=1}^m{A}_{j,i}{y}_j=c_i\mathrm{\forall }j\in I_{\in }$

$y_j\ge 0\mathrm{\forall }i\in J_{\ge }$

$y_j\le 0\mathrm{\forall }i\in J_{\le }$

$y_j\in R\mathrm{\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{array}{cc}& \min \{{𝐜}^{𝖳}𝐱:𝐀𝐱\ge 𝐛,𝐱\ge \mathrm{𝟎}\},\\ & \max \{{𝐛}^{𝖳}𝐲:{𝐀}^{𝖳}𝐲\le 𝐜,𝐲\ge \mathrm{𝟎}\},\end{array}$

kde $𝐀\in {ℝ}^{m\times n},𝐱,𝐜\in {ℝ}^m,𝐲,𝐛\in {ℝ}^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ť $𝐱\in M,𝐲\in N$ jsou libovolná, pak platí

${𝐜}^{𝖳}𝐱\ge {𝐛}^{𝖳}𝐲$

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

$\begin{array}{cc}& \mathrm{\forall }j\in \{1,\dots ,m\}:\text{ buď }{y}_j=0\text{ nebo }\sum _{i=1}^n{A}_{ij}{x}_i=b_j,\\ & \mathrm{\forall }i\in \{1,\dots ,n\}:\text{ buď }{x}_i=0\text{ nebo }\sum _{j=1}^m{A}_{ij}{y}_j=c_i.\end{array}$

Důkaz

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

${𝐜}^{𝖳}𝐱\ge ({𝐀}^{𝖳}𝐲{)}^{𝖳}𝐱={𝐲}^{𝖳}𝐀𝐱\ge {𝐲}^{𝖳}𝐛={𝐛}^{𝖳}𝐲$.

Rovnost v předcházejícím výrazů nastává, právě tehdy když

$\begin{array}{cc}& {𝐲}^{𝖳}(𝐀𝐱-𝐛)=0,\\ & (𝐜-{𝐀}^{𝖳}𝐲{)}^{𝖳}𝐱=0,\end{array}$

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{𝐱\in M}{\min }{𝐜}^{𝖳}𝐱=\underset{𝐲\in N}{\max }{𝐛}^{𝖳}𝐲$

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\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 $\theta =({\theta }^1,{\theta }^2,\dots ,{\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 $\hat{S}=(S^1\dots S^m)$ jako cenu rizikových aktiv, $\theta =({\theta }^1,\dots ,{\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 {\hat{S}}_1)$

$s.t.𝖤[\hat{\theta }\cdot {\hat{S}}_1]=r_0$

$\hat{\theta }\cdot {\hat{S}}_0=w_0$,

kde $\hat{S}$ je řádkový vektor, $\hat{\theta }$ je řádkový vektor a platí $𝖤\mathsf{[}{\widehat{𝖲}}_{\mathrm{𝟣}}\mathsf{]}=[𝖤\mathsf{[}{\hat{S}}_{\mathrm{𝟣}}^{\mathrm{𝟣}}\mathsf{]},\mathsf{\dots },𝖤\mathsf{[}{\hat{S}}_{\mathrm{𝟣}}^{𝗆}\mathsf{]}]$. Předpisem $𝖤[X]$ rozumíme střední hodnotu náhodné veličiny X. Maticovým zápisem $A=(\genfrac{}{}{0ex}{}{𝖤[{\hat{S}}_1]}{{\hat{S}}_0})$, $b=(\genfrac{}{}{0ex}{}{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={\hat{\theta }}^T$, $\sum =𝖤[({\hat{S}}_1-𝖤[\widehat{S_1}]{)}^T({\hat{S}}_1-𝖤[\widehat{S_1}]{)}^T]=(𝖤[({\hat{S}}_1^i-𝖤[\widehat{S_1^i}]{)}^T({\hat{S}}_1^j-𝖤[\widehat{S_1^j}]{)}^T])$,$i,j=1,\dots 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

$max{b}^{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 $\overline{y}=\frac{b}{A(\sum {)}^{-}1A^T}$. Označme $\overline{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

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