In this blog, we try to find the relation between primal and dual problems. In specific, we will introduce two theorems – Weak Duality and Strong Duality.
Preparation
Recall the Relations between primal and dual variables and constraints
| Primal | $\min \quad \bar{c}^\top \bar{x}$ | $\max \quad \bar{p}^\top \bar{b}$ | Dual |
|---|---|---|---|
| Constraints | $ \begin{aligned} \bar{a}_i^\top \bar{x} & \geq b_i \ \bar{a}_i^\top \bar{x} & \leq b_i \ \bar{a}_i^\top \bar{x} & = b_i \end{aligned} $ | $\begin{aligned} p_i & \geq 0 \ p_i & \leq 0 \ p_i &\text{ free} \end{aligned}$ | Variables |
| Variables | $\begin{aligned} x_j & \geq 0 \ x_j & \leq 0 \ x_j &\text{ free} \end{aligned}$ | $\begin{aligned} \bar{p}^\top \bar{A}_j & \leq c_j \ \bar{p}^\top \bar{A}_j & \geq c_j \ \bar{p}^\top \bar{A}_j & = c_j \end{aligned} $ | Constraints |
Let’s change the form in following way
| Primal | $\min \quad \bar{c}^\top \bar{x}$ | $\max \quad \bar{p}^\top \bar{b}$ | Dual |
|---|---|---|---|
| Constraints | $ \begin{aligned} \bar{a}_i^\top \bar{x} -b_j & \geq 0 \ \bar{a}_i^\top \bar{x} - b_j & \leq 0 \ \bar{a}_i^\top \bar{x} - b_j & = 0 \end{aligned} $ | $\begin{aligned} p_i & \geq 0 \ p_i & \leq 0 \ p_i &\text{ free} \end{aligned}$ | Variables |
| Variables | $\begin{aligned} x_j & \geq 0 \ x_j & \leq 0 \ x_j &\text{ free} \end{aligned}$ | $\begin{aligned} c_j - \bar{p}^\top \bar{A}_j & \geq 0 \ c_j - \bar{p}^\top \bar{A}_j & \leq 0 \ c_j -\bar{p}^\top \bar{A}_j & = 0 \end{aligned} $ | Constraints |
Weak Duality
Theorem: ** Weak Duality. Given a primal/dual pair of LP problems, If $\bar{x}$ is a **feasible solution of the primal problem (min problem) and $\bar{p}$ is a feasible solution of the dual problem (max problem), then $\bar{p}^\top \bar{b} \leq \bar{c}^\top \bar{x}$.
Proof: Given $\bar{x}$ primal feasible and $\bar{p}$ dual feasible, we have:
- $\bar{a}_i^\top \bar{x} - b_i$, and $\bar{p}_i$ have the same sign
- $\bar{x}_j$ and $(c_j - \bar{p}^\top \bar{A}_j)$ have the same sign
This leads to the inequalities:
- $\bar{p}_i (\bar{a}_i^\top \bar{x} - b_i) \geq 0$ for $i=1,\ldots,m$
- $(c_j - \bar{p}^\top \bar{A}_j)\bar{x}_j \geq 0$ for $j=1,\ldots,n$
Summing these up, we get:
\[\bar{p}^\top (A\bar{x} - \bar{b}) = \sum_{i=1}^m \bar{p}_i (\bar{a}_i^\top \bar{x} - b_i) \geq 0\]and
\[(\bar{c}^\top - \bar{p}^\top A)\bar{x} = \sum_{j=1}^n (c_j - \bar{p}^\top \bar{A}_j)\bar{x}_j \geq 0\]It follows that $\bar{c}^\top \bar{x} - \bar{p}^\top \bar{b} = (\bar{c}^\top - \bar{p}^\top A)\bar{x} + \bar{p}^\top (A\bar{x} - \bar{b}) \geq 0$. $\square$
Corollary 1
(a) If the optimal cost in the primal problem is $-\infty$, then the dual problem must be infeasible.
(b) If the optimal cost in the dual problem is $+\infty$, then the primal problem must be infeasible.
Proof. Denote the Polyhedra of Primal and dual problems is $P$ and $D$.
(a) Suppose that the optimal cost in the primal problem is $-\infty$ and that the dual problem has a feasible solution $\bar{p}$. By weak duality,
\[\bar{p}^\top \bar{b} \leq \bar{c}^\top \bar{x} \quad \forall \bar{x} \in P.\]We know $\bar{p}^\top \bar{b}$ is a finite number. But ${ \bar{p}^\top \bar{b} \leq \min \{\bar{c}^\top \bar{x} \mid \bar{x} \in P \}}$, which contradicts to that optimal cost of the primal problem is $-\infty$. Therefore the dual problem cannot have a feasible solution if the optimal cost for the primal is $-\infty$.
(b) Suppose that the optimal cost in the dual problem is $+\infty$ and that the primal problem has a feasible solution $\bar{x}$. By weak duality,
\[\bar{p}^\top \bar{b} \leq \bar{c}^\top \bar{x} \quad \forall \bar{p} \in D.\]We know $\bar{c}^\top \bar{x}$ is a finite number. But ${ \max \{\bar{p}^\top \bar{b} \mid \bar{p}\in D\} \leq \bar{c}^\top \bar{x}}$, which contradicts to the optimal cost in the dual problem is $+\infty$. Therefore the primal problem cannot have a feasible solution if the optimal cost for the dual is $+\infty$. $\square$
Corollary 2 Given a primal/dual pair of LP problems \(\begin{aligned} \text{minimize} \quad & \bar{c}^\top \bar{x} \\ \text{subject to} \quad & \text{...} \end{aligned}\) and \(\begin{aligned} \text{maximize} \quad & \bar{p}^\top \bar{b} \\ \text{subject to} \quad & \text{...} \end{aligned}\)
If $\bar{x}$ is a feasible solution of the primal problem, $\bar{p}$ is a feasible solution of the dual problem, and $\bar{p}^\top \bar{b} = \bar{c}^\top \bar{x}$ , then $\bar{x}$ is an optimal solution of the primal problem and $\bar{p}$ is an optimal solution of the dual problem.
Proof: Since $\bar{p}$ is a feasible solution of the dual problem, the weak duality theorem tell us that
\[\bar{p}^\top \bar{b} \leq \bar{c}^\top \bar{y}, \forall \bar{y} \in P\]And $\bar{p}^\top \bar{b} = \bar{c}^\top \bar{x}$, we have
\[\bar{c}^\top \bar{x} \leq \bar{c}^\top \bar{y}, \forall \bar{y} \in P\]By assumption, we know $\bar{x}$ is a feasible solution of primal problem. Hence $\bar{x}$ is an optimal solution of the primal problem.
On the other hand, since $\bar{x}$ is a feasible solution of the primal problem, the weak duality theorem asserts that
\[\bar{q}^\top \bar{b} \leq \bar{c}^\top \bar{x}, \forall \bar{q} \in D\]Since $\bar{p}^\top \bar{b} = \bar{c}^\top \bar{x}$, it follows that $\bar{q}^\top \bar{b} \leq \bar{p}^\top \bar{b}, \forall \bar{q} \in D. $ And $\bar{p}$ is feasible solution of dual problem. Hence, $\bar{p}$ is an optimal solution of the dual problem. $\square$
Note: The corollary 2 tells us if we can find pair feasible solutions $\bar{x},\bar{p}$ in primal and dual problems, then we know they are both optimal solution in each problem, which give us an inspiration that the optimal costs of primal and dual problem are equal. The above idea lead to following theorem – Strong Duality. In this proof, the key step is to construct a pair of feasible solutions such that $\bar{p}^\top \bar{b} = \bar{c}^\top \bar{x}$ .
Strong Duality
Theorem: Strong Duality. If a LP problem admits an optimal solution, so does its dual, and the respective (primal and dual) optimal costs are equal.
Proof.
First, we consider the primal problem in standard form, and then generalize this conclusion.
Consider the standard form primal problem:
\[\begin{aligned} \text{minimize} \quad & \bar{c}^\top \bar{x} \\ \text{subject to} \quad & A\bar{x} = \bar{b} \\ & \bar{x} \geq \bar{0} \end{aligned}\]and its dual problem:
\[\begin{aligned} \text{maximize} \quad & \bar{p}^\top \bar{b} \\ \text{subject to} \quad & \bar{p}^\top A \leq \bar{c}^\top. \end{aligned}\]Assume (temporarily) that the rows of $A$ are linearly independent and that there exists an optimal solution to the primal problem. The simplex algorithm applied to the primal problem will terminate with an optimal basis $B$. The vector of basic variables of the corresponding optimal (primal) basic feasible solution $\bar{x}$ is $B^{-1}\bar{b}$. At $\bar{x}$. where the simplex algorithm terminates, the reduced costs must be nonnegative:
\[\bar{c}^\top - \bar{c}_B^\top B^{-1}\bar{A} \geq \bar{0}^\top\]Set $\bar{p} = \bar{c}_B^\top B^{-1}$. Then $ \bar{p}^\top A = \bar{c}_B^\top B^{-1} A \leq \bar{c}^\top$, which shows that $\bar{p}$ is a feasible solution of the dual problem. Furthermore, we have
\[\bar{p}^\top \bar{b} = \bar{c}_B^\top B^{-1}\bar{b} = \bar{c}_B^\top \bar{x}_B= \bar{c}^\top \bar{x}\]Since the dual cost at the dual feasible solution $\bar{p}$ is equal to the primal cost at the primal optimal solution $\bar{x}$, Corollary 2 asserts that $\bar{p}$ is an optimal solution to the dual problem. Hence the dual optimal cost $\bar{p}^\top \bar{b}$ is equal to the primal optimal cost $\bar{c}^\top \bar{x}$.
Now let’s consider the general cases, by theorem, we know dual problems of equivalent problems are equivalent. We can reformulate any LP problem $\Pi$ into standard form $\Phi$. So, we know optimal costs of problem $\Pi$ and $\Phi$ are equal. And we know optimal costs are equal in dual and primal problem in standard form case. Hence, we know the optima costs of $\Pi$ and its dual problem are equal. $\square$
Relations between Primal and Dual
The table below illustrates the relationships between the primal and dual problems:
| PRIMAL \ DUAL | Optimal Cost is $+\infty$ | Finite Optimal Cost | Infeasible |
| Optimal Cost is $-\infty$ | X | X | ✓ |
| Finite Optimal Cost | X | ✓ | X |
| Infeasible | ✓ | X | ✓($*$) |
- A checkmark (✓) denotes a possible scenario.
- A cross (X) indicates an impossible scenario.
For ($*$) case, we can give an example to verify the possibility
Primal Problem:
\[\begin{aligned} \text{minimize} \quad & x_1 + 2x_2 \\ \text{subject to} \quad & x_1 + x_2 = 1 \\ & 2x_1 + 2x_2 = 3 \end{aligned}\]Dual Problem:
\[\begin{aligned} \text{maximize} \quad & p_1 + 3p_2 \\ \text{subject to} \quad & p_1 + 2p_2 = 1 \\ & p_1 + 2p_2 = 2 \end{aligned}\]Complementary Slackness
Theorem Complementary Slackness. Given the PRIMAL problem (min problem) and the DUAL problem (max problem). And given a feasible solution $\bar{x}$ of the primal problem and a feasible solution $\bar{p}$ of the dual problem, we have:
$\bar{x}$ is an optimal solution of the primal and $\bar{p}$ is an optimal solution of the dual if and only if
- ${\bar{p}_i(\bar{a}_i^\top \bar{x} - b_i) = 0 \quad \forall i\in\{1,\ldots,m\}}$ (slackness in primal constraint)
- ${(c_j - \bar{p}^\top \bar{A}_j)\bar{x}_j = 0 \quad \forall j\in\{1,\ldots,n\}}$ (slackness in dual constraint)
Proof:
As we shown earlier, $\bar{x}$ is a feasible solution of the primal and $\bar{p}$ is a feasible solution implies
\[u_i := \bar{p}_i(\bar{a}_i^\top \bar{x} - b_i) \geq 0, \quad \forall i \quad (A)\]and
\[v_i := (c_j - \bar{p}^\top \bar{A}_j)\bar{x}_j \geq 0, \quad \forall j \quad (B)\]These lead to
\[\begin{aligned} 0 \leq \sum_{j=1}^n v_j + \sum_{i=1}^m u_i &= \sum_{i=1}^m \bar{p}_i (\bar{a}_i^\top \bar{x} - b_i) + \sum_{j=1}^n (c_j - \bar{p}^\top \bar{A}_j)\bar{x}_j \\ & =(\bar{c}^\top - \bar{p}^\top A)\bar{x} + \bar{p}^\top (A\bar{x} -\bar{b})\\ &= \bar{c}^\top \bar{x} - \bar{p}^\top \bar{b} \quad (*) \end{aligned}\]Thus, $\bar{x}$ primal optimal and $\bar{p}$ dual optimal implies, by strong duality, we have \(\bar{c}^\top \bar{x} - \bar{p}^\top \bar{b} = 0\)
Form $(*)$ we know, \(\sum_{j=1}^n v_j + \sum_{i=1}^m u_i = 0\) Then, by (A) and (B), we get $u_j = 0, \forall j \in {1,\ldots,n}$ and $v_i = 0, \forall i \in {1,\ldots,m}$. All the deduction are sufficient and necessary, so we can prove the converse statement. Proof done. $\square$
Note: In fact, we can derive the Karush–Kuhn–Tucker (KKT) condition of Linear Programming problem from Complementary Slackness. In other word, we can use this condition to check if a solution is a optimal solution of primal problem.
Primal in std form
Suppose $\bar{x}^*$ is a nondegenerate optimal basic feasible solution of
\[\begin{aligned} \text{minimize} \quad & \bar{c}^\top \bar{x} \\ \text{subject to} \quad & \bar{A}\bar{x} = \bar{b}\\ & \bar{x} \geq \bar{0}\\ \end{aligned}\]and $x^*_j$ is a basic component of the optimal b.f.s. $\bar{x}^*$. Then the complementary slackness condition $(\bar{c}_j - \bar{p}^\top \bar{A}_j)\bar{x}^*_j = 0$ must be satisfied by any optimal solution $\bar{p}^*$ of the dual problem.
Since $\bar{x}^*$ is a nondegenerate b.f.s and $x^*_j$ is a basic component of it, it must be that $x^*_j > 0$. Therefore, any optimal solution $\bar{p}^*$ of the dual problem must satisfy $(\bar{p}^{*})^\top \bar{A}_j = \bar{c}_j$ for every basic index $j$ (at the primal optimal b.f.s. $\bar{x}^*$). Hence any optimal solution $\bar{p}^*$ of the dual problem must be a solution of the linear system
\[(\bar{p}^*)^ \top B = \bar{c}_B^\top\]which leads to
\[\bar{p}^\* = \bar{c}_B^\top B^{-1}\]If the primal problem is in standard form and a nondegenerate optimal basic feasible solution is known, the complementary slackness conditions determine a unique optimal solution to the dual problem.
Genomic View
Now, we can try to portray the relation between primal and dual from geometric view. I think this part can give us a intuition that how mathematicians figure out the “Dual problem”.
$A$ is an $m \times n$ matrix (with $m \geq n$ since we must have $\text{rank}(A)= n$), $\bar{b} \in \mathbb{R}^m$ and $\bar{c} \in \mathbb{R}^n$. Consider the following pair of primal and dual problem
PRIMAL
\[\begin{aligned} \text{minimize} \quad & \bar{c}^\top \bar{x} \\ \text{subject to} \quad & A\bar{x} \geq \bar{b}\\ \end{aligned}\]DUAL
\[\begin{aligned} \text{minimize} \quad & \bar{c}^\top \bar{x} \\ \text{subject to} \quad & \bar{p} \geq \bar{0}\\ & \bar{p}^\top A = \bar{c}\\ \end{aligned}\]Let $I$ be a subset of ${\{1,2,\ldots,m\}}$ such that ${\{\bar{a}_i \mid i \in I\}}$ is a basis for $\mathbb{R}^n$. Note that $I$ necessarily contains $n$ elements. Since ${\{\bar{a}_i \mid i \in I\}}$ is a basis for $\mathbb{R}^n$, the linear system $\bar{a}_i^\top \bar{x} = b_i , i \in I$ has unique solution $\bar{x}^I$. This vector $\bar{x}^I$ is a basic solution of the primal problem.
NONDEGENERATE CASE
Suppose this basic solution $\bar{x}^I$ is nondegenerate, i.e., $\bar{a}_i^\top \bar{x}^I \neq b_i$ for $i \notin I$. In other words, $I$ is precisely the subset of ${1, 2, \ldots, m}$ indexing the primal constraints active at the nondegenerate basic solution $\bar{x}^I$ of the primal problem.
Let $\bar{p} \in \mathbb{R}^n$ be an optimal solutions of the primal and the dual problem. According to Complementary Slackness, $\bar{x}^I$ and $\bar{p}$ must satisfy (1), (2), (3) below.
(1). Primal feasibility: $\bar{a}_i^\top \bar{x}^I \geq b_i$, ${\forall i \in \{1, 2, \ldots, m\}}$
(2). Complementary slackness: $p_i = 0$, $\forall i \notin I$. (Because ${p_i(\bar{a}_i^\top \bar{x} - b_i) = 0 , \forall i\in\{1,\ldots,m\}}$, and $\forall i \notin I, \bar{a}_i^\top \bar{x}^I \neq b_i$, so $p_i$ has to be $0$.)
(3). Dual feasibility: $\sum_{i =1}^m p_i \bar{a}_i = \bar{c}$ and $\bar{p} \geq \bar{0}$.
Since ${\{\bar{a}_i \mid i \in I\}}$ is a basis for $\mathbb{R}^n$, (2) and (3) can determine a unique solution, say $\bar{p}^I$. (In specific, $\forall i \notin I, p_i=0$ and $\sum_{i \in I} p_i \bar{a}_i = \bar{c}^\top$). The vectors $\bar{a}_i$, with $i \in I$, form a basis for the dual problem (which is in standard form) and $\bar{p}^I$ is the associated basic solution. If $\bar{p}^I \geq \bar{0}$, this basic solution $\bar{p}^I$ is a b.f.s of the dual.
Attention! If $\bar{x}^I$ is a nondelegate basic feasible solution and we can compute unique solution $\bar{p}^I$, if $\bar{p}^I \geq \bar{0}$ (feasible solution of dual problem), we know we have $\bar{x}^I,\bar{p}^I$ are all feasible and meet complementary slackness, that means $\bar{x}^I$ and $\bar{p}^I$ are all optimal solution in primal and dual problem.
Note: In another view, we need a set of nonnegative $p_i$ such that $\sum_{i\in I} p_i \bar{a}_i = \bar{c}$, that means $\bar{c}$ and any normal vector of active constraint $\bar{a}_i, i \in I$ must have a sharp angle. Or in geometric view, we observe $\bar{c}$ is caught around all the normal vector $\bar{a}_i, i \in I$.
Example
Let’s give an example from textbook1.
Consider a primal problem with two variables and five inequality constraints ($n = 2, m = 5$), and suppose that no two of the vectors $\bar{a}_i$ are collinear. Every two-element subset $I$ of ${\{1,2,3,4,5\}}$ determines basic solutions $\bar{x}^I$ and $\bar{p}^I$ of the primal and the dual, respectively.
-
If ${I = \{1,2\}}$, $\bar{x}^I$ is primal infeasible (point A) and $\bar{p}^I$ is dual infeasible, because $\bar{c}$ cannot be expressed as a nonnegative linear combination of the vectors $\bar{a}_1$ and $\bar{a}_2$.
-
If ${I = \{1,3\}}$, $\bar{x}^I$ is primal feasible (point B) and $\bar{p}^I$ is dual infeasible.
-
If ${I = \{1,4\}}$, $\bar{x}^I$ is primal feasible (point C) and $\bar{p}^I$ is dual feasible, because $\bar{c}$ can be expressed as a nonnegative linear combination of the vectors $\bar{a}_1$ and $\bar{a}_4$. Hence, $\bar{x}^I$ and $\bar{p}^I$ are optimal.
-
If ${I = \{1,5\}}$, $\bar{x}^I$ is primal infeasible (point D) and $\bar{p}^I$ is dual feasible.
DEGENERATE CASE
If $\bar{x}^*$ is a degenerate basic solution to the primal problem, there can be several subsets $I$ of $\{1,2,\ldots,m\}$ such that $\bar{x}^* = \bar{x}^I$.
For instance1, in the example below, we have $\bar{x}^* = \bar{x}^J = \bar{x}^K$ for ${J = \{1,2\}}$ and ${K = \{2,3\}}$.
Solving $\sum_{i \in I} p_i \bar{a}_i = \bar{c}$ using different choices for $I$, we may obtain several basic solutions $\bar{p}^I$ to the dual problem all satisfying the complementary slackness relations relative to $\bar{x}^*$.
It may well be the case that some of them are dual feasible and some are not.
For instance, in the example above, we have
-
${J = \{1,2\}}$, ${\bar{x}^J = \bar{x}^*}$ primal feasible, $\bar{p}^J$ dual infeasible;
-
${K = \{2,3\}}$, ${\bar{x}^K = \bar{x}^*}$ primal feasible, $\bar{p}^K$ dual feasible;
Since $\bar{x}^K$ is primal feasible, $\bar{p}^K$ is dual feasible, and they satisfy the complementary slackness relations, they are both optimal b.f.s.