Duality

300. Duality

300.1. Linear Programming Duality

Every linear program (primal) has a unique and symmetric dual problem. For any primal LP, there is a unique dual, whose dual is the primal.

Solving the dual gives you information about the primal.

300.1.1. General Form

300.1.2. Standard Form

Obj	max	min	Obj
Constraint	$\begin{matrix} \leq \\ \geq \\ = \end{matrix}$	$\begin{matrix} \geq 0 \\ \leq 0 \\ urs . \end{matrix}$	Variable
Variable	$\begin{matrix} \geq 0 \\ \leq 0 \\ urs . \end{matrix}$	$\begin{matrix} \leq \\ \geq \\ = \end{matrix}$	Constraint

Example

Minimization

Maximization

300.1.3. Weak Duality

Dual objective gives a lower bound for a minimization primal

𝑐^{𝑇} 𝑥 \geq 𝑏^{𝑇} 𝑦

Dual objective gives an upper bound for a maximization primal

𝑐^{𝑇} 𝑥 \leq 𝑏^{𝑇} 𝑦

Sufficiency of optimality

If $\bar{𝑥}$ and $\bar{𝑦}$ are primal and dual feasible and $𝑐^{𝑇} \bar{𝑥} \leq {\bar{𝑦}}^{𝑇} 𝑏$ , then $\bar{𝑥}$ and $\bar{𝑦}$ are primal and dual optimal

Example

Given a primal feasible solution $\bar{𝑥}$ , if we find a dual feasible solution so that their objective values are identical, $\bar{𝑥}$ is optimal (strong duality)

300.1.4. Dual Oprimal solution

If we have solved the primal LP, the dual optimal solution can be obtained

If $\bar{𝑥}$ is primal optimal with basis $𝐵$ , then ${\bar{𝑦}}^{𝑇} = 𝑐_{𝐵}^{𝑇} 𝐴_{𝐵}^{- 1}$ is dual optimal

300.1.5. Strong Duality

If both primal and dual are feasible and at least one has an optimal solution:

$\bar{𝑥}$ and $\bar{𝑦}$ are primal and dual optimal iff $\bar{𝑥}$ and $\bar{𝑦}$ are primal and dual feasible and

𝑐^{𝑇} \bar{𝑥} = 𝑏^{𝑇} \bar{𝑦}

Example

Using the simplex method, we obtain the optimal tableau:

The associated optimal basis is $𝐵 = (1, 2, 5)$
The optimal solution is $\bar{𝑥} = (3, 2)$
The associated objective value is $𝑧^{*} = 3$

For the standard form primal LP:

𝑐^{𝑇} = [\begin{matrix}  \end{matrix}] 𝐴 = [\begin{matrix}  \end{matrix}]

Given $𝑥_{𝐵} = (𝑥_{1}, 𝑥_{2}, 𝑥_{5})$ and $𝑥_{𝑁} = (𝑥_{2}, 𝑥_{4})$ :

𝑐_{𝐵}^{𝑇} = [\begin{matrix}  \end{matrix}] 𝐴_{𝐵} = [\begin{matrix}  \end{matrix}]

\bar{𝑦} = 𝑐_{𝐵}^{𝑇} 𝐴_{𝐵}^{- 1} = [\begin{matrix} 1 & 0 & 0 \end{matrix}] [\begin{matrix} \frac{1}{4} & \frac{1}{4} & 0 \\ - \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & - \frac{1}{2} & 1 \end{matrix}] = [\begin{matrix} \frac{1}{4} & \frac{1}{4} & 0 \end{matrix}]

For $\bar{𝑦} = (\frac{1}{4}, \frac{1}{4}, 0)$ :

It is dual feasible: $2 (\frac{1}{4}) + 2 (\frac{1}{4}) > 1$ and $- \frac{1}{4} + \frac{1}{4} + 0 \geq 0$
Its dual objective value $𝑤 = 4 (\frac{1}{4}) + 8 (\frac{1}{4}) = 3 = 𝑧^{*}$

