1
$\begingroup$

Suppose I have the systems $S_1: Ax \leq b$ where $A \in \mathbb{R}^{n\times m}$, $x \in \mathbb{R}^m$ and $b \in \mathbb{R}^n$, and $S_2 : y^{\intercal}A=0,\\ y \geq 0,\\ y^{\intercal}b < 0 $

where $y \in \mathbb{R}^n$. I want to cast these systems into a linear programming form. How would I do that? Specifically, how should I pick my objective functions?

  • 0
    For what it's worth, proving that at most one of them has a solution should be easy enough without LPP (consider $y^T A x$).2012-02-29

1 Answers 1

1

I don't know what the best way to prove this, but obviously this is rephrased version of Farkas Lemma, therefore we can prove it similarly to proof of Farkas Lemma.

The primal problem

$max\space0^{T}x$

$S_{1} : Ax \leq b$

$x$ is unrestricted

The dual problem

$min\space y^{T}b$

$y^{T}A=0$

$y\geq0$

We have equality in constraint because of unrestricted $x$ in the primal problem.

When the first condition holds, the primal is feasible and its optimal objective is obviously zero. By applying the weak duality theorem, we have that any dual feasible vector $y$ (that is, one which satisfies $y^{T}A=0$) must have $y^{T}b\geq0$ (the primal solution is $0$ is a lower bound), therefore the conditions $y^{T}A=0$ and $y^{T}b<0$ cannot simultaneously hold, so the second condition is not satisfied.

The dual is, however, always feasible, since $y=0$ satisfies $y^{T}A=0$ trivially. By applying strong duality, we deduce that the dual objective is unfounded below, and hence $y^{T}A=0$ and $y^{T}b<0$ has a solution.

  • 0
    I'm not gonna read this answer because, as I've said in a comment, this problem is part of a homeworkset and I want to solve it m$y$self. I'll give you the checkmark though since no one else seems to be answering. Thanks anyway.2012-03-03