Is a halfspace intersection unbounded?
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
> 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.
The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce