Hi everyone!

Previously I wrote about theoretical grounds of "aliens trick". Specifically, I introduced the concept of the Lagrangian duality and explained its connection with the trick. Today I want to elaborate a bit more on the concept of dual problems and their applications to linear programming as well as to common problems in competitive programming.

I initially wanted to also write about some applications in competitive programming problems, but given that the introduction is already quite lengthy, I decided to leave it for another blog, while using most common and well-known theoretical examples here, focusing more on how to construct and interpret dual problems to begin with, rather than how to use it in contests.

I think, it is a crucial first step towards using the duality in actual programming challenges.

General Lagrangian duality

I wrote a long and elaborate story about general Lagrangian duality. It should provide you with additional insights and interpretation on what's going on if you, like me, like to start learning new concepts from abstract nonsense rather than specific examples. However according to some feedback such approach would rather scare anyone else, so I put the scary stuff under the spoiler tag.

Long story about general duality

Let $$$f : X \mapsto \mathbb R$$$ be the objective function and $$$g : X \mapsto \mathbb R^c$$$ be the constraint function.

Def. 1. The primal optimization problem is defined as

$$$\begin{gather} \min\limits_{x \in X} & f(x),\\ s.t. & g(x) \geq 0. \end{gather}$$$

Here $$$g(x) \geq 0$$$ means that each component of $$$g(x)$$$ is non-negative.

Roundtrip to the constraint domain

Let $$$Y$$$ be a set of valid $$$g(x)$$$ values. Let's look on the optimization problem from the perspective of $$$Y$$$.

Def. 2. The value function $$$h : Y \mapsto \mathbb R$$$ is defined as $$$h(y) = \min\limits_{\substack{x \in X \newline g(x) = y}} f(x)$$$.

In terms of $$$h(y)$$$, the primal problem could be formulated as

$$$\begin{gather} \min\limits_{y \in Y} & h(y), \\ s.t. & y \geq 0. \end{gather}$$$

The primal problem is easier to analyze in the $$$Y$$$ domain, but computing $$$h(y)$$$ is often harder than computing $$$f(x)$$$. Therefore the methods that are developed in $$$Y$$$ domain should be then translated back to $$$X$$$ domain. A possible way to work with $$$h(y)$$$ indirectly is by finding the supporting hyperplanes of its epigraph.

Def. 3. The epigraph of a function $$$f : Y \mapsto \mathbb R$$$ is a set $$$\operatorname{epi} f = \{(y, z) : z \geq f(y) \} \subset Y \times \mathbb R$$$.

Let $$$\lambda^\top x$$$ be the dot product of $$$\lambda$$$ and $$$x$$$.

Def. 4. A supporting hyperplane of a set $$$X \subset \mathbb R^d$$$ with a normal vector $$$\lambda \in \mathbb R^d$$$ is a surface defined as $$$\lambda^\top x = t(\lambda)$$$, where $$$t(\lambda)$$$ is the largest possible number such that $$$\lambda^\top x \geq t(\lambda)$$$ for all $$$x \in X$$$. Equivalently, $$$t(\lambda)$$$ is the infimum of $$$\lambda^\top x$$$ among all $$$x \in X$$$.

Def. 5. The function $$$t(\lambda)$$$ defined above is called the support function of $$$X$$$.

For $$$X = \operatorname{epi} f$$$ and the normal vector represented as $$$(-\lambda, 1)$$$ it means $$$t(\lambda) = \min\limits_{y \in Y} [h(y) - \lambda^\top y]$$$.

The supporting hyperplane with the normal vector $$$(-\lambda, 1)$$$ touches the epigraph in the point $$$(y^*, h(y^*))$$$.

Let $$$y^* \geq 0$$$ be the value that delivers minimum $$$h(y)$$$ on $$$y \geq 0$$$. Then $$$t(\lambda) \leq h(y^*)$$$ when $$$\lambda \geq 0$$$, because $$$\lambda^\top y^* \geq 0$$$. That being said, $$$t(\lambda)$$$ provides a lower bound for $$$h(y^*)$$$ and to make this estimate as precise as possible, it is natural to find $$$\lambda^* \geq 0$$$ such that $$$t(\lambda^*)$$$ is the largest possible on $$$\lambda \geq 0$$$. Then it will hold that $$$t(\lambda^*) \leq h(y^*)$$$.

