4.5. The Dual of a Non-Canonical LP

We defined the dual of an LP in canonical form, a maximization LP

\[\begin{gathered} \text{Maximize } cx\\ \begin{aligned} \text{s.t. }Ax &\le b\\ x &\ge 0, \end{aligned} \end{gathered}\tag{4.17}\]

as the minimization LP

\[\begin{gathered} \text{Minimize } b^Ty\\ \begin{aligned} \text{s.t. }A^Ty &\ge c^T\\ y &\ge 0. \end{aligned} \end{gathered}\tag{4.18}\]

What if the LP is not in canonical form? Can we still easily define its dual?

Let's start with a warm-up exercise. Every mathematician expects any duality construction to be its own inverse: If we take the dual of the dual, we should get back the primal. LP duality meets this expectation:

Observe that the dual LP (4.18) can easily be converted into canonical form by negating the objective function and all constraints:

\[\begin{gathered} \text{Maximize } {-}b^Ty\\ \begin{aligned} \text{s.t. }{-}A^Ty &\le {-}c^T\\ y &\ge 0. \end{aligned} \end{gathered}\]

The dual of this LP is

\[\begin{gathered} \text{Minimize } {-}cx\\ \begin{aligned} \text{s.t. }{-}Ax &\ge {-}b\\ x &\ge 0. \end{aligned} \end{gathered}\]

But that's just our primal (4.17) written as a minimization LP via negation. So the dual of a maximization LP is a minimization LP, the dual of a minimization LP is a maximization LP, and LP duality is well-behaved: The dual of the dual of an LP is just the original LP.

Next let us tackle the problem of constructing the dual of an arbitrary maximization LP. We can partition its constraints into three groups: upper bound constraints, lower bound constraints, and equality constraints. We can also partition its variables into three groups: non-negative variables, non-positive variables, and completely unconstrained variables. Thus, a general maximization LP can be written like this:

\[\begin{gathered} \text{Maximize } c_1x_+ + c_2x_- + c_3x_{\pm}\\ \begin{aligned} \text{s.t. }A_1x_+ + A_2x_- + A_3x_{\pm} &\le b_1\\ A_4x_+ + A_5x_- + A_6x_{\pm} &\ge b_2\\ A_7x_+ + A_8x_- + A_9x_{\pm} &= b_3\\ x_+ &\ge 0\\ x_- &\le 0. \end{aligned} \end{gathered}\tag{4.19}\]

Note that \(c_1, c_2, c_3\) are row vectors and \(b_1, b_2, b_3, x_+, x_-, x_{\pm}\) are column vectors, not numbers.

The canonical form of (4.19) is

\[\begin{gathered} \text{Maximize } c_1x_+ - c_2x_-' + c_3x_{\pm}' - c_3x_{\pm}''\\ \begin{aligned} \text{s.t. }A_1x_+ - A_2x_-' + A_3x_{\pm}' - A_3x_{\pm}'' &\le \phantom{-}b_1\\ -A_4x_+ + A_5x_-' - A_6x_{\pm}' + A_6x_{\pm}'' &\le -b_2\\ A_7x_+ - A_8x_-' + A_9x_{\pm}' - A_9x_{\pm}'' &\le \phantom{-}b_3\\ -A_7x_+ + A_8x_-' - A_9x_{\pm}' + A_9x_{\pm}'' &\le -b_3\\ x_+, x_-', x_{\pm}', x_{\pm}'' &\ge 0. \end{aligned} \end{gathered}\]

Here, \(x_-' = -x_-\) and \(x_{\pm}' - x_{\pm}'' = x_{\pm}\).

The dual of this LP is

\[\begin{gathered} \text{Minimize } b_1^Ty_+ - b_2^Ty_-' + b_3^Ty_{\pm}' - b_3^Ty_{\pm}''\\ \begin{aligned} \text{s.t. }A_1^Ty_+ - A_4^Ty_-' + A_7^Ty_{\pm}' - A_7^Ty_{\pm}'' &\ge \phantom{-}c_1^T\\ -A_2^Ty_+ + A_5^Ty_-' - A_8^Ty_{\pm}' + A_8^Ty_{\pm}'' &\ge -c_2^T\\ A_3^Ty_+ - A_6^Ty_-' + A_9^Ty_{\pm}' - A_9^Ty_{\pm}'' &\ge \phantom{-}c_3^T\\ -A_3^Ty_+ + A_6^Ty_-' - A_9^Ty_{\pm}' + A_9^Ty_{\pm}'' &\ge -c_3^T\\ y_+, y_-', y_{\pm}', y_{\pm}'' &\ge 0. \end{aligned} \end{gathered}\tag{4.20}\]

Here, \(y_+\) is the vector of dual variables corresponding to the original upper bound constraints, \(y_-'\) is the vector of dual variables corresponding to the original lower bound constraints, \(y_{\pm}'\) is the vector of dual variables corresponding to the upper bound constraints derived from the equality constraints, and \(y_{\pm}''\) is the vector of dual variables corresponding to the lower bound constraints derived from the equality constraints.

Here comes the cool part. First, we can flip the signs of the second and last groups of constraints in (4.20):

