LP Duality

For any given LP, we can construct LP like one of the format follow.

Minimization problem

For given vectors $X = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}$, $C = \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{pmatrix}$, $B = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix}$ and matrix $A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}$ $=$ $\begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_m \end{pmatrix}$.

Minimize $C^T X$ such that
$a_i X \ge b_i$ for $i \in C_p$,
$a_i X \le b_i$ for $i \in C_m$,
$a_i X = b_i$ for $i \in C_e$,
$x_i \ge 0$ for $i \in B_p$,
$x_i \le 0$ for $i \in B_m$,
No limitation $x_i$ for $i \in B_f$.

Notice that $C_p \cup C_m \cup C_e = \{1, 2, \cdots, m\}$, $C_p \cap C_m$ $=$ $C_m \cap C_e$ $=$ $C_p \cap C_e$ $=$ $\emptyset$, $B_p \cup B_m \cup B_f = \{1, 2, \cdots, n\}$, $B_p \cap B_m$ $=$ $B_m \cap B_f$ $=$ $B_p \cap B_f$ $=$ $\emptyset$

Maximization problem

Maximize $C^T X$ such that
$a_i X \ge b_i$ for $i \in C_p$,
$a_i X \le b_i$ for $i \in C_m$,
$a_i X = b_i$ for $i \in C_e$,
$x_i \ge 0$ for $i \in B_p$,
$x_i \le 0$ for $i \in B_m$,
No limitation $x_i$ for $i \in B_f$.

Duality

For any given problem, it is so-called dual of primal problem if it fulfills following condition. Let’s assume that primal is a minimization problem like follow.

Then dual of primal minimization problem is a maximization problem like follow.

For given vectors $Y = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_m \end{pmatrix}$, $C = \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{pmatrix}$, $B = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix}$ and matrix $A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}$ $=$ $\begin{pmatrix} A_1 & A_2 & \cdots & A_n \end{pmatrix}$.

Maximize $B^T Y$ such that
$y_i \ge 0$ for $i \in C_p$,
$y_i \le 0$ for $i \in C_m$,
No limitation for $y_i$ for $i \in C_e$,
$A_i^T Y \le c_i$ for $i \in B_p$,
$A_i^T Y \ge c_i$ for $i \in B_m$,
$A_i^T Y = c_i$ for $i \in B_f$.

It’s the same for the opposite.

Then dual of primal maximization problem is a minimization problem like follow.

Example

Now, we’ve understood what is dual of primal. But where does the dual come from?

Consider the following LP.

Minimize $-x_1 + 3x_2 + x_3$ such that
$x_2 + 2x_3 \ge 6$,
$x_1 - x_2 + x_3 \ge 4$,
$x_1 - 3x_2 \le 2$,
$2x_1 - x_2 + x_3 = 7$,
$x_1 \ge 0$,
$x_2 \le 0$,
No restriction on $x_3$.

The optimal solution is $1$, achieved at $(x_1, x_2, x_3) = (2, 0, 3)$.

Even knowing the optimum is $1$, we may want a provable lower bound. One approach is to take a non-negative weighted sum of the constraints. If we think about any feasible solution $X = \begin{pmatrix}x_1 \\ x_2 \\ x_3 \end{pmatrix}$, all of constraints should hold. As a result all of following is true.

$x_2 + 2x_3$ $\ge$ $6$
$x_1 - x_2 + x_3$ $\ge$ $4$
$x_1 - 3x_2$ $\le$ $2$
$2x_1 - x_2 + x_3$ $=$ $7$

Define a multiplier vector $Y = \begin{pmatrix}y_1 \\ y_2 \\ y_3 \\ y_4 \end{pmatrix}$ and multiply each constraint by the corresponding $y_i$. The signs of $y_i$ are chosen to preserve the inequality direction.

$(x_2 + 2x_3) y_1$ $\ge$ $6y_1$, $y_1$ $\ge$ $0$
$(x_1 - x_2 + x_3)y_2$ $\ge$ $4y_2$, $y_2$ $\ge$ $0$
$(x_1 - 3x_2)y_3$ $\ge$ $2y_3$, $y_3$ $\le$ $0$
$(2x_1 - x_2 + x_3)y_4$ $=$ $7y_4$, no limitation for $y_4$

