Skok duality

V teorii optimalizace je dualitním skokem rozdíl mezi primárním a duálním řešením .

Definice

Zvažujeme problém s optimalizací

{\ displaystyle \ inf f (\ mathrm {x}), \ mathrm {x} \ v X \ subseteq \ mathbb {R} ^ {n}}

Pokud $d *$ je optimální duální hodnota $ap *$ optimální primární hodnota, pak dualitní skok má hodnotu $p * - d *$ . Tato hodnota je vždy pozitivní (pro problémy s minimalizací) a je zrušena tehdy a jen tehdy, je-li ověřena silná dualita, jinak mluvíme o slabé dualitě.

Obecně platí, že pro dva páry oddělených lokálně konvexních prostorů a pózováním můžeme napsat primární problém jako ${\ displaystyle \ left (X, X ^ {*} \ right)}$ ${\ displaystyle \ left (Y, Y ^ {*} \ right)}$ ${\ displaystyle f: X \ až \ mathbb {R} \ pohár \ {+ \ infty \}}$

{\ displaystyle \ inf _ {\ mathrm {x} \ v X} f (x). \,}

U problému s omezeními můžeme opravit omezení $f$ pomocí $omezení$ $f + I,$ přičemž $I$ je indikátorová funkce prostoru omezení. Nechť je tedy rušivá funkce taková . Skok duality je pak dán vztahem ${\ displaystyle F: X \ krát Y \ to \ mathbb {R} \ pohár \ {+ \ infty \}}$ ${\ displaystyle F (\ mathrm {x}, 0) = f (\ mathrm {x})}$

{\ displaystyle \ inf _ {\ mathrm {x} \ v X} [F (\ mathrm {x}, 0)] - \ sup _ {\ mathrm {y} ^ {*} \ v Y ^ {*}} [-F ^ {*} (0, \ mathrm {y} ^ {*})]}

s $F *$ konjugát funkce podle dvou proměnných.

Ve výpočetní optimalizaci je často vyvolán další „dualitní skok“, kterým je rozdíl v hodnotách mezi jakýmkoli duálním řešením a hodnotou proveditelné, ale neoptimální iterace prvotního problému. Tento „skok duality“ kvantifikuje rozdíl mezi hodnotou proveditelné, ale neoptimální aktuální iterace prvotního problému a hodnotou dvojího problému; druhý je za podmínek pravidelnosti roven hodnotě konvexní relaxace prvotního problému: konvexní relaxace je problém, který se objevuje nahrazením nekonvexní množiny, kterou lze vytvořit pomocí uzavřené konvexní obálky a nekonvexní funkce jeho konvexním uzávěrem nebo funkcí, jejíž epigraf je uzavřená konvexní obálka původní původní objektivní funkce.

Příklady

Lineární programování na nekonvexním prostoru

Zvažujeme problém s minimalizací

{\ Displaystyle \ min _ {(x, y, z) \ v X} f (x, y, z) = 10-3x-2y-z, \ X = \ {(x, y, z) \ v \ {0; 1 \} ^ {3}, 2x + 3y + 4z \ leq 4 \}.}

Maximum je dosaženo v $p * = f (1,0,0) = 7$ . Metodou Lagrangeovy relaxace definujeme Lagrangeovu

{\ Displaystyle L (X, y, z, \ mu) = f (x, y, z) + \ mu (2x + 3y + 4z-4) = 10-4 \ mu + (- 3 + 2 \ mu) x + (- 2 + 3 \ mu) y + (- 1 + 4 \ mu) z.}

ze kterého stavíme dvojí problém

{\ Displaystyle \ inf \ left (10-4 \ mu + (- 3 + 2 \ mu) x + (- 2 + 3 \ mu) y + (- 1 + 4 \ mu) z \ right).}

Reference

(fr) Tento článek je částečně nebo zcela převzat z článku Wikipedie v angličtině s názvem „ Duality gap “ ( viz seznam autorů ) .

Jonathan Borwein a Qiji Zhu , Techniky variační analýzy , Springer,2005( ISBN 978-1-4419-2026-3 )
Radu Ioan Boţ, Gert Wanka a Sorin-Mihai Grad, Dualita v optimalizaci vektorů , Springer,2009( ISBN 978-3-642-02885-4 )
Ernö Robert Csetnek, Překonání selhání klasických obecných podmínek pravidelnosti vnitřních bodů v konvexní optimalizaci. Aplikace teorie duality na rozšíření maximálních monotónních operátorů , Logos Verlag Berlin GmbH,2010( ISBN 978-3-8325-2503-3 )
C. Zălinescu , Konvexní analýza v obecných vektorových prostorech , River Edge, NJ, World Scientific Publishing Co. Inc,2002, 106 –113 s. ( ISBN 981-238-067-1 , Math Reviews 1921556 , číst online )
Ravindra K. Ahuja, Thomas L. Magnanti a James B. Orlin, Síťové toky: Teorie, algoritmy a aplikace , Prentice Hall,1993( ISBN 0-13-617549-X )
Dimitri P. Bertsekas , nelineární programování , Athena Scientific,1999, 2. vyd. ( ISBN 1-886529-00-0 )
J. Frédéric Bonnans , J. Charles Gilbert , Claude Lemaréchal a Claudia A. Sagastizábal , Numerická optimalizace: Teoretické a praktické aspekty , Berlín, Springer-Verlag, kol. "Universitext",2006, Druhé přepracované vydání. překladu z roku 1997 francouzsky vyd. , xiv + 490 str. ( ISBN 3-540-35445-X , DOI 10.1007 / 978-3-540-35447-5 , Math Reviews 2265882 , číst online )
Jean-Baptiste Hiriart-Urruty a Claude Lemaréchal , Konvexní analýza a minimalizační algoritmy, Svazek I: Základy , sv. 305, Berlín, Springer-Verlag, kol. "Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]",1993, xviii + 417 str. ( ISBN 3-540-56850-6 , Math Reviews 1261420 )
Jean-Baptiste Hiriart-Urruty a Claude Lemaréchal , Konvexní analýza a minimalizační algoritmy, Svazek II: Pokročilá teorie a svazkové metody , sv. 306, Berlín, Springer-Verlag, kol. "Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]",1993, xviii + 346 str. ( ISBN 3-540-56852-2 , DOI 10.1007 / 978-3-662-06409-2_4 , Math Reviews 1295240 ) , „XII. Abstraktní dualita pro odborníky »
Leon S. Lasdon , Teorie optimalizace pro velké systémy , Mineola, New York, Dover Publications, Inc.,2002( 1 st ed. Dotisk 1970 Macmillan), xiii + 523 s. ( ISBN 978-0-486-41999-2 , Math Reviews 1888251 )
Claude Lemaréchal a Naddef, Denis, Výpočetní kombinatorická optimalizace: Příspěvky z jarní školy konané ve Schloß Dagstuhl, 15. – 19. Května 2000 , sv. 2241, Berlín, Springer-Verlag, kol. "Lecture Notes in Computer Science (LNCS)",2001, 112–156 s. ( ISBN 3-540-42877-1 , DOI 10.1007 / 3-540-45586-8_4 , Math Reviews 1900016 ) , „Lagrangeova relaxace“
Minoux, Michel. „ Matematické programování: teorie a algoritmy , technická vydání a dokumentace,2008( ISBN 978-2-7430-1000-3 , OCLC 261201111 , Math Reviews 2571910 )
Jeremy F. Shapiro , Matematické programování: Struktury a algoritmy , New York, Wiley-Interscience [John Wiley & Sons],1979, xvi + 388 str. ( ISBN 0-471-77886-9 , Math Reviews 544669 , číst online )