Svag dualitet

Svag dualitet er et begreb inden for optimering , der siger, at dualitetsgabet altid er større end eller lig med nul. Det betyder, at løsningen på det primære problem (minimeringsproblemet) altid er større end eller lig med løsningen på det tilhørende dobbelte problem . Dette udtryk er i modsætning til stærk dualitet , som kun opfyldes under visse betingelser [1] .

Brug

Mange direkte dobbelte [2] tilnærmelsesalgoritmer er baseret på princippet om svag dualitet [3] .

Svag dualitetssætning

Direkte opgave:

Maksimer under betingelsen ;

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

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

Dobbelt opgave:

Minimer med forbehold for .

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

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

Den svage dualitetssætning siger, at . $\mathbf {c} ^{T}\mathbf {x} \leqslant \mathbf {b} ^{T}\mathbf {y}$

Nemlig, hvis det er en gennemførlig løsning på det direkte problem med at maksimere lineær programmering , og er en mulig løsning på det dobbelte problem med at minimere lineær programmering, så kan den svage dualitetssætning formuleres som følger: , hvor og er koefficienterne for den tilsvarende objektive funktioner. $(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))$ $b_i$

Bevis: $\mathbf {c} ^{T}\mathbf {x} =\mathbf {x} ^{T}\mathbf {c} \leqslant \mathbf {x} ^{T}A^{T}\mathbf {y} \leqslant \mathbf {b} ^{T}\mathbf {y}$

Generaliseringer

I et mere generelt tilfælde, hvis er en gennemførlig løsning på det primære maksimeringsproblem og er en mulig løsning på det dobbelte minimeringsproblem, følger det af svag dualitet , at hvor og er de objektive funktioner for henholdsvis de primære og dobbelte problemer. $x$ $y$ $f(x)\leqslant g(y)$ $f$ $g$

Se også

Konveks programmering

Noter

↑ Boţ, Grad, Wanka, 2009 , s. en.
↑ En primal-dual-algoritme er en algoritme til at løse de primære og dobbelte problemer samtidigt.
↑ Gonzalez, 2007 , s. 2.

Litteratur

Radu Ioan Boţ, Sorin-Mihai Grad, Gert Wanka. Dualitet i vektoroptimering . - Berlin: Springer-Verlag, 2009. - S. 1. - ISBN 978-3-642-02885-4 . - doi : 10.1007/978-3-642-02886-1 .
Teofilo F. Gonzalez. Håndbog i tilnærmelsesalgoritmer og metaheuristik . - CRC Press, 2007. - S. 2-12. — ISBN 9781420010749 .