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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.