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

Advertisements