The case when the constraints are strict and require $$$y=0$$$ was considered in the previous article on "aliens trick", in which it was deduced that when $$$h(y)$$$ is convex, the strong equality $$$t(\lambda^*) = h(y^*)$$$ holds. The same is true for a more generic $$$y \geq 0$$$ constraint: there are $$$\lambda^* \geq 0$$$ and $$$y^* \geq 0$$$ such that for each $$$i$$$, either $$$\lambda^*_i$$$ or $$$y^*_i$$$ is zero (a condition known as complementary slackness) and $$$t(\lambda^*) = h(y^*)$$$.

As $$$\lambda$$$ represents the normal vector of a supporting hyperplane, the complementary slackness condition means that in $$$y^*$$$ point, either $$$y^*_i=0$$$ which means that the constraint is strictly implemented, or $$$\lambda_i^*=0$$$, which means that $$$i$$$-th component of the normal vector is zero, thus movements along the $$$i$$$-th axis in any direction won't reduce $$$h(y^*)$$$.

Back to the objective domain

Alternatively, the same $$$t(\lambda)$$$ can be defined in terms of $$$X$$$ as $$$t(\lambda) = \min\limits_{x \in X} [f(x) - \lambda^\top g(x)]$$$. From this fact follows the following theory:

Def. 6. A function $$$L(x, \lambda) = f(x) - \lambda^\top g(x)$$$ is called the Lagrange function or the Lagrangian.

Def. 7. A vector $$$\lambda \in \mathbb R^c$$$ defined above is called the Lagrange multiplier.

The support function $$$t(\lambda)$$$ defined above has the following meaning in the Lagrange duality:

Def. 8. The Lagrangian dual function $$$t(\lambda)$$$ is defined as $$$t(\lambda) = \min\limits_{x \in X} L(x,\lambda)$$$.

Let $$$x^*$$$ be the solution to the primal problem. Then $$$g(x^*) \geq 0$$$ and $$$t(\lambda) \leq L(x^*,\lambda) \leq f(x^*)$$$ for $$$\lambda \geq 0$$$, since $$$\lambda^\top g(x^*) \geq 0$$$.

Thus, $$$t(\lambda)$$$ on $$$\lambda \geq 0$$$ gives the lower bound for $$$f(x^*)$$$. To make the estimate as precise as possible, we maximize $$$t(\lambda)$$$:

Def. 9. The dual optimization problem is defined as

$$$\begin{gather} \max\limits_{\lambda \in \mathbb R^c} & t(\lambda),\\ s.t. & \lambda \geq 0 \end{gather}$$$

It is worth noting that $$$t(\lambda)$$$ is a concave function, as a point-wise minimum of concave in $$$\lambda$$$ functions.

If $$$\lambda^*$$$ is the solution to the dual optimization problem, the following inequality holds:

$$$ t(\lambda^*) \leq L(x^*, \lambda^*) \leq f(x^*). $$$

The $$$t(\lambda^*) \leq f(x^*)$$$ inequality is generally referred to as the weak duality.

Def. 10. The difference $$$f(x^*) - t(\lambda^*)$$$ is called the duality gap. By definition, it is always non-negative.

Def. 11. The condition when the duality gap is zero is called the strong duality.

Turns out that strong duality holds in many common cases, including linear programming problems.

Treating equalities separately

Let $$$g_1(x),\dots,g_c(x) : X \mapsto \mathbb R$$$ be the components of $$$g(x)$$$. When $$$g_i(x) = -g_j(x)$$$, the inequality constraint degrades to an equality and becomes $$$g_i(x) = g_j(x) = 0$$$. In the Lagrange function it produces a $$$\lambda_i g_i + \lambda_j g_j = (\lambda_i - \lambda_j) g_i$$$ summand.

On practice, it is often convenient to treat $$$g_i = g_j = 0$$$ as a single equality constraint and $$$\mu_i = \lambda_i - \lambda_j$$$ as a single "free" variable which is allowed to be negative. Let $$$h(x) : X \mapsto \mathbb R^d$$$ denote equality constraint function, then we could define the primal problem as

