I'm working on the following exercise:

Let $a \in \mathbb{R}^{n \times n}$ be a skew symmetric matrix and $ b \in \mathbb{R}^n$ with $c = -b$. Consider the following $(LP)$ named $(P)$

$$\min_{x \in \mathbb{R}^n} c^Tx$$ $$ \text{such that: } Ax \ge b, x \ge 0$$

Show that it is equivalent to it's dual problem $(DP)$

$$\max_{y \in \mathbb{R}^n} y^Tb$$ $$ \text{such that: }y^TA \le c^T, y \ge 0$$

Show that if a feasible solution exists for $(P)$ then there is also an optimal solution for $P$.

I managed to show that both LPs are equivalent by just plugging in the assumptions the assumptions that $A = -A^T$ and $c = -b$ into $(P)$.

But I don' t know how to do the second part. Could you give me a hint?

  • 1
    $\begingroup$ What the duality theorems say? $\endgroup$ – metamorphy May 24 '18 at 17:25
  • $\begingroup$ Ok, that was the point I missed. Thank you. $\endgroup$ – 3nondatur May 24 '18 at 19:53

Your Answer

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

Browse other questions tagged or ask your own question.