3
$\begingroup$

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.

1 Answers 1

2

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$.

  • 0
    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}$?2011-05-10
  • 0
    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.2011-05-10
  • 0
    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$.2011-05-10
  • 0
    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.2011-05-10
  • 0
    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$.2011-05-10