# Polyhedra to Simplex by using convex combination of vertices

Optimization problems over linear constraints (defining a convex polyhedron) can be written as optimization over a simplex in a higher dimension. Let $$\mathcal{P}$$ be a bounded polyhedron, and the vertices of this polyhedron are saved as columns of the matrix $$V$$. Then, any feasible solution $$x \in \mathcal{P}$$ can be found by some convex combination of columns of $$V$$. If $$x \in \mathbb{R}^n$$, and $$V \in \mathbb{R}^{n \times m}$$, then we can always find some $$y \in \mathbb{R}^m$$ with $$x = Vy$$. Since $$y$$ defines the weights of a convex combination, it lies in a standard simplex.

In other words, $$\min \{ f(x) \ : \ x \in \mathcal{P} \} \equiv \min\{f(Vy) \ : \ y \geq 0, \ \sum_{i=1}^m y_i = 1 \}$$. Sometimes, solving the lifted problem makes our life easier (I will soon cite some examples here). However, as you can notice, $$m$$ is typically large. There are some examples of polyhedra that have linearly or polynomially many vertices. Some examples:

• 1-norm constraint ($$c \geq 0$$): $$\mathcal{P} = \{x \in \mathbb{R}^n \ : \ ||x||_1 \leq c \}$$ with $$V = \begin{bmatrix} c\cdot \mathbb{I}_{n\times n} & -c\cdot\mathbb{I}_{n\times n} \end{bmatrix}$$
• $$\leq$$-simplex: $$\mathcal{P} = \{x \in \mathbb{R}^n \ : \ x \geq 0, \ \sum_{i=1}^m x_i\leq 1\}$$ with $$V = \begin{bmatrix} \mathbb{I}_{n\times n} & \mathbf{0}_{n \times 1}\end{bmatrix}$$.

I just wanted to ask if there are some other explicit examples, where, we would be able to detect (linearly many, or polynomially) vertices of a polyhedron in closed form. I know there are algorithmic ways to enumerate vertices of any polyhedron, but I am looking for some closed form polyhedron-vertex pairs that usually appear in convex optimization.