Is a halfspace intersection unbounded?

[Komei Fukuda]

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
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.