Dual linear program

Constructing the dual LP

In general, given a primal LP, the following algorithm can be used to construct its dual LP. The primal LP is defined by:

• A set of n variables: ${\displaystyle x_1,\dots ,x_n}$.
• For each variable ${\displaystyle x_i}$, a sign constraint – it should be either non-negative (${\displaystyle x_i\ge 0}$), or non-positive (${\displaystyle x_i\le 0}$), or unconstrained (${\displaystyle x_i\in \mathbb{R}}$).
• An objective function: ${\displaystyle \text{maximize}{c}_1{x}_1+\cdots +c_n{x}_n}$
• A list of m constraints. Each constraint j is: ${\displaystyle a_{j1}{x}_1+\cdots +a_{jn}{x}_n⪋b_j}$where the symbol before the ${\displaystyle b_j}$ can be one of ${\displaystyle \ge }$ or ${\displaystyle \le }$ or ${\displaystyle =}$.

The dual LP is constructed as follows.

• Each primal constraint becomes a dual variable. So there are m variables: ${\displaystyle y_1,\dots ,y_m}$.
• The sign constraint of each dual variable is "opposite" to the sign of its primal constraint. So "${\displaystyle \ge b_j}$" becomes ${\displaystyle y_j\le 0}$ and "${\displaystyle \le b_j}$" becomes ${\displaystyle y_j\ge 0}$ and "${\displaystyle =b_j}$" becomes ${\displaystyle y_j\in \mathbb{R}}$.
• The dual objective function is ${\displaystyle \text{minimize }{b}_1{y}_1+\cdots +b_m{y}_m}$
• Each primal variable becomes a dual constraint. So there are n constraints. The coefficient of a dual variable in the dual constraint is the coefficient of its primal variable in its primal constraint. So each constraint i is: ${\displaystyle a_{1i}{y}_1+\cdots +a_{mi}{y}_m⪋c_i}$, where the symbol before the ${\displaystyle c_i}$ is similar to the sign constraint on variable i in the primal LP. So ${\displaystyle x_i\le 0}$ becomes "${\displaystyle \le c_i}$" and ${\displaystyle x_i\ge 0}$ becomes "${\displaystyle \ge c_i}$" and ${\displaystyle x_i\in \mathbb{R}}$ becomes "${\displaystyle =c_i}$".

From this algorithm, it is easy to see that the dual of the dual is the primal.

Vector formulations

If all constraints have the same sign, it is possible to present the above recipe in a shorter way using matrices and vectors. The following table shows the relation between various kinds of primals and duals.

The duality theorems

Below, suppose the primal LP is "maximize c^Tx subject to [constraints]" and the dual LP is "minimize b^Ty subject to [constraints]".

Weak duality

The weak duality theorem says that, for each feasible solution x of the primal and each feasible solution y of the dual: c^Tx ≤ b^Ty. In other words, the objective value in each feasible solution of the dual is an upper-bound on the objective value of the primal, and objective value in each feasible solution of the primal is a lower-bound on the objective value of the dual. Here is a proof for the primal LP "Maximize c^Tx subject to Ax ≤ b, x ≥ 0":

• c^Tx
• = x^Tc [since this just a scalar product of the two vectors]
• ≤ x^T(A^Ty) [since A^Ty ≥ c by the dual constraints, and x ≥ 0]
• = (x^TA^T)y [by associativity]
• = (Ax)^Ty [by properties of transpose]
• ≤ b^Ty [since Ax ≤ b by the primal constraints, and y ≥ 0]

Weak duality implies:

max_x c^Tx ≤ min_y b^Ty

In particular, if the primal is unbounded (from above) then the dual has no feasible solution, and if the dual is unbounded (from below) then the primal has no feasible solution.

Strong duality

The strong duality theorem says that if one of the two problems has an optimal solution, so does the other one and that the bounds given by the weak duality theorem are tight, i.e.:

max_x c^Tx = min_y b^Ty

The strong duality theorem is harder to prove; the proofs usually use the weak duality theorem as a sub-routine.

One proof uses the simplex algorithm and relies on the proof that, with the suitable pivot rule, it provides a correct solution. The proof establishes that, once the simplex algorithm finishes with a solution to the primal LP, it is possible to read from the final tableau, a solution to the dual LP. So, by running the simplex algorithm, we obtain solutions to both the primal and the dual simultaneously.