Now, let’s sum up all the constraints. $(x_2 + 2x_3)y_1$ $+$ $(x_1 - x_2 + x_3)y_2$ $+$ $(x_1 - 3x_2)y_3$ $+$ $(2x_1 - x_2 + x_3)y_4$ $\ge$ $6y_1 + 4y_2 + 2y_3 + 7y_4$. Now, just reorder the formula with the $x_1, x_2, x_3$. Then, $(y_2 + y_3 + 2y_4)x_1$ $+$ $(y_1 - y_2 - 3y_3 - y_4)x_2$ $+$ $(2y_1 + y_2 + y_4)x_3$ $\ge$ $6y_1 + 4y_2 + 2y_3 + 7y_4$. Now, if each of factor of $x_1, x_2, x_3$ is less or equal than original problem then it should be less or equal than before.

Therefore, $-x_1 + 3x_2 + x_3$ $\ge$ $(y_2 + y_3 + 2y_4)x_1$ $+$ $(y_1 - y_2 - 3y_3 - y_4)x_2$ $+$ $(2y_1 + y_2 + y_4)x_3$ should hold if followings are true.

$y_2 + y_3 + 2y_4$ $\le$ $-1$ because $x_1$ $\ge$ $0$
$y_1 - y_2 - 3y_3 - y_4$ $\ge$ $3$ because $x_2$ $\le$ $0$
$2y_1 + y_2 + y_4$ $=$ $1$ because there was no limitation for $x_3$

Then $-x_1 + 3x_2 + x_3$ $\ge$ $6y_1 + 4y_2 + 2y_3 + 7y_4$ is true.

As a result, we can define a maximization problem of lower bound of minization problem like follow.

Maximize $6y_1 + 4y_2 + 2y_3 + 7y_4$ such that
$y_2 + y_3 + 2y_4$ $\le$ $-1$,
$y_1 - y_2 - 3y_3 - y_4$ $\ge$ $3$,
$2y_1 + y_2 + y_4$ $=$ $1$,
$y_1 \ge 0$,
$y_2 \ge 0$,
$y_3 \le 0$,
No limitation for $y_4$.

Notice that optimum of this maximization problem is $1$ with $(y_1, y_2, y_3, y_4) = (\frac{5}{9}, 0, -\frac{7}{9}, -\frac{1}{9})$.

As shown above, we can systematically derive the dual, which gives a lower (or upper) bound on the primal optimum.

Weak Duality

Suppose the primal is a minimization problem for $C^T X$ and the dual is a maximization problem for $B^T Y$. Let $X^$ and $Y^$ be optimal solutions for the primal and dual, respectively. Then $C^T X^* \ge B^T Y^*$ always holds, because the dual optimum is a lower bound on the primal optimum.

Strong Duality

A stronger result holds: if both the primal and dual have feasible optima, then $C^T X^* = B^T Y^*$. Proof will be updated later.

Notice that there are three type of situations for LP.

LP has an optimum.
LP has no feasible solution.
LP has unbounded solution.(Infinitely small or big)

For each case, the possible situation is like follow.

	Primal has an optimum	Primal has no feasible solution	Primal has unbounded solution
Dual has an optimum	Possible	Impossible	Impossible
Dual has no feasible solution	Impossible	Possible	Possible
Dual has unbounded solution	Impossible	Possible	Impossible

Complementary slackness

For given vectors $X = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}$, $Y = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_m \end{pmatrix}$, $C = \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{pmatrix}$, $B = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix}$ and matrix $A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}$ $=$ $\begin{pmatrix} A_1 & A_2 & \cdots & A_n \end{pmatrix}$ $=$ $\begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_m \end{pmatrix}$.

Primal problem is like follow.

With the primal problem, dual is like follow.

Then, there is so-called complementary slackness condition which is follow.

$(a_i X - b_i) y_i = 0$ for all $0 \le i \le m$
$x_j(A_j^T Y \le c_j) = 0$ for all $0 \le j \le n$

The following is the complementary slackness theorem. Let $X$ and $Y$ be feasible solutions for the primal and dual LP, respectively. Then $X$ and $Y$ satisfy the complementary slackness conditions if and only if they are optimal for their respective problems. Proof will be updated later.