I've been struggling with this for quite some time. I'm looking for the extreme points of some convex set. Let $y, a \in \mathbb{R}^n$ with $y \in \{-1, 1\}^n$, and with the following restrictions on $a$:
- $a_i \geq 0 \ \forall i $
- $ \sum_i a_i = 2 $
- $\langle a, y\rangle=0$
This defines a convex set $C$, which is a hyperplane intersected with the $n$ dimensional scaled simplex. I'm pretty sure the extreme points of $C$ is just the set of all $a$ such that $a_i, a_j = 1, \ a_k = 0, k \not = i, k \not = j $ for some $i$ and some $j$.
I'm trying to show that these are the extreme points. I've tried to express some $a$ as the convex combination of $x, y \in C$, and find that either $x$ or $y$ has to be $a$, but so far I haven't been able to show that.
There may be some other ways, namely I'm aware that there's a theorem that says extreme points correspond to basic feasible solutions to an optimization problem defined by the restrictions mentioned above, but I don't want to use that.
Best Answer
Not all such $a$ are going to be in $C$, because there's an additional condition - $y_i$ and $y_j$ must be of opposite sign, otherwise the inner product constraint isn't satisfied (which also means that if there isn't at least one of each, then $C = \{0\}$).
Then we want to prove three things:
That the set $A = \{a \in \mathbb{R}^n : \exists i,j\ (a_i = a_j = y_i = -y_j = 1), (k \neq i, j \implies a_k = 0) \}$ is a subset of $C$.
That $a \in A$ implies that $a$ is an extreme point of $C$.
That if $x$ is an extreme point of $C$, then $x \in A$.
I think 1 is reasonably simple. To prove 2, I'm going to use the following property of an extreme point:
Consider $a \in A$ such that $a_i = a_j = y_i = 1$, $y_j = -1$ and $a_k = 0$ for any $k \neq i, j$. Suppose we have $x \in \mathbb{R}^n$ such that $a + x, a - x \in C$. Then by definition:
$a_k \pm x_k \geq 0 \implies \pm x_k \geq 0 \implies x_k = 0$ when $k \neq i,j$.
$\sum (a_k + x_k) = a_i + a_j + x_i + x_j = 2 + x_i + x_j = 2$ but since $x_i, x_j \geq 0$ we must have $x_i, x_j = 0$.
Thus $x = 0$, meaning that $a$ is an extreme point of $C$.
Finally, we want to prove 3, that all extreme points of $C$ are in $A$. I'm going to start by defining $Y^+ := \{i : y_i = +1\}$ and $Y^- := \{i : y_i = -1\}$, i.e. the indices of positive and negative values of $y_i$. I claim that for $p \in C \setminus A$, $p$ must have two non-zero indices in either $Y^+$ or $Y^-$ (to prove, assume that $p$ has at most one non-zero index in each, and you'll quickly prove that those indices must both be 1, so $p \in A$ which is a contradiction). Without loss of generality, assume that they're in $Y^+$, so in other words there are distinct indices $i, j$ such that $p_i, p_j \gt 0$.
Then take $\epsilon = \min(p_i, p_j) / 2$ and consider $x \in \mathbb{R}$ such that $x_i = \epsilon, x_j = -\epsilon, x_k = 0$ for $k \neq i, j$. It should be pretty easy to prove that $p \pm x \in C$, which means that $p$ cannot be an extreme point of $C$, which proves that all of the extreme points lie in $A$.