Dualität (Optimierung) - Duality (optimization)

In der mathematischen Optimierungstheorie ist die Dualität oder das Dualitätsprinzip das Prinzip, dass Optimierungsprobleme aus einer von zwei Perspektiven betrachtet werden können, dem Primärproblem oder dem Dualproblem . Die Lösung des dualen Problems liefert eine untere Schranke für die Lösung des primären (Minimierungs-)Problems. Im Allgemeinen müssen die optimalen Werte des primären und des dualen Problems jedoch nicht gleich sein. Ihr Unterschied wird als Dualitätslücke bezeichnet . Bei konvexen Optimierungsproblemen ist die Dualitätslücke unter einer Einschränkungsqualifikationsbedingung null .

Doppelproblem

Normalerweise bezieht sich der Begriff "Dualproblem" auf das Lagrangesche Dualproblem, aber es werden auch andere Dualprobleme verwendet – zum Beispiel das Wolfe-Dualproblem und das Fenchel-Dualproblem . Das duale Lagrange-Problem wird erhalten, indem die Lagrange-Funktion eines Minimierungsproblems gebildet wird, indem nichtnegative Lagrange-Multiplikatoren verwendet werden , um die Randbedingungen zu der Zielfunktion hinzuzufügen, und dann nach den Werten der primären Variablen aufgelöst wird, die die ursprüngliche Zielfunktion minimieren. Diese Lösung liefert die primalen Variablen als Funktionen der Lagrange-Multiplikatoren, die duale Variablen genannt werden, so dass das neue Problem darin besteht, die Zielfunktion in Bezug auf die dualen Variablen unter den abgeleiteten Beschränkungen der dualen Variablen (einschließlich mindestens der Nichtnegativität Einschränkungen).

Im Allgemeinen können wir bei zwei dualen Paaren von getrennten lokal konvexen Räumen und und der Funktion das primäre Problem als eine Feststellung definieren , mit anderen Worten, falls existiert, ist das Minimum der Funktion und das Infimum (größte untere Schranke) der Funktion erreicht ist. ${\displaystyle \left(X,X^{*}\right)}$${\displaystyle \left(Y,Y^{*}\right)}$${\displaystyle f:X\to\mathbb{R}\cup\{+\infty\}}$${\displaystyle {\hat {x}}}$${\displaystyle f({\hat{x}})=\inf _{x\in X}f(x).\,}$${\displaystyle {\hat {x}}}$${\displaystyle f({\hat{x}})}$${\displaystyle f}$

Wenn es Randbedingungen gibt, können diese in die Funktion eingebaut werden, indem angegeben wird, wo ist eine geeignete Funktion , die ein Minimum von 0 bei den Randbedingungen hat und für die man beweisen kann, dass . Die letztere Bedingung wird trivialerweise, aber nicht immer bequemerweise, für die charakteristische Funktion erfüllt (dh um die Randbedingungen zu erfüllen usw. ). Erweitern Sie dann auf eine Störungsfunktion, so dass . ${\displaystyle f}$${\displaystyle {\tilde{f}}=f+I_{\mathrm {Nebenbedingungen}}}$${\displaystyle I_{\mathrm {Einschränkungen} }}$${\displaystyle X}$${\displaystyle \inf _{x\in X}{\tilde {f}}(x)=\inf _{x\ \mathrm {beschränkt} }f(x)}$${\displaystyle I_{\textrm {Einschränkungen}}(x)=0}$${\displaystyle x}$${\displaystyle I_{\textrm {Beschränkungen}}(x)=\infty}$${\displaystyle {\tilde{f}}}$ ${\displaystyle F:X\times Y\to\mathbb{R}\cup\{+\infty\}}$${\displaystyle F(x,0)={\tilde {f}}(x)}$

Die Dualitätslücke ist die Differenz der rechten und linken Seite der Ungleichung

${\displaystyle \sup_{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x, 0),\,}$

wobei ist die konvexe Konjugierte in beiden Variablen und bezeichnet das Supremum (kleinste obere Schranke). ${\displaystyle F^{*}}$${\displaystyle \sup}$

Dualitätslücke

Die Dualitätslücke ist die Differenz zwischen den Werten aller Primärlösungen und aller dualen Lösungen. Wenn der optimale duale Wert und der optimale primäre Wert ist, dann ist die Dualitätslücke gleich . Dieser Wert ist immer größer oder gleich 0. Die Dualitätslücke ist genau dann null, wenn eine starke Dualität gilt. Andernfalls ist die Lücke streng positiv und es gilt eine schwache Dualität . ${\displaystyle d^{*}}$${\displaystyle p^{*}}$${\displaystyle p^{*}-d^{*}}$

