Is a halfspace intersection unbounded?

Komei Fukuda fukuda at
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
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list