5
$\begingroup$

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.

$\endgroup$

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.