0
$\begingroup$

suppose we have the linear program min{$c^Tx: Ax \leq 0, x \leq 0$} and its corresponding dual

max{$0^Tx: A^Ty \geq 0, y \leq 0$}. How can we show that the Dual is infeasible? I started by contradiction and assumed the Dual is feasible, then its optimal value will be $0$ and by strong duality, the primal should also have an optimal value of $0$, however I am not able to reach a contradiction from this point.

$\endgroup$
0
$\begingroup$

Hint

The dual for this problem is $${\max g(\lambda_1,\lambda_2)\\\text{s. t.}\\\lambda_1,\lambda_2\succeq 0}$$where $$g(\lambda_1,\lambda_2){=\inf_{x}c^Tx+\lambda_1^TAx+\lambda_2^Tx\\=\inf_{x}(c+A^T\lambda_1+\lambda_2)^Tx}$$Now, when is the dual problem infeasible? How is it applied here?

$\endgroup$
  • $\begingroup$ I am not familiar with this way of applying duality $\endgroup$ – Skrrrrrtttt Mar 20 '19 at 20:34

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.