Dualität - Atlas optimization

Theorie: Dualität

Definition

Zu jedem beliebigen Minimierungsproblem existiert ein auf bestimmte Art gespiegeltes Maximierungsproblem. Dieses wird duales Problem genannt und zielt darauf ab, eine untere Schranke für den Minimalwert des ursprünglichen (primalen) Problemes zu finden.

Die Lösung des dualen Problemes gibt Auskünfte über den Einfluss der Nebenbedingungen auf die Lage des Optimums. Damit können Sensitivitätsuntersuchungen durchgeführt werden, womit Fragen nach einem der Robustheit des Optimums zuträglichen Systemdesign beantwortet werden können. Oft sehen duale Probleme ähnlich aus dem zugrundeliegenden (primalen) Problem. Ist etwa $$ \begin{align} P~~~~~~\min_x ~~~&f(x) \\ \text{s.t.} ~~~&A(x) =b \\ & G(x)\le h \end{align}$$ ein beliebiges Minimierungsproblem, so lautet das dazu duale Problem

$$ \begin{align}D~~~~~~ \max_{\nu,\lambda} ~~~&\underbrace{\inf_x \left(f(x)+\nu^T(A(x)-b)+\lambda^T(G(x)-h)\right)}_{g(\nu,\lambda)} \\ \text{s.t.} ~~~&\lambda \ge 0 \end{align}$$

wobei $\nu, \lambda$ die vektorwertigen dualen Optimierugnsvariablen sind und $\inf_x$ ein gegenüber Grenzwertbildung robustes Minimum über $x$ ist. Detailliertere Informationen sind z.B. in [1, pp.215–230] zu finden.

Relevanz

Für jedes zulässige x des primalen Problemes ist der Term $f(x)+\nu^T(A(x)-b)+\lambda^T(G(x)-h)$ kleiner als $f(x)$, da für $\lambda \ge 0$ gilt, dass $ \nu^T(A(x)-b)=0$ und $\lambda^T(G(x)-h)\le 0$. Folglich ist

$ g(\nu,\lambda) \le \min_{x\in D} f(x) ~~~D=\{x \in \mathbb{R}^n: A(x)=b \text{ und } G(x)\le h\}$

für alle $\lambda \ge 0$ und $\nu \in \mathbb{R}^{m_1}$. Ist $ g(\nu,\lambda)$ bekannt, kann der Minimalwert von $P$ einfach abgeschätzt werden. Eine Maximierung über diese untere Schranke führt zum dualen Problem $D$, dessen Lösung $d^*$ die beste so ableitbare untere Schranke ist für die Lösung $p^*$ des primalen Problems. Der Vorteil dieses Formalismus ist dreifach:

Unter Umständen ist $P$ schiwerig aber $D$ ist einfach
Lösungen $ \lambda^*, \nu^*$ von $D$ erlauben Aussagen über $P$
Der duality gap $p^*-d^*\ge 0$ zeigt an, ob $P$ und $D$ korrekt gelöst sind

Beispiel

Dies lässt sich am archetypischen Produktionsbeispiel zeigen, welches auch zur Illustration linearer Programmierung herangezogen wurde. Es sollen Produktmengen $x=[x_1,x_2]\ge 0$ produziert werden, sodass der bedarf von $x_1+x_2=2$ gedeckt ist und die Kosten $c^Tx = c_1x_1+c_2x_2$ mit $c=[1,5]$ minimal sind. Das entsprechende lineare Programm

$$ \begin{align} P~~~~~~\min_x ~~~&c^Tx ~~~~~~~&c=[1,5] \\ \text{s.t.} ~~~&Ax =b &b=2 ~~~A=[1,1] \\ & x\ge 0 & \end{align}$$

wird von Algorithmen gelöst zu $x^*=[,0]$ mit den Minimalkosten $c^Tx^*=2$. Das duale Programm

$$ \begin{align} D~~~~~~\max_{\nu,\lambda} ~~~&-b^T\nu \\ \text{s.t.} ~~~& A^T\nu +c -\lambda =0 \\ & \lambda \ge 0 \end{align}$$

