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.

I am working on a problem where it would be nice to prove that the feasible region of a LP problem is bounded, but where it is not necessary to solve any particular problem.

In particular, given an NxN matrix $A$ and a non-negative vector $\vec{b}\in\mathbb{R}^N$, I would like to find a set of sufficient conditions to guarentee that the set of non-negative vectors $\vec{x}\in\mathbb{R}^N$ such that $A\vec{x}\leq\vec{b}$ is bounded.

Having no experience with linear programming, I am not sure where to even start and have been getting unnecessarily bogged down with details on the simplex algorithm - which aren't needed right now because I don't need a particular solution. Any references to literature focusing on this aspect of the LP problem would be very much appreciated!

Just in case anyone has a better idea of how to approach the problem I'm currently working, I'm trying to, given a N-dimensional quadratic form $Q:\mathbb{R}^N\rightarrow\mathbb{R}$, find a set of conditions guarenteeing that the set of non-negative vectors $\vec{x}\in\mathbb{R}^N$ such that the partial derivative of $Q$ in each direction is non-negative is bounded. This naturally turned into something like a LP problem, so I thought this would be the direction to head.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

If $b \ge 0$, the feasible region is nonempty (because $0$ is feasible); the feasible region is unbounded iff the linear programming problem

P: maximize $e^T x$ subject to $A x \le b$, $x \ge 0$

is unbounded (where $e$ is the vector of all 1's), and this is true iff the dual problem

D: minimize $b^T y$ subject to $A^T y \ge e$, $y \ge 0$

is infeasible. This in turn is equivalent to: there is no linear combination of the rows of $A$ with all coefficients $\ge 0$ and all entries $> 0$.

share|improve this answer
    
I'm confused by your last sentence. Did you mean, that you take linear combinations of rows in the augmented matrix $[A|\vec{e}]$ and want the coefficients in the left-most N columns to be non-negative and those in the far-right column to be positive? If that is the case, does it follow that a sufficient condition (though weak one) would be that there is a non-negative vector $\vec{x}\in\mathbb{R}$ such that $A\vec{x}=\vec{e}$? –  Chris M May 10 '11 at 5:47
    
Ideally, I am hoping for a statement concerning the eigenvalues or determinant of $A$ because I feel like this would tie in nicely with the known information of the quadratic form that I am working with. I have a hunch that if $A$ has a positive eigenvalue with an associated strictly positive eigenvector, then the feasible region is bounded, but I haven't had time to thoroughly think this through. –  Chris M May 10 '11 at 7:00
    
I mean (if $A$ is $m \times n$) there do not exist $y_1, \ldots, y_m \ge 0$ such that $\sum_{i=1}^m A_{ij} y_i > 0$ for all $j = 1 \ldots n$. –  Robert Israel May 10 '11 at 17:02
    
As for your hunch, it's almost right, except that you want an eigenvector of $A^T$ (or a left eigenvector of $A$) rather than an eigenvector of $A$. That is, if there exist $\lambda > 0$ and a vector $y > 0$ such that $A^T y = \lambda y$, in particular you have $A^T y > 0$, so my criterion says the feasible region is bounded. –  Robert Israel May 10 '11 at 17:07
    
Thank you so much! I've actually been working with symmetric matrices so far, so I guess that's why I didn't think too hard about if it should be eigenvectors of $A$ or $A^T$. –  Chris M May 10 '11 at 18:53

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.