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

Question

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?

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

Answer 1

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.

Answer 2

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