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\}$

Like this:

Related