\[\begin{gathered} \text{Minimize } b_1^Ty_+ - b_2^Ty_-' + b_3^Ty_{\pm}' - b_3^Ty_{\pm}''\\ \begin{aligned} \text{s.t. }A_1^Ty_+ - A_4^Ty_-' + A_7^Ty_{\pm}' - A_7^Ty_{\pm}'' &\ge c_1^T\\ A_2^Ty_+ - A_5^Ty_-' + A_8^Ty_{\pm}' - A_8^Ty_{\pm}'' &\le c_2^T\\ A_3^Ty_+ - A_6^Ty_-' + A_9^Ty_{\pm}' - A_9^Ty_{\pm}'' &\ge c_3^T\\ A_3^Ty_+ - A_6^Ty_-' + A_9^Ty_{\pm}' - A_9^Ty_{\pm}'' &\le c_3^T\\ y_+, y_-', y_{\pm}', y_{\pm}'' &\ge 0. \end{aligned} \end{gathered}\]

This LP is equivalent to:

\[\begin{gathered} \text{Minimize } b_1^Ty_+ - b_2^Ty_-' + b_3^Ty_{\pm}' - b_3^Ty_{\pm}''\\ \begin{aligned} \text{s.t. }A_1^Ty_+ - A_4^Ty_-' + A_7^Ty_{\pm}' - A_7^Ty_{\pm}'' &\ge c_1^T\\ A_2^Ty_+ - A_5^Ty_-' + A_8^Ty_{\pm}' - A_8^Ty_{\pm}'' &\le c_2^T\\ A_3^Ty_+ - A_6^Ty_-' + A_9^Ty_{\pm}' - A_9^Ty_{\pm}'' &= c_3^T\\ y_+, y_-', y_{\pm}', y_{\pm}'' &\ge 0. \end{aligned} \end{gathered}\]

Second, we can replace every occurrence of \(y_{\pm}' - y_{\pm}''\) in the objective function and in any constraint with \(y_{\pm} = y_{\pm}' - y_{\pm}''\). While \(y_{\pm}', y_{\pm}'' \ge 0\), \(y_{\pm}\) is unconstrained: Any value we assign to \(y_{\pm}\) can be written as the difference of two non-negative vectors assigned to \(y_{\pm}'\) and \(y_{\pm}''\). We can also replace every occurrence of \(y_-'\) with \(-y_- = y_-'\). Since \(y_-' \ge 0\), we have \(y_- \le 0\). This gives our final dual LP:

\[\begin{gathered} \text{Minimize } b_1^Ty_+ + b_2^Ty_- + b_3^Ty_{\pm}\\ \begin{aligned} \text{s.t. }A_1^Ty_+ + A_4^Ty_- + A_7^Ty_{\pm} &\ge c_1^T\\ A_2^Ty_+ + A_5^Ty_- + A_8^Ty_{\pm} &\le c_2^T\\ A_3^Ty_+ + A_6^Ty_- + A_9^Ty_{\pm} &= c_3^T\\ y_+ &\ge 0\\ y_- &\le 0. \end{aligned} \end{gathered}\tag{4.21}\]

If you refer back to the primal LP (GP) that we started with, you can observe that, just as in the dual of an LP in canonical form, the coefficients of the dual objective function are the right-hand sides of the primal constraints, the right-hand sides of the dual constraints are the coefficients of the primal objective function, and the matrix of coefficients in the dual constraints is the transpose of the matrix of coefficients in the primal constraints. What differs is that some dual variables are now constrained to be non-positive or completely unconstrained, and some constraints are upper bound constraints or equality constraints instead of lower bound constraints. By looking at (4.19) and (4.21), we can easily discern the rules that govern which constraint should be an upper bound, lower bound or equality constraint:

• The dual constraint corresponding to any non-negative primal variable is a lower bound constraint (the constraints corresponding to variables \(x_+\) in our example).

• The dual constraint corresponding to any non-positive primal variable is an upper bound constraint (the constraints corresponding to variables \(x_-\) in our example).

• The dual constraint corresponding to any unconstrained primal variable is an equality constraint (the constraints corresponding to variables \(x_{\pm}\) in our example).

Similarly, our example tells us which dual variables are non-negative, non-positive or unconstrained:

• Every dual variable corresponding to an upper bound constraint in the primal is non-negative (the vector \(y_+\) in our example).

• Every dual variable corresponding to a lower bound constraint in the primal is non-positive (the vector \(y_-\) in our example).

• Every dual variable corresponding to an equality constraint in the primal is unconstrained (the vector \(y_{\pm}\) in our example).

These rules apply when the primal is a maximization LP and, consequently, the dual is a minimization LP. We observed before that

• The dual of a maximization LP is a minimization LP and the dual of a minimization LP is a maximization LP.

If the primal is a minimization LP and we convert it into a dual that is a maximization LP, the rules above are reversed: Unconstrained primal variables still translate into equality constraints in the dual and equality constraints in the primal still translate into unconstrained dual variables. However, upper bound and lower bound constraints in the primal now translate into non-positive and non-negative dual variables, respectively, and non-negative and non-positive primal variables now translate into upper bound and lower bound constraints in the dual, respectively.

As an exercise, you should verify that these rules ensure that once again, the dual of the dual of an arbitrary LP is the original LP.