Bijection between extreme points of convex sets

Question

Below problem 2.8.15 from Linear and Nonlinear Programming by D. Luenberger 5th edition is presented as well as my attempt at a proof.

$\textbf{Problem: } $Let $S$ be a convex set in $E^n$ and $S^∗$ a convex set in $E^m$. Suppose $\mathbf{T}$ is an m × n matrix that establishes a one-to-one correspondence between $S$ and $S^∗$, i.e., for every $\mathbf{s}$ $\in$ $S$ there is $\mathbf{s}^∗$ $\in$ $S^∗$ such that $\mathbf{Ts}$ = $\mathbf{s}^*$, and for every $\mathbf{s}^*$ $\in$ $S^*$ there is a single $\mathbf{s}$ $\in$ $S$ such that $\mathbf{Ts}$ = $\mathbf{s}^*$. Show that there is a one-to-one correspondence between extreme points of $S$ and $S^∗$.

$\textbf{Strategy: }$ My attempt at solving the problem includes the following steps:

1. Prove a one-to-one correspondence between the subset of internal (non-extreme) points in $S$ and the subset of internal (non-extreme) points in $S^*$.
2. Show that a one-to-one correspondence exists between the subset of extreme points in $S$ and the subset of extreme points in $S^*$.

$\textbf{Proof: }$

Define $S_I$ = {$\mathbf{s}$ | $\mathbf{s}$ $\in{S}$ $\land$ $\mathbf{s}$ is an internal point }.

Define $S_I^*$ = {$\mathbf{s^*}$ | $\mathbf{s^*}$ = $\mathbf{Ts}$ $\land$ $\mathbf{s}$ $\in{S}$ $\land$ $\mathbf{s}$ is an internal point }.

$\textbf{Claim 1: }$ $\textit{i)}$ All elements $\mathbf{s}$ $\in$ $S_I^*$ are internal points. $\textit{ii)}$ The sets $S_I$ and $S_I^*$ have a one-to-one correspondence.

$\textbf{Proof of Claim 1: }$

$\textit{Proof of i): Proof by Contradiction}$

Assume that the first part of the claim is not true - there exists an element $\mathbf{s}$ $\in$ $S_I^*$ that is an extreme point. By definition, all points $\mathbf{s}$ $\in$ $S_I$ are internal, thus they can be represented as the weighted average of two other points in the set.

$\mathbf{s}$ = $\lambda$ $\cdot$ $\mathbf{s}_0$ + (1 - $\lambda$) $\cdot$ $\mathbf{s}_1$ for some $\mathbf{s}_0$, $\mathbf{s}_1$ $\in$ $S_I$ and $\lambda$ $\in$ $\left(0, 1\right)$

By definition, all points $\mathbf{s}^*$ $\in$ $S_I^*$ can be represented as

$\mathbf{s}^*$ = $\mathbf{Ts}$

Thus, all points $s^*$ $\in$ $S_I^*$ can be represented as

$s^*$ = $\mathbf{T}$ ($\lambda$ $\cdot$ $\mathbf{s}_0$ + (1 - $\lambda$) $\cdot$ $\mathbf{s}_1$)

$s^*$ = $\lambda$ $\mathbf{T}$ $\cdot$ $\mathbf{s}_0$ + (1 - $\lambda$) $\mathbf{T}$ $\cdot$ $\mathbf{s}_1$

We have shown that each point $s^*$ $\in$ $S_I^*$ can be represented as the weighted average of two other points in $S_I^*$, meaning that no point in $S_I^*$ is extreme, arriving at a contradiction. $\textit{Q.E.D}$

$\textit{Proof of ii): }$

It is given that $\mathbf{T}$ is a bijective mapping from $S$ to $S^*$. By definition, $S_I^*$ uses this mapping to construct its elements from $S_I$. Thus, there is a one-to-one correspondence between $S_I$ and $S_I^*$. $\textit{Q.E.D.}$

$\textbf{Corolary to Claim 1: }$ The set $S_I^*$ contains all internal points and only the internal points of $S^*$.

Define $S_E$ = {$\mathbf{s}$ | $\mathbf{s}$ $\in{S}$ $\land$ $\mathbf{s}$ is an extreme point }.

Define $S_E^*$ = {$\mathbf{s}^*$ | $\mathbf{s}$ $\in{S}^*$ $\land$ $\mathbf{s}^*$ is an extreme point }.

Since a point is either extreme or internal, $S_E$ = $S$ - $S_I$ and $S_E^*$ = $S^*$ - $S_I^*$. Furthermore, since there is a one-to-one correspondence between $S$ and $S^*$ and between $S_I$ and $S_I^*$, we can conclude that there is a one-to-one correspondence between $S_E$ and $S_E^*$. $\mathit{Q.E.D.}$

$\textbf{Research: }$ I have found a question about the very same problem being asked here, with the difference that it is a general "check my proof" question. I did not find it helpful.

$\textbf{Questions: }$

1. I have concerns about the correctness of the proof of $\textbf{Claim 1.}$ $\textit{part ii)}$. I am unsure if that sort of statement can be made. Is it correct? If yes, how can it be expressed with more rigor?

2. I have strong $\textit{belief}$ that the second part of my strategy is correct, but I do not if this is the proper way to prove it. Once again, if it is correct, how can I show more rigor?

3. Are there any major flaws in my attempted proof? Anything that should be changed styling/notation-wise? Have I asked my question in a proper manner with regard to this forum?

Thank you in advance.

Answer 1

If $C$ is convex, then $e \in C$ is an extreme point of $C$ iff whenever $L$ is a closed line segment contained in $C$ and $e \in \operatorname{ri} L$ then $L=\{e\}$ (this is Rockafellar's characterisation).

The direct argument is straightforward, contradiction just complicates things and hides the essence.

Suppose $T$ is a linear (or affine) map such that $T:S \to S^*$ is bijective. Let $T^{-1}$ be the inverse map $T^{-1}:S^* \to S$ (note that $T$ need not have an inverse in general).

Suppose $e $ is an extreme point of $S$. Let $L=[a,b]$ be a line segment in $S^*$ such that $T(e) \in (a,b)$. Then we must have $e \in (T^{-1}(a), T^{-1}(b)) $ and hence $T^{-1}(a) = T^{-1}(b)$ and so $a=b$. Hence $T(e)$ is an extreme point of $S^*$.

The same argument, mutatis mutandis, applies to extreme points of $S^*$.

The one to one correspondence is provided by $T$.