Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  Inquest Feb 29 '12 at 17:03
    
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 :) –  Stijn Feb 29 '12 at 17:07
    
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$). –  TMM Feb 29 '12 at 18:37
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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. –  Stijn Mar 3 '12 at 12:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.