ergibt sich $g(\nu,\lambda)=\inf_x c^Tx+\nu^T(Ax‑b)-\lambda^Tx = \inf_x -\nu^Tb +(c^T+\nu^TA-\lambda^T)x$, wobei letztere Formulierung entwerder den Wert $-\nu^Tb$ hat (falls $c+A^T\nu — \lambda =0$) oder $-\infty$ (alle anderen Konstellationen).

Interpretation

Das duale Problem ist ebenfalls ein LP und kann gelöst werden zu $\nu^*=-1, \lambda^*=[0,4]$ mit maximalem Wert $d^*=-b\nu^*=2$ daraus lassen sich zwei Schlussfolgerungen ableiten.

Der duality gap $p^*-d^*$ ist $0$. $P$ kann keine Lösung $p^*$ mit Werten kleiner als 2 haben, da $d^*=2$ eine untere Schranke ist. Da $p^*=d^*$ und es nur ein Optimum gibt, ist es eindeutig identifiziert worden und beide Optimierungsprobleme sind zertifizierbar korrekt gelöst worden.
Die optimalen Parameter $\nu^*, \lambda^*$ des dualen Problemes sind $[\nu^*]=-1 $ und $[\lambda_1^*,\lambda^*_2]=[0,4]$. Sie stehen in direktem Zusammenhang mit den Gewinnen, die aus einer Missachtung der Nebenbedingungen erwachsen würden [1, p.252].
- Die Lösung von $P$ mit veränderter Nebenbedingung $x_1\ge 1 $ statt $x_1 \ge 0$ ist $x^*=[2,0]$ mit $c^Tx^*=2$ — eine Veränderung von $\lambda_1^*=0$ von $p^*$.
- Die Lösung von $P$ mit veränderter Nebenbedingung $x_2\ge 1 $ statt $x_2 \ge 0$ ist $x^*=[1,1]$ mit $c^Tx^*=6$ — eine Veränderung von $\lambda_2^*=4$ von $p^*$.
- Die Lösung von $P$ mit veränderter Nebenbedingung $x_1+x_2=1 $ statt $x_1+x_2=2$ ist $x^*=[1,0]$ mit $c^Tx^*=1$ — eine Veränderung von $\nu^*=-1$ von $p^*$.

Somit sind $\nu^*, \lambda^*$ Quantifizierungen, welcher wirtschaftliche Verlust durch die Nebenbedingungen entsteht und zu welchem Preis ihre Vermeidung angemessen zu erkaufen wäre.

Anwendung

Ist das primale Programm ein optimales Produktionsmanagement Problem, so ist das duale Programm ein Problem der optimalen Presifindung seites der Rohstofflieferanten [2, pp. 77–80]. Duale Programme erlauben eine Sensitivtätsanalyse des ursprünglichen Problemes und eine bessere Beurteilung der Nebenbedingungen. Damit refokussieren sie Aufmerksamkeit weg von den optimalen Entscheidungen im System und hin zum optimalen Systemdesign. Sie repräsentieren interessante Probleme unabhängig ihres Verhältnisses zum primalen Programm.

Wenn für das Paar $(P,D)$ von Problemen $p^*=d^*$ gilt, spricht man von starker Dualität. Starke Dualität ist an die Efüllung der Slater-Bedingungen betreffen der zulässigen Menge von $P$ geknüpft und stellt den Regelfall dar für LP, QP, QCQP, SOCP, und SDP. Die Zusammenhänge zwischen $P$ und $D$ werden von primal-dualen Lösungsalgorithmen ausgenutzt, welche Optimierungsschritte für $P$ und $D$ synchron und gekoppelt durchführen. Diese Methoden sind dank der Zertifizierbarkeit der Lösung und der schnellen Konvergenz durch Nutzung der primalen und dualen Gradienten enorm beliebt [3, p. 115].

Quellen

[1] Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge: Cambridge University Press.

[2] Vanderbei, Robert J. (2013). Linear Programming: Foundations and Extensions. USA: Springer US.

[3] De Klerk, E. (2006). Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Berlin Heidelberg: Springer Science & Business Media.