$$$\begin{gather} \min\limits_{x \in X} & f(x),\\ s.t. & g(x) \geq 0,\\ & h(x) = 0. \end{gather}$$$

And the dual problem as

$$$\begin{gather} \max\limits_{\lambda, \mu \in \mathbb R^{c+d}} & t(\lambda, \mu),\\ s.t. & \lambda \geq 0, \end{gather}$$$

where $$$t(\lambda, \mu) = \min\limits_{x \in X} [f(x) - \lambda^\top g(x) - \mu^\top h(x)]$$$. As you see, unlike $$$\lambda$$$ that corresponds to the inequalities and must be non-negative, the vector $$$\mu$$$ doesn't have any sign constraints and is deemed "free" in this regard.

Maximization problems

Sometimes, the primal problem is formulated as maximization rather than minimization:

$$$\begin{gather} \max\limits_{x \in X} & f(x),\\ s.t. & g(x) \geq 0. \end{gather}$$$

In such case, the Lagrange dual is defined as $$$t(\lambda) = \max\limits_{x \in X}[f(x) + \lambda^\top g(x)]$$$ and the dual problem is

$$$\begin{gather} \min\limits_{\lambda \in \mathbb R^c} & t(\lambda),\\ s.t. & \lambda \geq 0. \end{gather}$$$

As you see, the sign of $$$\lambda^\top g(x)$$$ is changed to preserve the $$$\lambda \geq 0$$$ constraint.

The duality inequality for the maximization problems looks like

$$$ t(\lambda^*) \geq L(x^*, \lambda^*) \geq f(x^*), $$$

where $$$L(x, \lambda) = f(x) + \lambda^\top g(x)$$$.

Minimax inequality

In terms of the Lagrange function for the minimization problem, $$$\max_\lambda t(\lambda) = \max_\lambda \min_x L(x, \lambda)$$$.

At the same time, we should note that $$$f(x) = \max_\lambda L(x, \lambda)$$$ for $$$g(x) \geq 0$$$. Therefore, $$$\min_x f(x) = \min_x \max_\lambda L(x,\lambda)$$$.

Hence, the weak duality $$$t(\lambda^*) \leq L(x^*, \lambda^*) \leq f(x^*)$$$ is the consequence of the general minimax inequality

$$$ \max_\lambda \min_x L(x, \lambda) \leq \min_x \max_\lambda L(x, \lambda), $$$

which can be proven to be true for any function $$$L(x, \lambda)$$$.

Conversely, the weak duality $$$t(\lambda^*) \geq L(x^*, \lambda^*) \geq f(x^*)$$$ for maximization problem follows from

$$$ \min_\lambda \max_x L(x, \lambda) \geq \max_x \min_\lambda L(x, \lambda). $$$

Among all the stuff above, I'll just briefly mention the most important things. For an optimization problem

where $$$f: X \mapsto \mathbb R$$$ is the objective function and $$$g: X \mapsto \mathbb R^c$$$ is the constraint function, the dual problem is

where $$$t(\lambda) = \min\limits_{x \in X} [f(x)-\lambda^\top g(x)]$$$ is the Lagrangian dual function and $$$\lambda^\top g(x)$$$ denotes the dot product of $$$\lambda$$$ and $$$g(x)$$$.

Correspondingly, for the maximization problem

its dual is

where $$$t(\lambda) = \max\limits_{x \in X} [f(x)+\lambda^\top g(x)]$$$. Note that the sign has changed.

Let $$$x^*$$$ be the solution for the primal problem and $$$\lambda^*$$$ be the solution for the dual problem. Then for the minimization problem it holds that $$$t(\lambda^*) \leq f(x^*)$$$ and for the maximization problem it holds that $$$t(\lambda^*) \geq f(x^*)$$$.

This connection between the solution to the primal and dual problem is called the weak duality. In linear programming specifically, as we will see, in a significant number of cases the strong duality $$$t(\lambda^*) = f(x^*)$$$ holds.

In linear programming

Def. 12. Let $$$c \in \mathbb R^d$$$, $$$b \in \mathbb R^c$$$ and $$$A \in \mathbb R^{c \times d}$$$. The primal linear programming problem is defined in canonical form as

In other words, the objective function and the constraint functions in a linear programming problem are all linear functionals.

