1
$\begingroup$

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements.

I have to convert the following generic linear program to their duals

$$(P1)=\begin{cases}\max & c^Tx\\ &Ax=b\\ &x\ge 0 \end{cases},(P2)=\begin{cases}\max & c^Tx\\ &Ax=b \end{cases}$$

$$(P3)=\begin{cases}\min & b^Tx\\ &Ax\le b\\ &x\ge 0 \end{cases},(P4)=\begin{cases}\min & c^Tx\\ &Ax\le b \end{cases}$$

I did:

$$(D1)=\begin{cases}\min & b^Ty\\ &A^{T}y\le c\\ &y\ge 0 \end{cases},(D2)=\begin{cases}\min & b^Ty\\ &A^{T}y=c \end{cases}$$

$$(D3)=\begin{cases}\max & c^Ty\\ &A^{T}y\le c\\ &y\ge 0 \end{cases},(D4)=\begin{cases}\max & b^Ty\\ &A^{T}y= c\\&y\le 0 \end{cases}$$

Yet, following the following array:

Array of Duality rules

Should I do:

$$(D1)=\begin{cases}\min & b^Ty\\ &A^{-1}y\le c\\ \end{cases},(D2)=\begin{cases}\min & b^Ty\\ &A^{-1}y=c \end{cases}$$

$$(D3)=\begin{cases}\max & b^Ty\\ &A^{-1}y\le c\\ &y\le 0 \end{cases},(D4)=\begin{cases}\max & b^Ty\\ &A^{-1}y\le c \end{cases}$$

Which are yet to be transformed into their canonical form?

$\endgroup$
  • $\begingroup$ For one thing, all the $A^{-1}$ should be $A^T $. $\endgroup$ – Théophile Apr 26 '16 at 13:24
  • $\begingroup$ @Théophile isn't it the same? $\endgroup$ – IggyPass Apr 28 '16 at 8:27
  • 1
    $\begingroup$ No, they are very different! $A^{-1}$ is the inverse while $A^T$ is the transpose. The inverse is a matrix such that $AA^{-1} = I$; note that in almost all linear programming problems, the inverse doesn't exist because it is only defined when $A$ is square. On the other hand, the transpose is the result of exchanging the rows and columns of the matrix. $\endgroup$ – Théophile Apr 28 '16 at 17:34
  • $\begingroup$ @Théophile Yes, okay! Understood! I mixed things up because to know if a program is feasible we have to see if its matrix is invertible... $\endgroup$ – IggyPass Apr 28 '16 at 20:52
  • 1
    $\begingroup$ Good work! (Are you sure about the objective function, though?) $\endgroup$ – Théophile Apr 29 '16 at 8:43
1
$\begingroup$

In all four cases, your $A^{-1}$ should be $A^T$. (Make sure you understand the difference!) Apart from that, $(D1)$ and $(D2)$ are fine.

For $(D3)$, since the primal is a minimization problem with the restriction $A \mathbf x \leq \mathbf b$ (as opposed to $A \mathbf x \geq \mathbf b$), then the dual should have its variables constrained by $\mathbf x \leq \mathbf 0$ (not $\mathbf x \geq \mathbf 0$). Also, the objective function should be $\mathbf b^T \mathbf y$, not $\mathbf c^T \mathbf y$.

Can you fix $(D4)$ yourself?

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