Part 11 - Linear Programming: Duality and Sensitivity Analysis

Introduction

In this part we will cover duality for Linear Programs (LPs) and the corresponding weak & strong duality theorems. Further, we will also discuss sensitivity analysis and complementarity of (dual) LPs, which will give us an alternative view of the simplex method.a

Primal-Dual LP Problems

Definition 1 (Primal LP Problem)

Consider the primal LP problem on standard form,

\begin{align*} (P) \quad & \newline z^{\star} & = \begin{cases} \min \ & \mathbf{c}^T \mathbf{x} \newline \text{subject to} \ & A \mathbf{x} = \mathbf{b} \newline \ & \mathbf{x} \geq \mathbf{0} \end{cases} \end{align*}

where $z^{\star}$ is the optimal objective value.

Definition 2 (Dual LP Problem)

The dual LP problem corresponding to the primal LP problem $(P)$ is,

\begin{align*} (D) \quad & \newline q^{\star} & = \begin{cases} \max \ & \mathbf{b}^T \mathbf{y} \newline \text{subject to} \ & A^T \mathbf{y} \leq \mathbf{c} \end{cases} \end{align*}

where $q^{\star}$ is the optimal objective value.

Explanation (Derivation of the Dual Problem)

We know that the Lagrangian for the primal LP problem is,

\begin{align*} \mathcal{L}(\mathbf{x}, \mathbf{y}) & = \mathbf{c}^T \mathbf{x} - \mathbf{y}^T (\mathbf{b} - A \mathbf{x}) \newline & = \mathbf{b}^T \mathbf{y} + \mathbf{x}^T (A^T \mathbf{y} - \mathbf{c}) \end{align*}

thus, the dual function $q(\mathbf{y})$ is,

\begin{align*} \begin{align*} q(\mathbf{y}) = & \inf \ \mathbf{b}^T \mathbf{y} + \mathbf{x}^T (A^T \mathbf{y} - \mathbf{c}) \newline & \text{subject to} \ \mathbf{x} \geq \mathbf{0} \newline \end{align*} \newline = \begin{cases} \mathbf{b}^T \mathbf{y}, & A^T \mathbf{y} - \mathbf{c} \leq \mathbf{0} \newline -\infty, & \text{otherwise} \end{cases} \end{align*}

Therefore, the dual problem is,

\begin{align*} \max \ & q(\mathbf{y}) \newline \text{subject to} \ & A^T \mathbf{y} \leq \mathbf{c} \end{align*}

which is exactly the dual LP problem defined above.

Remark 1

We note that the primal has $n$ variables and $m$ constraints, while the dual has $m$ variables and $n$ constraints.

Further, the dual of the dual is the primal, i.e., $(D)$ is the dual of $(P)$ and $(P)$ is the dual of $(D)$ .

Proof

The Lagrangian for the dual LP problem is,

\begin{align*} \mathcal{L}(\mathbf{y}, \mathbf{x}) & = \mathbf{b}^T \mathbf{y} + \mathbf{x}^T (\mathbf{c} - A^T \mathbf{y}) \newline & = \mathbf{c}^T \mathbf{x} + \mathbf{y}^T (\mathbf{b} - A \mathbf{x}) \end{align*}

thus, the dual function $p(\mathbf{x})$ is,

\begin{align*} \begin{align*} p(\mathbf{x}) = & \sup \ \mathbf{c}^T \mathbf{x} + \mathbf{y}^T (\mathbf{b} - A \mathbf{x}) \newline & \text{subject to} \ \mathbf{y} \text{ free} \newline \end{align*} \newline = \begin{cases} \mathbf{c}^T \mathbf{x}, & A \mathbf{x} = \mathbf{b} \newline +\infty, & \text{otherwise} \end{cases} \end{align*}

Therefore, the dual problem is,

\begin{align*} \min \ & p(\mathbf{x}) \newline \text{subject to} \ & A \mathbf{x} = \mathbf{b} \newline \ & \mathbf{x} \geq \mathbf{0} \end{align*}

which is exactly the primal LP problem defined above, thus the dual of the dual is the primal.

Lastly, we can derive duals of LPs on non-standard form as well.

Intuition (Dual Problems on Non-Standard Form)

