2
$\begingroup$

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

  • 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.2012-11-26

4 Answers 4

0

\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}

  • 0
    would you explain how $y^T b$ become $b^T y$? would you use inner product or any other formula?2016-12-17
2

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}

  • 0
    @dineshdileep I just edited my answer to show how I derived the dual problem.2012-11-26
1

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

0

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

  • 0
    This is what I also figured. But can you please give an explanation for it...2012-11-26