Slabá dualita - Weak duality

v aplikovaná matematika, slabá dualita je koncept v optimalizace který uvádí, že rozdíl v dualitě je vždy větší než nebo rovno 0. To znamená, že řešení prvotního (minimalizačního) problému je vždy větší nebo rovno řešení přidruženého dvojí problém. To je proti silná dualita který platí pouze v určitých případech.^[1]

Použití

Mnoho primal-dual aproximační algoritmy jsou založeny na principu slabé duality.^[2]

Slabá věta o dualitě

The původní problém:

Maximalizovat C^TX podléhá A X ≤ b, X ≥ 0;

The dvojí problém,

Minimalizovat b^Ty podléhá A^Ty ≥ C, y ≥ 0.

Uvádí se věta o slabé dualitě C^TX ≤ b^Ty.

Jmenovitě, pokud ${ displaystyle (x_ {1}, x_ {2}, ...., x_ {n})}$ je proveditelné řešení pro prvotní maximalizaci lineární program a ${ displaystyle (y_ {1}, y_ {2}, ...., y_ {m})}$ je proveditelné řešení pro lineární program dvojí minimalizace, pak lze teorém o slabé dualitě uvést jako ${ displaystyle sum _ {j = 1} ^ {n} c_ {j} x_ {j} leq sum _ {i = 1} ^ {m} b_ {i} y_ {i}}$, kde ${ displaystyle c_ {j}}$ a ${ displaystyle b_ {i}}$ jsou koeficienty příslušných objektivních funkcí.

Důkaz:C^TX = X^TC≤ X^TA^Ty≤ b^Ty

Zobecnění

Obecněji, pokud ${ displaystyle x}$ je proveditelné řešení problému prvotní maximalizace a ${ displaystyle y}$ je proveditelné řešení problému dvojí minimalizace, pak naznačuje slabá dualita ${ displaystyle f (x) leq g (y)}$ kde ${ displaystyle f}$ a ${ displaystyle g}$ jsou objektivní funkce pro prvotní a dvojí problém.

Viz také

• Konvexní optimalizace

Reference