Proving infeasibility using Duality

89 Views Asked by At

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.

1

There are 1 best solutions below

1
On

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?