0
$\begingroup$

Consider the primal linear program

\begin{align} \operatorname{min} c^T &x \\ A&x\leq b \\ &x \geq 0 \end{align}

In the dual problem, we associate each constraint $i$ with dual variable $y_i \leq 0$ and each variable $j$ with constraint $a_j^T y \leq c_j$. Therefore, the dual is

\begin{align} \operatorname{max} b^T &y \\ A^T&y\leq c \\ &y \leq 0 \end{align}

Now if the primal is a maximization problem the memorization rule is a little different.

\begin{align} \operatorname{max} c^T &x\\ A&x\leq b \\ &x \geq 0 \end{align}

has the dual

\begin{align} \operatorname{min} b^T &y\\ A^T&y\geq c \\ &y \geq 0 \end{align}

I didn't want to memorize the rule for the primal max case, so I thought I could just transform the maximization problem to minimization problem and follow the steps from there.

\begin{align} \operatorname{max} c^T &x \to - \operatorname{min} -c^T x\\ A&x\leq b \\ &x \geq 0 \end{align}

Which has the dual

\begin{align} - \operatorname{max} b^T &y \\ A^T&y\leq -c \\ &y \leq 0 \end{align}

Now if I change the objective and multiply each row with $-1$, I get \begin{align} \operatorname{min} -b^T &y \\ -A^T&y\geq c \\ -&y \geq 0 \end{align}

I cannot reason that this is equivalent to $\operatorname{min}\{ b^T y \,|\, A^T y \geq c, y \geq 0\}$. Did I miss something?

$\endgroup$
  • $\begingroup$ Observe that $\max c^{\top}x=-\min -c^{\top}x$ $\endgroup$ – Marcello Sammarra Jun 23 '17 at 5:25
  • $\begingroup$ @MarcelloSammarra, good point, but I'm still stuck... I feel like I'm missing something pretty simple. $\endgroup$ – ELEC Jun 25 '17 at 19:10
  • 1
    $\begingroup$ That's indeed equivalent! Substitute y by. _y $\endgroup$ – Red shoes Jun 25 '17 at 19:47
1
+50
$\begingroup$

So you are asking why \begin{align} \operatorname{min} -b^T &y \\ -A^T&y\geq c \\ -&y \geq 0 \end{align}

is equivalent to \begin{align} \operatorname{min} b^T &y\\ A^T&y\geq c \\ &y \geq 0 \;? \end{align}

This can be seen by substituting $y$ with $-y$.

To make it more explicit:

As an intermediate step we can write down \begin{align} \operatorname{min} b^T &(-y) \\ A^T&(-y)\geq c \\ &(-y) \geq 0. \end{align}

This is equivalent to the first system by linearity, and then if you replace $y$ with $(-y)$, you can see that it is equivalent to the second system.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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