18
$\begingroup$

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?

$\endgroup$
  • 1
    $\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$ – littleO Jun 8 at 4:07
26
$\begingroup$

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:

  1. $x\geq0$ $\leftarrow$ sensible
  2. $x$ free $\leftarrow$ odd
  3. $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

  1. $Ax\leq{b}$ $\leftarrow$ sensible
  2. $Ax=b$ $\leftarrow$ odd
  3. $Ax\geq{b}$ $\leftarrow$ bizarre

Just the opposite reasoning holds for minimization:

Minimization

  1. $Ax\geq{b}$ $\leftarrow$ sensible
  2. $Ax=b$ $\leftarrow$ odd
  3. $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=3\\ & 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} $$

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot. This method could really come in handy when teaching/reviewing dual formulation in optimization courses. $\endgroup$ – Ehsan Jun 7 at 15:41
13
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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. $$

$\endgroup$
3
$\begingroup$

We can present the canonical format for minimization and maximization problems as follows:

\begin{align} \min &\ cx\\ s.t.: &\ Ax\geq b\\ &\ x\geq 0 \end{align} and \begin{align} \max &\ wb\\ s.t.: &\ wA\leq c\\ &\ 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) ....

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.