Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

\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|cite|improve this question
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
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|cite|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|cite|improve this answer
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


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

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

Take $x=x_1-x_2$ \begin{align} \min c^T(x_1-x_2) \\ s.t.~A(x_1-x_2)=b \\ ~ x_1, x_2 \ge 0 \end{align}

This is can be written as \begin{align} \min {\begin {pmatrix}c \\ -c \\ \end {pmatrix} }^T \begin {pmatrix} x_1 \\ x_2 \\ \end {pmatrix} \\ s.t.~\begin {pmatrix} A, & -A \end {pmatrix} \begin {pmatrix} x_1 \\ x_2 \\ \end {pmatrix}=b \\ ~ x_1, x_2 \ge 0 \end{align}

Now, this is in the standard form of the linear program. Therefore, the dual can be written as

\begin{align} \max b^T y \\ s.t.~ \begin {pmatrix}c \\ -c \\ \end {pmatrix} - \begin {pmatrix} A^T\\ -A^T \\ \end {pmatrix} y \ge 0\\ ~ y \ge 0 \end{align}

This can be simplify as

\begin{align} \max b^T y \\ s.t.~ c-A^T y \ge 0\\ ~ -c+A^T y \ge 0\\ ~ y \ge 0 \end{align}

\begin{align} \max b^T y \\ s.t.~ A^T y \le c\\ ~ A^T y \ge c\\ ~ y \ge 0 \end{align}

This is equivalent to

\begin{align} \max b^T y \\ s.t.~ A^T y = c\\ ~ y \ge 0 \end{align}

share|cite|improve this answer

Your Answer


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.