If we follow the approach above, we'd need to introduce the Lagrange multipliers $$$\lambda_1 \in \mathbb R^c$$$ and $$$\lambda_2 \in \mathbb R^d$$$. Then the Lagrangian is

and the Lagrangian dual is

When $$$A^\top\lambda_1 - c \neq \lambda_2$$$, this value can be arbitrarily large. Otherwise $$$t(\lambda_1, \lambda_2) = \lambda_1^\top b$$$. To make a problem a bit more regular and avoid dealing with $$$+\infty$$$, we place the $$$A^\top\lambda_1 - c = \lambda_2$$$ equality into constraints section.

After that $$$t(\lambda_1,\lambda_2)$$$ does not depend on $$$\lambda_2$$$ and we can completely remove it from the dual problem formulation replacing $$$A^\top\lambda_1 - c = \lambda_2$$$ equality with $$$A^\top\lambda_1 - c \geq 0$$$ inequality. Then, we can formulate the dual problem.

Def. 13. The dual linear programming problem is defined as

In a similar way dual problems can be constructed for minimization problems and with different kinds of constraints. There is an alternative way to interpret the duality for LP problems specifically. If we multiply both parts of $$$A x \leq b$$$ with $$$\lambda^\top$$$, we get

At the same time $$$\lambda^\top A = (A^\top \lambda)^\top$$$, hence for $$$A^\top \lambda \geq c$$$ it holds that

This immediately shows that $$$\lambda^\top b$$$ provides an upper bound for $$$c^\top x$$$ and by minimizing $$$\lambda^\top b$$$, we make the bound as tight as possible.

Mnemonics to construct dual problems

On practice, it is not always possible to easily write LP problem in the needed form.

To mitigate this, one should keep in mind that there is generally a correspondence between:

1. Primal variables and dual constraints;
2. Primal constraints and dual variables.

This correspondence can be summed up in a table:

With the standard definition of LP duality it looks like

Here's an example that highlights all possible variations (source):

Finally, if the primal problem has explicit constraint on the variable (e.g. $$$x=0$$$), it doesn't produce a constraint in the dual problem.

Weirdly indexed variables and constraints

It often happens so that e.g. variables are indexed by two numbers (e.g. row and column) rather than just one, which might make the construction of the dual somewhat puzzling. What is the actual meaning behind $$$Ax \leq b$$$ and $$$A^\top \lambda \geq c$$$?

The $$$Ax \leq b$$$ inequality says that there are $$$n$$$ variables $$$x_1, \dots, x_n$$$ and $$$m$$$ constraints defined by rows of $$$A$$$ and $$$b_1, \dots, b_m$$$. In such terms, $$$i$$$-th constraints is a linear combination of variables which should be less or equal than $$$b_i$$$. Let the coefficient near $$$j$$$-th variable in $$$i$$$-th constraint be $$$a_{ij}$$$.

Now, $$$A^\top \lambda \geq c$$$ inequality says that there are $$$m$$$ dual variable $$$\lambda_1, \dots, \lambda_m$$$ and $$$n$$$ constraints defined by columns of $$$A$$$ and $$$c_1, \dots, c_n$$$. Specifically, $$$j$$$-th constraint collects $$$a_{ij}$$$ and places it near $$$\lambda_i$$$. In other words, the $$$j$$$-th constraint in the dual problem collects together all the coefficients that were near $$$j$$$-th variable in each of primal constraints.

Let's practice it on some concrete examples.

Shortest paths as linear programming

As a simpler example, we start off with the shortest path problem. Given a weighted directed graph, one needs to find the length of the shortest path from $$$s$$$ to all the other vertices. We assume that there are $$$n$$$ vertices and the weight of the edge from $$$i$$$ to $$$j$$$ is denoted by $$$c_{ij}$$$. If there is no such edge, we set $$$c_{ij} = +\infty$$$.

Let $$$d_i$$$ symbolize the length of the shortest path from $$$s$$$ to $$$i$$$. Then the primal problem could be formulated as:

