Dual Program, Weak Duality, Complementary Slackness, Strong Duality

Every linear program can be converted into Canonical form

for some $c, x \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$.

Dual Program and Weak Duality

Next, we try to construct an upper bound for the optimal solution of this optimization problem, based on its linear constraints.

If $y \in \mathbb{R}^m$ and $y \ge 0$, then $y^T (Ax)$ is called a conic combination of the constraints. It holds that

If $y$ further satisfies the constraint

combining with the fact that $x \ge 0$, we get

Hence $y^T b$ is an upper bound of the optimal value of the original program. We want the bound to be as tight as possible. This motivates another linear program:

We call the original program the primal and the derived program its dual. The philosophy behind the dual construction is to combine the primal constraints to obtain a bound of its optimal value.

Corollary. If the primal is unbounded, then the dual is infeasible. If the dual is unbounded, then the primal is infeasible.

In general, the primal may not be given in Canonical form and can be formulated as

Note that the $\bar x$'s are unconstrained variables. Driven by the same philosophy, we hope to derive an upper bound by using the constraints:

1. To guarantee the second inequality, we require that

   • $y^T \ge 0$ (since the constraint $Ax + \bar A \bar x + \hat A \hat x \le b$ holds),

   • $\bar y^T$ be unconstrained (since the constraint $Bx + \bar B \bar x + \hat B \hat x = \bar b$ holds), and

   • $\hat y^T \le 0$ (since the constraint $Cx + \bar C \bar x + \hat C \hat x \ge \hat b$ holds).

   We see that the types of constraints in the primal determine the signs of variables in the dual.

2. The reverse is also true: the constraints in the dual are determined the signs of variables in the primal. The first inequality implies that (by proper rearranging):

   $$\begin{aligned} c^T x + \bar c^T \bar x + \hat c^T \hat x & \le (y^T A + \bar y^T B + \hat y^T C)x \\ & + (y^T \bar A + \bar y^T \bar B + \hat y^T \bar C) \bar x \\ & + (y^T \hat A + \bar y^T \hat B + \hat y^T \hat C) \hat x \end{aligned}$$

   As $x \ge 0$, $\bar x$ unconstrained and $\hat x \le 0$, a sufficient condition for the inequality to become true is

   $$\begin{aligned} c^T & \le (y^T A + \bar y^T B + \hat y^T C) \\ \bar c^T & = (y^T \bar A + \bar y^T \bar B + \hat y^T \bar C) \\ \hat c^T & \ge (y^T \hat A + \bar y^T \hat B + \hat y^T \hat C) \\ \end{aligned}$$

   That gives the first set of constraints the dual variables $y$, $\bar y$ and $\hat y$ need to satisfies, respectively. We have just seen that the sign of the primal variable determines the type of constraint in the dual.

   Of particular interest is the inequality constraint, which we will discuss in details in the next section.

The rules of obtaining dual are summarized as follows:

$$\begin{array}{llll} \hline \text{Primal} & \max & \min & \text{Dual} & \\ \hline \text{Constraints} & \begin{array}{l} \le b_i \\ \ge b_i \\ = b_i \end{array} & \begin{array}{l} \ge 0 \\ \le 0 \\ \text{Both sides} \end{array} & \text{Variables} & \\ \hline \text{Variables} & \begin{array}{l} \ge 0 \\ \le 0 \\ \text{Both sides} \end{array} & \begin{array}{l} \ge c_j \\ \le c_i \\ = c_j \end{array} & \text{Constraints} & \\ \hline \end{array}$$

Complementary Slackness

The strong duality states that, if both primal and dual are feasible, then the objective function values of their optimal solutions are equal. It follows that the inequalities in weak duality are saturated

Therefore,

If the primal is in canonical form, then the fact that $y^T A \ge c$, $x \ge 0$, $y \ge 0$, and $b - Ax \ge 0$ implies that

where $(y^T A - c^T)_i$ is its $i$-th coordinate of the vector $y^T A - c^T \in \mathbb{R}^{1 \times n}$, and $(b - Ax)_j$ is the $j$-th coordinate of the vector $b - Ax \in \mathbb{R}^{m \times 1}$.

This is known as complementary slackness.

Question to ponder: what is the geometric interpretation of complementary slackness?

Strong Duality

Theorem. Exactly one of the following four cases holds:

1. Neither the primal nor the dual is feasible.
2. If both the primal and dual are feasible, then their optimal values are equal.
3. If the primal is feasible and unbounded, and dual is infeasible.
4. If the dual is feasible and unbounded, and primal is infeasible.

Special Case

We first consider the special case such that not every linear program can be converted to this case. We consider the general form in the next section.

The special case is given by

The dual form is given by

The primal is feasible if $c$ is a linear combination of rows of $A$, i.e., in the row space of $A$. The dual is feasible if $b$ is a linear combination of columns of $A$, i.e., in column space of $A$, denoted as $C(A)$.

