Dualität |
|
Zu jedem LP \[ \begin{aligned} \max \quad & c^T x \\ \text{s.t.} \quad & Ax \leq b \\ & x \geq 0 \end{aligned} \] |
gehörte ein duales LP \[ \begin{aligned} \min \quad & b^T y \\ \text{s.t.} \quad & A^T y \geq c \\ & y \geq 0 \end{aligned} \] |
Duale Probleme lassen sich allgemein für Optimierungsprobleme formulieren (nicht nur LPs).
Kernidee: Das duale Problem ist eine obere Schranke für das original (primale) Maximierungsproblem
Oder eine untere Schranke für ein Minimierungsproblem.
Mit dem dualen Problem können wir uns dem optimalen Wert auch aus der anderen Richtung nähern.
- Wenn das primale Problem unbeschränkt ist, dann gibt es keine zulässige duale Lösung
- Wenn das duale Problem unbeschränkt ist, dann gibt es keine zulässige primale Lösung
- Es kann sein, dass es keine Lösung für das primale und das duale Problem gibt.
Für lineare Programme gilt:
Wenn es eine optimale primale Lösung gibt, gibt es auch eine optimale duale Lösung und beide haben den gleichen Zielfunktionswert.
Im dualen LP wird aus jeder Variablen eine Nebenbedingung und aus jeder Nebenbedingung eine Variable:
| \[ \begin{aligned} \max \quad & c^T x \\ \text{s.t.} \quad & Ax \leq b \\ & x \geq 0 \end{aligned} \] | \[ \begin{aligned} \min \quad & b^T y \\ \text{s.t.} \quad & A^T y \geq c \\ & y \geq 0 \end{aligned} \] |
Ausgehend von einem (Maximierungs) LP, das nicht in kanonischer Form ist gibt es folgende Regeln für das duale LP:
- Aus jeder Ungleichheits-Nebenbedingung wird eine Variable mit mit umgekehrtem Vorzeichen ($a\cdot x \geq b \Rightarrow y \leq 0$).
- Aus einer Gleichheits-Nebenbedingung wird eine freie Variable.
- Jede primale Variable wird zu einer Nebenbedingung mit dem gleichen Vorzeichen ($x \geq 0 \Rightarrow a\cdot y \geq c$ und $x \in \mathbb{R} \Rightarrow a \cdot y = c$)
Beispiel:
| \[ \begin{aligned} \max \quad & x_1 + 6x_2 \\ \text{s.t.} \quad & x_1 + x_2 \leq 4 \\ & 2x_1 + 3 x_2 \geq 5 \\ & x_1 \geq 0 \end{aligned} \] | \[ \begin{aligned} \min \quad & 4y_1 + 5y_2 \\ \text{s.t.} \quad & y_1 + 2y_2 \geq 1 \\ & y_1 + 3 y_2 = 6 \\ & y_1 \geq 0 \\ & y_2 \leq 0 \end{aligned} \] |
Für das LP \[ \begin{aligned} \max \quad & x_1 + 6x_2 \\ \text{s.t.} \quad & x_1 + x_2 \leq 4 \\ & 2x_1 + 3 x_2 \geq 5 \\ & x_1 \geq 0 \end{aligned} \] haben wir die optimale Lösung \[ x^* = \begin{bmatrix} 0 \\ 4 \end{bmatrix} \quad y^* = \begin{bmatrix} 6 \\ 0 \end{bmatrix} \]
$y^*_1 = 6$ sagt uns, dass der Zielfunktionwert um $6$ steigt, wenn wir die $b_1$ um 1 erhöhen
| \[ \begin{aligned} \max \quad & x_1 + 6x_2 \\ \text{s.t.} \quad & x_1 + x_2 \leq 4 {\color{red} + 1} \\ & 2x_1 + 3 x_2 \geq 5 \\ & x_1 \geq 0 \end{aligned} \] | \[ \begin{aligned} \min \quad & (4 {\color{red} + 1})y_1 + 5y_2 \\ \text{s.t.} \quad & y_1 + 2y_2 \geq 1 \\ & y_1 + 3 y_2 = 6 \\ & y_1 \geq 0 \\ & y_2 \leq 0 \end{aligned} \] |
Die Werte der dualen Lösung werden auch als Schattenpreise bezeichnet.
import mip
model = mip.Model()
variables = [model.add_var("x1"), model.add_var("x2")]
constraints = [
model.add_constr(variables[0] + variables[1] <= 4),
model.add_constr(2 * variables[0] + 3 * variables[1] >= 5)
]
model.objective = mip.maximize( variables[0] + 6 * variables[1] )
model.optimize()
for con in constraints:
print(con.pi)
Beispiel: Max-Flow
\[ \begin{aligned} \max \quad & \sum_{(s,i) \in E} x_{si} \\ \text{s.t.} \quad & \sum_{(i,j) \in E} x_{ij} - \sum_{(j,i) \in E} x_{ji} = 0 &&\forall i \in V \setminus \{s, t\} \\ & x_{ij} \leq \text{capacity}_{ij} && \forall (i,j) \in E \\ & 0 \leq x_{ij} && \forall (i,j) \in E \end{aligned} \]
$s$ ist die Quelle und $t$ die Senke.
Konkretes Beispiel:
|
\[ \begin{aligned} \max \quad & x_{AB} + x_{AC} \\ \text{s.t.} \quad & x_{BD} + x_{BC} - x_{AB} = 0 \\ & x_{CD} - x_{AC} - x_{BC} = 0 \\ & x_{AB} \leq 4 \\ & x_{AC} \leq 2 \\ & x_{BC} \leq 1 \\ & x_{BD} \leq 2 \\ & x_{CD} \leq 5 \\ &x \geq 0 \end{aligned} \] |
Jede Nebenbedingung erhält eine duale Variable:
- Eine Variable $y_{ij}$ je Kante
- Größer oder gleich 0
- Kosten = Kapazität
- Eine Variable $y_i$ je Knoten (ausser Senke und Quelle)
- frei
- Kosten = 0
|
\[ \begin{aligned} \max \quad & x_{AB} + x_{AC} \\ \text{s.t.} \quad & x_{BD} + x_{BC} - x_{AB} = 0 \\ & x_{CD} - x_{AC} - x_{BC} = 0 \\ & x_{AB} \leq 4 \\ & x_{AC} \leq 2 \\ & x_{BC} \leq 1 \\ & x_{BD} \leq 2 \\ & x_{CD} \leq 5 \\ &x \geq 0 \end{aligned} \] |
\[ \begin{aligned} \min \quad & 4 y_{AB} + 2 y_{AC} + 1 y_{BC} + 2 y_{BD} + 5 y_{CD} \\ \text{s.t} \quad & y_{AB}, y_{AC}, y_{BC}, y_{BD}, y_{CD} \geq 0 \end{aligned} \] |
Wir erhalten eine Nebenbedingung pro Variable
(also pro Kante):
|
\[ \begin{aligned} \max \quad & {\color{red} x_{AB}} + x_{AC} \\ \text{s.t.} \quad & x_{BD} + x_{BC} - {\color{red} x_{AB}} = 0 \\ & x_{CD} - x_{AC} - x_{BC} = 0 \\ & {\color{red} x_{AB}} \leq 4 \\ & x_{AC} \leq 2 \\ & x_{BC} \leq 1 \\ & x_{BD} \leq 2 \\ & x_{CD} \leq 5 \\ &x \geq 0 \end{aligned} \] |
$x_{AB}$ taucht in folgenden NB auf:
$x_{AB} \geq 0$ und $c_{AB} = 1 \quad\Rightarrow\quad \geq 1$ \[ \begin{aligned} \min \quad & 4 y_{AB} + 2 y_{AC} + 1 y_{BC} + 2 y_{BD} + 5 y_{CD} \\ \text{s.t} \quad & {\color{red} y_{AB} - y_{B} \geq 1} \\ & y_{AB}, y_{AC}, y_{BC}, y_{BD}, y_{CD} \geq 0 \end{aligned} \] |
$x_{AC}$
|
\[ \begin{aligned} \max \quad & x_{AB} + {\color{red} x_{AC}} \\ \text{s.t.} \quad & x_{BD} + x_{BC} - x_{AB} = 0 \\ & x_{CD} - {\color{red} x_{AC}} - x_{BC} = 0 \\ & x_{AB} \leq 4 \\ & {\color{red} x_{AC}} \leq 2 \\ & x_{BC} \leq 1 \\ & x_{BD} \leq 2 \\ & x_{CD} \leq 5 \\ &x \geq 0 \end{aligned} \] |
\[ \begin{aligned} \min \quad & 4 y_{AB} + 2 y_{AC} + 1 y_{BC} + 2 y_{BD} + 5 y_{CD} \\ \text{s.t.} \quad & y_{AB} - y_{B} \geq 1 \\ & {\color{red} y_{AC} - y_{C} \geq 1} \\ & y_{AB}, y_{AC}, y_{BC}, y_{BD}, y_{CD} \geq 0 \end{aligned} \] |
$x_{BC}$
|
\[ \begin{aligned} \max \quad & x_{AB} + x_{AC} \\ \text{s.t.} \quad & x_{BD} + {\color{red} x_{BC}} - x_{AB} = 0 \\ & x_{CD} - x_{AC} - {\color{red} x_{BC}} = 0 \\ & x_{AB} \leq 4 \\ & x_{AC} \leq 2 \\ & {\color{red} x_{BC}} \leq 1 \\ & x_{BD} \leq 2 \\ & x_{CD} \leq 5 \\ &x \geq 0 \end{aligned} \] |
\[ \begin{aligned} \min \quad & 4 y_{AB} + 2 y_{AC} + 1 y_{BC} + 2 y_{BD} + 5 y_{CD} \\ \text{s.t.} \quad & y_{AB} - y_{B} \geq 1 \\ & y_{AC} - y_{C} \geq 1 \\ & {\color{red} y_{BC} + y_B - y_C \geq 0} \\ & y_{AB}, y_{AC}, y_{BC}, y_{BD}, y_{CD} \geq 0 \end{aligned} \] |
Keine Variable taucht in mehr als 3 Nebenbedingungen auf.
Duales Problem
|
\[ \begin{aligned} \max \quad & x_{AB} + x_{AC} \\ \text{s.t.} \quad & x_{BD} + x_{BC} - x_{AB} = 0 \\ & x_{CD} - x_{AC} - x_{BC} = 0 \\ & x_{AB} \leq 4 \\ & x_{AC} \leq 2 \\ & x_{BC} \leq 1 \\ & x_{BD} \leq 2 \\ & x_{CD} \leq 5 \\ &x \geq 0 \end{aligned} \] |
\[ \begin{aligned} \min \quad & 4 y_{AB} + 2 y_{AC} + 1 y_{BC} + 2 y_{BD} + 5 y_{CD} \\ \text{s.t.} \quad & y_{AB} - y_{B} \geq 1 \\ & y_{AC} - y_{C} \geq 1 \\ & y_{BC} + y_B - y_C \geq 0 \\ & y_{BD} + y_B \geq 0 \\ & y_{CD} + y_C \geq 0 \\ & y_{AB}, y_{AC}, y_{BC}, y_{BD}, y_{CD} \geq 0 \end{aligned} \] |
Original LP
import mip
model = mip.Model()
x_AB = model.add_var(lb=0)
x_AC = model.add_var(lb=0)
x_BC = model.add_var(lb=0)
x_BD = model.add_var(lb=0)
x_CD = model.add_var(lb=0)
model.objective = mip.maximize(x_AB + x_AC)
y_B = model.add_constr(x_BD + x_BC - x_AB == 0)
y_C = model.add_constr(x_CD - x_AC - x_BC == 0)
y_AB = model.add_constr(x_AB <= 4)
y_AC = model.add_constr(x_AC <= 2)
y_BC = model.add_constr(x_BC <= 1)
y_BD = model.add_constr(x_BD <= 2)
y_CD = model.add_constr(x_CD <= 5)
model.optimize()
Duales LP
model = mip.Model()
y_B = model.add_var(lb=-float("infinity"))
y_C = model.add_var(lb=-float("infinity"))
y_AB = model.add_var(lb=0)
y_AC = model.add_var(lb=0)
y_BC = model.add_var(lb=0)
y_BD = model.add_var(lb=0)
y_CD = model.add_var(lb=0)
model.objective = mip.minimize(4 * y_AB + 2 * y_AC + y_BC + 2 * y_BD + 5 * y_CD)
model.add_constr(y_AB - y_B >= 1)
model.add_constr(y_AC - y_C >= 1)
model.add_constr(y_BC + y_B - y_C >= 0)
model.add_constr(y_BD + y_B >= 0)
model.add_constr(y_CD + y_C >= 0)
model.optimize()
Allgemein:
\[ \begin{aligned} \max \quad & \sum_{(s,i) \in E} x_{si} \\ \text{s.t.} \quad & \sum_{(i,j) \in E} x_{ij} - \sum_{(j,i) \in E} x_{ji} = 0 &&\forall i \in V \setminus \{s, t\} \\ & x_{ij} \leq \text{capacity}_{ij} && \forall (i,j) \in E \\ & 0 \leq x_{ij} && \forall (i,j) \in E \end{aligned} \]
Das duale LP hat eine Variable je Nebenbedingung
| \[ \begin{aligned} \max \quad & \sum_{(s,i) \in E} x_{si} \\ \text{s.t.} \quad & \sum_{(i,j) \in E} x_{ij} - \sum_{(j,i) \in E} x_{ji} = 0 &&\forall i \in V \setminus \{s, t\} \\ & x_{ij} \leq \text{capacity}_{ij} && \forall (i,j) \in E \\ & 0 \leq x_{ij} && \forall (i,j) \in E \end{aligned} \] |
|
| \[ \begin{aligned} \max \quad & \sum_{(s,i) \in E} x_{si} \\ \text{s.t.} \quad & \sum_{(i,j) \in E} x_{ij} - \sum_{(j,i) \in E} x_{ji} = 0 &&\forall i \in V \setminus \{s, t\} \\ & x_{ij} \leq \text{capacity}_{ij} && \forall (i,j) \in E \\ & 0 \leq x_{ij} && \forall (i,j) \in E \end{aligned} \] |
|
$\min \sum_{(i,j) \in E} \text{capacity}_{ij} y_{ij}$
Je Variable (also je Kante) erhalten wir eine Nebenbedingung
\[ \begin{aligned} \max \quad & \sum_{(s,i) \in E} x_{si} \\ \text{s.t.} \quad & \sum_{(i,j) \in E} x_{ij} - \sum_{(j,i) \in E} x_{ji} = 0 &&\forall i \in V \setminus \{s, t\} \\ & x_{ij} \leq \text{capacity}_{ij} && \forall (i,j) \in E \\ & 0 \leq x_{ij} && \forall (i,j) \in E \end{aligned} \]
\[ \begin{aligned} \max \quad & \sum_{(s,i) \in E} x_{si} \\ \text{s.t.} \quad & \sum_{(i,j) \in E} x_{ij} - \sum_{(j,i) \in E} x_{ji} = 0 &&\forall i \in V \setminus \{s, t\} \\ & x_{ij} \leq \text{capacity}_{ij} && \forall (i,j) \in E \\ & 0 \leq x_{ij} && \forall (i,j) \in E \end{aligned} \]
\[ \begin{aligned} \max \quad & \sum_{(s,i) \in E} x_{si} \\ \text{s.t.} \quad & \sum_{(i,j) \in E} x_{ij} - \sum_{(j,i) \in E} x_{ji} = 0 &&\forall i \in V \setminus \{s, t\} \\ & x_{ij} \leq \text{capacity}_{ij} && \forall (i,j) \in E \\ & 0 \leq x_{ij} && \forall (i,j) \in E \end{aligned} \]
\[ \begin{aligned} \max \quad & \sum_{(s,i) \in E} x_{si} \\ \text{s.t.} \quad & \sum_{(i,j) \in E} x_{ij} - \sum_{(j,i) \in E} x_{ji} = 0 &&\forall i \in V \setminus \{s, t\} \\ & x_{ij} \leq \text{capacity}_{ij} && \forall (i,j) \in E \\ & 0 \leq x_{ij} && \forall (i,j) \in E \end{aligned} \]
Wir wollen möglichst wenige $y_{ij}$ auswählen.
Wenn $y_{si}=0$ dann folgt aus
$y_{si} - u_i \geq 1 \quad \forall (s,i) \in E, i \neq t$
das
$u_i \leq -1$.
Wenn $y_{ij}=0$ dann folgt aus
$y_{ij} + u_i - u_j \geq 0 \quad \forall (i,j) \in E, i \neq s, j \neq t$
das
$u_j \leq u_i$
Wenn $y_{it}=0$ dann folgt aus
$y_{it} + u_i \geq 0 \quad \forall (i,t) \in E, i \neq s$
das
$u_i \geq 0$.
An der Quelle sind die $u$ also $-1$ und sollen an der Senke $0$ sein. Sie können nur ansteigen, wenn wir zwischendurch ein $y = 1$ setzen.
Wir brauchen einen ganzen Cut durch den Graph, an dem wir die $y$ auf eins setzen.
Unser duales LP
berechnet einen minimalen s-t-Cut
Daher gilt auch, dass der Wert des minimalen Cuts gleich dem Wert des maximalen Flusses ist.
Manchmal hat das duale LP eine Weg, um es gut zu interpretieren.
Dualität ist ein generelles Konzept für Optimierungsprobleme
Für Support Vector Machines (SVM) braucht man die duale Umformung um den Kernel-Trick anzuwenden.
Auch in einem weniger mathematisch-formellen Setting macht das Nachdenken über duale Probleme Sinn:
Beispiel: Um ein IT System sicher zu machen, sollte man überlegen, wie man es angreifen kann.