On one hand, each of $$$d_i$$$ can't be greater than the length of the shortest path from $$$s$$$ to $$$i$$$. Indeed, let $$$s = i_0 \to i_1 \to i_2 \to \dots \to i_k = i$$$ be the shortest path. Then the inequalities imply that $$$d_s \geq d_i - c_{i_0 i_1} - \dots - c_{i_{k-1} i_k}$$$. If $$$d_i$$$ is greater than the sum which is subtracted from it, it would mean that $$$d_s > 0$$$ and would violate $$$d_s = 0$$$ constraint.

On the other hand, setting all $$$d_i$$$ to the actual lengths of the shortest path would satisfy all constraints, hence deliver the maximum sum.

Constructing dual

For the dual problem we need to introduce dual variables $$$x_{ij}$$$ corresponding to the $$$d_j - d_i \leq c_{ij}$$$ constraint.

In this way, the target function would be

The coefficient near $$$x_{ij}$$$ in the $$$k$$$-th constraint would be equal to the coefficient near $$$d_k$$$ in the $$$d_j - d_i \leq c_{ij}$$$ constraint in the primal problem. That being said, we take the coefficient $$$1$$$ near $$$x_{ik}$$$ for every $$$d_k - d_i \leq c_{ik}$$$ constraint and we take the coefficient $$$-1$$$ near $$$x_{kj}$$$ for every $$$d_j - d_k \leq c_{kj}$$$ constraint, and the coefficient $$$0$$$ from all other constraints. This results into the following dual problem:

Note that, because of $$$d_s=0$$$ constraint in the primal problem, we only add constraints for $$$k \neq s$$$ in the dual problem. At the same time, because all the other primal variables were free, all the constraints in the dual problem are equality-like.

To interpret this problem, we could say that $$$x_{ij}$$$ denotes the number of times the edge $$$i \to j$$$ was picked into a network formed by the combination of all shortest paths from $$$s$$$ to all vertices in the graph. The $$$= 1$$$ constraints mean that every vertex (except for $$$s$$$) must have one more incoming edge than outgoing ones.

In terms of flows it would mean that we used $$$s$$$ as a source vertex and every other vertex is connected to the sink with an edge that has zero cost and capacity $$$1$$$ while original graph edges have a cost of $$$c_{ij}$$$ for traversing them, but infinite capacities. Then, $$$x_{ij}$$$ is the minimum cost flow in such network.

Maximum flow as linear programming

Let's recall the definition of a flow. Let $$$(V, E)$$$ be a network with $$$s, t \in V$$$ being the source and the sink. Each edge $$$i \to j$$$ has a capacity $$$q_{ij} \geq 0$$$. Then the flow is a function on the edges $$$f_{ij}$$$ such that:

1. The flow on the edge is non-negative and doesn't exceed its capacity (capacity constraint): $$$0 \leq f_{ij} \leq q_{ij}$$$;
2. The sum of incoming flow is equal to the sum of outgoing flow for any vertex except $$$s$$$ and $$$t$$$ (flow conservation):

In this terms, we can define a net flow $$$b_k$$$ on the vertex $$$k$$$ as the difference between outgoing and incoming flows in this vertex. The definition above essentially says that the net flow of all vertices except $$$s$$$ and $$$t$$$ should be $$$0$$$. Let $$$f$$$ be the net flow in the vertex $$$s$$$, from the flow conservation it follows that the net flow of $$$t$$$ is $$$-f$$$. In this terms the maximum flow problem is

Constructing dual

Each constraint in the primal problem will correspond to a variable in the dual problem. There are three types of variables, let $$$\lambda_{ij}$$$ be a variable corresponding to $$$f_{ij} \leq q_{ij}$$$ constraint, $$$\mu_k$$$ be the variables corresponding to flow conservation constraints and let $$$\alpha$$$ be the variable corresponding to $$$b_s=-b_t$$$ constraints.

Then, the target function is

As for the dual constraints, the constraint corresponding to the primal variable $$$f_{ij}$$$ would look like

getting $$$\lambda_{ij}$$$ from $$$f_{ij} \leq q_{ij}$$$ and $$$\mu_i,-\mu_j$$$ from flow conservation constraints with $$$k=i$$$ and $$$k=j$$$.

As for the primal variable $$$b_k$$$, it will only generate dual constraints for $$$k=s$$$ and $$$k=t$$$, specifically:

