Duality in Linear Programming

In this article, I will try to delivery the concept of duality. Especially, I want to clear up the understanding and proof of its nice properties, i.e., the weak and strong duality property.

Duality in Linear ProgrammingI. Definition of DualityII. Conversion of DualityIII. Fundamental Duality PropertyA. Weak DualityDefinitionOptimal PropertyUnbounded PropertyB. Strong Duality

I. Definition of Duality

given n decision variables $x_j$ with objective coefficients $c_j$ and m constraints $b_i$ , there are two LPs which is of dual respectively.

Primal
$max \: z = \sum_{j=1}^{n} c_jx_j \quad | \quad \bf{c}^\intercal \dot \bf{x} \\ s.t. \quad \sum_{j=1}^{n} a_{ij} x_j \leq b_j \quad | \quad \bf{A} \dot \bf{x} \leq \bf{b} \\ \quad x_j \geq 0 \quad | \quad \bf{x} \geq \bf0$

Dual
$min \: z = \sum_{i=1}^{m} b_iy_i \quad | \quad \bf{b}^\intercal \dot \bf{y} \\ s.t. \quad \sum_{i=1}^{m} a_{ji} y_i \geq c_j \quad | \quad \bf{A}^\intercal \dot \bf{y} \geq \bf{c} \\ \quad y_i \geq 0 \quad | \quad \bf{y} \geq \bf0$

II. Conversion of Duality

for any LP problem with constraint matrix $\mathbf{A}$ , through basic transformation, its dual can be derived along the order of transpose $\mathbf{A}^\intercal$ and reversal equality conversion

the reverse equality relationship from m constraints ( $\bf{A} \dot \bf{x} \:? \: \mathbf{b}$ ) and n variables ( $\mathbf{x} \:?\: \mathbf0$ ) to m varialbe ( $\bf{A}^\intercal \dot \bf{y} \:? \: \mathbf{c}$ ) and n constraint ( $\mathbf{y} \:?\: \mathbf0$ ) follows the rule of below table

Primal	Dual
$i^{th}$ constraint $\leq$	$i^{th}$ variable $\geq 0$
$i^{th}$ constraint $\geq$	$i^{th}$ variable $\leq 0$
$i^{th}$ constraint =	$i^{th}$ variable unrestricted
$j^{th}$ variable $\geq 0$	$j^{th}$ constraint $\leq$
$j^{th}$ variable $\leq 0$	$j^{th}$ constraint $\geq$
$j^{th}$ variable unrestricted	$j^{th}$ constraint =

III. Fundamental Duality Property

there exists subtle equivalence between the primal and dual

A. Weak Duality

Weak Duality provides a bound on the optimal value of the objective function for the primal $P$ and the corresponding dual $D$ , specifically, any dual objective value v is an upper bound for the primal objective value z and any primal objective value z is a lower bound for the dual objective value z

Definition

In mathematical form,

\forall \: \bar{x} \in Solution(P) ,\: \bar{y} \in Solution(D): \\ \bf{c}^\intercal\dot \bf{\bar{x}} \: \leq \: \bf{b}^\intercal\dot \bf{\bar{y}}

Proof:
$\because \bf{A}\bf{x} \leq \bf{b},\: \bf{y}\geq \bf{0} \\ \Rightarrow \bf{x}^\intercal \bf{A}^\intercal \bf{y} \leq \bf{b}^\intercal \bf{y} \\ \because \bf{c} \leq \bf{A}^\intercal \bf{y},\: \bf{x}\geq \bf{0} \\ \Rightarrow \bf{c}^\intercal \bf{x} = \bf{x}^\intercal \bf{c} \leq \bf{x}^\intercal \bf{A}^\intercal \bf{y} \\ \therefore \bf{c}^\intercal \bf{x} \leq \bf{b}^\intercal \bf{y}$

Optimal Property