Therefore $\bar{𝑦}$ is dual optimal

Example

Minimization

300.1.6. Feasibility-Infeasibility Certificates

If the primal is infeasible, the dual is either infeasible or unbounded
If the primal is unbounded, the dual is necessarily infeasible

Primal	Dual
Primal	Infeasible	Unbounded	Finitely Optimal
Infeasible	✅	✅	❌
Unbounded	✅	❌	❌
Finitely Optimal	❌	❌	✅

✅ means possible and ❌ means impossible
Primal unbounded $\to$ no upper bound $\to$ dual infeasible
Primal finitely optimal $\to$ finite objective value $\to$ dual finitely optimal
Primal infeasible $\to$ dual infeasible or unbounded

Example

Infeasible Primal $\to$ Infeasible Dual

Infeasible Primal $\to$ Unbounded Dual

Unbounded Primal $\to$ Infeasible Primal

300.1.7. Strong and Weak Duality

Problem Type	Duality	Weak Duality	Strong Duality
Min Primal Max Dual	$𝑐^{𝑇} 𝑥 \geq 𝑏^{𝑇} 𝑦$	$\begin{matrix} 𝑐^{𝑇} 𝑥 > 𝑏^{𝑇} 𝑦 \\ if \\ 𝑥 \neq 𝑥^{} or 𝑦 \neq 𝑦^{} \end{matrix}$	$𝑐^{𝑇} 𝑥^{} = 𝑏^{𝑇} 𝑦^{}$
Max Primal Min Dual	$𝑐^{𝑇} 𝑥 \leq 𝑏^{𝑇} 𝑦$	$\begin{matrix} 𝑐^{𝑇} 𝑥 < 𝑏^{𝑇} 𝑦 \\ if \\ 𝑥 \neq 𝑥^{} or 𝑦 \neq 𝑦^{} \end{matrix}$	$𝑐^{𝑇} 𝑥^{} = 𝑏^{𝑇} 𝑦^{}$

300.1.8. Complimentary Slackness

Slack variables of the dual LP

\begin{aligned} min & 𝑦^{𝑇} 𝑏 \\ 𝑠 . 𝑡 . & 𝑦^{𝑇} 𝐴 - 𝑣^{𝑇} = 𝑐^{𝑇} \\ 𝑣 \geq 0 \end{aligned}

$\bar{𝑥}$ and $(\bar{𝑦}, \bar{𝑣})$ are primal and dual optimal iff they are feasible and ${\bar{𝑣}}^{𝑇} \bar{𝑥} = 𝟎$

Proof

We have

\begin{aligned} 𝑐^{𝑇} \bar{𝑥} & = ({\bar{𝑦}}^{𝑇} 𝐴 - {\bar{𝑣}}^{𝑇}) \bar{𝑥} \\ = {\bar{𝑦}}^{𝑇} 𝐴 \bar{𝑥} - {\bar{𝑣}}^{𝑇} \bar{𝑥} \\ = {\bar{𝑦}}^{𝑇} 𝑏 - {\bar{𝑣}}^{𝑇} \bar{𝑥} \end{aligned}

Therefore ${\bar{𝑣}}^{𝑇} \bar{𝑥} = 0$ iff $𝑐^{𝑇} \bar{𝑥} = {\bar{𝑦}}^{𝑇} 𝑏$ , i.e., $\bar{𝑥}$ and $(\bar{𝑦}, \bar{𝑣})$ are primal and dual optimal according to strong duality.

Note that $𝑣^{𝑇} \bar{𝑥} = 0$ iff ${\bar{𝑣}}_{𝑖} {\bar{𝑥}}_{𝑖} = 0$ for all $𝑖$ as ${\bar{𝑥}}_{𝑖} \geq 0$ and $\bar{𝑣} \geq 0$
If a dual (primal) constraint is nonbinding, the corresponding primal (dual) variable is zero

Example

If optimal solution:

