# Is a halfspace intersection unbounded?

Komei Fukuda fukuda at ifor.math.ethz.ch
Sun Dec 5 20:30:17 PST 2004

```Just a side remark.

> P is unbounded
> <=>   there is a nonzero vector z  such that  A z = 0 and  z >= 0
> <=>   there is no  m-vector  y  such that   y^T  A  > 0  (totally
> positive).
>
> The last equivalence is a variant of Farkas' Lemma.
> The last condition can be checked by solving an LP:
>
> max  alpha
>    (y^T A)_j  >= alpha   for all j=1,...,d   and
>    alpha   <= 1.

One can also use the following LP instead:

max   z_1 + z_2 + ... z_d
subject to    A z =0, z >=0 and  z_j <= 1 for all j.

If the LP has a positive optimal value, P is unbounded.
In fact   the optimal solution   z*   will be an unbounded
direction.   On the other hand, if the optimal value
is zero, constructing a certificate for boundedness
is a bit implicit in this method.

Also, it is better to use an exact arithmetic to solve
these LPs, as one needs to distinguish zero from
any positive number correctly.

Best, Komei

-------------
The compgeom mailing lists: see