Minimal common and maximal crossing points.

be a subset of $\QTR{cal}{R}^{n+1}$ . The

may have common points with the $\left( n+1\right)$ -th coordinate axis. We introduce the quantity MATH

A normal vector to a nonvertical hyperplane may be normalized to a form

. A nonvertical hyperplane that crosses the $\left( n+1\right)$ -th coordinate axis at the point

and has a normal vector

has the representation MATH

Indeed,

The set

is contained in the upper half plane of

iff

Hence, the quantity MATH

is the maximum $\left( n+1\right)$ -th axis crossing level for all hyperplanes that contain the set

in the upper half space and have the normal vector

We investigate the conditions for the equality MATH

Observe that by definition of these quantities all that is needed is existence of a supporting hyperplane at a point

. The pictures ( Crossing points figure 1 )-( Crossing points figure 3 ) show basic examples when this may or may not happen.

Crossing points figure 2. The upper boundary is included in the set. The other boundaries are excluded.

Proposition

(Crossing theorem 1). Let be a subset of $\QTR{cal}{R}^{n+1}$ . Assume the following:

1. and $\left( n+1\right)$ -th axis have nonempty intersection and $w^{\ast}\neq\infty$ .

2. The set MATH is convex.

Then if and only if for any sequence such that $u_{k}\rightarrow0$ we have MATH

Proof

By definition of $w^{\ast}$ , .

$\bar{M}$ contains no vertical lines. Indeed, if it does then by the proposition ( Main properties of direction of recession ) one may infinitely go along the vector inside $\bar{M}$ starting from any . This contradicts the condition 1.

We have for any small positive $\varepsilon$ . Indeed, on the contrary, if then by definition of the closure one can construct the sequence that violates .

Therefore, by the proposition ( Nonvertical separation ), there is a nonvertical separation of $\bar{M}$ from for any small positive $\varepsilon$ . The $\left( n+1\right)$ -th axis crossing point for such separating hyperplane must be between and . Hence, $q^{\ast}=w^{\ast}$ .

Proposition

(Crossing theorem 2). Let be a subset of $\QTR{cal}{R}^{n+1}$ . Assume the following:

1. and $\left( n+1\right)$ -th axis have nonempty intersection and $w^{\ast}\neq\infty$ .

2. The set MATH is convex.

3. , where the set is defined by MATH Then and the solution set has the form MATH where the set $\tilde{Q}$ is nonempty convex and compact and is the orthogonal complement of relative to the plane of the first n coordinates .

Proof

By the proposition ( Proper separation 1 ) there is a separating hyperplane for the point and set $\bar{M}$ . Such hyperplane cannot be vertical. Indeed, if it is vertical then the point projects on the plane along the onto the origin . Indeed, the segment MATH would belong to . But then the condition is violated because it would belong to the boundary of . Therefore the is nonvertical, and $Q^{\ast}$ is nonempty.

We next claim that . Indeed, by construction of if it has an orthogonal complement in then we can rotate coordinate system to make a coordinate subspace and then remove the coordinates that span the from the consideration (see the picture ( Crossing theorem 2 figure )).

In addition, . To see this, consider any hyperplane , corresponding normal $\mu$ that delivers and the perturbation . If then $\mu+\lambda\eta$ can be made arbitrarily close to horizontal and would be close to vertical by taking large enough $\pm\lambda$ . Hence, such $\eta$ can be in $R_{Q^{\ast}}$ only if . If then the statement is trivially true. We exclude such case from consideration.

We conclude that .

We next apply the proposition ( Decomposition of a convex set ) within the $\QTR{cal}{R}^{n}$ MATH with . The $Q^{\ast}$ and have no common direction of recession as we already established. Hence, MATH for some convex and nonempty $\tilde{Q}$ . The $\tilde{Q}$ is compact by ( Main properties of direction of recession )-2.