# Duality

We will now look at a problem that is more general than solving linear systems of the form $A\boldsymbol{x} = \boldsymbol{b}$.

Linear programs are of the form: $\min \boldsymbol{c^T}\boldsymbol{x}$ $s.t.$ $A\boldsymbol{x} \geq \boldsymbol{b}$

Note that linear programs have a linear objective ( $\boldsymbol{c^T}\boldsymbol{x}$) and linear constraints ( $A\boldsymbol{x} \geq \boldsymbol{b}$). We can easily see how to reduce solving a linear system $A\boldsymbol{x} = \boldsymbol{b}$ to a linear program, which would look like $\min \boldsymbol{0}$ $s.t.$ $A\boldsymbol{x} \geq \boldsymbol{b}$ $A\boldsymbol{x} \leq \boldsymbol{b}$

Let’s take a look at a few examples of linear programs.

Example 1. (Max Flow)

Let $G(V, E)$ be a graph with directed edges and capacities $c_{ij} \geq 0$. Let vertices $s, t \in V$ be the source and the sink respectively. Our goal is to find flows $f_{ij} \geq 0$ such that $f_{ij} \leq c_{ij}$ and $\sum_{i}f_{ij} = \sum_{l}f_{jl}$ $\forall j \neq s,t$. We want to maximize our net flow, which is the total flow out of source $s$, so out linear program is $\max \sum_{j}f_{sj}$ $s.t.$ $\sum_{i}f_{ij} = \sum_{l}f_{jl}$ $\forall j \in V \setminus \{s,t\}$ $f_{ij} \geq 0$ $\forall i,j \in V$ $f_{ij} \leq c_{ij}$ $\forall i,j \in V$

Example 2. (Low-cost Diet)

We need 180 units of protein, 100 units of carbs, and 20 units of fat. We can get sushi for 9 units of cost, tomato soup for 2 units of cost, and chicken massaman for 6 units of cost. A single unit of sushi gives 15 protein, 20 carbs, and 5 fat; tomato soup gives 5 protein, 30 carbs, 15 fat; chicken massaman gives 40 protein, 10 carb, 8 fat. What is the minimum cost satisfactory diet? Let’s assign the following variables: $x =$ sushi $y =$ tomato soup $z =$ chicken massaman

Then, we get the following linear program, $\min 9x + 2y + 6z$ $s.t.$ $(1)\ \ \ \ 15x + 5y + 40z \geq 180$ $(2)\ \ \ \ 20x + 30y + 10z \geq 100$ $(3)\ \ \ \ 5x + 15y + 8z \geq 20$

Let’s note the costs of some solutions to the above program. $x = 12,\ y = z = 0\ \ \ \ cost = 108$ $x = 2,\ y = 1,\ z = 4\ \ \ \ cost = 44$

Is there a better solution? If not, how can we show that there is no better solution? Let’s work towards a lower bound for $OPT$, the value of the optimal solution to the above program.

We will first try taking a multiple of one of our constraints, $\frac{1}{7}(1) = \frac{15}{7}x + \frac{5}{7}y + \frac{40}{7}z \geq \frac{180}{7}$ $\implies 9x + 2y + 6z \geq \frac{180}{7} = 25\frac{5}{7}$

So, $25\frac{5}{7} \leq OPT \leq 44$. Can we tighten this lower bound?

We will explore this question on another example. Consider the following LP, $\max 4x_1 + x_2 + 5x_3 + 3x_4$ $s.t.$ $(1)\ \ \ \ x_1 - x_2 - x_3 + 3x_4 \leq 1$ $(2)\ \ \ \ 5x_1 + x_2 + 3x_3 + 8x_4 \leq 55$ $(3)\ \ \ \ -x_1 + 2x_2 + 3x_3 - 5x_4 \leq 3$ $x_1, x_2, x_3, x_4 \geq 0$

Let $z^{*}$ be the value of the optimal solution. Again, let’s try some solutions and note the values $\boldsymbol{x} = (0, 0, 1, 0) \implies z^* \geq 5$ $\boldsymbol{x} = (2, 1, 1, \frac{1}{3}) \implies z^* \geq 15$

How can we tell if this $z^*$ is optimal? $\frac{5}{3}(2) = \frac{25}{3}x_1 + \frac{5}{3}x_2 + 5x_3 + \frac{40}{3}x_4 \leq \frac{275}{3}$ $\implies 4x_1 + x_2 + 5x_3 + 3x_4 \leq \frac{275}{3} \implies z^* \leq \frac{275}{3}$

We can try another linear combination of constraints $(2) + (3) = 4x_1 + 3x_2 + 6x_3 + 3x_4 \leq 58$ $\implies z^* \leq 58$

What is the best possible upper bound? We would like to choose multipliers $y_1, y_2, y_3 \geq 0$ for constraints $(1), (2), (3)$. Then, we get $(y_1 + 5y_2 - y_1)x_1 + (-y_1 + y_2 + 2y_3)x_2 + (-y_1 + 3y_2 + 3y_3)x_3 + (3y_1 + 8y_2 - 5y_3)x_4 \leq y_1 + 55y_2 + 3y_3$

So we’d like, $\min y_1 + 55y_2 + 3y_3$ $s.t.$ $y_1 + 5y_2 - y_1 \geq 4$ $-y_1 + y_2 + 2y_3 \geq 1$ $-y_1 + 3y_2 + 3y_3 \geq 5$ $3y_1 + 8y_2 - 5y_3 \geq 3$ $y_1, y_2, y_3 \geq 0$

Then, this gives a valid upper bound on $z^*$.

More generally the solution to the linear program $\min \boldsymbol{b^T}\boldsymbol{y}$ $s.t.$ $A^T \boldsymbol{y} \geq \boldsymbol{c}$ $\boldsymbol{y} \geq 0$

gives an upper bound for the linear program $\max \boldsymbol{c^T} \boldsymbol{x}$ $s.t.$ $A\boldsymbol{x} \leq \boldsymbol{b}$ $\boldsymbol{x} \geq 0$

or more concisely,

Theorem 1. (Weak Duality) $\max\{\boldsymbol{c^T}\boldsymbol{x}:A\boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq 0\} \leq \min\{\boldsymbol{b^T}\boldsymbol{y}:A^T \boldsymbol{y} \geq \boldsymbol{c}, \boldsymbol{y} \geq 0\}$