Here, $$$\alpha$$$ comes with coefficients from $$$b_t = -b_s$$$ and $$$\mu_s, \mu_t$$$ come with coefficients from flow conservation constraints. Finally, $$$1$$$ from the first equality comes from the target function $$$b_s$$$. Note that $$$\alpha$$$ and $$$\mu_k$$$ are free variables, as they come from equality constraints, while $$$\lambda_{ij}$$$ must be non-negative. This allows to get rid of $$$\alpha$$$ altogether substituting two constraints above with $$$\mu_t = \mu_s+1$$$.

Getting it all together, the dual to the maximum flow looks like

Note that increasing all $$$\mu_k$$$ by the same value will not change anything, so we may stick to $$$\mu_s=0$$$ and $$$\mu_t=1$$$. Another useful observation is that, since $$$q_{ij}$$$ are by definition non-negative it is always good to make $$$\lambda_{ij}$$$ as low as possible, either saturating the inequality $$$\lambda_{ij} \geq \mu_j - \mu_i$$$ or making $$$\lambda_{ij} = 0$$$. With this observations, we may further simplify the dual problem and rewrite it as

Thus getting rid of $$$\lambda_{ij}$$$ altogether. Then, it can be proven that in this special case, the optimal solution only have $$$\mu_k \in \{0,1\}$$$, forming a cut between sets $$$S = \{k : \mu_k = 0\}$$$ and $$$T = \{k : \mu_k = 1\}$$$. Since $$$s \in S$$$ and $$$t \in T$$$, the dual problem indeed looks for the minimum cut between $$$s$$$ and $$$t$$$.

Min-cost flow

Now assume that alongside the capacity $$$q_{ij}$$$, each edge also has a cost $$$c_{ij}$$$ for one unit of flow on the edge. Then, you want to find a flow of value $$$b$$$, while maintaing its minimum cost. The primal problem for such case is formulated as

Constructing dual

We will need two types of dual variables. Specifically, $$$\lambda_{ij}$$$ for each $$$f_{ij} \leq q_{ij}$$$ constraint and $$$\pi_k$$$ for each flow conservation constraint.

The target function then will be

Variables $$$b_k$$$ are, in fact, constant, hence will not generate any constraints. Each variable $$$f_{ij}$$$ will generate a single constraint:

That being said, the dual problem is

Note that here $$$\lambda_{ij} \leq 0$$$, as we're considering dual to the minimization problem and it is generated by $$$\leq$$$-type constraint.

Since $$$q_{ij} \geq 0$$$ and we want to maximize target function, we would like to make $$$\lambda_{ij}$$$ as large as possible. Thus, it is always optimal to take

which allows us to get rid of $$$\lambda_{ij}$$$ altogether, leaving us with the simplest version:

As far as my understanding goes, $$$\pi_k$$$ dual variables should be directly related to Johnoson potentials in the residual network of the minimum-cost $$$b$$$-flow. Stated this way, the dual problem can be interpreted in the following way:

Let $$$c_{ij}^\pi = c_{ij} - \pi_i + \pi_j$$$ be the adjusted cost of the edge $$$i \to j$$$. Consider a path

and sum up the adjusted weights on the path:

In particular, for $$$i_0 = i_k$$$, when the path is a cycle, the total adjusted cost is same as total initial cost.

In particular, from this and cycle-path decomposition theorem follows that the cost of any $$$b$$$-flow on adjusted costs would exceed the cost of same $$$b$$$-flow on initial costs by exactly $$$b(\pi_t - \pi_s)$$$, so we get rid of this excess by subtracting this value from the target function.

As for the first summand, it is comprised as if all negative-cost edges are taken into the flow, bounding the minimum-cost flow from below, so maximizing it would take it as close to the actual minimum-cost flow as possible.

Practical example

605C - Freelancer's Dreams. Statement as it is boils down to the following LP problem, given $$$a_1, \dots, a_n, b_1, \dots, b_n, p, q$$$:

Its dual is

The optimal solution to the dual problem can be found with nested binary search, as there are only two variables involved.

This approach was shared by jqdai0815 in his comment to the contest editorial.

Further reading

• Laurent Lessard — Dual flows and algorithms
• Mikhail Lavrov — The Max-Flow Min-Cut Theorem