Discovering the mirror of linear optimization, the fascinating world of duality

Have you ever felt that a problem has two sides? In the world of mathematics and optimization, this is not just a feeling: it is the theory of duality. Duality is one of the most surprising results in linear optimization: every problem has a mathematical mirror that produces the same optimal value, but from a completely different perspective.

Origin

The theory of duality emerged from conversations between two brilliant minds: George Dantzig and John von Neumann. Together they discovered that every linear optimization problem, which we call the Primal, has a mathematical “twin” called the Dual.

Game theory and linear optimization: rock, paper, scissors

To understand duality, nothing is better than a game we all know. Rock, Paper, Scissors is a zero-sum game, which means that whatever one player wins, the other loses. The basis of the game is the payoff matrix, which represents the outcomes for Player I (by rows):

If we want to find the optimal strategy using linear optimization, let us consider both players:

• Player I (Primal): seeks to maximize their minimum gain (maximin strategy) by defining the probability of choosing each option:

\[\begin{aligned} \max\;\; & \min\{x_2-x_3, -x_1+x_3,x_1-x_2\} \\ \textrm{s. t.:}\;\; & x_1 + x_2 + x_3 = 1 \\ & x_1, x_2, x_3 \geqslant 0 \end{aligned}\]

We introduce a variable $z$ representing the guaranteed minimum gain and force it to be less than or equal to every possible outcome. With this step, we obtain a fully linear model:

\[\begin{aligned} \max\;\; & z \\ \textrm{s. t.:}\;\; & -x_2 + x_3 + z \leqslant 0 \\ & x_1 - x_3 + z \leqslant 0 \\ & -x_1 + x_2 + z \leqslant 0 \\ & x_1 + x_2 + x_3 = 1 \\ & x_1, x_2, x_3 \geqslant 0\\ & z \in \mathbb{R} \end{aligned}\]

This strategy can be modeled with linear optimization:

• Player II (Dual): seeks to minimize the maximum loss the opponent can inflict (minimax strategy).

This strategy can also be modeled with linear optimization:

\[\begin{aligned} \min\;\; & \max\{-u_2+u_3, u_1-u_3,-u_1+u_2\} \\ \textrm{s. t.:}\;\; & u_1 + u_2 + u_3 = 1 \\ & u_1, u_2, u_3 \geqslant 0 \end{aligned}\]

whose linear form is given by:

\[\begin{aligned} \min\;\; & w \\ \textrm{s. t.:}\;\; & u_2 - u_3 + w \geqslant 0 \\ & -u_1 + u_3 + w \geqslant 0 \\ & u_1 - u_2 + w \geqslant 0 \\ & u_1 + u_2 + u_3 = 1 \\ & u_1, u_2, u_3 \geqslant 0\\ & w \in \mathbb{R} \end{aligned}\]

Remarkably, solving both models leads to the same conclusion: the optimal strategy for both players is to choose each option with probability $1/3$, that is $x_1=x_2=x_3=1/3$ and $u_1,u_2,u_3=1/3$. The expected value of the game for both players is 0, meaning $z=w=0$. Duality shows that the equilibrium of the game is the same for both sides.

This result is a particular case of the minimax theorem, one of the pillars of game theory.

Example 2: The Resource Dilemma (Firm vs. Competitor)

Imagine a company that manufactures four products $(p_1,p_2,p_3,p_4)$ using three limited resources (raw materials) $(r_1,r_2,r_3)$ in order to maximize profit. The model is:

\[\begin{aligned} \max\;\; & z = 4x_1 + 3x_2 + 6x_3 + 2x_4 \\ \textrm{s. t.:}\;\; & 2x_1 + 3x_2 + 1.5x_3 + 4x_4 \leqslant 300 \\ & 2x_1 + 4x_2 + 3x_3 + x_4 \leqslant 500 \\ & 5x_1 + x_2 + 2x_3 + 2x_4 \leqslant 250 \\ & x_1, x_2, x_3, x_4 \geqslant 0 \end{aligned}\]

This is what we call the primal problem.

Now imagine a competitor who does not want to produce anything, but instead wants to buy the resources from the company at the lowest possible cost. This competitor must decide how much to pay for each unit of resource $(u_1,u_2,u_3)$, with the condition that the offered price must be attractive enough for the company to prefer selling the resources rather than producing:

\[\begin{aligned} \min\;\; & w = 300u_1 + 500u_2 + 250u_3 \\ \textrm{s. t.:}\;\; & 2u_1 + 2u_2 + 5u_3 \geqslant 4 \\ & 3u_1 + 4u_2 + u_3 \geqslant 3 \\ & 1.5u_1 + 3u_2 + 2u_3 \geqslant 6 \\ & 4u_1 + u_2 + 2u_3 \geqslant 2 \\ & u_1, u_2, u_3 \geqslant 0 \end{aligned}\]

This problem is called the Dual.

Solving both models independently yields $z^* = 750$ and $w^* = 750$, meaning that the firm’s profit equals the minimum cost at which the competitor could acquire the resources.

