Let's say we're given two sets of points, $X:=(x_i)_{i\in k_1},Y:=(y_i)_{i\in k_2}\subseteq\mathbb{R}^n$ and their convex hulls $conv(X),conv(Y)$.
Let's assume $conv(X),conv(Y)$ are disjunct. We want to find $x\in conv(X),y\in conv(Y)$ so that the euclidian distance $d(x,y)$ is minimal.
One possible phrasing of this problem as optimization problem would be:
$$
\min_{\lambda_1,\ldots,\lambda_{k_1},\mu_1,\ldots,\mu_{k_2}\in\mathbb{R}}{d}\left(\sum_{i=1}^{k_1}\lambda_ix_i,\sum_{i=1}^{k_2}\mu_iy_i\right) $$,
under the constraints
$$ \begin{align*}
\sum_{i=1}^{k}\lambda_i&=1&\\
\sum_{i=1}^{k_2}\mu_i&=1 &\\
\lambda_i&\geq0 &, i=1,..,k_1\\
\mu_i&\geq0 &, i=1,\ldots,k_2\\
\end{align*}$$
I'm wondering whether there's an easier formulation of this problem which doesn't rely on quadratic optimization.
An iterative algorithm for determining a pair of closest points of two disjunct convex hulls running in linear time can be given as a variant of The Gilbert-Johnson-Keerthi Distance Algorithm.