Theorem 2.2.1. Weak Duality Theorem for Linear Programming.
If a primal linear program in Standard Inequality Form and its dual both have at least one feasible point, then the value of the primal LP is at most the value of the dual.
Section 2.2 Equivalent Formulations and Weak Duality
In the Section 2.1, we approached linear programming from a geometric viewpoint. In contrast, in this section, we will present some basic algebraic manipulations for linear programs which can be useful for converting them from one form to another. As an application of this, we will show how one can use the “Standard Inequality Form” of a linear program to define an important concept known as the dual of a linear program. At the end of the section, we will prove the Weak Duality Theorem for linear programming.
Two of the most common forms of a linear program are the Standard Inequality and Standard Equality Forms (note that, in the literature, these are often called “Standard” and “Canonical” forms, but these names are used inconsistently). For \(x\in\mathbb{R}^n\text{,}\) we write \(x\geq0\) to mean that all entries of \(x\) are non-negative. The Standard Inequality Form of an LP is as follows:
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp Ax\leq b\\
\amp \amp x\geq 0
\end{align*}
where, as usual, \(A\in\mathbb{R}^{m\times n}\) (i.e. the set of all real \(m\times n\) matrices), \(b\in\mathbb{R}^m\) and \(c\in\mathbb{R}^n\text{.}\) The Standard Equality Form is as follows:
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp Ax= b\\
\amp \amp x\geq 0.
\end{align*}
In this section, we will deal with Standard Inequality Form more frequently than with Standard Equality Form, but it is worth being aware of both of them. In particular, Standard Equality Form is convenient in certain implementations of the Simplex Method discussed in Section 2.1.
A very useful observation is that any linear program is equivalent to a linear program in Standard Inequality or Standard Equality form. Here, we are using the term “equivalent” rather loosely, but it will hopefully be clear what we mean as we go along.
First, let us show that any LP is equivalent to an LP in Standard Inequality Form. Consider an LP of the form
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp Ax\leq b.
\end{align*}
Currently, this linear program may not have any constraints which ensure that the variables are non-negative. However, we can achieve this by replacing each variable \(x_j\) with two variables \(x_j^+\) and \(x_j^-\text{,}\) both of which are non-negative, such that \(x_j = x_j^+-x_j^-\text{.}\) By substituting \(x_j^+-x_j^-\) in for every instance of \(x_j\) and adding the constraint that all of our new variables are non-negative, we get a linear program which is equivalent to the original one with twice as many variables which is in Standard Inequality Form. Therefore, whenever dealing with linear programs, we can assume that they are in Standard Inequality Form if it is convenient to do so.
Similarly, any linear program is equivalent to one in Standard Equality Form. For this, suppose that we start with a linear program in Standard Inequality Form
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp Ax\leq b\\
\amp \amp x\geq 0
\end{align*}
and we want to convert it into Standard Equality Form. For this, we introduce \(m\) non-negative slack variables \(s_1,\dots,s_m\text{,}\) one for each constraint. We then replace the \(i\)th inequality constraint \(a_{i,1}x_1 +\cdots+a_{i,n}x_n\leq b_i\) with the equality constraint \(a_{i,1}x_1 +\cdots+a_{i,n}x_n+s_i= b_i\text{.}\) Since each slack variable is non-negative, the presence of the slack variables will ensure that the original inequalities are satisfied. So, any LP in Standard Inequality Form with \(n\) variables and \(m\) inequality constraints (not including the non-negativity constraints) can be converted into an LP in Standard Equality Form with \(n+m\) variables and \(m\) equality constraints. Since any LP can be converted into Standard Inequality Form as we saw above, we get that any LP can also be converted into Standard Equality Form.
Note also that it is possible to convert back from Standard Equality Form or Standard Inequality Form to the form max \(c^Tx\) subject to \(Ax\leq b\text{.}\) This is because each equality constraint in Standard Equality Form can be written as two inequality constraints to go from Standard Equality Form to Standard Inequality Form (doubling the number of constraints), and then each of the non-negativity constraints \(x_j\geq0\) can be written as \(-x_j\leq 0\) which adds \(n\) rows to the constraint matrix.
Subsection 2.2.1 The Dual of an LP
We are now ready to introduce the important concept of the dual of a linear program. Before doing so, let us go back to Example 2.1.1 from Section 2.1 and see how we can bound the value of this LP from below and above in an “algebraic” fashion. Of course, there is a very natural certificate for a lower bound. If we simply take a point \((x,y)\in \mathbb{R}^2\text{,}\) then one can easily check whether each of the constraints are satisfied by \((x,y)\) and compute the value of the objective function at that point. For example, if we take \((x,y)=(9/4,1/4)\text{,}\) then we can check that all of the constraints are satisfied and therefore the value of the LP is at least \(f(9/4,1/4)=17/4\text{.}\) So, we see that, in general, proving that the value of an LP satisfies a given lower bound is in NP because a feasible point yields a certificate which can be efficiently verified.
Now, what about proving an upper bound on the value of the LP in Example 2.1.1? Of course, as we saw in Section 2.1, this can be done by computing the value of the objective function at each of the vertices of the feasible region. However, the concept of duality will provide us with an alternative method for proving upper bounds which is purely algebraic (and very slick!). What we want to prove is that \(2x-y\leq 17/4\) for any choice of variables \((x,y)\) satisfying the constraints. A clever way to do this is to try to “combine” the constraints in such a way that it gives us an upper bound on the objective function. For example, suppose that we add together the constraints \(x+3y\leq 3\) and \(x-y\leq 2\) to get \(2x+2y\leq 5\text{.}\) Since we know that \(y\geq0\text{,}\) we get
\begin{equation*}
2x-y\leq 2x+2y\leq 5
\end{equation*}
which means that the value of the LP is at most 5. This is, of course, weaker than the bound of \(17/4\) that we wanted, but it demonstrates the principle that, by combining constraints in the right way, one can often get an upper bound on the objective function. To prove the best possible upper bound via this strategy, what we want to do is to multiply both sides of \(x+3y\leq 3\) by a non-negative number, say \(a\text{,}\) and both sides of \(x-y\leq 2\) by a non-negative number, say \(b\text{,}\) and add them together so that the following holds
\begin{equation*}
2x-y\leq a(x+3y) + b(x-y)\leq 3a + 2b
\end{equation*}
and, moreover, the quantity \(3a+2b\) is as small as possible. The second inequality holds simply because \(a\) and \(b\) are non-negative. For the first inequality to hold, it suffices to ensure that the coefficients of \(x\) and \(y\) in \(a(x+3y) + b(x-y) = (a+b)x + (3a-b)y\) are at least \(2\) and \(-1\) respectively since \(x,y\geq0\) (this explains why Standard Inequality Form is so useful). In other words, the best possible upper bound that we can prove via this approach is equal to the value of the following linear program in variables \(a\) and \(b\text{:}\)
\begin{align*}
\text{min } \amp \amp 3a+2b\\
\text{subject to } \amp \amp a+b\geq 2\\
\text{subject to } \amp \amp 3a-b\geq -1\\
\amp \amp a\geq 0\\
\amp \amp b\geq 0.
\end{align*}
This linear program turns out to be the dual of the LP in Example 2.1.1. A cool thing about the dual is that it gives us a “constructive” method for bounding the value of the original LP (called the primal LP in the context of duals) from above. That is, every feasible point for the dual gives us an upper bound for the primal. By plugging in \((a,b)=(1/4, 7/4)\text{,}\) one can check that all of the constraints of the dual are satisfied and the objective function \(3a+2b\) evaluates to \(17/4\text{.}\) Therefore, when combined with the lower bound proved earlier, this gives us another proof that the value of the LP in Example 2.1.1 is \(17/4\text{.}\)
Let us now define the dual of an LP in general. Given an LP
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp Ax\leq b\\
\amp \amp x\geq 0
\end{align*}
in Standard Inequality Form, the dual is a linear program in variables \(y_1,\dots,y_m\) defined by
\begin{align*}
\text{min } \amp \amp b^Ty\\
\text{subject to } \amp \amp A^Ty\geq c\\
\amp \amp y\geq 0
\end{align*}
where \(A^T\) denotes the transpose of the matrix \(A\text{.}\) As in Example 2.1.1, the value of the dual linear program is always an upper bound for the value of the primal; this is known as the Weak Duality Theorem. In fact, somewhat magically, the primal and dual actually have the same value. This is known as the Strong Duality Theorem and will be proved in Section 2.3.
Proof.
Consider a linear program in Standard Inequality Form with objective function \(c^Tx\) and constraints \(Ax\leq b\text{.}\) Suppose that \(x\) is feasible for the primal and \(y\) is feasible for the dual. Then, since \(c\leq A^Ty\) and all entries of \(x\) are non-negative, we have
\begin{equation*}
c^Tx \leq (A^Ty)^Tx.
\end{equation*}
By standard facts about multiplying matrices, the right side of this inequality can be manipulated as follows
\begin{equation*}
(A^Ty)^Tx = (y^TA)x = y^T(Ax).
\end{equation*}
Finally, we have that \(Ax\leq b\) and so, since all entries of \(y\) are non-negative, the right side can be bounded as follows
\begin{equation*}
y^T(Ax) \leq y^Tb = b^Ty.
\end{equation*}
So, \(c^Tx\leq b^Ty\) for every primal feasible \(x\) and every dual feasible \(y\) which completes the proof.
Here is a YouTube video related to this section:
