Recovering a Dual Solution from a Primal Solution

Given an optimal primal solution $\mathbf{x}^*,$ we can recover the optimal dual solution $\mathbf{y}^*$ by solving a small linear system built from the complementary slackness conditions.

For a primal of the form

$$\max\ \mathbf{c}^T\mathbf{x} \quad \text{subject to} \quad A\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq \mathbf{0},$$

the dual is

$$\min\ \mathbf{b}^T\mathbf{y} \quad \text{subject to} \quad A^T\mathbf{y} \geq \mathbf{c},\ \mathbf{y} \geq \mathbf{0}.$$

Complementary slackness gives two rules:

1. (Positive primal variable.) If $x_j^* > 0,$ then the $j$-th dual constraint is tight: $(A^T\mathbf{y}^*)_j = c_j.$
2. (Slack primal constraint.) If $(A\mathbf{x}^*)_i < b_i,$ then $y_i^* = 0.$

To recover $\mathbf{y}^*,$ write one equation for each positive $x_j^*$ and one equation for each slack primal constraint, and solve the linear system in $\mathbf{y}.$

For example, consider the primal

$$\max\ 2x_1 + x_2 \quad \text{s.t.} \quad x_1 + x_2 \leq 3,\ x_1 \leq 2,\ \mathbf{x} \geq \mathbf{0},$$

with optimal $\mathbf{x}^* = (2, 1).$ Both primal constraints are tight, and both variables are positive. The dual constraints (one per primal variable) are

$$y_1 + y_2 \geq 2 \quad \text{and} \quad y_1 \geq 1.$$

Rule 1 forces both to be tight:

$$\begin{align*} y_1 + y_2 &= 2 \quad (\text{from } x_1 > 0)\\ y_1 &= 1 \quad (\text{from } x_2 > 0). \end{align*}$$

Solving gives $\mathbf{y}^* = (1, 1).$