From what we have seen, we can see some symmetries between the primal and dual LP problems. Using these symmetries, we can derive duals of LPs on non-standard form.

Table 1: Symmetries between primal and dual linear programs.

Primal (P)	Dual (D)
$\min$ / $\inf$	$\max$ / $\sup$
Variables	Constraints
$\geq 0$	$\leq$
$\leq 0$	$\geq$
free	$=$
Constraints	Variables
$=$	free
$\geq$	$\geq 0$
$\leq$	$\leq 0$

Weak and Strong Duality

Theorem 1 (Weak Duality Theorem)

If $\mathbf{x}$ is a feasible solution to the primal LP problem $(P)$ and $\mathbf{y}$ is a feasible solution to the dual LP problem $(D)$ , then,

\mathbf{c}^T \mathbf{x} \geq \mathbf{b}^T \mathbf{y}

Proof

Since $\mathbf{x}$ is feasible for $(P)$ , we have that $A \mathbf{x} = \mathbf{b}$ and $\mathbf{x} \geq \mathbf{0}$ .

Since $\mathbf{y}$ is feasible for $(D)$ , we have that $A^T \mathbf{y} \leq \mathbf{c}$ . Therefore,

\begin{align*} \mathbf{c}^T \mathbf{x} & \geq (\underbrace{A^T \mathbf{y}}_{\leq \mathbf{c}})^T \mathbf{x} \newline & = \mathbf{y}^T \underbrace{(A \mathbf{x})}_{= \mathbf{b}} \newline & = \mathbf{b}^T \mathbf{y} _\blacksquare \end{align*}

From this theorem, we have some corollaries.

Corollary 1

If $z^{\star} = -\infty$ (the primal is unbounded), then the dual is infeasible.
If $q^{\star} = +\infty$ (the dual is unbounded), then the primal is infeasible.

Proof

Suppose that the primal is unbounded, i.e., $z^{\star} = -\infty$ . If the dual is feasible, then there exists a feasible $\mathbf{y}$ such that $\mathbf{b}^T \mathbf{y}$ is finite. However, by the weak duality theorem, we have that $\mathbf{c}^T \mathbf{x} \geq \mathbf{b}^T \mathbf{y}$ for all feasible $\mathbf{x}$ . This contradicts the assumption that the primal is unbounded, thus the dual must be infeasible.
The proof is similar to the first part, by swapping the roles of the primal and dual.

If $\mathbf{x}$ is feasible to $(P)$ and $\mathbf{y}$ is feasible to $(D)$ such that $\mathbf{c}^T \mathbf{x} = \mathbf{b}^T \mathbf{y}$ , then $\mathbf{x}$ and $\mathbf{y}$ are optimal to $(P)$ and $(D)$ , respectively.

Theorem 2 (Strong Duality Theorem)

If both $(P)$ and $(D)$ are both feasible, then there exists optimal $\mathbf{x}^{\star}$ to $(P)$ and optimal $\mathbf{y}^{\star}$ to $(D)$ such that,

\mathbf{c}^T \mathbf{x}^{\star} = \mathbf{b}^T \mathbf{y}^{\star}

Proof

Let $(P)$ be feasible, thus $z^{\star} > -\infty$ , therefore, there exists an optimal BFS.

Let $\mathbf{x}^{\star}$ be an optimal BFS to $(P)$ , for this BFS, we know that $\tilde{\mathbf{c}}_N^T \geq \mathbf{0}$ , let $\mathbf{y}^{\star} = \mathbf{c}_B^T B^{-1}$ .a

\begin{align*} \tilde{\mathbf{c}}_N^T & = \mathbf{c}_N^T - \mathbf{c}_B^T B^{-1} N \newline & = \mathbf{c}_N^T - \mathbf{y}^{\star T} N \newline & \geq \mathbf{0} \newline \Rightarrow & N^T \mathbf{y}^{\star} \leq \mathbf{c}_N \newline \end{align*}

Furthermore,

\begin{align*} \mathbf{c}_B^T - \mathbf{y}^{\star T} B & = \mathbf{c}_B^T - \mathbf{c}_B^T \underbrace{B^{-1} B}_{\mathbf{I}} \newline \mathbf{B}^T \mathbf{y}^{\star} & = \mathbf{c}_B \leq \mathbf{c}_B \newline \end{align*}

