Chapter 8 Weak and Strong Duality
We’ll now prove several theorems relating the optimal objective values of the primal-dual pairs. As mentioned previously, these theorems generalize to non-linear programming and are important for analyzing the solution spaces for both linear and non-linear programs.
8.1 Weak Duality
Consider a standard linear program (primal) (2.1) and its dual (7.1). We say that a vector \(x\) is primal feasible if it is in the feasible region of the primal and a vector \(y\) is dual feasible if it is in the feasible region of the dual.
Theorem 8.1 (Weak Duality) Suppose \(x\) is primal feasible and \(y\) is dual feasible. Then the primal objective value at \(x\) is less than or equal to the dual objective value at \(y\).
Proof. The proof relies on analyzing the term \(y^T A x\) and follows from the following sequence of inequalities: \[\begin{align*} b^T y & = y^T b \\ & \ge y^T (Ax) && \mbox{ as } Ax \leq b \mbox{ and } y \geq 0 \\ & = (y^T A x)^T \\ & = x^T A^T y \\ & \ge x^T c && \mbox{ as } A^Ty \geq c \mbox{ and } x \geq 0 \\ & = c^T x. \end{align*}\]
We get several immediate corollaries from weak duality.
Corollary 8.1 If the primal is unbounded, then the dual is infeasible.
Corollary 8.2 If the dual is unbounded, then the primal is infeasible.
Corollary 8.3 If both the primal and dual have optimal solutions, then the optimal value of the primal is less than or equal to the optimal value of the dual.2
Note that all of these results are one-sided implications. We cannot say anything about the dual in the case when the primal is infeasible. Similarly, we cannot conclude anything about the existence of an optimal value of the dual in the case when the primal has an optimal solution.
Exercise 8.1 Using Weak Duality, what can you say about the dual if the primal is infeasible?
Exercise 8.2 Find primal-dual pairs of linear programs such that
- both the primal and dual are infeasible,
- the primal is infeasible and the dual is unbounded,
- the primal is unbounded and the dual is infeasible.
Can you have primal-dual pairs such that both the primal and the dual are unbounded?
8.2 Strong Duality
Weak duality asserts that the optimal objective value of the primal is always less that on equal to the optimal objective of the dual (if both exist). The proof of this statement was a simple manipulation of algebraic expressions. Strong duality further says that there is no duality gap i.e. if both the optimal objective values exist then they must be equal! The proof of this result is far more involved. Weak duality is easy to generalize to non-linear programs but the generalization of strong duality requires stronger proof techniques from convex analysis. For the case of linear programs, strong duality follows from an analysis of the simplex method!
The tableau of the primal problem (2.1) is as follows: \[\begin{equation} \begin{array}{ll|r} c^T & 0 & c_0 \\ \hline A & I_m & b \end{array} \tag{8.1} \end{equation}\] We can standardize the dual problem (7.1) and form its tableau: \[\begin{equation} \begin{array}{ll|r} -b^T & 0 & -c_0 \\ \hline -A^T & I_n & -c \end{array} \tag{8.2} \end{equation}\]
We will call such tableaux duals of each other. More generally, we’ll say that two tableaux (of appropriate dimensions) are duals of each other if after rearranging the pivot columns (if necessary) they’re of the above forms. The following theorem follows from explicit computations.
Lemma 8.1 Consider the two dual tableaux (8.1) and (8.2) . If we pivot the first tableau about the \(i^{th}\) row and \(j^{th}\) column of \(A\) and the second tableau about the \(i^{th}\) column and \(j^{th}\) row of \(-A^T\), then the resulting tableaux remain duals of each other.
Exercise 8.3 This exercise proves Lemma 8.1 in the case when \(n = 3\) and \(m = 2\). Consider the linear program: \[\begin{align*} \begin{array}{rrrrrrrrrrr} \mbox{maximize: } & c_1 x_1 & + & c_2 x_2 & + & c_3 x_3 \\ \mbox{subject to: } & a_{11} x_1 & + & a_{12} x_2 & + & a_{13} x_3 & \le & b_1 \\ & a_{21} x_1 & + & a_{22} x_2 & + & a_{23} x_3 & \le & b_2 \\ & x_1 & , & x_2 & , & x_3 & \ge & 0 \end{array} \end{align*}\]
- Form the primal and dual tableaux.
- Perform a pivot about the entry \(a_{12}\) in the primal tableau (assume that \(a_{12} \neq 0\)) and the corresponding entry in the dual tableau.
In the end, you should see that the two resulting tableaux are still dual to each other. The same calculation works in full generality for an arbitrary linear program as we never used the fact that \(n = 3\) and \(m = 2\).
Lemma 8.2 If the tableau (8.1) corresponds to an optimal solution of the primal then the tableau (8.2) corresponds to an optimal solution of the dual.
Proof. The tableau (8.1) corresponds to an optimal solution of the primal precisely when
- (primal-optimality) \(c^T \le 0\) as in this case no entering variable can be found for the primal, and
- (primal-feasibility) \(b \ge 0\).
These conditions translate to
- (dual-optimality) \(-b^T \le 0\) as in this case no entering variable can be found for the dual, and
- (dual-feasibility) \(-c \ge 0\).
Note the interesting fact that the condition for primal-optimality translates to dual-feasibility and the condition for primal-feasibility translates to dual-optimality.
Theorem 8.2 (Strong duality) If the primal has an optimal solution then so does the dual. Moreover, they have the same optimal values.3
Proof. By weak duality, it suffices to show that there is some dual-feasible solution which has the same objective value as a optimal objective value of the primal. This dual-feasible solution will be dual-optimal by Corollary 8.3.
At the optimal solution for the primal, we have a set of basic and non-basic variables. We can perform a sequence of pivot operations to get this tableau from the initial tableau. We then perform the corresponding pivots on the dual tableau. By Lemma 8.1 the resulting tableau will be dual to the primal tableau at the optimal solution. By Lemma 8.2 the dual is also optimal and has the same objective value.
Remark. Strong duality establishes as one-to-one correspondence between the primal optimal BFS and dual optimal BFS. At every primal-optimal BFS there is a unique corresponding dual-optimal BFS obtained by dualizing the tableau. This is by no means the only dual-optimal solution, but rather the dual-optimal solution dual to a particular primal-optimal BFS.
8.3 Certificate of Optimality
We can use the two duality theorems to come up with a fast way to verify optimality.
Theorem 8.3 (Certificate of optimality) \(x\) is an optimal solution for the primal and \(y\) is an optimal solution for the dual if and only if
- \(x\) is primal-feasible,
- \(y\) is dual-feasible,
- \(c^T x = b^T y\) i.e. the primal objective value at \(x\) is equal to the dual objective value at \(y\).
Proof. ( \(\Rightarrow\) )
If \(x\) and \(y\) are optimal solutions, then they are feasible by definition. By strong duality (Theorem 8.2) they must the same objective value.
( \(\Leftarrow\) )
If \(x\) and \(y\) are feasible solutions then by weak duality (Theorem 8.1) the dual objective values provide an upper bound on the primal objective value. Because this upper bound is attained at \(x\), it must be an optimal solution of the primal. Similarly, for \(y\).
8.3.1 Complimentary slackness
There is another closely related method for verifying the correctness of solution that uses primal and dual slack variables instead of primal and dual objective values.
Denote by \(w = \begin{bmatrix} w_1 \\ \vdots \\ w_m \end{bmatrix}\) the primal slack variables and by \(z = \begin{bmatrix} v_1 \\ \vdots \\ v_n \end{bmatrix}\) the dual slack variables. More explicitly, let \[\begin{align*} w &= b - A x \\ z &= -c + A^T y. \end{align*}\] We use this convention for \(z\) to ensure that at a dual feasible solution \(z \ge 0\).
Theorem 8.4 (Complementary slackness) Suppose \(x\) is primal feasible and \(y\) is dual feasible. Then \(x\) and \(y\) are optimal if and only if
- for all \(1 \le j \le n\), \(x_j z_j = 0\), and
- for all \(1 \le i \le m\), \(y_i w_i = 0\).
Proof. The proof is in two steps. We first show a weaker statement about the vanishing of two scalars and then show that the vanishing of these scalars implies complementary slackness.
Claim 1: \(x\) and \(y\) are optimal solutions if and only if \(x^T z = 0\) and \(y^T w = 0\).
We start by expanding out the slack variables: \[\begin{align*} && x^T z = 0 && \mbox{ and } && y^T w = 0 \\ \Leftrightarrow && x^T (-c + A^T y) = 0 && \mbox{ and } && y^T (b - A x) = 0 \\ \Leftrightarrow && x^T c = x^T A^T y && \mbox{ and } && y^T b = y^T A x \\ \Leftrightarrow && c^T x = y^T A x && \mbox{ and } && b^T y = y^T A x \end{align*}\] We have reduced the problem to showing that \(x\) and \(y\) are optimal solutions if and only if \(c^T x = y^T A x\) and \(b^T y = y^T A x\).
( \(\Leftarrow\) ) As \(c^T x = y^T A x = b^T y\), and \(x\) and \(y\) are given to be feasible, \(x\) and \(y\) are optimal by Theorem 8.3.
( \(\Rightarrow\) ) By the proof of weak duality 8.1, we know that, \[c^T x \le y^T A x \le b^T y.\] By strong duality, as \(x\) and \(y\) are optimal \[c^T x = b^T y.\] The only way the two can be simultaneously true is if \(c^T x = y^T A x\) and \(b^T y = y^T A x\). This completes the proof of Claim 1.
Claim 2: \(x^T z = 0\) and \(y^T w = 0\) if and only if
- for all \(1 \le j \le n\), \(x_j z_j = 0\), and
- for all \(1 \le i \le m\), \(y_i w_i = 0\).
This follows from the fact that at a feasible solution \(x, y, w, z \ge 0\).
Remark. Complementary slackness as stated in Theorem 8.4 holds true even for general linear programs. The definition of slack variables, \[\begin{align*} w &= b - A x \\ z &= -c + A^T y. \end{align*}\] ensures that we will have \(x_j w_j \ge 0\) for all \(1 \le j \le n\) and \(y_i z_i \ge 0\) for all \(1 \le i \le m\) and hence the above proof is still valid.
If the optimal solution of the primal is at a non-degenerate BFS, then complementary slackness can be used to find the optimal solution to the dual without having to run the simplex method on it. At a non-degenerate BFS, the basic variables are non-zero. By complementary slackness, the corresponding dual variables must be 0. This gives us a system of \(m\) variables in \(m\) equations which can be solved to find the dual optimal solution.
Example 8.1 Consider the linear program (1.2) whose dual is (7.2). At the optimal solution \(x_1 = 0.6\), \(x_2 = 0.3\), \(w_1 = 0\), \(w_2 = 0\), and \(w_3 = 0.1\). By complementary slackness, we must have \(z_1 = 0\), \(z_2 = 0\), and \(y_3 = 0\) at the dual optimal solution. Plugging these in (7.2), we get a system of equations \[\begin{align*} 3y_1 + 2y_2 &= 4 \\ 6y_1 + y_2 &= 3 \end{align*}\] whose solutions are \(y_1 = 2/9\) and \(y_2 = 5/3\). One can check that this is indeed dual optimal by comparing the dual objective at this point to the primal objective value: \[\begin{align*} 3.6 (2/9) + 1.5 (5/3) + 0 (1) = 3.3 = 4 (0.6) + 3 (0.3). \end{align*}\]
Exercise 8.4 We can use complementary slackness and certificate of optimality to show that the optimal solution of a standard linear program can never be attained in the interior of the feasible region.
Consider the standard linear program (2.1) and assume that \(b \ge 0\) and \(c \neq \vec{0}\). Let \(x^*\) be a point in the interior of the feasible region. Suppose \(x^*\) is an optimal solution to the primal. By strong duality, we know that a dual-optimal solution \(y^*\) exists. We’ll show that this leads to a contradiction.
- What can you say about the values of the decision and slack variables at \(x^*\)?
- What can you say about the values of the dual decision variables at \(y^*\) using complementary slackness?
We now consider two cases, depending on the sign of \(c\), and in each case show that \(y^*\) cannot be optimal.
- Suppose that \(c_j > 0\) for some \(0 \le j \le n\). Explain why \(y^*\) cannot be dual-feasible (and hence optimal).
- Suppose \(c \le 0\).
- What can you say about the objective values at \(x^*\) and \(y^*\)?
- Explain why \(y^*\) cannot be dual-optimal.