Dualitate slabă

Dualitatea slabă este un concept în optimizare care afirmă că decalajul de dualitate este întotdeauna mai mare sau egal cu zero. Aceasta înseamnă că soluția problemei primare (problema minimizării) este întotdeauna mai mare sau egală cu soluția problemei duale asociate . Acest termen se opune dualității puternice , care este îndeplinită doar în anumite condiții [1] .

Utilizare

Mulți algoritmi de aproximare duală [2] directe se bazează pe principiul dualității slabe [3] .

Teorema dualității slabe

Sarcina directă :

Maximizați în condițiile ;

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

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

Sarcină dublă :

Minimizați subiectul la .

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

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

Teorema dualității slabe afirmă că . $\mathbf {c} ^{T}\mathbf {x} \leqslant \mathbf {b} ^{T}\mathbf {y}$

Și anume, dacă este o soluție fezabilă la problema directă a maximizării programării liniare și este o soluție fezabilă a problemei duale de minimizare a programării liniare, atunci teorema dualității slabe poate fi formulată după cum urmează: , unde și sunt coeficienții coeficienților corespunzătoare. functii obiective. $(x_{1},x_{2},.....,x_{n})$ $(y_{1},y_{2},.....,y_{m})$ $\sum _{j=1}^{n}c_{j}x_{j}\leqslant \sum _{i=1}^{m}b_{i}y_{i)$ $c_{j)$ $b_i$

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

Generalizări

Într-un caz mai general, dacă este o soluție fezabilă pentru problema de maximizare primară și este o soluție fezabilă pentru problema de minimizare duală, rezultă din dualitatea slabă că , unde și sunt funcțiile obiectiv pentru problemele primale și, respectiv, duale. $X$ $y$ $f(x)\leqslant g(y)$ $f$ $g$

Vezi și

Programare convexă

Note

↑ Boţ, Grad, Wanka, 2009 , p. unu.
↑ Un algoritm primal-dual este un algoritm pentru rezolvarea simultană a problemelor primale și duale.
↑ Gonzalez, 2007 , p. 2.

Literatură

Radu Ioan Boţ, Sorin-Mihai Grad, Gert Wanka. Dualitate în optimizarea vectorială . - Berlin: Springer-Verlag, 2009. - P. 1. - ISBN 978-3-642-02885-4 . - doi : 10.1007/978-3-642-02886-1 .
Teofilo F. Gonzalez. Manual de algoritmi de aproximare și metaeuristică . - CRC Press, 2007. - S. 2-12. — ISBN 9781420010749 .