Here we see the two perspectives on the same problem:

• The Engineer (Primal): focuses on the quantities of products to manufacture.

• The Economist (Dual): focuses on the prices or value of the resources (called shadow prices).

Equivalence table

The pair of dual problems in canonical form is given by:

\[\begin{aligned} \min\;\;& LP_c = \mathbf{c}^\intercal \mathbf{x} \\ \textrm{s. t.:} \;\;& \mathbf{A}\mathbf{x} \geqslant \mathbf{b} \\ & \mathbf{x} \geqslant \mathbf{0} \\ \end{aligned} \qquad \begin{aligned} \max\;\;& DLP_c = \mathbf{b}^\intercal \mathbf{u} \\ \textrm{s. t.:} \;\;& \mathbf{A}^\intercal \mathbf{u} \leqslant \mathbf{c} \\ & \mathbf{u} \geqslant \mathbf{0} \end{aligned}\]

From these we obtain the following table, the “Rosetta stone” of optimization. It allows us to translate any optimization problem into its dual counterpart in a mechanical way:

Remember that the number of variables and constraints of each problem equals the number of constraints and variables of the other. In other words, each primal constraint corresponds to a dual variable and each primal variable corresponds to a dual constraint. This implies that in the dual problem the technical coefficient matrix must be transposed.

Fundamental results

Several theoretical results play a key role in duality theory:

Double duality

The dual of the dual problem is the primal problem.

Weak duality theorem

Given feasible solutions $\bar{\mathbf{x}}$ and $\bar{\mathbf{u}}$ of the primal $LP_c$ and dual $DLP_c$ problems, respectively, the following always holds:

\[\mathbf{c}^\intercal \bar{\mathbf{x}} \geqslant \mathbf{b}^\intercal \bar{\mathbf{u}}\]

This leads to the following result:

Fundamental theorem of duality

Given two dual problems $LP$ and $DLP$, exactly one of the following situations occurs:

• Both problems are infeasible.
• One problem has an unbounded optimal solution and the other is infeasible.
• Both problems have an optimal solution.

Another key result that directly links the solutions of both problems is the following:

Complementary slackness theorem

Given two problems $LP_c$ and $DLP_c$ in canonical form, two feasible solutions $\bar{\mathbf{x}}$ and $\bar{\mathbf{u}}$ are optimal if and only if:

\[\begin{cases}\bar{\mathbf{u}}^\intercal(\mathbf{A}\bar{\mathbf{x}}-\mathbf{b})=0 \\ (\mathbf{c}^\intercal - \bar{\mathbf{u}}^\intercal\mathbf{A})\bar{\mathbf{x}} = 0 \end{cases}\]

Explicitly, given feasible solutions $\bar{\mathbf{x}}$ and $\bar{\mathbf{u}}$, the following hold:

\[\begin{aligned} u_i\,(a_i^\intercal x - b_i) & = 0 && \forall i \\ x_j\,(c_j - a_j^\intercal u) & = 0 && \forall j \end{aligned}\]

Which is equivalent to saying:

• If $x_j > 0$, the corresponding dual constraint holds with equality.

• If $c_j - a_j^\intercal u > 0$, then $x_j = 0$.

• If $u_i > 0$, the corresponding primal constraint holds with equality.
• If $a_i^\intercal x - b_i > 0$, then $u_i = 0$.

Identifying the dual solution

One might think that solving a linear optimization problem using the simplex method only gives the solution to the original (primal) problem. However, the final tableau also reveals the solution to the dual problem without performing any additional calculations.

In a simplex tableau the information is distributed as follows:

• Dual variables ($u_i$): appear in the objective row ($z_j - c_j$) under the columns corresponding to the initial slack variables of the primal. These values represent how much the objective would improve if we had one additional unit of each resource.

• Dual slack variables: appear in the same objective row but under the columns of the original decision variables ($x_j$).

• Optimal value: the value of the objective function is exactly the same for both problems ($z^* = w^*$).

Economics in the Dual Problem (Shadow Prices)

Duality is not only a mathematical mirror, it is also a decision-making tool for businesses. For an economist, dual variables are known as shadow prices.

What is a Shadow Price?

It is the marginal value of a resource. It tells us how much our objective function (for example, total profit) would increase if we increased the availability of that limited resource by one unit, keeping everything else constant.

Key economic interpretation:

If the Shadow Price is $>0$: the resource is scarce. We are using all of it (its slack variable in the primal is 0). It may be worthwhile to pay to obtain more of that resource, as long as the cost is lower than the shadow price.

If the Shadow Price is $=0$: the resource is not binding. We have not exhausted the available amount, so having one additional unit does not provide any additional benefit. Its marginal value is zero.

Conclusion

From a geometric perspective, duality also has a fascinating interpretation: while the primal problem searches for the best point inside a feasible polyhedron, the dual problem describes the hyperplane that supports it at the optimum.

Two different perspectives on the same phenomenon: one decides what to do, while the other reveals how much each resource is worth.

And, surprisingly, both arrive at exactly the same result.