When taking the dual of a linear program (LP), is there a trick/easy way to remember the rules for the directions of the inequalities, signs of the variables, etc.? A trick with a catchy name, perhaps?
-
3$\begingroup$ I recommend just learning the general dual problem construction, as presented in Boyd and Vandenberghe for example, where you first write down the Lagrangian, then minimize the Lagrangian with respect to the primal variables to obtain the dual function, etc. This can always be used to derive the dual of a linear program. $\endgroup$– littleOJun 8, 2019 at 4:07
-
$\begingroup$ Lagrangian Duality might be the most universal framework for deriving the dual. Another nice interpretation of the LP duality is using the Theorem of Alternatives, or Farkas Lemma. I strongly recommend the chapter 1 of "Lectures on modern convex optimization" written by Ben-tal and Nemirovski. $\endgroup$– SeokApr 11 at 2:28
5 Answers
There sure is! It's called the SOB Method, originally proposed by A.T. Benjamin.
In the SOB method, we classify each variable and each constraint as either sensible, odd, or bizarre (hence the name SOB). For "usual" models, we expect variables to be non-negative (for example, lengths, times, etc.). Sometimes, a variable might be unrestricted (maybe like $xy$ coordinates in the plane), though this isn't as usual. It's even possible that the variable must be negative--weird! This intuition leads to:
- $x\geq0$ $\leftarrow$ sensible
- $x$ free $\leftarrow$ odd
- $x\leq0$ $\leftarrow$ bizarre
Note that the classification of variables doesn't depend on whether we're minimizing or maximizing.
Constraints are also intuitive. Suppose we're maximizing something. Then we would expect that our constraints should bound $x$ from above (so we don't run off to infinity). That is, $Ax\leq{b}$ constraints are sensible. It's possible the constraints are equalities (somewhat weirder), or we might even have $Ax\geq{b}$ constraints--weird, because they look like a lower bound, even though we're maximizing.
Maximization
- $Ax\leq{b}$ $\leftarrow$ sensible
- $Ax=b$ $\leftarrow$ odd
- $Ax\geq{b}$ $\leftarrow$ bizarre
Just the opposite reasoning holds for minimization:
Minimization
- $Ax\geq{b}$ $\leftarrow$ sensible
- $Ax=b$ $\leftarrow$ odd
- $Ax\leq{b}$ $\leftarrow$ bizarre
Once everything is labeled, taking the dual is easy! A sensible primal variable matches up with a sensible dual constraint, etc. So if we're maximizing, and we have a variable $x_3\geq0$, say, then there will be a constraint in the dual with a $\geq$ sign (the dual is a minimization problem, and $\geq$ constraints are sensible in the minimization case).
Here's a full example from the linked paper:
$$ \begin{array}{rl} \text{Minimize} & 3x_1+5x_2+x_3\\ \text{subject to} & x_1+x_2+x_3=2\\ & 2x_1-3x_3\leq0\\ &x_1\geq0,x_2\geq0 \end{array} $$ The primal constraints tell us that our dual variables $y_1$ and $y_2$ will be, respectively, odd and bizarre. Likewise, the first two dual constraints will be sensible and the third one will be odd, resulting in the following LP: $$ \begin{array}{rl} \text{Maximize} & 2y_1\\ \text{subject to} & y_1+2y_2\leq3\\ & y_1\leq5\\ & y_1-3y_2=1\\ & y_2\leq0 \end{array} $$
-
2$\begingroup$ Thanks a lot. This method could really come in handy when teaching/reviewing dual formulation in optimization courses. $\endgroup$– EhsanJun 7, 2019 at 15:41
-
I have always, for some reason, had troubles remembering those rules. In the book by Bertsimas and Tsitsiklis there is even a nice little table showing the conversion from a primal to a dual in a nice compact fashion. But as stated, I am not good at remembering these rules. Thus, I always write up the Lagrangean and identify for what values of the dual multipliers the Lagrangean function is unbounded; that gives me the constraints of the dual. For example, if we have a linear program of the form \begin{align} \min &\ cx\\ s.t.: &\ Ax\geq b\\ &\ Dx=d\\ &\ x\geq 0 \end{align} Then we can assign dual variables $ \mu\in\mathbb{R}^{m_b}_+ $ and $\pi\in\mathbb{R}^{m_d} $ to the two sets of constraints. The sign of the dual variables tend to come a little easier when you think of them as adding a penalty for violating the constraints. For example here, $\mu$ should be non-negative, as we want to add a positive amount to the objective function if $b_i< A_ix$ and $\pi$ should be able to take both positive and negative values, as any solution $x$ with $Dx\neq d$ should be discouraged. Hence we have the Lagrangean \[ L(\mu,\pi)=\min_{x\geq 0}cx+\mu(b-Ax)+\pi(d-Dx) \] If the Lagrangean is rearranged a bit you get \[ L(\mu,\pi)=\mu b+\pi d + \min_{x≥0}(c-\mu A-\pi D)x \] We should note, that as $x\geq 0$ we will have the following definition of the Lagrangean \begin{equation} L(\mu,\pi)=\begin{cases} -\infty,&\text{if } (c-\mu A-\pi D)_i<0 \text{ for some variable } x_i \\ \mu b+\pi d&\text{if } c-\mu A-\pi D\geq 0\end{cases} \end{equation} Thus, if the Lagrangean should be maximized, we want to avoid the cases where $(c-\mu A-\pi D)_i<0$. This means that the Lagrangean dual problem (and therefore also the linear programming dual) is given by \begin{align} \max_{\mu\geq 0,\pi\in\mathbb{R}^{m_d}}L(\mu,\pi) = \max&\ b\mu+d\pi\\ s.t.:&\ \mu A + \pi D\leq c\\ & \mu \geq 0,\pi \text{ free} \end{align} This helps me as I do not have to remember some conversion-rules (which I most definitely will screw up), and it also keeps it present for me why the dual looks as it does. This more "mechanical" (admitted, not "easy") way, has help many of my students too.
-
1$\begingroup$ This is the best method. Many people forget how to find the dual problem of the classical problems due to the implicit matrix form of them. $\endgroup$ Oct 4, 2019 at 17:52
-
$\begingroup$ Hello Sune. You say that in the Lagrangian, $\pi$ should be able to take both positive and negative values, because any $x$ with $Dx \not = d$ should be discouraged. Can you please explain this a little more? Is it discouraged when solving $\min_{x\geq 0}cx+\mu(b-Ax)+\pi(d-Dx)$, or where? Thank you for your time. $\endgroup$ May 18, 2021 at 16:21
-
1$\begingroup$ You can see $Dx=d$ as the two systems $Dx\leq d$ and $Dx\geq d$. Relax them both with multipliers $\pi^{\leq}\geq 0$ and $\pi^{\geq}\geq 0$, simplify and get the Lagrangean function $L(\mu,\pi^{\geq},\pi^{\leq})=\min_{x\geq 0}cx+\mu(b-Ax)+(\pi^{\geq}-\pi^{\leq})(d-Dx)$. Now observe that by setting $\pi=\pi^{\geq}-\pi^{\leq}$ and substitution you get the expression in the answer. Also, since $\pi$ is the difference between to non-negative numbers, it might be negative, positive, or zero. Thus $\pi$ should be a free variable. $\endgroup$– SuneMay 19, 2021 at 11:35
Here is a simple rule I use. Assume you are minimizing and
$$ A x \leq b $$
So the dual value $(y)$ tells you how the objective value change if you increase b. Now if you increase b, then you relax the problem and the objective value most go down. Therefore, the dual variables must satisfies
$$ y \leq 0. $$
-
2$\begingroup$ Either that, or just look it up in the MOSEK Modeling Cookbook docs.mosek.com/modeling-cookbook/… . $\endgroup$ Jun 7, 2019 at 12:20
I was having the same problem: I always had to look up the rules for taking LP duals. So I've built a small web page at https://lpdual.com that quickly gives the answer. It shows a sample primal program, and allows you to change the sense of the constraints and variables and to then see the effect on the dual.
-
6$\begingroup$ How is this going to help someone $remember$ the rules for taking a dual? This is just a tool which dualizes an LP for you but it does not make me remember the rules. $\endgroup$– YukiJJan 18, 2022 at 7:19
-
1$\begingroup$ @YukiJ For someone learning the rules, it provides a way to practice on new problems and confirm that their answers are correct. $\endgroup$– prubin ♦Jan 18, 2022 at 16:21
We can present the canonical format for minimization and maximization problems as follows:
\begin{align} \min &\quad cx\\ \text{s.t.} &\quad Ax\geq b\\ &\quad x\geq 0 \end{align} and \begin{align} \max &\quad wb\\ \text{s.t.} &\quad wA\leq c\\ &\quad w\geq 0 \end{align} The second problem is dual of the first problem and vice versa.
$Ax=b$ in the first problem results in having free variable $w$ in the dual problem (vice versa) and $Ax\leq b$ results in $w\leq 0$ in dual problem (vice versa).
In the same fashion, $wA=c $ gives $x $ free (vice versa) ....