Computing the Signed Distance Between Overlapping Ellipsoids
本文提出一个O(n^6)算法，通过将KKT条件转化为多项式方程并求解双参数二次特征值问题，精确计算重叠椭球体之间的有符号距离，解决了非凸优化难题。
Computing the signed distance between two ellipsoids is a convex optimization problem when the two ellipsoids have no intersection, but it becomes nonconvex when the ellipsoids overlap. Efficient algorithms for convex optimization problems are thus not guaranteed to find the correct signed distance between overlapping ellipsoids. In this paper, we first show that computing the signed distance is equivalent to minimizing the norm along the boundary of the Minkowski difference. We then derive an algorithm with running time $O(n^6)$, where $n$ is the dimension of the ellipsoids, that obtains a global minimizer on the boundary of the Minkowski difference and hence provides the exact signed distance. The algorithm first finds all the points that satisfy the Karush--Kuhn--Tucker (KKT) conditions, and then identifies a relevant KKT point with the smallest signed distance. The primary difficulty in computing the KKT points is that they are the solutions of two bivariate rational equations, whose poles are not known explicitly. Our key step is to convert the rational equations into polynomial equations, which we do by constructing certain bivariate matrix pencils whose zeros of determinants are the zeros of the rational functions. This reduces the problem to a two-parameter quadratic eigenvalue problem, which can be solved via a single-parameter linear eigenvalue problem of larger (squared) size, for which reliable algorithms are available. Thus we provide the first algorithm for computing the signed distance between overlapping ellipsoids with polynomial complexity.