Closed-form expression for intersection of convex hulls of two finite sets of points

Question

Consider an optimization problem where the decision variables are two finite subsets of $\mathbb{R}^n$ each containing $k$ elements: $$ X = [x_1, x_2, \dots, x_k],\ \ Y = [y_1, y_2, \dots, y_k] $$ We wish to solve the following problem for arbitrary smooth $f$: $$ \begin{split} \text{minimize} \quad & f(X, Y) \\ \text{subject to} \quad & \text{Conv}(X) \cap \text{Conv}(Y) = \emptyset. \end{split} $$

Algorithms for nonlinear, nonconvex optimization like Sequential Quadratic Programming require that the optimization problem can be written as:

$$ \begin{split} \text{minimize} \quad & f(x) \\ \text{subject to} \quad & g(x) \leq 0 \\ \end{split} $$ (where $g$ may be multidimensional). Is it possible to write the convex hull constraint in the closed form $g(x) \leq 0$?

Answer 1

Take a look at this page by Komei Fukuda (link) and the others under faq in Polyhedral Computation. It's a good start.

Answer 2

Here is one solution I have reached. It requires adding new variables to the problem though.

If the convex hulls do not intersect, there exists $a \in \mathbb{R}^n,\ a \neq 0, \ b \in \mathbb{R}$ such that the hyperplane $a^T x = b$ strictly separates $\text{Conv(X)}$ and $\text{Conv}(Y)$, by the separating hyperplane theorem. Strict separation comes from the fact that the convex hull of a finite set of points is both closed and bounded. The converse is also true: if a strictly separating hyperplane exists, the sets are disjoint.

By elementary properties of convex sets, separating $\text{Conv(X)}$ and $\text{Conv}(Y)$ is equivalent to separating $X$ and $Y$. So we can find the separating hyperplane by solving the following linear program:

$$ \begin{split} \text{find}\quad & a,\ b \\ \text{subject to} \quad & a^T x_i + \epsilon \leq b\quad \forall\ i \\ & a^T y_i - \epsilon \geq b\quad \forall\ i \end{split} $$

where $\epsilon > 0$ is added because LP solvers generally do not handle strict equality constraints. We can add the LP to the original problem. The LP constraints become quadratic constraints in the full problem because the $x_i,\ y_i$ are also decision variables. However, the quadratic constraints still fit the $g(x) \leq 0$ form.