Bei der rechnerischen Optimierung wird oft über eine andere "Dualitätslücke" berichtet, die den Wertunterschied zwischen einer beliebigen dualen Lösung und dem Wert einer machbaren, aber suboptimalen Iteration für das Primärproblem darstellt. Diese alternative "Dualitätslücke" quantifiziert die Diskrepanz zwischen dem Wert einer aktuellen machbaren, aber suboptimalen Iteration für das Primärproblem und dem Wert des dualen Problems; der Wert des dualen Problems ist unter Regularitätsbedingungen gleich dem Wert der konvexen Relaxation des primalen Problems: Die konvexe Relaxation ist das Problem, das entsteht, wenn man eine nichtkonvexe zulässige Menge durch ihre geschlossene konvexe Hülle ersetzt und eine nicht-konvexe konvexe Funktion mit ihrem konvexen Verschluß , der die Funktion hat, die die epigraph daß die geschlossene konvexe Hülle der ursprünglichen ursprünglichen Zielfunktion ist.

Linearer Fall

Lineare Programmierprobleme sind Optimierungsprobleme , bei denen die Zielfunktion und die Nebenbedingungen alle linear sind . Im Primalproblem ist die Zielfunktion eine Linearkombination von n Variablen. Es gibt m Beschränkungen, von denen jede eine obere Schranke für eine Linearkombination der n Variablen setzt. Das Ziel besteht darin, den Wert der Zielfunktion unter den Bedingungen zu maximieren. Eine Lösung ist ein Vektor (eine Liste) von n Werten, der den Maximalwert für die Zielfunktion erreicht.

Im dualen Problem ist die Zielfunktion eine Linearkombination der m Werte, die die Grenzen in den m Randbedingungen des Primärproblems sind. Es gibt n duale Nebenbedingungen, von denen jede eine untere Schranke für eine Linearkombination von m dualen Variablen setzt.

Beziehung zwischen dem Primärproblem und dem dualen Problem

Im linearen Fall, im Primalproblem, gibt es von jedem suboptimalen Punkt, der alle Randbedingungen erfüllt, eine Richtung oder einen Unterraum von Richtungen zu bewegen, der die Zielfunktion erhöht. Eine Bewegung in eine solche Richtung soll den Spielraum zwischen der Kandidatenlösung und einer oder mehreren Beschränkungen beseitigen . Ein infeasible Wert der Kandidatenlösung ist eine , die eine oder mehrere der Beschränkungen übersteigt.

Beim dualen Problem multipliziert der duale Vektor die Beschränkungen, die die Positionen der Beschränkungen im Primal bestimmen. Das Variieren des dualen Vektors im dualen Problem ist äquivalent zur Revision der oberen Schranken im primären Problem. Die niedrigste obere Schranke wird gesucht. Das heißt, der duale Vektor wird minimiert, um Spiel zwischen den Kandidatenpositionen der Beschränkungen und dem tatsächlichen Optimum zu beseitigen. Ein nicht durchführbarer Wert des dualen Vektors ist einer, der zu niedrig ist. Es setzt die Kandidatenpositionen einer oder mehrerer der Beschränkungen in eine Position, die das tatsächliche Optimum ausschließt.

Diese Intuition wird durch die Gleichungen in der linearen Programmierung formalisiert : Dualität .

Nichtlinearer Fall

Bei der nichtlinearen Programmierung sind die Randbedingungen nicht unbedingt linear. Dennoch gelten viele der gleichen Prinzipien.

Um sicherzustellen, dass das globale Maximum eines nichtlinearen Problems leicht identifiziert werden kann, erfordert die Problemformulierung oft, dass die Funktionen konvex sind und kompakte Mengen niedrigerer Ebenen aufweisen.

Dies ist die Bedeutung der Karush-Kuhn-Tucker-Bedingungen . Sie liefern die notwendigen Bedingungen für die Identifizierung lokaler Optima von nichtlinearen Programmierproblemen. Es sind zusätzliche Bedingungen (Constraint-Qualifikationen) notwendig, damit die Richtung zu einer optimalen Lösung definiert werden kann. Eine optimale Lösung ist eine Lösung, die ein lokales Optimum, aber möglicherweise kein globales Optimum ist.

Das starke Lagrange-Prinzip: Lagrange-Dualität

Gegeben ein nichtlineares Programmierproblem in Standardform

${\displaystyle {\begin{aligned}{\text{minimieren}}&f_{0}(x)\\{\text{abhängig von }}&f_{i}(x)\leq 0,\ i\in \left \{1,\ldots,m\right\}\\&h_{i}(x)=0,\i\in \left\{1,\ldots,p\right\}\end{ausgerichtet}}}$

mit dem Bereich mit nichtleerem Inneren ist die Lagrange-Funktion definiert als ${\displaystyle {\mathcal{D}}\subset \mathbb{R}^{n}}$ ${\displaystyle \Lambda:\mathbb{R}^{n}\times \mathbb{R}^{m}\times \mathbb{R}^{p}\to \mathbb{R}}$

