Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1137/140979654 | SIAM JOURNAL ON OPTIMIZATION |
Keywords | Field | DocType |
ellipsoids,signed distance,nonconvex optimization,KKT conditions,Minkowski difference,two-parameter eigenvalue problem,Bezoutian | Discrete mathematics,Mathematical optimization,Combinatorics,Ellipsoid,Signed distance function,Minkowski space,Karush–Kuhn–Tucker conditions,Bivariate analysis,Convex optimization,Mathematics | Journal |
Volume | Issue | ISSN |
25 | 4 | 1052-6234 |
Citations | PageRank | References |
2 | 0.41 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Satoru Iwata | 1 | 759 | 70.03 |
| Yuji Nakatsukasa | 2 | 97 | 17.74 |
| Akiko Takeda | 3 | 196 | 29.72 |