Heikko kaksinaisuus

Heikko kaksinaisuus on optimoinnin käsite, jonka mukaan kaksinaisuusrako on aina suurempi tai yhtä suuri kuin nolla. Tämä tarkoittaa, että ratkaisu alkuongelmaan (minimointiongelma) on aina suurempi tai yhtä suuri kuin siihen liittyvän kaksoisongelman ratkaisu . Tämä termi vastustaa vahvaa kaksinaisuutta , joka toteutuu vain tietyin ehdoin [1] .

Käyttö

Monet suorat kaksoisapproksimaatioalgoritmit [2] perustuvat heikon duaalisuuden periaatteeseen [ 3] .

Heikko kaksinaisuuslause

Suora tehtävä:

Maksimoi olosuhteissa ;

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

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

Kaksoistehtävä :

Minimoi kohteena .

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

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

Heikko kaksinaisuuslause sanoo, että . $\mathbf {c} ^{T}\mathbf {x} \leqslant \mathbf {b} ^{T}\mathbf {y}$

Nimittäin, jos on toteuttamiskelpoinen ratkaisu suoralle lineaarisen ohjelmoinnin maksimoimisen ongelmalle ja se on toteuttamiskelpoinen ratkaisu kaksoisongelmaan minimoida lineaarisen ohjelmoinnin, niin heikko kaksinaisuuslause voidaan muotoilla seuraavasti: , missä ja ovat vastaavan kertoimet tavoitefunktiot. ${\näyttötyyli (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$

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

Yleistykset

Yleisemmässä tapauksessa, jos on toteuttamiskelpoinen ratkaisu primaali- ja kaksoisminimointiongelmaan, heikosta duaalisuudesta seuraa, että , missä ja ovat kohdefunktiot primaali- ja duaaliongelmalle, vastaavasti. $x$ $y$ $f(x)\leqslant g(y)$ $f$ $g$

Katso myös

Kupera ohjelmointi

Muistiinpanot

↑ Boţ, Grad, Wanka, 2009 , s. yksi.
↑ Alku-kaksoisalgoritmi on algoritmi primaali- ja duaaliongelmien ratkaisemiseksi samanaikaisesti.
↑ Gonzalez, 2007 , s. 2.

Kirjallisuus

Radu Ioan Boţ, Sorin-Mihai Grad, Gert Wanka. Kaksinaisuus vektorioptimoinnissa . - Berliini: Springer-Verlag, 2009. - P. 1. - ISBN 978-3-642-02885-4 . - doi : 10.1007/978-3-642-02886-1 .
Teofilo F. Gonzalez. Approksimaatioalgoritmien ja metaheuristiikan käsikirja . - CRC Press, 2007. - S. 2-12. — ISBN 9781420010749 .