Slabá dualita

Slabá dualita je koncept v optimalizaci , který říká, že mezera duality je vždy větší nebo rovna nule. To znamená, že řešení primárního problému (problému minimalizace) je vždy větší nebo rovno řešení souvisejícího duálního problému . Tento termín je v protikladu k silné dualitě , která je splněna pouze za určitých podmínek [1] .

Použití

Mnoho přímých duálních [2] aproximačních algoritmů je založeno na principu slabé duality [3] .

Věta o slabé dualitě

Přímý úkol:

Maximalizovat za podmínky ;

\mathbf {c} ^{T}\mathbf {x}

A\mathbf {x} \leqslant \mathbf {b} ,\mathbf {x} \geqslant 0

Dvojitý úkol:

Minimalizovat předmět .

\mathbf {b} ^{T}\mathbf {y}

A^{T}\mathbf {y} \geqslant \mathbf {c} ,\mathbf {y} \geqslant 0

Slabá věta o dualitě říká, že . $\mathbf {c} ^{T}\mathbf {x} \leqslant \mathbf {b} ^{T}\mathbf {y}$

Konkrétně, pokud je proveditelné řešení přímého problému maximalizace lineárního programování a je proveditelným řešením duálního problému minimalizace lineárního programování, pak lze větu o slabé dualitě formulovat následovně: , kde a jsou koeficienty odpovídajícího objektivní funkce. $(x_{1},x_{2},....,x_{n})$ $(y_{1},y_{2},....,y_{m})$ ${\displaystyle \sum _{j=1}^{n}c_{j}x_{j}\leqslant \sum _{i=1}^{m}b_{i}y_{i))$ ${\displaystyle c_{j))$ $bi$

Důkaz: $\mathbf {c} ^{T}\mathbf {x} =\mathbf {x} ^{T}\mathbf {c} \leqslant \mathbf {x} ^{T}A^{T}\mathbf {y} \leqslant \mathbf {b} ^{T}\mathbf {y}$

Zobecnění

V obecnějším případě, pokud je proveditelné řešení problému primární maximalizace a je proveditelné řešení problému duální minimalizace, vyplývá ze slabé duality, že , kde a jsou objektivní funkce pro primární a duální problémy, v tomto pořadí. $X$ $y$ $f(x)\leqslant g(y)$ $F$ $G$

Viz také

Konvexní programování

Poznámky

↑ Boţ, Grad, Wanka, 2009 , str. jeden.
↑ Prvotní-duální algoritmus je algoritmus pro současné řešení primárního a duálního problému.
↑ Gonzalez, 2007 , str. 2.

Literatura

Radu Ioan Boţ, Sorin-Mihai Grad, Gert Wanka. Dualita ve vektorové optimalizaci . - Berlin: Springer-Verlag, 2009. - S. 1. - ISBN 978-3-642-02885-4 . - doi : 10.1007/978-3-642-02886-1 .
Teofilo F. Gonzalez. Příručka aproximačních algoritmů a metaheuristiky . - CRC Press, 2007. - S. 2-12. — ISBN 9781420010749 .