# minimize $c^tx$ subject to $Ax=b,x\ge0$ dual problem

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

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.

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

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

• 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? – user441848 Jun 22 '18 at 20:43
• And what could be an example of choosing appropiate sequence of $x$ to make $L(x,y,v)$ converge to $-\infty?$ – user441848 Jun 22 '18 at 20:51
• 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. – Michal Adamaszek Jun 22 '18 at 21:50
• I normally avoid advertising but you can read a similar sort of gentle introduction here with examples docs.mosek.com/modeling-cookbook/… – Michal Adamaszek Jun 22 '18 at 21:53
• 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? – user441848 Jun 30 '18 at 4:58