\begin{matrix} 𝑥_{1} 𝑣_{1} = 𝟎 \\ 𝑥_{2} 𝑣_{2} = 𝟎 \\ ⋮ \end{matrix}

Similarly, for an optimal solution:

\begin{matrix} 𝑠_{1} 𝑦_{1} = 𝟎 \\ 𝑠_{2} 𝑦_{2} = 𝟎 \\ ⋮ \end{matrix}

Let $(\bar{𝑥}, \bar{𝑠})$ be primal optimal, we have $(\bar{𝑥}, \bar{𝑠}) = (3, 2, 0, 0, 1)$ . Let’s find the dual optimal solution $(\bar{𝑦}, \bar{𝑣})$ without solving the LP.

According to complimentary slackness $\bar{𝑥_{1}}, \bar{𝑥_{2}}, \bar{𝑠_{1}} > 0$ imply $\bar{𝑣_{1}} = \bar{𝑣_{2}} = \bar{𝑦_{3}} = 0$ since:

\begin{matrix} \bar{𝑥_{1}} \bar{𝑥_{1}} = 0 \\ \bar{𝑥_{2}} \bar{𝑥_{2}} = 0 \\ \bar{𝑠_{3}} \bar{𝑦_{3}} = 0 \end{matrix}

The two dual functional equalities are reduced to:

\begin{matrix} 2 \bar{𝑦_{1}} + 2 \bar{𝑦_{2}} = 1 \\ - \bar{𝑦_{1}} + \bar{𝑦_{2}} = 0 \end{matrix}

Solving the above equaltions results in $\bar{𝑦_{1}} = \frac{1}{4}$ and $\bar{𝑦_{2}} = \frac{1}{4}$ .

$(\bar{𝑦}, \bar{𝑣})$ is then guaranteed to be dual optimal

( $𝑧^{*} = 3 = 𝑤^{*}$ )

If a primal solution is positive, the dual slack must be zero and vis versa.

𝑥_{𝑖} (𝑐_{𝑖} - {(𝐴^{𝑇} 𝑦)}_{𝑖}) = 𝟎 \forall 𝑖

If:

$𝑥_{𝑖} > 0$ : dual constraint is tight (equality holds)
$𝑥_{𝑖} = 0$ : dual constraint is slack (inequality not binding)

300.1.9. Shadow Prices

What if I have an additional unit of a particular resource?

For each resource there is a maximum price we are willing to pay for one additional unit

Definition: Shadow Price

For an LP that has an optimal colution, the shadow price of a constraint if the amount the objective value increases when the RHS of that constraint increases by 1, assuming the current optimal basis remains optimal

Sign or Shadow Price

Objective Function	Constraint
Objective Function	$\leq$	$\geq$	$=$
max	$\geq 0$	$\leq 0$	Free
min	$\leq 0$	$\geq 0$	Free

If shifting a constraint does not affect the optimal solution, the shadow price is zero. Shadow prices are zero for constraints that are nonbinding at the optimal solution.

Finding all shadow prices:

$𝑚$ : number of constraints

Example

The solution to the dual program is the shadow price of the primal

What are the shadow prices?

\begin{aligned} min & 6 & 𝑥_{1} & + & 4 & 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑥_{1} & + & 𝑥_{2} & \geq 2 \\ 2 & 𝑥_{1} & + & 𝑥_{2} & \geq 1 \end{aligned}

Solve the dual LP

\begin{aligned} max & 2 𝑦_{1} & + & 𝑦_{2} \\ 𝑠 . 𝑡 . & 𝑦_{1} & + & 3 𝑦_{2} & \leq & 6 \\ 𝑦_{1} & + & 𝑦_{2} & \leq & 4 \end{aligned}

The dual optimal solution is $𝑦^{*} = (4, 0)$

So shadow prices are 4 and 0 respectively

The shadow price is the absolute increase on the objective value given an increase of 1 on the RHS values

Instead of solving $𝑚$ LPs (one for each constraint increase by 1), we can just solve the dual LP