0
$\begingroup$

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$?

  • 0
    $g_1(x,y) = x - y$ and $g_2(x,y) = -x - y$2011-04-20

1 Answers 1

4

$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$.