Another proof uses the Farkas lemma.

Theoretical implications

1. The weak duality theorem implies that finding a single feasible solution is as hard as finding an optimal feasible solution. Suppose we have an oracle that, given an LP, finds an arbitrary feasible solution (if one exists). Given the LP "Maximize c^Tx subject to Ax ≤ b, x ≥ 0", we can construct another LP by combining this LP with its dual. The combined LP has both x and y as variables:

Maximize 1

subject to Ax ≤ b, A^Ty ≥ c, c^Tx ≥ b^Ty, x ≥ 0, y ≥ 0

If the combined LP has a feasible solution (x,y), then by weak duality, c^Tx = b^Ty. So x must be a maximal solution of the primal LP and y must be a minimal solution of the dual LP. If the combined LP has no feasible solution, then the primal LP has no feasible solution either.

2. The strong duality theorem provides a "good characterization" of the optimal value of an LP in that it allows us to easily prove that some value t is the optimum of some LP. The proof proceeds in two steps:

• Show a feasible solution to the primal LP with value t; this proves that the optimum is at least t.
• Show a feasible solution to the dual LP with value t; this proves that the optimum is at most t.

Examples

Tiny example

Consider the primal LP, with two variables and one constraint:

${\displaystyle \begin{array}{cc}\text{maximize }& 3x_1+4x_2\\ \text{subject to }& 5x_1+6x_2=7\\ & x_1\ge 0,x_2\ge 0\end{array}}$

Applying the recipe above gives the following dual LP, with one variable and two constraints:

${\displaystyle \begin{array}{cc}\text{minimize }& 7y_1\\ \text{subject to }& 5y_1\ge 3\\ & 6y_1\ge 4\\ & y_1\in \mathbb{R}\end{array}}$

It is easy to see that the maximum of the primal LP is attained when x₁ is minimized to its lower bound (0) and x₂ is maximized to its upper bound under the constraint (7/6). The maximum is 4 ⋅ 7/6 = 14/3.

Similarly, the minimum of the dual LP is attained when y₁ is minimized to its lower bound under the constraints: the first constraint gives a lower bound of 3/5 while the second constraint gives a stricter lower bound of 4/6, so the actual lower bound is 4/6 and the minimum is 7 ⋅ 4/6 = 14/3.

In accordance with the strong duality theorem, the maximum of the primal equals the minimum of the dual.

We use this example to illustrate the proof of the weak duality theorem. Suppose that, in the primal LP, we want to get an upper bound on the objective ${\displaystyle 3x_1+4x_2}$. We can use the constraint multiplied by some coefficient, say ${\displaystyle y_1}$. For any ${\displaystyle y_1}$ we get: ${\displaystyle y_1\cdot (5x_1+6x_2)=7y_1}$. Now, if ${\displaystyle y_1\cdot 5x_1\ge 3x_1}$and ${\displaystyle y_1\cdot 6x_2\ge 4x_2}$, then ${\displaystyle y_1\cdot (5x_1+6x_2)\ge 3x_1+4x_2}$, so ${\displaystyle 7y_1\ge 3x_1+4x_2}$. Hence, the objective of the dual LP is an upper bound on the objective of the primal LP.

Farmer example

Consider a farmer who may grow wheat and barley with the set provision of some L land, F fertilizer and P pesticide. To grow one unit of wheat, one unit of land, ${\displaystyle F_1}$ units of fertilizer and ${\displaystyle P_1}$ units of pesticide must be used. Similarly, to grow one unit of barley, one unit of land, ${\displaystyle F_2}$ units of fertilizer and ${\displaystyle P_2}$ units of pesticide must be used.

The primal problem would be the farmer deciding how much wheat (${\displaystyle x_1}$) and barley (${\displaystyle x_2}$) to grow if their sell prices are ${\displaystyle S_1}$ and ${\displaystyle S_2}$ per unit.

In matrix form this becomes:

Maximize: ${\displaystyle \left[\begin{array}{cc}{S}_1& S_2\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]}$