This means that,

\begin{align*} A^T \mathbf{y}^{\star} & = \begin{bmatrix} B^T \newline N^T \end{bmatrix} \mathbf{y}^{\star} = \begin{bmatrix} B^T \mathbf{y} \newline N^T \mathbf{y} \end{bmatrix} \leq \begin{bmatrix} \mathbf{c}_B \newline \mathbf{c}_N \end{bmatrix} = \mathbf{c} \newline \end{align*}

and thus $\mathbf{y}^{\star}$ is feasible for $(D)$ .

Further,

\begin{align*} \mathbf{b}^T \mathbf{y}^{\star} & = \mathbf{y}^{\star T} \mathbf{b} \newline & = \underbrace{\mathbf{c}_B^T B^{-1} b}_{\mathbf{x}_B} \newline & = \mathbf{c}_B^T \mathbf{x}_B^{\star} + \mathbf{c}_N^T \mathbf{x}_N^{\star} \newline & = \mathbf{c}^T \mathbf{x}^\star \newline \end{align*}

Thus, by corollary of weak duality, $\mathbf{x}^{\star}$ and $\mathbf{y}^{\star}$ are optimal to $(P)$ and $(D)$ , respectively. $_\blacksquare$

Remark 2

If $\mathbf{x}^{\star}$ is an optimal BFS to $(P)$ such that $\tilde{\mathbf{c}}_N^T \geq \mathbf{0}$ , then $\mathbf{y}^{\star} = (B^{-1})^T \mathbf{c}_B$ is optimal to $(D)$ .

Table 2: Possible primal and dual linear-program outcomes.

	Finite Optimal Solution	Unbounded	Infeasible
Finite Optimal Solution	$\color{green}{\text{Possible}}$	$\color{red}{\text{Impossible}}$	$\color{red}{\text{Impossible}}$
Unbounded	$\color{red}{\text{Impossible}}$	$\color{red}{\text{Impossible}}$	$\color{green}{\text{Possible}}$
Infeasible	$\color{red}{\text{Impossible}}$	$\color{green}{\text{Possible}}$	$\color{green}{\text{Possible}}$

Sensitivity Analysis

When solving LP problems, it is often the case that the parameters (i.e., $A$ , $\mathbf{b}$ , and $\mathbf{c}$ ) are not known exactly. Thus, it is important to understand how changes in these parameters affect the optimal solution and objective value. This is the goal of sensitivity analysis.

Definition 3 (Sensitivity Analysis in

\mathbf{c}

)

Let $\mathbf{x}^{\star}$ (nondegenerate and unique) be an optimal BFS to the primal LP problem $(P)$ . Further, consider some arbitrary perturbation,

\begin{align*} \min \ & (\mathbf{c} + \Delta \mathbf{c})^T \mathbf{x} \newline \text{subject to} \ & A \mathbf{x} = \mathbf{b} \newline \ & \mathbf{x} \geq \mathbf{0} \end{align*}

$\mathbf{x}^{\star}$ remains optimal if and only if,

\tilde{\mathbf{c}}_N^T = (\mathbf{c}_N + \Delta \mathbf{c}_N)^T - (\mathbf{c}_B + \Delta \mathbf{c}_B)^T B^{-1} N \geq \mathbf{0}

Note

We would ideally like to define a function that maps,

w(\mathbf{c}) = \begin{align*} & \min \ \mathbf{c}^T \mathbf{x} \newline & \text{subject to} \ A \mathbf{x} = \mathbf{b} \newline & \mathbf{x} \geq \mathbf{0} \end{align*}

If $\Delta \mathbf{c}$ is small enough, then we are interested in $\nabla_{\mathbf{c}} w(\mathbf{c})$ ,

\begin{align*} w(\mathbf{c}) & = \mathbf{c}^T \mathbf{x}^{\star} \newline \nabla_{\mathbf{c}} w(\mathbf{c}) & = \mathbf{x}^{\star} \end{align*}

However, this is only valid if $\mathbf{x}^{\star}$ remains optimal for all small perturbations in $\mathbf{c}$ .

