I am studying Boyd's convex optimization book and came across the following two concepts, which I couldn't explain to myself why. It was mentioned in the book that the set $C$ with $L_\infty$-norm:
$C = \{x\ |\ \|x_i\|\le 1,\ i = 1, \cdots, n\}$
can be described in the form with $2n$ linear inequalities $±e_i^Tx\le 1$, Where $e_i$ is the ith unit vector. Could someone elaborate on this?
The book continues and claims that at least $2^n$ points are needed to describe it in the convex hull form of $\{\theta_1v_1 + · · · + \theta_kv_k\ |\ \theta_1 + · · · + \theta_m = 1, \theta_i\ge 0,\ i = 1, \cdots , k\}$:
$C = \boldsymbol{\rm conv}\{v_1, \cdots, v_{2^n}\}$
where $v_1, \cdots, v_{2^n}$ are the $2^n$ vectors all of whose components are 1 or −1. Also, I could not figure out why this is a true statement. I would appreciate any hint so I can understand these two points.
Assume $ f \left( x \right) $ is a convex function and one wants to solve the following:
$$\begin{alignat*}{3} \arg \min_{x} & \quad & f \left( x \right) \\ \text{subject to} & \quad & \left\| x \right\|_{\infty} \leq 1 \end{alignat*}$$
What does it means $ \left\| x \right\|_{\infty} \leq 1 $?
Well, by the definition of the $ {L}_{\infty} $ norm it means:
$$ \max_{i} \left| {x}_{i} \right| \leq 1 $$
If the maximum is smaller than 1 we could replace it by having all elements less than 1:
$$ \max_{i} \left| {x}_{i} \right| \leq 1 \Leftrightarrow \forall i \, \left| {x}_{i} \right| \leq 1 $$
Now, using the property of the Absolute Function $ \left| \cdot \right| $:
$$ \max_{i} \left| {x}_{i} \right| \leq 1 \Leftrightarrow \forall i \, \left| {x}_{i} \right| \leq 1 \Leftrightarrow \forall i \, -1 \leq {x}_{i} \leq 1 $$
Now, if $ x \in \mathbb{R}^{n} $ the last term is basically 2 $ 2 n $ simple equations.
Which means our convex problem can be reformulated as:
$$\begin{alignat*}{3} \arg \min_{x} & \quad & f \left( x \right) & \quad \\ \text{subject to} & \quad & {x}_{i} \leq 1 & \quad \forall i \\ & \quad & -{x}_{i} \leq 1 & \quad \forall i \end{alignat*}$$