subject to: ${\displaystyle \left[\begin{array}{cc}1& 1\\ F_1& F_2\\ P_1& P_2\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\le \left[\begin{array}{c}L\\ F\\ P\end{array}\right],\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\ge 0.}$

For the dual problem assume that y unit prices for each of these means of production (inputs) are set by a planning board. The planning board's job is to minimize the total cost of procuring the set amounts of inputs while providing the farmer with a floor on the unit price of each of his crops (outputs), S₁ for wheat and S₂ for barley. This corresponds to the following LP:

In matrix form this becomes:

Minimize: ${\displaystyle \left[\begin{array}{ccc}L& F& P\end{array}\right]\left[\begin{array}{c}{y}_L\\ y_F\\ y_P\end{array}\right]}$

subject to: ${\displaystyle \left[\begin{array}{ccc}1& F_1& P_1\\ 1& F_2& P_2\end{array}\right]\left[\begin{array}{c}{y}_L\\ y_F\\ y_P\end{array}\right]\ge \left[\begin{array}{c}{S}_1\\ S_2\end{array}\right],\left[\begin{array}{c}{y}_L\\ y_F\\ y_P\end{array}\right]\ge 0.}$

The primal problem deals with physical quantities. With all inputs available in limited quantities, and assuming the unit prices of all outputs is known, what quantities of outputs to produce so as to maximize total revenue? The dual problem deals with economic values. With floor guarantees on all output unit prices, and assuming the available quantity of all inputs is known, what input unit pricing scheme to set so as to minimize total expenditure?

To each variable in the primal space corresponds an inequality to satisfy in the dual space, both indexed by output type. To each inequality to satisfy in the primal space corresponds a variable in the dual space, both indexed by input type.

The coefficients that bound the inequalities in the primal space are used to compute the objective in the dual space, input quantities in this example. The coefficients used to compute the objective in the primal space bound the inequalities in the dual space, output unit prices in this example.

Both the primal and the dual problems make use of the same matrix. In the primal space, this matrix expresses the consumption of physical quantities of inputs necessary to produce set quantities of outputs. In the dual space, it expresses the creation of the economic values associated with the outputs from set input unit prices.

Since each inequality can be replaced by an equality and a slack variable, this means each primal variable corresponds to a dual slack variable, and each dual variable corresponds to a primal slack variable. This relation allows us to speak about complementary slackness.

Infeasible program

A LP can also be unbounded or infeasible. Duality theory tells us that:

• If the primal is unbounded, then the dual is infeasible;
• If the dual is unbounded, then the primal is infeasible.

However, it is possible for both the dual and the primal to be infeasible. Here is an example:

Viewing the solution to a linear programming problem as a (generalized) eigenvector

There is a close connection between linear programming problems, eigenequations, and von Neumann's general equilibrium model. The solution to a linear programming problem can be regarded as a generalized eigenvector.

The eigenequations of a square matrix are as follows:

${\displaystyle \begin{array}{c}{\mathbf{p}}^T\mathbf{A}=\rho {\mathbf{p}}^T\\ \mathbf{A}\mathbf{z}=\rho \mathbf{z}\end{array}}$

where ${\displaystyle {\mathbf{p}}^T}$ and ${\displaystyle \mathbf{z}}$ are the left and right eigenvectors of the square matrix ${\displaystyle \mathbf{A}}$, respectively, and ${\displaystyle \rho }$ is the eigenvalue.

The above eigenequations for the square matrix can be extended to von Neumann's general equilibrium model:

${\displaystyle \begin{array}{c}{\mathbf{p}}^T\mathbf{A}\ge \rho {\mathbf{p}}^T\mathbf{B}\\ \mathbf{A}\mathbf{z}\le \rho \mathbf{B}\mathbf{z}\end{array}}$

where the economic meanings of ${\displaystyle \mathbf{p}}$ and ${\displaystyle \mathbf{z}}$ are the equilibrium prices of various goods and the equilibrium activity levels of various economic agents, respectively.

The von Neumann's equilibrium model can be further extended to the following structural equilibrium model with ${\displaystyle \mathbf{A}}$ and ${\displaystyle \mathbf{B}}$ as matrix-valued functions:

${\displaystyle \begin{array}{c}{\mathbf{p}}^T\mathbf{A}(\mathbf{p},\mathbf{u},\mathbf{z})\ge \rho {\mathbf{p}}^T\mathbf{B}(\mathbf{p},\mathbf{u},\mathbf{z})\\ \mathbf{A}(\mathbf{p},\mathbf{u},\mathbf{z})\mathbf{z}\le \rho \mathbf{B}(\mathbf{p},\mathbf{u},\mathbf{z})\mathbf{z}\end{array}}$

where the economic meaning of ${\displaystyle \mathbf{u}}$ is the utility levels of various consumers. A special case of the above model is

${\displaystyle \begin{array}{c}{\mathbf{p}}^T\mathbf{A}(u)\ge {\mathbf{p}}^T\mathbf{B}\\ \mathbf{A}(u)\mathbf{z}\le \mathbf{B}\mathbf{z}\end{array}}$

This form of the structural equilibrium model and linear programming problems can often be converted to each other, that is, the solutions to these two types of problems are often consistent.

If we define ${\displaystyle \mathbf{A}(u)=\left[\begin{array}{cc}\mathbf{0}& u\\ \mathbf{A}& \mathbf{0}\end{array}\right]}$, ${\displaystyle \mathbf{B}=\left[\begin{array}{cc}{\mathbf{c}}^T& 0\\ \mathbf{0}& \mathbf{b}\end{array}\right]}$, ${\displaystyle \mathbf{p}=\left[\begin{array}{c}1\\ \mathbf{y}\end{array}\right]}$, ${\displaystyle \mathbf{z}=\left[\begin{array}{c}\mathbf{x}\\ 1\end{array}\right]}$, then the structural equilibrium model can be written as

${\displaystyle \left[\begin{array}{cc}{\mathbf{y}}^T\mathbf{A}& u\end{array}\right]\ge \left[\begin{array}{cc}{\mathbf{c}}^T& {\mathbf{y}}^T\mathbf{b}\end{array}\right]}$

${\displaystyle \left[\begin{array}{c}u\\ \mathbf{A}\mathbf{x}\end{array}\right]\le \left[\begin{array}{c}{\mathbf{c}}^T\mathbf{x}\\ \mathbf{b}\end{array}\right]}$

Let us illustrate the structural equilibrium model with the previously discussed tiny example. In this example, we have ${\displaystyle \mathbf{A}=\left[\begin{array}{cc}5& 6\end{array}\right]}$, ${\displaystyle \mathbf{A}(u)=\left[\begin{array}{ccc}0& 0& u\\ 5& 6& 0\end{array}\right]}$ and ${\displaystyle \mathbf{B}=\left[\begin{array}{ccc}3& 4& 0\\ 0& 0& 7\end{array}\right]}$.

To solve the structural equilibrium model, we obtain

${\displaystyle {\mathbf{p}}^{\ast }=(1,2/3{)}^T,{\mathbf{z}}^{\ast }=(0,7/6,1{)}^T,u^{\ast }=14/3}$

These are consistent with the solutions to the linear programming problems.

We substitute the above calculation results into the structural equilibrium model, obtaining ${\displaystyle \begin{array}{c}{\mathbf{p}}^T\mathbf{A}(u)=(10/3,4,14/3)\ge (3,4,14/3)={\mathbf{p}}^T\mathbf{B}\\ \mathbf{A}(u)\mathbf{z}=(14/3,7{)}^T\le (14/3,7{)}^T=\mathbf{B}\mathbf{z}\end{array}}$

Applications

The max-flow min-cut theorem is a special case of the strong duality theorem: flow-maximization is the primal LP, and cut-minimization is the dual LP. See Max-flow min-cut theorem#Linear program formulation.

Other graph-related theorems can be proved using the strong duality theorem, in particular, Konig's theorem.

The Minimax theorem for zero-sum games can be proved using the strong-duality theorem.

Alternative algorithm

Sometimes, one may find it more intuitive to obtain the dual program without looking at the program matrix. Consider the following linear program:

We have m + n conditions and all variables are non-negative. We shall define m + n dual variables: y_j and s_i. We get:

Since this is a minimization problem, we would like to obtain a dual program that is a lower bound of the primal. In other words, we would like the sum of all right hand side of the constraints to be the maximal under the condition that for each primal variable the sum of its coefficients do not exceed its coefficient in the linear function. For example, x₁ appears in n + 1 constraints. If we sum its constraints' coefficients we get a_1,1y₁ + a_1,2y₂ + ... + a_1,;;n;;y_n + f₁s₁. This sum must be at most c₁. As a result, we get:

Note that we assume in our calculations steps that the program is in standard form. However, any linear program may be transformed to standard form and it is therefore not a limiting factor.