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
    Isn't choosing your objective function the first step of LPP? Anyway, without the knowledge of the variables, it is difficult to set a objective function for you. The best way is to ask yourself : What do you want to minimize or maximize?2012-02-29
  • 0
    The idea behind my question is that I want to prove that either $S_1$ or $S_2$ has a solution, but not both. I wanted to do this by casting the systems in a LP form and then consider their duals. **EDIT:** This question is an exercise on a homework set I have to do, so I'd appreciate it if no one helps me with the original question :)2012-02-29
  • 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 myself. I'll give you the checkmark though since no one else seems to be answering. Thanks anyway.2012-03-03