Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

\begin{align} \min_{x} c^Tx \\ s.t.~Ax=b \end{align} Note that here $x$ is unrestricted. I need to prove that the dual of this program is given by \begin{align} \max_{\lambda} \lambda^Tb \\ s.t.~\lambda^TA\leq c^T \end{align}

But in the constraint, I always get an equality (using what I learnt) \begin{align} \max_{\lambda} \lambda^Tb \\ s.t.~\lambda^TA = c^T \end{align} Please give some explanation also.

share|improve this question
1  
It looks to me like the form of the dual with the inequality constraint is wrong, and your answer (with the equality constraint) is correct. –  Mike Spivey Nov 26 '12 at 16:40

3 Answers 3

up vote 1 down vote accepted

\begin{align} \min_{x} c^Tx \\ s.t.~Ax=b \end{align}

Is the same as: \begin{align} \min_{x} c^T(x^+-x^-) \\ s.t.~A(x^+-x^-)=b\\ x^+,x^-\geq 0 \end{align} Is the same as: \begin{align} \min_{x} [c^T|-c^T]z \\ s.t.~[A|-A]z=b\\ z\geq 0 \end{align} $$z=[x^T|-x^T]^T$$ Dual of this is : \begin{align} \max \quad b^Tp\\ s.t. [A|-A]^Tp\leq [cT|-c^T]^T\\ \implies Ap=c \end{align} I think your answer is correct.

share|improve this answer

You wrote the dual problem correctly. Perhaps whoever wrote your assignment forgot to include the constraint $x \geq 0$ in the primal problem.

Edit: here's how I derived the dual problem. The Lagrangian is \begin{align} L(x,\nu) &= \langle c, x \rangle + \langle \nu, b - Ax \rangle \\ &= \langle c, x \rangle - \langle \nu, Ax \rangle + \langle \nu, b \rangle \\ &= \langle c, x \rangle - \langle A^T \nu, x \rangle + \langle \nu, b \rangle \\ &= \langle c - A^T \nu, x \rangle + \langle \nu, b \rangle. \end{align}

The dual function is \begin{equation} g(\nu) = \begin{cases} \langle \nu,b \rangle & \quad \text{if } A^T \nu = c \\ -\infty & \quad \text{otherwise}. \end{cases} \end{equation}

So the dual problem is \begin{align} \text{maximize} & \quad \langle \nu, b \rangle \\ \text{subject to} & \quad A^T \nu = c. \end{align}

share|improve this answer
1  
Thanks for the reply. The variable is unconstrained and it was explicitly stated. Can you give a reason why the way i wrote it was correct. –  dineshdileep Nov 26 '12 at 11:19
    
@dineshdileep I just edited my answer to show how I derived the dual problem. –  littleO Nov 26 '12 at 21:59

Given

$\begin{align} \min_{x} c^Tx \\ s.t.~Ax=b \end{align}$

I think the dual of the problem would be

$\begin{align} \max_{x} b^Tw \\ s.t.~A^Tw (*)c \end{align}$

where $(*)$ actually depends on the restrictions of the variables in the primal problem. If the restriction is $x_i \geq 0$ then the type of constraint will follow the same inequality. But if $x_i$'s are unrestricted, then the constraints will become $=$

share|improve this answer
    
This is what I also figured. But can you please give an explanation for it... –  dineshdileep Nov 26 '12 at 10:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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