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$
3
  • $\begingroup$ Observe that $\max c^{\top}x=-\min -c^{\top}x$ $\endgroup$ Commented Jun 23, 2017 at 5:25
  • $\begingroup$ @MarcelloSammarra, good point, but I'm still stuck... I feel like I'm missing something pretty simple. $\endgroup$
    – ELEC
    Commented Jun 25, 2017 at 19:10
  • 1
    $\begingroup$ That's indeed equivalent! Substitute y by. _y $\endgroup$
    – Red shoes
    Commented Jun 25, 2017 at 19:47

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .