In the end of the series of LP blogs, we will introduce a very important structure in LP problem, that is the dual problem. Dual problem can give us another view of a LP problem. There are a lot of applications of Duality in algorithm, like Max flow and Min Cut problem. Additionally, you can find more application of primal-dual techniques in my another blog series.
In this blog, we will first introduce what is dual problem, how to convert the primal problem to its dual problem.
Dual problem
Given matrix $A$ represented as:
\[A = \begin{bmatrix} \bar{a}^\top_1 \\ \bar{a}^\top_2 \\ \vdots \\ \bar{a}^\top_m \\ \end{bmatrix} = [\bar{A}_1, \bar{A}_2, \ldots, \bar{A}_n]\]where $\bar{b} \in \mathbb{R}^m$ and $\bar{c} \in \mathbb{R}^n$.
(a) PRIMAL PROBLEM \(\begin{aligned} &\text{Minimize} \quad & \bar{c}^\top \bar{x} && \\ &\text{subject to} & \bar{a}_i^\top \bar{x} \geq b_i; && i \in M_1, \\ && \bar{a}_i^\top \bar{x} \leq b_i; && i \in M_2, \\ && \bar{a}_i^\top \bar{x} = b_i; && i \in M_3, \\ && \bar{x}_j \geq 0; && j \in N_1, \\ && \bar{x}_j \leq 0; && j \in N_2, \\ && \bar{x}_j \in \mathbb{R}; && j \in N_3. \end{aligned}\)
(b) DUAL PROBLEM \(\begin{aligned} &\text{Maximize} \quad & \bar{p}^\top \bar{b} &&\\ &\text{subject to} & \bar{p}_i \geq 0; && i \in M_1, \\ && \bar{p}_i \leq 0; && i \in M_2, \\ && \bar{p}_i \in \mathbb{R}; && i \in M_3, \\ && \bar{p}^\top \bar{A}_j \leq c_j; && j \in N_1, \\ && \bar{p}^\top \bar{A}_j \geq c_j; && j \in N_2, \\ && \bar{p}^\top \bar{A}_j = c_j; && j \in N_3. \end{aligned}\)
For each constraint in the primal (other than sign constraints), we introduce a variable in the dual problem. For each variable in the primal, we introduce a constraint in the dual.
-
Depending on whether the primal constraint is an equality or inequality constraint, the corresponding dual variable is either free or sign-constrained, respectively.
-
Depending on whether a variable in the primal problem is free or sign-constrained, we have either an equality or an inequality constraint, respectively, in the dual problem.
Relations between primal and dual variables and constraints
| Primal | $\min \quad \bar{c}^\top \bar{x}$ | $\max \quad \bar{p}^\top \bar{b}$ | Dual |
|---|---|---|---|
| Constraints | $ \begin{aligned} \bar{a}_i^\top \bar{x} & \geq b_i \ \bar{a}_i^\top \bar{x} & \leq b_i \ \bar{a}_i^\top \bar{x} & = b_i \end{aligned} $ | $\begin{aligned} p_i & \geq 0 \ p_i & \leq 0 \ p_i &\text{ free} \end{aligned}$ | Variables |
| Variables | $\begin{aligned} x_j & \geq 0 \ x_j & \leq 0 \ x_j &\text{ free} \end{aligned}$ | $\begin{aligned} \bar{p}^\top \bar{A}_j & \leq c_j \ \bar{p}^\top \bar{A}_j & \geq c_j \ \bar{p}^\top \bar{A}_j & = c_j \end{aligned} $ | Constraints |
Every maximization problem can always be converted into an equivalent minimization problem and conversely. However, to avoid confusion, we will adhere to the convention that the primal is a minimization problem and its dual is a maximization problem.
Involution and Equivalency
Dual of Dual is Primal
Theorem: The dual of the dual is the primal. If we transform the dual into an equivalent minimization problem and then find its dual, we obtain a problem equivalent to the original (primal) problem.
Proof:
Let’s give a primal problem:
\[\begin{aligned} &\text{Minimize} \quad & \bar{c}^\top \bar{x} && \\ &\text{subject to} & \bar{a}_i^\top \bar{x} \geq b_i; && i \in M_1, \\ && \bar{a}_i^\top \bar{x} \leq b_i; && i \in M_2, \\ && \bar{a}_i^\top \bar{x} = b_i; && i \in M_3, \\ && \bar{x}_j \geq 0; && j \in N_1, \\ && \bar{x}_j \leq 0; && j \in N_2, \\ && \bar{x}_j \in \mathbb{R}; && j \in N_3. \end{aligned}\]Then we can give the dual problem by definition:
\[\begin{aligned} &\text{Maximize} \quad & \bar{p}^\top \bar{b} &&\\ &\text{subject to} & \bar{p}_i \geq 0; && i \in M_1, \\ && \bar{p}_i \leq 0; && i \in M_2, \\ && \bar{p}_i \in \mathbb{R}; && i \in M_3, \\ && \bar{p}^\top \bar{A}_j \leq c_j; && j \in N_1, \\ && \bar{p}^\top \bar{A}_j \geq c_j; && j \in N_2, \\ && \bar{p}^\top \bar{A}_j = c_j; && j \in N_3. \end{aligned}\]Equivalent reformulation of the dual problem involves renaming the decision variables $\bar{q} = \bar{p}$ and transforming the objective function by $c \rightarrow -c$ transforms min into max: \(\begin{aligned} &\text{Maximize} \quad & -\bar{b}^\top \bar{q} &&\\ &\text{subject to} & \bar{q}_i \geq 0; && i \in M_1, \\ && \bar{q}_i \leq 0; && i \in M_2, \\ && \bar{q}_i \in \mathbb{R}; && i \in M_3, \\ && (-\bar{A}_j)^\top \bar{q} \geq -c_j; && j \in N_1, \\ && (-\bar{A}_j)^\top \bar{q} \leq- c_j; && j \in N_2, \\ && (-\bar{A}_j)^\top \bar{q} = -c_j; && j \in N_3. \end{aligned}\)
The dual of this equivalent reformulation yields following problem:
\[\begin{aligned} &\text{Maximize} \quad & \bar{x}^\top (-\bar{c}) && \\ &\text{subject to} & \bar{x}^\top (-\bar{a}_i) \leq -b_i; && i \in M_1, \\ && \bar{x}^\top (-\bar{a}_i) \geq -b_i; && i \in M_2, \\ && \bar{x}^\top (-\bar{a}_i) = -b_i; && i \in M_3, \\ && \bar{x}_j \geq 0; && j \in N_1, \\ && \bar{x}_j \leq 0; && j \in N_2, \\ && \bar{x}_j \in \mathbb{R}; && j \in N_3. \end{aligned}\]The above problem is exactly the primal problem by equivalent reformulation. Hence, we have the dual of the dual is the primal. $\square$
Dual of equivalent problems are equivalent
Theorem: The duals of equivalent problems are equivalent. Suppose that we have transformed a LP problem $\Pi_1$ to another (equivalent) LP problem $\Pi_2$ by a sequence of transformations of the following types:
(a) Replace a variable $x$ unrestricted in sign with the difference $x^+ - x^-$ of two nonnegative variables.
(b) Replace an inequality constraint (e.g. $\bar{a}^\top \bar{x} \leq b$) by an equality constraint involving a nonnegative slack variable (e.g. $\bar{a}^\top \bar{x} + s = b$ with $s \geq 0$).
(c) If some row of the constraint matrix $A$ in a feasible standard form problem is a linear combination of the other rows of $A$, eliminate the corresponding equality constraint.
Then, the duals of $\Pi_1$ and $\Pi_2$ are equivalent, i.e. they are either both infeasible or they have the same optimal cost.
Proof:
Consider the primal problem shown on the left and its dual shown on the right:
\[\begin{equation} \begin{aligned} \text{minimize} \quad & \bar{c}^\top \bar{x} \\ \text{subject to} \quad & A\bar{x} \geq \bar{b} \\ & \bar{x} \text{ free} \end{aligned} \quad \quad \begin{aligned} \text{maximize} \quad & \bar{p}^\top \bar{b} \\ \text{subject to} \quad & \bar{p} \geq \bar{0} \\ & \bar{p}^\top A = \bar{c}^\top \end{aligned} \end{equation}\]We transform the primal problem by introducing surplus variables and then obtain its dual:
\[\begin{equation} \begin{aligned} \text{minimize} \quad & \bar{c}^\top \bar{x} + \bar{0}^\top \bar{s} \\ \text{subject to} \quad & A\bar{x} - I \bar{s} = \bar{b} \\ & \bar{s} \geq \bar{0} \\ & \bar{x} \text{ free} \end{aligned} \quad \quad \begin{aligned} \text{maximize} \quad & \bar{p}^\top \bar{b} \\ \text{subject to} \quad & \bar{p} \text{ free} \\ & \bar{p}^\top (-I) \leq \bar{0}^\top \\ & \bar{p}^\top A = \bar{c}^\top \end{aligned} \end{equation}\]We observe that the constraint $\bar{p} \geq \bar{0}$ is equivalent to the constraint $\bar{p} (- I) \leq \bar{0}$. Note the above dual problem of adding surplus variables is equivalent to the dual problem of primal problem, which implies operation (a) will not change equivalency.
Alternatively, if we take the original primal problem and replace $\bar{x}$ by sign-constrained variables, we obtain the following pair of problems:
\[\begin{equation} \begin{aligned} \text{minimize} \quad & \bar{c}^\top \bar{x}^+ - \bar{c}^\top \bar{x}^- \\ \text{subject to} \quad & A\bar{x}^+ - A\bar{x}^- \geq \bar{b} \\ & \bar{x}^+ \geq \bar{0} \\ & \bar{x}^- \geq \bar{0} \end{aligned} \quad \quad \begin{aligned} \text{maximize} \quad & \bar{p}^\top \bar{b} \\ \text{subject to} \quad & \bar{p} \geq \bar{0} \\ & \bar{p}^\top A \leq \bar{c}^\top \\ & \bar{p}^\top (-A) \leq -\bar{c}^\top \\ \end{aligned} \end{equation}\]Notice that the constraint $\bar{p}^\top A = \bar{c}^\top$ is equivalent to the two constraints $\bar{p}^\top A \leq \bar{c}^\top$ and $\bar{p}^\top (-A) \leq -\bar{c}^\top$. Thus, we have equivalent forms of the primal, which implies operation (b) will not change equivalency.
Now, we can consider a standard form problem, assumed feasible, and its dual:
\[\begin{equation} \begin{aligned} \text{minimize} \quad & \bar{c}^\top \bar{x} \\ \text{subject to} \quad & A\bar{x} = \bar{b} \\ & \bar{x} \geq \bar{0} \end{aligned} \quad \quad \begin{aligned} \text{maximize} \quad & \bar{p}^\top \bar{b} \\ \text{subject to} \quad & \bar{p} \text{ free}\\ & \bar{p}^\top A \leq \bar{c}^\top \end{aligned} \end{equation}\]Let $\bar{a}_1, …, \bar{a}_m$ be the rows of $A$ and suppose that $\bar{a}_m = \sum_{i=1}^{m-1} \lambda_i \bar{a}_i$ for some scalars $\lambda_1, …, \lambda_{m-1}$, that means the last equality constraint is redundant and can be eliminated.
By considering an arbitrary feasible solution $\bar{x}$, we obtain
\[b_m = \bar{a}_m^\top \bar{x} = (\sum_{i=1}^{m-1} \lambda_i \bar{a}_i^\top)\bar{x} = \sum_{i=1}^{m-1} \lambda_i b_i\]Note that the dual constraints are of the form $ \sum_{i=1}^m p_i \bar{a}_i^\top \leq \bar{c}^\top $ and can be rewritten as
\[\sum_{i=1}^{m-1} (p_i + p_m \lambda_i) \bar{a}_i \leq \bar{c}^\top\]Furthermore, using $b_m = \sum_{i=1}^{m-1} \lambda_i b_i$, the dual cost $\sum p_i b_i$ is equal to $\sum_{i=1}^{m-1} (p_i + p_m \lambda_i) b_i$.
If we now let $\bar{q}_i = \bar{p}_i + \bar{p}_m\lambda_i$, we see that the dual problem is equivalent to:
\[\begin{aligned} \text{maximize} \quad & \sum_{i=1}^{m-1} \bar{q}_i b_i \\ \text{subject to} \quad & \sum_{i=1}^{m-1} \bar{q}_i \bar{a}_i^\top \leq \bar{c}^\top. \end{aligned}\]We observe that this is the exact same dual that we would have obtained if we had eliminated the last (and redundant) constraint in the primal problem, before forming the dual. $\square$