From: horst.kraemer@snafu.de (Horst Kraemer)
Subject: Re: half spaces and first orthant in R^n
Date: Wed, 01 Sep 1999 21:12:10 GMT
Newsgroups: sci.math
Keywords: linear optimization

On Wed, 01 Sep 1999 12:24:42 +0100, Geert Stremersch
<geert@ensmain.rug.ac.be> wrote:

> 
> Given two half spaces A_1=a_1 . x <= b_1 and A_2 =a_2 . x <= b_2 in R^n.
 
> So a_1 and a_2 are row matrices with n columns and x is column matrix
> with n rows.
> b_1 and b_2 are reals.
> Denote R^n_+ as the first orthant of R^n.
 
> Question:
 
> Under which conditions does the following hold:
 
> A_1\cap R^n_+ \subset A_2\cap R^n_+
> 
> Or in words: when is the intersection of a half space with the first
> orthant a subset of
> the intersection of another half space with the first orthant ?

There is a very simple necessary and sufficient condition. Note that

	A_1\cap R^n_+ \subset A_2\cap R^n_+  (1)

is equivalent to

	A_1\cap R^n_+ \subset A_2            (2)


(2) holds if and only if there is a nonnegative number p such that


	p*a_1 >= a_2  and  p*b_1 <= b_2


This is a direct application of the theorem 

(A is a matrix, x and c n-vectors, b and p m-vectors, d is a number)

<c,x> <= d is a consequence of A*x<=b for all x if and only if there
is a nonnegative vector p such that

	A'*p = c  and <b,p><=d

This is one of the central theorems in linear optimization.

Regards
Horst