${\displaystyle \Lambda(x,\lambda,\nu)=f_{0}(x)+\sum_{i=1}^{m}\lambda_{i}f_{i}(x)+\ Summe _{i=1}^{p}\nu _{i}h_{i}(x).}$

Die Vektoren und werden als duale Variablen oder Lagrange-Multiplikatorvektoren bezeichnet, die dem Problem zugeordnet sind. Die Lagrange-Doppelfunktion ist definiert als ${\displaystyle \lambda}$${\displaystyle \nu}$ ${\displaystyle g:\mathbb{R}^{m}\times \mathbb{R}^{p}\to\mathbb{R}}$

${\displaystyle g(\lambda,\nu)=\inf_{x\in {\mathcal {D}}}\Lambda(x,\lambda,\nu)=\inf_{x\in {\mathcal{ D}}}\left(f_{0}(x)+\sum_{i=1}^{m}\lambda_{i}f_{i}(x)+\sum_{i=1}^ {p}\nu_{i}h_{i}(x)\right).}$

Die duale Funktion g ist konkav, auch wenn das Ausgangsproblem nicht konvex ist, weil sie ein punktweises Infimum affiner Funktionen ist. Die duale Funktion liefert untere Schranken für den optimalen Wert des Ausgangsproblems; für alles, was wir haben . ${\displaystyle p^{*}}$${\displaystyle \lambda\geq 0}$${\displaystyle \nu}$${\displaystyle g(\lambda,\nu)\leq p^{*}}$

Wenn eine Einschränkungsqualifikation wie die Slater-Bedingung gilt und das ursprüngliche Problem konvex ist, dann haben wir eine starke Dualität , dh . ${\displaystyle d^{*}=\max _{\lambda\geq 0,\nu}g(\lambda,\nu)=\inf f_{0}=p^{*}}$

Konvexe Probleme

Für ein konvexes Minimierungsproblem mit Ungleichungsbeschränkungen gilt:

${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0, \quad i=1,\ldots ,m\end{ausgerichtet}}}$

das Lagrangesche duale Problem ist

${\displaystyle {\begin{aligned}&{\underset {u}{\operatorname {maximize}}}&&\inf _{x}\left(f(x)+\sum _{j=1}^{m }u_{j}g_{j}(x)\right)\\&\operatorname {subject\;to} &&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}} }$

wobei die Zielfunktion die Lagrange-Dualfunktion ist. Sofern die Funktionen und stetig differenzierbar sind, tritt das Infimum dort auf, wo die Steigung gleich Null ist. Das Problem ${\displaystyle f}$${\displaystyle g_{1},\ldots,g_{m}}$

${\displaystyle {\begin{aligned}&{\underset {x,u}{\operatorname {maximize}}}&&f(x)+\sum _{j=1}^{m}u_{j}g_{j }(x)\\&\Operatorname {Subjekt\;zu} &&\nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x) =0\\&&&u_{i}\geq 0,\quad i=1,\ldots ,m\end{ausgerichtet}}}$

heißt Wolfe-Dualproblem. Dieses Problem kann rechnerisch schwer zu lösen sein, da die Zielfunktion in den gemeinsamen Variablen nicht konkav ist . Außerdem ist die Gleichheitsbeschränkung im Allgemeinen nichtlinear, sodass das Wolfe-Dualproblem typischerweise ein nichtkonvexes Optimierungsproblem ist. In jedem Fall gilt die schwache Dualität . ${\displaystyle (u,x)}$${\displaystyle \nabla f(x)+\sum_{j=1}^{m}u_{j}\,\nabla g_{j}(x)}$

Geschichte

Nach George Dantzig wurde der Dualitätssatz für die lineare Optimierung von John von Neumann unmittelbar nach der Vorstellung des linearen Programmierproblems durch Dantzig vermutet . Von Neumann merkte an, dass er Informationen aus seiner Spieltheorie benutzte und vermutete, dass ein Zwei-Personen-Nullsummenmatrixspiel der linearen Programmierung äquivalent sei. Rigorose Beweise wurden erstmals 1948 von Albert W. Tucker und seiner Gruppe veröffentlicht. (Dantzigs Vorwort zu Nering und Tucker, 1993)

Siehe auch

• Konvexe Dualität
• Dualität
• Entspannung (Annäherung)

Anmerkungen

Verweise

Bücher

