5
$\begingroup$

Consider the linear program to minimize $c^tx$ subject to $Ax=b,x\ge0.$ Write the dual problem.

Drew Brady user helped me to do this but I still have doubts about it.

First off, the lagrangian function is given by $L(x,u,v)=c^tx+u^t(b-Ax)-v^tx$

Now we have to infimize $L$ in the primal variable $x$.

For convenince we rewrite $L(x,u,v)=(c-v-A^tu)^tx+u^tb$

this implies that the dual problem is $$\max u^tb$$ $$s.t.\ c-v-A^tu=0$$ $$v\ge0$$

but this is equivalent to $$\max u^tb$$ $$s.t.\ c-A^tu\ge0$$ $\iff$ $$\max u^tb$$ $$s.t. A^tu\le c$$

Question:

  1. I don't understand the bold text. I know that the the dual function $\theta$ of $\max \theta$ is $\theta=\inf\{f(x)+ug(x)+vh(x)\}$ thus in this case Are we taking the $\inf\{L(x,u,v)\}$ ?

Or where does this $$\max u^tb$$ $$s.t.\ c-v-A^tu=0$$ $$v\ge0$$ came from?

  1. Why $$\max u^tb$$ $$s.t.\ c-v-A^tu=0$$ $$v\ge0\iff \max u^tb$$ $$s.t.\ c-A^tu\ge0$$
$\endgroup$
2
+100
$\begingroup$

As you mentioned, the Lagrangian is $L(x,u,v)=(c-v-A^T u)^T x + u^T b$. The dual function is \begin{align} g(u,v) &= \inf_x \, L(x,u,v) \\ &= \begin{cases} u^T b & \quad \text{if } c - v - A^T u = 0, \\ -\infty & \quad \text{otherwise}. \end{cases} \end{align} You can see why the infimum is $-\infty$ if $c - v - A^T u \neq 0$. In that case, we can select $x$ to make $L(x,u,v)$ as negative as we like. For example, we could take $x = -\alpha(c - v - A^T u)$, where $\alpha$ is some huge positive number. With that choice of $x$, we would have $$ L(x,u,v) = -\alpha \|c-v-A^T u \|^2 + u^T b $$ which approaches $-\infty$ as $\alpha$ approaches $\infty$. The only thing that can prevent the infimum from being $-\infty$ is if $c - v - A^T u = 0$.

Now that we have found the dual function, we can write down the dual problem: \begin{align} \operatorname{maximize}_{u,v} & \quad g(u,v) \\ \text{subject to } & \quad v \geq 0. \end{align} Certainly a maximum is not achieved if $g(u,v) = -\infty$, so we may as well restrict attention to values of $u,v$ such that $c - v - A^T u = 0$. When this constraint is satisfied, we have $g(u,v) = u^T b$. Thus, the dual problem can be written equivalently as \begin{align} \operatorname{maximize}_{u,v} & \quad u^T b\\ \text{subject to } & \quad v = c - A^T u\\ & \quad v \geq 0. \end{align} The two constraints can be combined into a single constraint that $c - A^T u \geq 0$. So, this problem in turn is equivalent to \begin{align} \operatorname{maximize}_{u} & \quad u^T b\\ \text{subject to } & \quad c - A^T u \geq 0. \\ \end{align}

By the way, the Lagrange dual of a standard form LP is also derived in section 5.2.1 (p. 224) of Boyd and Vandenberghe, which is free online.

$\endgroup$
  • 1
    $\begingroup$ That makes lot of sense $x = -\alpha(c - v - A^T u)$ with alpha huge positive number makes $L\to-\infty$, thank you! $\endgroup$ – user441848 Jul 1 '18 at 22:24
5
$\begingroup$

So you have the Lagrangian $$L(x,y,v)=c^Tx+y^T(b-Ax)-v^Tx.$$ Note that the Lagrangian is designed so that it always gives a lower bound on the objective $$L(x,y,v)\leq c^Tx$$ for feasible $x$ and when $v\geq 0$. In particular, for any $v\geq 0, y$ we have: $$\min_x L(x,y,v)\leq \min_{\{x~:~b=Ax,x\geq 0\}} c^Tx.$$ The right hand side is the optimal objective. So the question is, how close can we approach it with the left hand side. For this you write: $$L(x,y,v)=(c-A^Ty-v)^Tx + b^Ty.$$ If $c-A^Ty-v\neq 0$ then by choosing appropriate sequence of $x$ you can make $L(x,y,v)$ converge to $-\infty$, so the minimum is not any useful in approximating the optimal objective. Therefore it makes more sense to restrict to $c-A^Ty-v=0$, and then the pair $y,v$ which gives the best left-hand side is given by the problem $$ \begin{array}{ll} \mbox{maximize} & b^Ty \\ \mbox{st} & c-A^Ty-v=0 \\ & v\geq 0 \end{array} $$ and that's how the dual problem pops up. Since the first constraint is $v=c-A^Ty$, the combination of the constraints is just $c-A^Ty\geq 0$.

$\endgroup$
  • $\begingroup$ Thank you for your help Michal, I have a question the definition that I have for dual problem is $\text {maximize}\ b^Ty,$ were $b^Ty=\inf\{ L(x,y,v)\}$ and I see that you used $\min $ instead of $\inf $. But I guess is somehow equivalent? $\endgroup$ – user441848 Jun 22 '18 at 20:43
  • $\begingroup$ And what could be an example of choosing appropiate sequence of $x$ to make $L(x,y,v)$ converge to $-\infty?$ $\endgroup$ – user441848 Jun 22 '18 at 20:51
  • $\begingroup$ Probably I meant inf, because it need not be attained. And if a vector $u$ has a nonzero at some position $i$ then you choose $x$ that has a huge nonzero of the right sign only in position $i$ and then $u^Tx <0$ is hugely negative. $\endgroup$ – Michal Adamaszek Jun 22 '18 at 21:50
  • 2
    $\begingroup$ I normally avoid advertising but you can read a similar sort of gentle introduction here with examples docs.mosek.com/modeling-cookbook/… $\endgroup$ – Michal Adamaszek Jun 22 '18 at 21:53
  • $\begingroup$ Hi, I saw it again and I think it's better $\min$ than $\inf $ because that would make more sense here $\min c^tx$. I don't understand your idea/comment And if a vector u has a nonzero at some position i then you choose x that has a huge nonzero of the right sign only in position $i$ and then $u^Tx<0$ is hugely negative. Would you mind to explain with more details? $\endgroup$ – user441848 Jun 30 '18 at 4:58

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.