Facets of the convex hull as solution of an optimization problem?

527 Views Asked by At

Given $N$ points $x_1, x_2, ..., x_N \in \mathbb{R}^n$, consider their convex hull $$\mathcal{C} = \text{conv}( \{ x_1, ..., x_n \} ) = \bigcap_{j=1}^{J} \{ x \in \mathbb{R}^n : \ A_j x \leq b_j \} $$ where $\ A_1, ..., A_J \in \mathbb{R}^{1 \times n}$, $\ b_1, ..., b_J \in \mathbb{R}$.

Consider the half-spaces containing all the points, i.e. of the kind $$\{ x \in \mathbb{R}^n : \ A x \leq b, \ A x_j \leq b \ \forall j \in [1,J] \}$$

A first example. An optimizer of the program $$ \min_{A,b} \ \max_{j \in [1,J]} \text{dist}\left( x_j, \{ x \in \mathbb{R}^n : \ A x \leq b \} \right) \\ \text{subject to: } Ax_j \leq b \ \ \forall j \in [1,N] $$

corresponds to an half-space containing all the points $x_j$'s, and with minimum distance from the farthest point. Any such half-space clearly passes through a facet of $\mathcal{C}$.

For instance, on the plane, i.e. $n=2$, if $x_1, x_2 = (\pm 1, 0)$, $x_3, x_4 = (0, \pm 1)$, we have $4$ optimizers for the above program, namely the ones passing through the $4$ facets of $\mathcal{C}$.

In general, the solutions of the above optimization program do not correspond to $all$ the facets of $\mathcal{C}$.

Question. How to get $all$ the half-spaces passing through the facets of $\mathcal{C}$ via the solutions of an optimization program of the following kind?

$$ \min_{A,b} \ f( \{ x_1, ..., x_N \}, A, b ) \\ \text{subject to: } Ax_j \leq b \ \ \forall j \in [1,N] $$

In other words, I am looking for a distance-like function $f$, which depends on $all$ the points in its first argument, so that solving the optimization program I get $all$ the half-spaces of the convex hull.