|
|
正轴形(cross-polytope)定义为$\mathbb R^n$中$ℓ_1$-赋范下的单位球$\{x\in \mathbb {R}^n:\|x\|_{1}\leq 1\}.$
$X$是实(或复)向量空间。
对于任何 $p, x, y \in X$, 如果 $x \neq y$ 并且存在 $0 < t < 1$ 使得 $p = t x + (1-t) y$, 就说 $p$ 位于 $x$ 和 $y$ 之间。
$K$ 是 $X$ 的子集，$p \in K$，如果 $p$ 不位于 $K$ 的任意两个不同点之间，则 $p$ 称为 $K$ 的顶点。
Find the extreme points of the set $\{(x_1,x_2,x_3): |x_1| + |x_2| + |x_3| \le 1\}$
Since ${\cal A} = \operatorname{co} \{ \pm e_k\}_{k=1}^3 $ (unit vectors) you need only check that these points are indeed extreme points since all other points cannot be extreme points.
To see why no other point can be an extreme point, suppose $x \in \operatorname{co} \{b_k\}_k$ (with the $b_k$ being distinct
and finite in number) and $x \notin \{ b_k \}_k $. Then $x = \sum_k \lambda_k b_k$ where $\lambda_k \ge 0$, $\sum_k \lambda_k = 1$. Since $x \notin \{ b_k \}_k $, there must be at least one $\lambda_i \in (0,1)$. Then $x = \lambda_i b_i + (1 -\lambda_i) {1 \over \sum_{k \neq i} \lambda_k }\sum_{k \neq i} \lambda_k b_k$ and since $b_i, {1 \over \sum_{k \neq i} \lambda_k }\sum_{k \neq i} \lambda_k b_k \in \operatorname{co} \{b_k\}_k$ we see that $x$ cannot be an extreme point. Hence the extreme points must be a subset of the $b_k$.
(Aside: The above proof is not quite correct as it is possible that $b_i = {1 \over \sum_{k \neq i} \lambda_k }\sum_{k \neq i} \lambda_k b_k$. If this is the case, then we can write $x = {1 \over \sum_{k \neq i} \lambda_k }\sum_{k \neq i} \lambda_k b_k$ and repeat the process as necessary until $b_i \neq {1 \over \sum_{k \neq i} \lambda_k }\sum_{k \neq i} \lambda_k b_k$.)
To see why the $\pm e_k$ are extreme, we have the following useful result:
Suppose $C$ is convex, $h$ some direction, and that $b \in C$ is the unique solution to the problem $\langle h, b \rangle = \sup_{c \in C} \langle h, c \rangle$. Then $b$ is an extreme point of $C$. (This is straightforward to prove by contradiction.) Note that this is a sufficient, not necessary requirement for $b$ to be extreme.
Proof: Suppose that $b \in C$ is the unique solution to the problem $\langle h, b \rangle = \sup_{c \in C} \langle h, c \rangle$
for some direction $h$, but that $b$ is not an extreme point. Then there are $y,z \in C$ distinct from $b$ and
$\alpha \in (0,1)$ such that $b= \alpha y + (1-\alpha)z$. Since $\langle h, b \rangle = \sup_{c \in C} \langle h, c \rangle \ge \alpha \langle h, y \rangle + (1-\alpha) \langle h, z \rangle = \langle h, b \rangle $, we see that $\langle h, y \rangle = \langle h, z \rangle= \langle h, b \rangle$, which contradicts the fact that $b$ is the unique minimiser.
If we choose $h = e_1$ then we see that $\langle e_1, e_1 \rangle = 1 =\sup_{x \in {\cal A}} \langle e_1, x \rangle$, hence $e_1$ is extreme. The other points follow in a similar manner.
Find the extremal points of $\{x \in \mathbb{R}^n \mid \sum_{i=1}^n \lvert x_i \rvert \le 1\}$
Find the extremal points of $K_1 := \{x \in \mathbb{R}^n \mid \sum_{i=1}^n \lvert x_i \rvert \le 1\}$
I have shown that $K_1$ is convex and that the following set is extremal:
$$M_{K_1} := \biggl\{ \pm e_i \mid e_i := (\underbrace{0, \cdots, 0}_{i-1},1, 0, \cdots) \in \mathbb{R}^n \biggr\}.$$
But I do not see how I could formally show that these are indeed ALL extremal points. Could you help me?
(Instead of denoting $x_i$ to be the $i$th entry of $x$, I will write $x \cdot e_i$, since the notation $e_i$ makes this confusing.)
First, note that if $x \in K_1$ does not take this form, and $|x \cdot e_i| = 1$ for some $i$, then $x \cdot e_j = 0$ for all $j \neq i$, and hence $x \in M_{K_1}$. To see this, suppose $|x \cdot e_i| = 1$. Then,
$$\sum_{j \neq i} |x \cdot e_j| = \sum_{j \ge 1} |x \cdot e_j| - |x \cdot e_i| = 1 - 1 = 0.$$
If $|x \cdot e_j| > 0$ for any $j \neq i$, then we would have the left side be strictly positive, and hence the claim holds.
So, suppose $x \notin M_{K_1}$, and let $i$ be such that $x \cdot e_i \neq 0$, and note that $|x \cdot e_i| < 1$. Let
$$N = \sum_{j \neq i} |x \cdot e_j| = 1 - |x \cdot e_i| \in (0, 1).$$
Define
$$y = \frac{x - (x \cdot e_i) e_i}{N}.$$
Then
$$y \cdot e_j = \begin{cases} \dfrac{x \cdot e_j}{N} & \text{if }j \neq i \\ 0 & \text{if }j = i. \end{cases}$$
Hence,
$$\sum_{j \ge 1} |y \cdot e_j| = \sum_{j \neq i} \frac{|x \cdot e_j|}{N} = \frac{N}{N} = 1,$$
and so $y \in K_1$. I claim that
$$x = Ny + (1 - N)\operatorname{sgn}(x \cdot e_i)e_i.$$
Note that $\operatorname{sgn}(x \cdot e_i)e_i \in M_{K_1} \subseteq K_1$, so we will have $y$ as a strict convex combination of two distinct elements of $K_1$, proving $x$ is not extreme.
We have,
\begin{align*}
x &= x - (x \cdot e_i)e_i + (x \cdot e_i)e_i \\
&= Ny + |x \cdot e_i|\operatorname{sgn}(x \cdot e_i)e_i \\
&= Ny + (1 - N)\operatorname{sgn}(x \cdot e_i)e_i,
\end{align*}
completing the proof. Thus, if $x \notin M_{K_1}$, then $x$ is not extreme. |
|
