3
$\begingroup$

Let $X \subset \mathbb{R}^n$ be a nonempty convex set, and suppose $x$ is an extreme point of $X$. Does there always exist a supporting hyperplane $H$ to $X$ at $x$ (i.e., $x$ lies on $H$) such that $H \cap X = \{x\}$?

Thoughts: My intuition says that the above statement holds. The above statement is equivalent to the following: "does there always exist a vector $c \in \mathbb{R}^n$ such that $x$ is the unique solution to the Problem $ \underset{z \in X}{\min} c^{\text{T}}z $?" From Chapter 2 of Bertsimas and Tsitsiklis' Introduction to to Linear Optimization, I know that the above result is true when $X$ is a polyhedron, but the generalization to general convex sets doesn't seem to follow directly.

For reference, the definition of extreme point I use is as follows: $x$ is an extreme point of a convex set $X$ if there do not exist two vectors $y, z \in X$, with $y \neq x$ and $z \neq x$, and a scalar $\lambda \in [0,1]$ such that $x = \lambda y + (1-\lambda)z$.

$\endgroup$
1
5
$\begingroup$

No - $x$ could be a $C^1$ boundary point separating a straight section of the boundary from a curved section, as in this example constructed from a square and a circle quadrant: convex set

Here the extreme point $x$ of $X$ has as its only supporting hyperplane the tangent line $H$, which intersects $X$ along a nontrivial interval.

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