论文标题
一种有效的方法来验证椭圆形的包含
An Efficient Method to Verify the Inclusion of Ellipsoids
论文作者
论文摘要
我们提出了一种新的方法，用于确定给定的N维椭圆形是否包含另一个（可能具有不同的中心）。该方法包括构建特定的凹函数并确定其在紧凑的间隔中是否具有大于-1的值，该间隔是[0,1]的子集。这可以通过双分解算法方法有效地完成，该算法可以保证在有限数量的迭代中停止。该方法的初始化需要O（n^3）浮点操作，并评估此功能及其衍生物需要O（n）。这也可以推广以计算包含有限数量的N ellipsoids的凸二次函数的最小级别集。在我们具有随机生成的椭圆形的基准测试中，与基于半决赛编程的经典方法相比，我们的算法对尺寸n = 3和2294倍的椭圆形的算法更快地执行27倍，维度n = 100。我们在控制理论领域中说明了该方法的有用性。
We present a novel method for deciding whether a given n-dimensional ellipsoid contains another one (possibly with a different center). This method consists in constructing a particular concave function and deciding whether it has any value greater than -1 in a compact interval that is a subset of [0,1]. This can be done efficiently by a bisection algorithm method that is guaranteed to stop in a finite number of iterations. The initialization of the method requires O(n^3) floating-point operations and evaluating this function and its derivatives requires O(n). This can be also generalized to compute the smallest level set of a convex quadratic function containing a finite number of n-ellipsoids. In our benchmark with randomly generated ellipsoids, when compared with a classic method based on semidefinite programming, our algorithm performs 27 times faster for ellipsoids of dimension n=3 and 2294 times faster for dimension n=100. We illustrate the usefulness of this method with a problem in the control theory field.
