Extreme points of the convex set $S:=\{\mathbf x \in \mathbb R^n : \|L\mathbf x\|_{*}\le 1\}.$

Question

Is there any algorithm to obtain (approximate) extreme points (assuming the set of extreme points is non empty) of any convex set in a similar way like the well known simplex algorithm gets the extreme points in case of polytope?

The convex set that I am interested in is a subset of $\mathbb R^n$ defined as

$$S:=\{\mathbf x \in \mathbb R^n : \| L \mathbf x\|_{*} \le 1 \}$$

where $\|\cdot\|_*$ is norm in $\mathbb R^{2n}$ and $L$ is linear operator mapping from $\mathbb R^n$ to $\mathbb R^{2n}$.

Are there any characterizations that can help in building algorithm that return the extreme point of a set.

---

Definition: A point $z \in S$ is called the extreme point of the convex set $S$ if the set $S - \{z\}$ is convex.

Answer 1

The vector unit $v$ in $n$-space that maps to the shortest possible vector in $2n$-space under $L$ is what you want to find. Then compute $w = Lv$, and let $s = \| w \|$. Then $\frac1s v$ is your desired vector.

How to find short vectors in the image? Compute the SVD of the matrix for $L$, and look at the singular vector corresponding to the smallest singular value.

You might want to try this for a few example maps from $\Bbb R^2$ to $\Bbb R^4$ to get a feel for how/why it works.

Here's an example for $n = 1$. Let $$ L(x) = \pmatrix{3x \\ 4x} = \pmatrix{3 \\ 4} \pmatrix{x} $$ The matrix is $M = \pmatrix{3 \\ 4}$.

The unit vectors in 1-space are $\pmatrix{\pm 1}$, and they map to $\pm \pmatrix{3 \\ 4}$. Those vectors have the same length (namely $5$), so each of them is the shortest possible, and could serve as $v$. But let's follow the instructions. We compute the SVD for $M$ (matlab interaction, somewhat cleaned up):

>> M = [3;4]    
M =    
     3
     4    
>> [u,d,v] = svd(M, 'econ')    
u =    
    0.6000
    0.8000    

d =    
     5    
v =    
     1

In short, $$ \pmatrix{3\\4} = \pmatrix{3/5\\4/5} \pmatrix{5}\pmatrix{1} $$ The smallest (indeed only) singular value is $5$; the corresponding right-eigenvector $v$ is $\pmatrix{1}$. $Lv$ is just $\pmatrix{3\\4}$, so $s = 5$. THen $$ \frac{1}{s} v = \frac{1}{5}\pmatrix{1} = \pmatrix{1/5} $$ is the largest vector in $\Bbb R^1$ that maps under $L$ to a unit vector in $\Bbb R^2$, as required. (Although $\pmatrix{-1/5}$ would also have worked.)