# Does a collection of non-linear inequalities have “extreme points”

Say I have a collection of m non-linear inequalities, where each of the $i = 1... m$ inequalities has the form:

$g_i(x) \leq 0$ where $g_i: \mathbb{R}^n \rightarrow \mathbb{R}$ and $g_i(x)$ is nonlinear with respect to $x \in \mathbb{R}^n$

Let $D$ be the set of feasible points $x \in \mathbb{R}^n$ - that is:

$D = \{x \in \mathbb{R}^n | g_i(x) \leq 0 \forall i \}$

Is $D$ a polyhedron? And does it always have vertices? And lastly, does $D$ have any special properties if $g_i(x)$ is convex for each $i = 1...m$?

-
There's no reason for $D$ to be a polyhedron if the $g_i$ are nonlinear. Consider, for example, $g(x, y) = x^2 - y$ in $\mathbb{R}^2$. – Qiaochu Yuan Apr 20 '11 at 6:31
You are right. I guess what I was wondering was whether it has vertices/non-differentiable points at the intersection of different $g_i$ right? – Elements Apr 20 '11 at 8:06
$g_1(x,y) = x - y$ and $g_2(x,y) = -x - y$ – Alexander Thumm Apr 20 '11 at 8:13

$D$ will look like a part produced by a machine tool. Its boundary $\partial D$ consists of (parts of) hypersurfaces $S_i: g_i(x)=0$. Two $S_i$ may intersect and produce a curved "boundary element of codimension 2", and so on, and if $n$ (or more) $S_i$ meet at the same point $x\in\partial D$ we have a vertex. But the appearance of such boundary elements of various codimensions is not mandatory. Consider the following example in ${\mathbb R}^3$: $$g_1(x):=x_1^2+x_2^2-1,\quad g_2(x):= x_3-1,\quad g_3(x):=-x_3-1$$ where there are no vertices.
If the functions $g_i$ are convex then each domain $D_i:=\{x\in{\mathbb R}^n\ |\ g_i(x)\leq 0\}$ is convex and so is their intersection $D$.