4
$\begingroup$

Suppose a finite set of $m$ half-spaces $H_i$ in $\mathbb{R}^n$ are described by equations $$ \mathbf{\ell}_i \cdot \mathbf{x} \leq 1. $$ for $1\leq i \leq m$. If $L$ is the $m\times n$ matrix with rows $\mathbf{\ell}_i$, then the intersection $I = \cap H_i$ of half-spaces can be described as the set $$ I = \{ \mathbf{x} \colon \, \text{entries of }L\mathbf{x}\text{ are }\leq 1\}. $$

Note that this intersection is always non-empty (it contains the origin). For many reasons (e.g. doing linear programming, optimization, and in some geometric problems), it is important to know whether the set I is bounded (a polytope). Incidentally, most references I see about linear programming assume that $I$ is bounded or not and don't discuss how best to determine this.

One can characterize boundedness as follows

$I$ is bounded iff for all $\mathbf{x}\neq 0$ there exists $1\leq i \leq m$ such that $\ell_i\cdot \mathbf{x} >0$.

I am wondering, is there a nice ``linear algebraic'' way to characterize this (e.g. in terms of some linear algebraic properties of the matrix $L$)? E.g. can I test for this by performing some sort of matrix decomposition or normal form of $L$?

Edit: By duality:

$I$ is bounded iff the dual $I^* = \text{convex hull}(\ell_i)$ contains zero.

In other words, $I$ is bounded iff there is a convex combination $$ \mathbf{0} = \sum_1^m a_i \ell_i, \text{ where } \sum_1^m a_i = 1. $$ I guess this is a problem that has a well known solution but it doesn't look like it's a solution of the form I was hoping for. Oh well.

$\endgroup$
  • $\begingroup$ From $\sum a_i = 1$ you get $a_m = 1-\sum\limits_{i=1}^{m-1}a_i$. Plugging it into $\sum a_i l_i =0$, we get a system of linear equations on $a_1, \dots, a_{m-1}$. Existence of solutions for such is a well-known topic. $\endgroup$ – lisyarus Apr 25 '18 at 17:42
0
$\begingroup$

Let's see what it means that the linear form $\ell$ is bounded above by $M$
$$\{x\ | \ \ell_i(x)\le 1\}$$

It means that the inequality $\ell(x)-M\le 0$ is a consequence $\ell_i(x)-1\le 0$, that is (Farkas lemma) there exists $\alpha_i\ge 0$ and $\beta\ge 0$ so that $$\ell(\cdot) - M = \sum_i\alpha_i(\ell(\cdot)-1) - \beta$$ It follows that $\ell = \sum \alpha_i \ell_i$. The converse is also true: any functional that is a positive combination of $\ell_i$ is bounded above on $\{x\ | \ \ell_i(x)\le 1\}$

So the condition for the boundedness is: the positive cone generated by the $\ell_i$'s is the whole (dual) space. It is enough that the $\pm$ coordinate functionals are.

It is not that hard to see that one needs at least $(n+1)$ functionals $\ell_i$.

Now, like you said ( translated) the cone is not the whole space if and only if there exists an $x$ so that $$l_i\cdot x < 0$$ for all $i$.

This can be tested as a linear programming problem:

$$\min t \ ,\ (x,t) \in \mathbb{R}^{n} \times \mathbb{R}, \ \ell_i \cdot x \le t \le 0 \ \text{ for all } i \text{ and } -1 \le t$$ (the last inequality to make the $\min$ larger than $-\infty$. There are two cases:

  1. the $min$ is $-1$, the cone of $\ell_i$ is not the full space, the set determined is unbounded

  2. the $min$ is $0$, the cone of $\ell_i$ is the full space, the set determined is bounded.

Another characterization: $I$ (with your notation) is bounded if and only if $0$ is in the interior of the cone $\ell_i$ . This is equivalent to : there exists $n+1$ of the $\ell_i$ forming a system of rank $n$ and $\alpha_1$, $\ldots$, $\alpha_{n+1}> 0$ so that $$\sum_i \alpha_i \ell_i = 0$$

This might be easy to check in some cases, otherwise, it's still a linear optimization problem, although seems more complicated than the previous one.

Added:

A sufficient condition for $n+1$ vectors $y_i$ such that the cone spanned by them is the full space: $y_i \cdot y_j < 0$ for $i\ne j$. Indeed, assume that there exists $y_{n+2}$ such that $y_i \cdot y_{n+2} < 0$ for all $1\le i \le n+1$. The system $$\sum \alpha_i y_i = 0 \\ \sum \alpha_i = 0$$ has a non-zero solution. Separate the positive and the negative coefficients So we can write $$y =\sum_{i \in I'} \alpha_i y_i= \sum_{i \in I''} \beta_i y_i$$

and taking the dot product $y \cdot y$ where the second $y$ is substituted with the second sum we get $y \cdot y < 0$, contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.