Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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