There are immediate nice properties for the weak duality (corollary), if we could find the existence of the weak duality inequality to be equal, that is the feasible solution $\hat{\mathbf{x}}$ of $P$ 's obejctive value is equal to the the feasible solution $\hat{\mathbf{y}}$ of $D$ 's obejctive value, then they are both optimal solutions. This is the so-called optimal property:

\forall \: \hat{x} \in Solution(P) ,\: \hat{y} \in Solution(D): \\ if \quad \bf{c}^\intercal\dot \bf{\bar{x}} \: = \: \bf{b}^\intercal\dot \bf{\bar{y}}:\\ \Rightarrow \hat{x} \in Optimal(P),\: \hat{y} \in Optimal(D)

Unbounded Property

Consider the inverse case of $\bf{c}^\intercal\dot \bf{\bar{x}} \leq \: \bf{b}^\intercal\dot \bf{\bar{y}}$ , if there is no boundary, then there will not be feasible solutions the dual LP, that is the unbounded property:

If the primal (dual) problem has an unbounded solution, then the dual (primal) problem is infeasible.

B. Strong Duality

Strong Duality implies the vital equivalence of primal and dual. It indicates that we may in fact solve the dual problem in place of or in conjunction with the primal problem.

If the primal (dual) problem has a finite optimal solution, then so does the dual (primal) problem, and these two values are equal.
that is,
$for \: P \: and \:D, \\ if \: \hat{z} \in max\{P\},\\ \Rightarrow \exist \: \hat{u} \quad s.t.\: \hat{u}\in min\{D\} \:and\: \hat{u} = \hat{z}$

Proof for standard form
Recall: for Simplex Method
$P \Leftrightarrow\\ max \: \bf{c_B}^\intercal \bf{x}_B + \bf{c_N}^\intercal \bf{x}_N \\ s.t. \:\bf{B} \dot \bf{x_B} + \bf{N} \dot \bf{x_N} = \bf{b} \\$
denote $x*$ as the optimal solution for $P$ that $x^* = (x_B^*, \mathbf{0})$
consider $\pi^* = (B^{-1})^\intercal \mathbf{c_B}$ , I want to show $\pi^*$ is the optimal solution for $D$
$\pi*$ is a feasible solution of $D$ , i.e. it satisfies the constraints of $D$ $A^\intercal y \geq \mathbf{c}$
$\bf{A}^\intercal= \begin{pmatrix} \bf{B}^\intercal \\ \bf{N}^\intercal \end{pmatrix} \\ B:\quad \bf{B}^\intercal \pi^* = B^\intercal ((B^{-1})^\intercal \bf{c_B}) = \bf{c}_B\\ N: \quad\because \:\:\:\quad\quad optimal \:\:\: solution\:\:\: P \\ \therefore \:\bf{c_N}^\intercal - \bf{c_B}^T B^{-1} \bf{N}\leq \bf0 \\ \Rightarrow^{\intercal} \quad \bf{N}^\intercal \pi^* = \bf{N}^\intercal ((B^{-1})^\intercal \bf{c_B}) \geq \bf{c_N}^\intercal \\$
$\pi*$ 's objective value is the same as $x^*$ 's
$\because \quad\mathbf{B} {x_B^*} = \mathbf{b} \:\Rightarrow\: {x_B^*} = \mathbf{B}^{-1} \mathbf{b} \\ \mathbf{c}^\intercal\mathbf{x}^*= \mathbf{c_B}^\intercal \mathbf{x_B^*} = \mathbf{c_B}^\intercal \mathbf{B}^{-1} \mathbf{b} = {\pi^*}^{\intercal}\mathbf{b} \\ \because \quad \mathbf{b}^{\intercal}{\pi^*} = {\pi^*}^{\intercal}\mathbf{b} \: (scalar) \\ \therefore \quad\mathbf{b}^{\intercal}{\pi^*} = \mathbf{c}^\intercal\mathbf{x}^*$
Lastly, from the @Weak Duality, $\pi^*$ is the optimal solution.
Hence, the dual $D$ has a optimal solution $\pi^*$ which has the same optimal value of P.
Proved 🤓