Duální mezera

Dualita mezera je rozdíl mezi přímým a duálním řešením . Pokud je optimální hodnota duálního problému a je optimální hodnota přímého problému, pak je mezera duality . Tato hodnota je vždy větší nebo rovna nule (pro problémy s minimalizací). Dualitní mezera je nulová právě tehdy, když existuje silná dualita . Jinak je diskontinuita striktně pozitivní a dochází ke slabé dualitě [1] . $d^{*}$ $p^{*}$ $p^{*}-d^{*}$

Popis

V obecném případě nechť duální pár oddělených místně konvexních prostorů a je dán . Poté, vzhledem k funkci , můžeme definovat přímý problém jako $\left(X,X^{*}\right)$ $\left(Y,Y^{*}\right)$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$

\inf _{x\in X}f(x).\,

Pokud existují omezení, lze je zabudovat do funkce přidáním funkce indikátoru k omezením — . Pak nechť je porucha funkce taková, že . Dualita mezera je rozdíl, který je dán vzorcem $F$ $já$ $f=f+I$ ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \))$ $F(x,0)=f(x)$

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

kde je konjugovaná funkce obou proměnných [2] [3] [4] . $F^{*}$

Alternativy

Ve výpočetní optimalizaci se často zmiňuje další „dualitní mezera“, kterou je rozdíl hodnot mezi jakýmkoli řešením a hodnotou přípustné, ale suboptimální hodnoty přímého problému. Tato alternativní „mezera duality“ kvantifikuje nesoulad mezi hodnotou současné proveditelné, ale suboptimální hodnoty přímého problému a hodnotou duálního problému. Hodnota duálního problému se podle podmínek regularity rovná hodnotě konvexní relaxace přímého problému. Konvexní relaxace je problém, který se získá nahrazením nekonvexní množiny proveditelných řešení jejím uzavřeným konvexním obalem a nahrazením nekonvexní funkce jeho konvexním uzávěrem , tj. funkcí, jejíž epigraf je uzavřený konvexní obal obalu. epigraf původní účelové funkce přímé úlohy [5] [6 ] [7] [8] [9] [10] [11] [12] [13] .

Poznámky

↑ Borwein, Zhu, 2005 .
↑ Boţ, Wanka, Grad, 2009 .
↑ Csetnek, 2010 .
↑ Zălinescu, 2002 , s. 106–113.
↑ Ahuja, Magnanti, Orlin, 1993 .
↑ Bertsekas, 1999 .
↑ Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006 , str. xiv+490.
↑ Hiriart-Urruty, Lemaréchal, 1993 , s. xviii+417.
↑ Hiriart-Urruty, Lemaréchal, 1993 , s. xviii+346.
↑ Lasdon, 2002 , str. xiii+523.
↑ Lemarechal, 2001 , str. 112–156.
↑ Minoux, 1986 , str. xxviii+489.
↑ Shapiro, 1979 , str. xvi+388.

Literatura

Jonathan Borwein, Qiji Zhu. Techniky variační analýzy. - Springer, 2005. - ISBN 978-1-4419-2026-3 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Dualita ve vektorové optimalizaci. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Ernö Robert Csetnek. Překonání selhání klasických zobecněných podmínek pravidelnosti vnitřního bodu v konvexní optimalizaci. Aplikace teorie duality na zvětšení maximálních monotónních operátorů. - Logos Verlag Berlin GmbH, 2010. - ISBN 978-3-8325-2503-3 .
Zălinescu C. Konvexní analýza v obecných vektorových prostorech. — River Edge, NJ: World Scientific Publishing Co. Inc, 2002. - ISBN 981-238-067-1 .
Ravindra K. Ahuja, Thomas L. Magnanti, 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í. — 2. - Athena Scientific, 1999. - ISBN 1-886529-00-0 .
J. Fredéric Bonnans, J. Charles Gilbert, Claude Lemaréchal, Claudia A. Sagastizábal. Numerická optimalizace: Teoretické a praktické aspekty . — Druhé revidované vyd. překladu francouzštiny z roku 1997. - Berlín: Springer-Verlag, 2006. - (Universitex). — ISBN 3-540-35445-X . - doi : 10.1007/978-3-540-35447-5 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konvexní analýza a minimalizační algoritmy, svazek I: Základy. - Berlin: Springer-Verlag, 1993. - V. 305. - (Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]). — ISBN 3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. XII. Abstrakt Dualita pro praktiky // Algoritmy konvexní analýzy a minimalizace, svazek II: Pokročilá teorie a metody svazků. - Berlin: Springer-Verlag, 1993. - V. 306. - (Grundlehren der Mathematischen Wissenschaften [Základní principy matematických věd]). — ISBN 3-540-56852-2 . - doi : 10.1007/978-3-662-06409-2_4 .
Leon S Lasdon. Teorie optimalizace pro velké systémy . - Mineola, New York: Dover Publications, Inc., 2002. - ISBN 978-0-486-41999-2 .
Claude Lemarechal. Lagrangiánská relaxace // Výpočetní kombinatorická optimalizace: Referáty z jarní školy konané v Schloß Dagstuhl, 15.–19. května 2000 / Michael Jünger, Denis Naddef. - Berlin: Springer-Verlag, 2001. - T. 2241. - (Poznámky k přednáškám z informatiky (LNCS)). — ISBN 3-540-42877-1 . - doi : 10.1007/3-540-45586-8_4 .
Michel Minoux. Matematické programování: Teorie a algoritmy / Egon Balas (vpřed); Steven Vajda (překlad) z (1983 Paris: Dunod). - Chichester: Publikace Wiley-Interscience. John Wiley & Sons, Ltd., 1986. - ISBN 0-471-90170-9 . Překlad knihy
- Matematické programování: Teorie a algoritmy. — 2. - Paris: Tec & Doc, 2008. - s. xxx+711 s. - ISBN 978-2-7430-1000-3 .
Jeremy F. Shapiro. Matematické programování: Struktury a algoritmy . - New York: Wiley-Interscience [John Wiley & Sons], 1979. - ISBN 0-471-77886-9 .