[proofplan]
We show that applying the LP duality construction twice returns to the original problem. Starting from the primal (minimise $c^\top x$ subject to $Ax \geq b$, $x \geq 0$), we write down the dual (maximise $\lambda^\top b$ subject to $A^\top \lambda \leq c$, $\lambda \geq 0$). We then convert the dual into a minimisation problem in general form, apply the duality construction again, and verify through algebraic manipulation that the resulting program is identical to the original primal.
[/proofplan]
[step:Write the dual of the primal]
The primal problem $(P)$ is
\begin{align*}
\min_{x \in \mathbb{R}^n} \; c^\top x \quad \text{subject to} \quad Ax \geq b, \quad x \geq 0.
\end{align*}
The dual $(D)$ is
\begin{align*}
\max_{\lambda \in \mathbb{R}^m} \; \lambda^\top b \quad \text{subject to} \quad A^\top \lambda \leq c, \quad \lambda \geq 0.
\end{align*}
[/step]
[step:Rewrite the dual as a minimisation problem in general form]
To apply the duality construction to $(D)$, we first express $(D)$ as a minimisation problem matching the general form. Maximising $\lambda^\top b$ is equivalent to minimising $-b^\top \lambda$. The constraint $A^\top \lambda \leq c$ is rewritten as $-A^\top \lambda \geq -c$. So $(D)$ becomes
\begin{align*}
\min_{\lambda \in \mathbb{R}^m} \; (-b)^\top \lambda \quad \text{subject to} \quad (-A^\top)\lambda \geq (-c), \quad \lambda \geq 0.
\end{align*}
This is a minimisation LP in general form with:
- decision variable $\lambda \in \mathbb{R}^m$,
- objective vector $-b \in \mathbb{R}^m$,
- constraint matrix $-A^\top \in \mathbb{R}^{n \times m}$,
- right-hand side $-c \in \mathbb{R}^n$.
[guided]
The duality construction as stated applies to minimisation problems in the form: minimise $\tilde{c}^\top \tilde{x}$ subject to $\tilde{A}\tilde{x} \geq \tilde{b}$, $\tilde{x} \geq 0$. The dual $(D)$ is a maximisation problem, so we must convert it.
The identity $\max\, \lambda^\top b = -\min\, (-b^\top \lambda)$ converts the objective. For the constraints, $A^\top \lambda \leq c$ is equivalent to $-(A^\top \lambda) \geq -c$, i.e., $(-A^\top)\lambda \geq (-c)$. The non-negativity constraint $\lambda \geq 0$ is already in the correct form. So we identify:
\begin{align*}
\tilde{x} = \lambda, \quad \tilde{c} = -b, \quad \tilde{A} = -A^\top, \quad \tilde{b} = -c.
\end{align*}
The reformulated dual is:
\begin{align*}
\min_{\lambda \in \mathbb{R}^m} \; (-b)^\top \lambda \quad \text{subject to} \quad (-A^\top)\lambda \geq (-c), \quad \lambda \geq 0.
\end{align*}
This is now in the standard form to which we can apply the duality construction.
[/guided]
[/step]
[step:Form the dual of the reformulated dual]
Applying the duality construction to the reformulated dual (with objective vector $\tilde{c} = -b$, constraint matrix $\tilde{A} = -A^\top$, and right-hand side $\tilde{b} = -c$), the dual is
\begin{align*}
\max_{\mu \in \mathbb{R}^n} \; \tilde{b}^\top \mu \quad \text{subject to} \quad \tilde{A}^\top \mu \leq \tilde{c}, \quad \mu \geq 0.
\end{align*}
Substituting $\tilde{b} = -c$, $\tilde{A}^\top = (-A^\top)^\top = -A$, and $\tilde{c} = -b$:
\begin{align*}
\max_{\mu \in \mathbb{R}^n} \; (-c)^\top \mu \quad \text{subject to} \quad (-A)\mu \leq -b, \quad \mu \geq 0.
\end{align*}
[guided]
The duality recipe says: given a primal $\min\, \tilde{c}^\top \tilde{x}$ s.t. $\tilde{A}\tilde{x} \geq \tilde{b}$, $\tilde{x} \geq 0$, the dual is $\max\, \tilde{b}^\top \mu$ s.t. $\tilde{A}^\top \mu \leq \tilde{c}$, $\mu \geq 0$.
We substitute:
- Objective of dual: $\tilde{b}^\top \mu = (-c)^\top \mu = -c^\top \mu$.
- Constraint: $\tilde{A}^\top \mu \leq \tilde{c}$ becomes $(-A^\top)^\top \mu \leq -b$. Since $(-A^\top)^\top = -A$, this is $-A\mu \leq -b$.
- Non-negativity: $\mu \geq 0$.
So the dual of the dual is:
\begin{align*}
\max_{\mu \in \mathbb{R}^n} \; (-c^\top \mu) \quad \text{subject to} \quad -A\mu \leq -b, \quad \mu \geq 0.
\end{align*}
[/guided]
[/step]
[step:Simplify to recover the original primal]
Multiplying the constraint $-A\mu \leq -b$ by $-1$ (which reverses the inequality) gives $A\mu \geq b$. Converting the maximisation of $-c^\top \mu$ to a minimisation:
\begin{align*}
\max_{\mu} \; (-c^\top \mu) = -\min_{\mu} \; c^\top \mu.
\end{align*}
So the dual of the dual is equivalent to
\begin{align*}
\min_{\mu \in \mathbb{R}^n} \; c^\top \mu \quad \text{subject to} \quad A\mu \geq b, \quad \mu \geq 0.
\end{align*}
Renaming $\mu$ as $x$, this is exactly the original primal $(P)$.
[guided]
The constraint $-A\mu \leq -b$ says $-(A\mu)_i \leq -b_i$ for each $i$. Multiplying by $-1$ reverses each inequality: $(A\mu)_i \geq b_i$, i.e., $A\mu \geq b$.
For the objective, maximising $-c^\top \mu$ is the same as minimising $c^\top \mu$ (the optimal $\mu$ is the same, the optimal values are negatives of each other). So the problem becomes:
\begin{align*}
\min_{\mu \in \mathbb{R}^n} \; c^\top \mu \quad \text{subject to} \quad A\mu \geq b, \quad \mu \geq 0.
\end{align*}
This is the original primal $(P)$ with the variable renamed from $x$ to $\mu$. The duality construction is therefore an involution: applying it twice returns to the starting problem. This has a concrete consequence: any theorem proved about primal-dual pairs automatically applies in both directions. For instance, if the primal is feasible and bounded, then the dual is feasible and bounded (by strong duality), and since the dual of the dual is the primal, the converse holds as well.
[/guided]
[/step]