• Ahuja, Ravindra K. ; Magnanti, Thomas L. ; Orlin, James B. (1993). Netzwerkflüsse: Theorie, Algorithmen und Anwendungen . Lehrlingssaal. ISBN 0-13-617549-X.
• Bertsekas, Dimitri; Nedic, Angelia; Özdaglar, Asuman (2003). Konvexe Analyse und Optimierung . Athena wissenschaftlich. ISBN 1-886529-45-0.
• Bertsekas, Dimitri P. (1999). Nichtlineare Programmierung (2. Aufl.). Athena wissenschaftlich. ISBN 1-886529-00-0.
• Bertsekas, Dimitri P. (2009). Konvexe Optimierungstheorie . Athena wissenschaftlich. ISBN 978-1-886529-31-1.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Numerische Optimierung: Theoretische und praktische Aspekte . Universitext (Zweite überarbeitete Ausgabe der Übersetzung der französischen Ausgabe von 1997). Berlin: Springer-Verlag. S. xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN 3-540-35445-X. MR  2.265.882 .
• Cook, William J .; Cunningham, William H.; Pulleyblank, William R .; Schrijver, Alexander (12. November 1997). Kombinatorische Optimierung (1. Aufl.). John Wiley & Söhne. ISBN 0-471-55894-X.
• Dantzig, George B. (1963). Lineare Programmierung und Erweiterungen . Princeton, NJ: Princeton University Press.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Konvexe Analyse- und Minimierungsalgorithmen, Band I: Grundlagen . Grundlehren der Mathematischen Wissenschaften. 305 . Berlin: Springer-Verlag. S. xviii+417. ISBN 3-540-56850-6. MR  1.261.420 .
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). „14 Dualität für Praktiker“. Konvexe Analyse- und Minimierungsalgorithmen, Band II: Fortgeschrittene Theorie und Bündelmethoden . Grundlehren der Mathematischen Wissenschaften. 306 . Berlin: Springer-Verlag. S. xviii+346. ISBN 3-540-56852-2. MR  1.295.240 .
• Lasdon, Leon S. (2002) [Nachdruck des Macmillan 1970]. Optimierungstheorie für große Systeme . Mineola, New York: Dover Publications, Inc. S. xiii+523. ISBN 978-0-486-41999-2. MR  1.888.251 .
• Lawler, Eugen (2001). "4.5. Kombinatorische Implikationen des Max-Flow-Min-Cut-Theorems, 4.6. Lineare Programmierung Interpretation des Max-Flow-Min-Cut-Theorems". Kombinatorische Optimierung: Netzwerke und Matroiden . Dover. S. 117–120. ISBN 0-486-41453-1.
• Lemaréchal, Claude (2001). "Lagrange-Entspannung". In Jünger, Michael; Naddef, Denis (Hrsg.). Computergestützte kombinatorische Optimierung: Vorträge der Spring School in Schloß Dagstuhl, 15.-19. Mai 2000 . Vorlesungsnotizen in Informatik (LNCS). 2241 . Berlin: Springer-Verlag. S. 112–156. doi : 10.1007/3-540-45586-8_4 . ISBN 3-540-42877-1. MR  1.900.016 .
• Minoux, Michel (1986). Mathematische Programmierung: Theorie und Algorithmen . Egon Balas (vorwärts); Steven Vajda (trans) aus dem (1983 Paris: Dunod) Französisch. Chichester: Eine Wiley-Interscience-Publikation. John Wiley & Sons, Ltd. S. xxviii+489. ISBN 0-471-90170-9. MR  0.868.279 . (2008 Zweite Aufl., auf Französisch: Programmation mathématique : Théorie et algorithmes , Editions Tec & Doc, Paris, 2008. xxx+711 pp. )).
• Nering, Evar D.; Tucker, Albert W. (1993). Lineare Programmierung und verwandte Probleme . Boston, MA: Akademische Presse. ISBN 978-0-12-515440-6.
• Papadimitriou, Christos H.; Steiglitz, Kenneth (Juli 1998). Kombinatorische Optimierung: Algorithmen und Komplexität (ungekürzte Ausgabe). Dover. ISBN 0-486-40258-4.
• Ruszczyński, Andrzej (2006). Nichtlineare Optimierung . Princeton, NJ: Princeton University Press . S. xii+454. ISBN 978-0691119151. MR  2.199.043 .

Artikel

• Everett, Hugh, III (1963). "Verallgemeinerte Lagrange-Multiplikatormethode zur Lösung von Problemen der optimalen Ressourcenallokation" . Betriebsforschung . 11 (3): 399–417. doi : 10.1287/opre.11.3.399 . JSTOR  168028 . MR  0.152.360 . Archiviert vom Original am 24.07.2011.
• Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P.O. (August 2007). "Lagrangesche Relaxation über Kugelschritt-Subgradienten-Methoden" . Mathematik des Operations Research . 32 (3): 669–686. doi : 10.1287/moor.1070.0261 . MR  2.348.241 .
• Dualität in der linearen Programmierung Gary D. Knott