IMG_5599.jpeg

# Lecture 14: Fri. Feb 16, 2024 ## 12. More on duality; examples ### Recap $\min c^T x$ s.t. $Ax \geq b$ $x \geq 0$ Dual: $\max b^T y$ s.t. $A^T y \leq c$ $y \geq 0$ ### Weak Duality If $x$ is feasible for the primal and $y$ is feasible for the dual, then $c^T x \geq b^T y$ ### Proof...

# Lecture 14: Fri. Feb 16, 2024 ## 12. More on duality; examples ### Recap $\min c^T x$ s.t. $Ax \geq b$ $x \geq 0$ Dual: $\max b^T y$ s.t. $A^T y \leq c$ $y \geq 0$ ### Weak Duality If $x$ is feasible for the primal and $y$ is feasible for the dual, then $c^T x \geq b^T y$ ### Proof $c^T x \geq (A^T y)^T x = y^T A x \geq y^T b = b^T y$. ### Strong Duality If the primal is feasible and bounded, then the dual is feasible and bounded and $\min c^T x = \max b^T y$. ### Complementary Slackness If $x$ is optimal for the primal and $y$ is optimal for the dual, then $y_i > 0 \Rightarrow a_i^T x = b_i$ $x_j > 0 \Rightarrow A_j^T y = c_j$ where $a_i^T$ is the $i$-th row of $A$ and $A_j$ is the $j$-th column of $A$. ### Example 1: Min-Cost Network Flow #### Primal $\min \sum_{(i,j) \in E} c_{ij} f_{ij}$ s.t. $\sum_{j:(i,j) \in E} f_{ij} - \sum_{j:(j,i) \in E} f_{ji} = d_i$, $\forall i \in V$ $0 \leq f_{ij} \leq u_{ij}$, $\forall (i,j) \in E$ * $f_{ij}$: flow on edge $(i,j)$ * $c_{ij}$: cost per unit flow on edge $(i,j)$ * $u_{ij}$: capacity of edge $(i,j)$ * $d_i$: demand at node $i$ #### Dual $y_i$: dual variable for flow conservation constraint at node $i$. $z_{ij}$: dual variable for capacity constraint on edge $(i,j)$. $\max \sum_{i \in V} d_i y_i - \sum_{(i,j) \in E} u_{ij} z_{ij}$ s.t. $y_i - y_j \leq c_{ij} + z_{ij}$, $\forall (i,j) \in E$ $z_{ij} \geq 0$, $\forall (i,j) \in E$