Dualitetsspring

I optimeringsteorien er dualitetshoppet forskellen mellem de primære og dobbelte løsninger .

Definitioner

Vi overvejer et optimeringsproblem

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

Hvis $d *$ er den dobbelte optimale værdi og $p *$ den primære optimale værdi, er dualitetshoppet værd $p * - d *$ . Denne værdi er altid positiv (for problemerne med minimering) og annulleres, hvis og kun hvis den stærke dualitet er verificeret, ellers taler vi om svag dualitet.

Generelt for to par af separate, lokalt konvekse rum, og ved at posere kan vi skrive det primære problem som ${\ displaystyle \ left (X, X ^ {*} \ right)}$ ${\ displaystyle \ left (Y, Y ^ {*} \ right)}$ ${\ displaystyle f: X \ til \ mathbb {R} \ cup \ {+ \ infty \}}$

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

For et problem under begrænsninger kan vi rette $f$ ved $f + I- begrænsninger,$ idet $jeg$ er indikatorfunktionen for begrænsningen. Lad være en forstyrrelsesfunktion sådan, at . Dobbelthedsspringet gives derefter af ${\ displaystyle F: X \ gange Y \ til \ mathbb {R} \ cup \ {+ \ infty \}}$ ${\ displaystyle F (\ mathrm {x}, 0) = f (\ mathrm {x})}$

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

med $F *$ den konjugerede funktion ifølge de to variable.

I beregningsoptimering fremkaldes ofte et andet "dualitetsspring", som er forskellen i værdier mellem enhver dobbelt løsning og værdien af en mulig, men suboptimal itereret af det primære problem. Dette "dualitetsspring" kvantificerer forskellen mellem værdien af en mulig, men suboptimal nuværende iteration af det primære problem og værdien af det dobbelte problem; sidstnævnte er under regelmæssige forhold lig med værdien af den konvekse afslapning af det primære problem: den konvekse afslapning er problemet, der vises ved at erstatte et ikke-konveks sæt, der kan produceres med dets lukkede konvekse kuvert og en ikke-konveks funktion ved sin konvekse lukning eller funktionen, hvis epigrafi er den lukkede konvekse konvolut af den oprindelige primære objektive funktion.

Eksempler

Lineær programmering på ikke-konveks plads

Vi overvejer minimeringsproblemet

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

Maksimumet nås i $p * = f (1,0,0) = 7$ . Ved metoden til Lagrangian afslapning definerer vi Lagrangian

{\ 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.}

hvorfra vi bygger det dobbelte problem

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

Referencer

(fr) Denne artikel er helt eller delvist taget fra Wikipedia-artiklen på engelsk med titlen " Duality gap " ( se listen over forfattere ) .

Jonathan Borwein og Qiji Zhu , Teknikker til variationsregning Analysis , Springer,2005( ISBN 978-1-4419-2026-3 )
Radu Ioan Boţ, Gert Wanka og Sorin-Mihai Grad, Duality in Vector Optimization , Springer,2009( ISBN 978-3-642-02885-4 )
Ernö Robert Csetnek, Overvinde svigtet med de klassiske generaliserede interiør-punkt regelmæssighedsforhold i konveks optimering. Anvendelser af dualitetsteorien til udvidelser af maksimale monotoneoperatorer , Logos Verlag Berlin GmbH,2010( ISBN 978-3-8325-2503-3 )
C. Zălinescu , konveks analyse i generelle vektorrum , River Edge, NJ, World Scientific Publishing Co. Inc,2002, 106 –113 s. ( ISBN 981-238-067-1 , Matematiske anmeldelser 1921556 , læs online )
Ravindra K. Ahuja, Thomas L. Magnanti og James B. Orlin, Network Flow: Teori, Algoritmer og Programmer , Prentice Hall,1993( ISBN 0-13-617549-X )
Dimitri P. Bertsekas , ikke- lineær programmering , Athena Scientific,19992. udgave ( ISBN 1-886529-00-0 )
J. Frédéric Bonnans , J. Charles Gilbert , Claude Lemaréchal og Claudia A. Sagastizábal , Numerisk optimering: Teoretiske og praktiske aspekter , Berlin, Springer-Verlag, koll. "Universitext",2006Anden revideret udgave af oversættelse af 1997 fransk ed. , xiv + 490 s. ( ISBN 3-540-35445-X , DOI 10.1007 / 978-3-540-35447-5 , Matematikanmeldelser 2265882 , læs online )
Jean-Baptiste Hiriart-Urruty og Claude Lemaréchal , Konvekse analyse- og minimeringsalgoritmer, bind I: Fundamentals , bind. 305, Berlin, Springer-Verlag, koll. "Grundlehren der Mathematischen Wissenschaften [Grundlæggende principper for matematiske videnskaber]",1993, xviii + 417 s. ( ISBN 3-540-56850-6 , matematikanmeldelser 1261420 )
Jean-Baptiste Hiriart-Urruty og Claude Lemaréchal , konvekse analyse- og minimeringsalgoritmer, bind II: avanceret teori og bundmetoder , bind. 306, Berlin, Springer-Verlag, koll. "Grundlehren der Mathematischen Wissenschaften [Grundlæggende principper for matematiske videnskaber]",1993, xviii + 346 s. ( ISBN 3-540-56852-2 , DOI 10.1007 / 978-3-662-06409-2_4 , Matematikanmeldelser 1295240 ) , “XII. Abstrakt dualitet for udøvere »
Leon S. Lasdon , optimering teori for store systemer , Mineola, New York, Dover Publications, Inc.,2002( 1 st ed. Genoptryk af 1970 Macmillan), xiii + 523 pp. ( ISBN 978-0-486-41999-2 , matematiske anmeldelser 1888251 )
Claude Lemaréchal og Naddef, Denis, Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, 15. - 19. maj 2000 , bind. 2241, Berlin, Springer-Verlag, koll. "Forelæsningsnotater inden for datalogi (LNCS)",2001, 112-156 s. ( ISBN 3-540-42877-1 , DOI 10.1007 / 3-540-45586-8_4 , Matematiske anmeldelser 1900016 ) , "Lagrangian afslapning"
Minoux, Michel. , Matematisk programmering: teori og algoritmer , Tekniske udgaver og dokumentation,2008( ISBN 978-2-7430-1000-3 , OCLC 261201111 , Matematiske anmeldelser 2571910 )
Jeremy F. Shapiro , Matematisk programmering: Strukturer og algoritmer , New York, Wiley-Interscience [John Wiley & Sons],1979, xvi + 388 s. ( ISBN 0-471-77886-9 , Matematiske anmeldelser 544669 , læs online )