Definition 4 (Sensitivity Analysis in

\mathbf{b}

)

Let $\mathbf{x}^{\star}$ (nondegenerate and unique) be an optimal BFS to the primal LP problem $(P)$ . Further, consider some arbitrary perturbation,

\begin{align*} \min \ & \mathbf{c}^T \mathbf{x} \newline \text{subject to} \ & A \mathbf{x} = \mathbf{b} + \Delta \mathbf{b} \newline \ & \mathbf{x} \geq \mathbf{0} \end{align*}

$\mathbf{x}^{\star}$ remains optimal if and only if,

\begin{bmatrix} \mathbf{x}_B \newline \mathbf{x}_N \end{bmatrix} = \begin{bmatrix} B^{-1} (\mathbf{b} + \Delta \mathbf{b}) \newline \mathbf{0} \end{bmatrix} \geq \mathbf{0}

Note

We would ideally like to define a function that maps,

v(\mathbf{b}) = \begin{align*} & \min \ \mathbf{c}^T \mathbf{x} \newline & \text{subject to} \ A \mathbf{x} = \mathbf{b} \newline & \mathbf{x} \geq \mathbf{0} \end{align*}

If $\Delta \mathbf{b}$ is small enough, then we are interested in $\nabla_{\mathbf{b}} v(\mathbf{b})$ ,

Theorem 3 (Shadow Prize Theorem)

If for a given $b$ the optimal BFS of $(P)$ is nondegenerate and unique, then $\nabla_{\mathbf{b}} v(\mathbf{b}) = \mathbf{y}^{\star}$ , where $\mathbf{y}^{\star}$ is the optimal solution to the dual problem $(D)$ .

Complementarity

Theorem 4 (Complementary Slackness Theorem)

Let $\mathbf{x}$ be feasible to the primal LP problem $(P)$ and $\mathbf{y}$ be feasible to the dual LP problem $(D)$ .

\begin{cases} \mathbf{x} \text{ is optimal to } (P) \newline \mathbf{y} \text{ is optimal to } (D) \end{cases} \newline \iff \newline x_j \left(c_j - (A_j)^T \mathbf{y}\right) = 0, \ \forall j = 1, \ldots, n \newline

where $A_j$ is the $j$ -th column of $A$ .

Corollary 2 (Characterization of Optimal Solutions)

$\mathbf{x}$ is optimal to $(P)$ and $\mathbf{y}$ is optimal to $(D)$ if and only if,

\begin{cases} A \mathbf{x} = \mathbf{b}, \ \mathbf{x} \geq \mathbf{0} \newline A^T \mathbf{y} \leq \mathbf{c} \newline x_j \left(c_j - (A_j)^T \mathbf{y}\right) = 0, \ \forall j = 1, \ldots, n \end{cases}

Algorithm (Alternative View of the Simplex Method)

Partition $A = \begin{bmatrix} B & N \end{bmatrix}$ with $\mathbf{x}_B = B^{-1} \mathbf{b}$ and $\mathbf{x}_N = \mathbf{0}$ (BFS), so primally feasible.
For $\begin{bmatrix} B^T \newline N^T \end{bmatrix} \mathbf{y} \leq \begin{bmatrix} \mathbf{c}_B \newline \mathbf{c}_N \end{bmatrix}$ , let $\mathbf{y} = (B^{-1})^T \mathbf{c}_B$ , this implies complementarity.
Left to check for optimality is dual feasibility, this means,

\begin{align*} N^T \mathbf{y} & \leq \mathbf{c}_N \newline N^T (B^{-1})^T \mathbf{c}_B & \leq \mathbf{c}_N \newline \tilde{\mathbf{c}}_N^T & = \mathbf{c}_N^T - \mathbf{c}_B^T B^{-1} N \geq \mathbf{0} \end{align*}

If $\tilde{\mathbf{c}}_N^T \geq \mathbf{0}$ , then $\mathbf{x}$ and $\mathbf{y}$ are optimal for $(P)$ and $(D)$ , respectively.
If $\tilde{\mathbf{c}}_N^T \not\geq \mathbf{0}$ , then perform a pivot step to get a new BFS and repeat from step 2.