Duality |
|
For each LP \[ \begin{aligned} \max \quad & c^T x \\ \text{s.t.} \quad & Ax \leq b \\ & x \geq 0 \end{aligned} \] |
corresponded a dual LP \[ \begin{aligned} \min \quad & b^T y \\ \text{s.t.} \quad & A^T y \geq c \\ & y \geq 0 \end{aligned} \] |
Dual problems can generally be formulated for optimization problems (not just LPs).
Core idea: The dual problem is an upper bound for the original (primal) maximization problem
Or a lower bound for a minimization problem.
With the dual problem, we can also approach the optimal value from the other direction.
- If the primal problem is unbounded, then there is no feasible dual solution
- If the dual problem is unbounded, then there is no feasible primal solution
- It is possible that there is no solution for the primal and dual problems.
For linear programs, the following applies:
If there is an optimal primal solution, there is also an optimal dual solution, and both have the same objective function value.
In dual LP, each variable is turned into a constraint and each constraint into a 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} \] |
Starting from a (maximization) LP that is not in canonical form, the following rules apply to the dual LP:
- From each inequality constraint, a variable is created with the reverse sign ($a\cdot x \geq b \Rightarrow y \leq 0$).
- From an equality constraint, a free variable is created.
- Each primal variable becomes a constraint with the same sign ($x \geq 0 \Rightarrow a\cdot y \geq c$ and $x \in \mathbb{R} \Rightarrow a \cdot y = c$)
Example:
| \[ \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} \] |
For the 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} \] we have the optimal solution \[ x^* = \begin{bmatrix} 0 \\ 4 \end{bmatrix} \quad y^* = \begin{bmatrix} 6 \\ 0 \end{bmatrix} \]
$y^*_1 = 6$ tells us that the objective function value increases by $6$ if we increase $b_1$ by 1.
| \[ \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} \] |
The values of the dual solution are also referred to as shadow prices.
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)
Example: 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$ is the source and $t$ is the sink.
Concrete example:
|
\[ \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} \] |
Each constraint receives a dual variable:
- One variable $y_{ij}$ per edge
- Greater or equal to 0
- Costs = Capacity
- One variable $y_i$ per node (excluding sink and source)
- Free
- Costs = 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} \] |
We receive one constraint per variable
(thus per edge):
|
\[ \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}$ appears in the following constraints:
$x_{AB} \geq 0$ and $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} \] |
No variable appears in more than 3 constraints.
Dual 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()
Dual 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()
General:
\[ \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} \]
The dual LP has one variable per constraint
| \[ \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}$
For each variable (or each edge), we receive a constraint
\[ \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} \]
We want to select as few $y_{ij}$ as possible.
If $y_{si}=0$, then it follows from
$y_{si} - u_i \geq 1 \quad \forall (s,i) \in E, i \neq t$
that
$u_i \leq -1$.
If $y_{ij}=0$, then from
$y_{ij} + u_i - u_j \geq 0 \quad \forall (i,j) \in E, i \neq s, j \neq t$
it follows that
$u_j \leq u_i$
If $y_{it}=0$ then it follows from
$y_{it} + u_i \geq 0 \quad \forall (i,t) \in E, i \neq s$
that
$u_i \geq 0$.
At the source, the $u$ are therefore $-1$ and should be $0$ at the sink. They can only rise if we set $y = 1$ in between.
We need a complete cut through the graph where we set $y$ to one.
Our dual LP
calculates a minimal s-t-Cut
Therefore, it also applies that the value of the minimal cut is equal to the value of the maximum flow.
Sometimes the dual LP has a way to interpret it well.
Duality is a general concept for optimization problems
For Support Vector Machines (SVM), one needs the dual formulation to apply the kernel trick.
Thinking about dual problems also makes sense in a less mathematically formal setting:
Example: To secure an IT system, one should consider how to attack it.