It is possible that neither the primal nor the dual is feasible.

Example.

$$A = \begin{bmatrix} 1,\, &0\\ 0,\, &0\\ \end{bmatrix},\, b= \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix},\, c= \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix}.$$

Then neither $A x = b$ nor $y^T A = c^T$ is feasible.

If both primal and dual are feasible, then for all feasible solutions $x$ and $y$, it holds that

Next, we show that

Theorem.

1. If the primal is feasible and dual is infeasible, then the primal is unbounded.
2. If the dual is feasible and primal is infeasible, then the dual is unbounded.

Proof. By symmetry, we prove just the former.

If $Ax = b$ is not feasible, then $b$ lies outside the column space of $A$, denoted as $C(A)$ (the subspace in $\mathbb{R}^m$ spanned by the column vectors of $A$). Let $N(A^T)$ be the subspace orthogonal to $C(A)$. We can decompose $b$ into two part:

where $b_1 \in C(A)$ is in the columns space of $A$ and $b_2 \in N(A^T)$ is orthogonal to the columns space of $A$. By assumption we have $b_2 \neq \vec 0$.

Suppose $y$ is a feasible solution to $y^T A = c^T$. Then for all $k \in \mathbb{R}$, $y + k \cdot b_2$ is still a feasible solution, since

The new solution has objective

When $k \rightarrow - \infty$, we have $y^T b + k \cdot \Vert b_2 \Vert_2^2 \rightarrow - \infty$, which implies that the primal is unbounded.

General Case

We discuss the more general form:

Every linear program can be converted into this general form.

Its dual is given by

By weak duality,

To prove strong duality, we need only to prove that

If both primal and dual are feasible, then there exists feasible $x, y$, such that $c^T x = y^T A x$.

Define the feasible set of the primal as

Let $y^\star$ be the optimal solution for the primal. We see that $y^\star$ can not be an interior point of the feasible set $F$. Otherwise, for small enough $k > 0$, $y^\star - k \cdot b$ belongs to $F$. But $(y^\star - k \cdot b)^T b < y^\star b$, contradicting $y^\star$ being optimal.

Therefore, $y^\star$ must be on the boundary of the $F$, and there must exit one or more constraints saturated by $y^\star$. Define the set of indexes of the constraints that are saturated by $y^\star$

where $A_i$ is the $i$-th column of matrix $A$ and $c_i$ is the $i$-th coordinator of vector $c$. Let $A_S$ be set of columns indexed by $S$.

Lemma. $b$ is in the conic hull of columns of $A_S$, i.e., $\exists x_S \in R^{|S|}$, such that

1. $A_S x_S = b$.
2. $x_S \ge 0$.

Such $x_S$ can be converted into a feasible solution $x$ to the dual (by padding zeros in dimensions other than $S$). It holds that

Question to ponder: prove the existence of optimal solution of the primal, assuming feasibility of the dual.

Proof. We prove that if $b$ is not in the conic hull of $A_S$, we can more $y^\star$ along some direction that decreases objective while maintaining feasibility.

By Farkas' Lemma, if $b$ is not in the conic hull of $A_S$, $\exists v \in \mathbb{R}^m$, such that

1. $v^T A_S \ge 0$.
2. $v^T b < 0$.

Then we can move the vector $y^\star$ along the direction of $v$, by adding $k \cdot v$ to $y^\star$ for some $k \ge 0$. This decreases the objective

How large can $k$ be, so the constraints $(y^\star + k \cdot v)^T A \ge c^T$ are maintained.

1. If $i \in \bar S$, then $(y^\star)^T A_i > c_i$. Define

   $$t_i \doteq \begin{cases} \infty,\, &\text{if }\, v^T A_i \ge 0, \\ \Big( (y^\star)^T A_i - c_i \Big) / \big| v^T A_i \big|,\, &\text{if }\, v^T A_i < 0, \\ \end{cases}$$

   Then $t_i > 0$ and it is guaranteed that

   $$(y^\star)^T A_i + t_i \cdot v \ge c_i.$$

   Denote $k \doteq \min_{i \in \bar S} t_i > 0$.

2. If $i \in S$, as $v^T A_i \ge 0$, for the value of $k$ defined above, it holds that

   $$(y^\star + k v)^T A_i = c_i + k v^T A_i \ge c_i,$$

It concludes that $(y^\star + k v)$ is feasible. But $(y^\star + k v)^T b < (y^\star)^T b$. A contradiction.

Question to ponder: connect the above discussion to Lagrange multiplier and K.K.T condition.

Reference.

1. David P. Williamson, ORIE 6300 Mathematical Programming I, Lecture 8
2. Boyd, S. and Vandenberghe, L., 2004. Convex optimization. Cambridge university press.