论文标题
恒星凸的内部和外部近似值
Inner and Outer Approximations of Star-Convex Semialgebraic Sets
论文作者
论文摘要
我们考虑使用多项式函数的级别集合近似于半ge的问题。在这种情况下，要寻求最小体积外近似值和/或最大体积内部近似是标准的。由于任意多项式的系数与其级别集合的体积之间没有已知的关系，因此以前的作品根据椭圆形拟合中常用的决定因素和痕量目标提出了启发式方法。对于Star-Convex半gebraic组的情况，我们提出了一个新的目标，该目标既可以产生外部和内部近似值，同时最小化各自体积的比率。这个目标是规模不变且容易解释的。给出了数值示例，这些示例表明所获得的近似通常比现有启发式方法返回的近似更紧。我们还提供了通过查找其内核的内部和外部近似值来确定半格式设置的恒星 - 跨体的方法。
We consider the problem of approximating a semialgebraic set with a sublevel-set of a polynomial function. In this setting, it is standard to seek a minimum volume outer approximation and/or maximum volume inner approximation. As there is no known relationship between the coefficients of an arbitrary polynomial and the volume of its sublevel sets, previous works have proposed heuristics based on the determinant and trace objectives commonly used in ellipsoidal fitting. For the case of star-convex semialgebraic sets, we propose a novel objective which yields both an outer and an inner approximation while minimizing the ratio of their respective volumes. This objective is scale-invariant and easily interpreted. Numerical examples are given which show that the approximations obtained are often tighter than those returned by existing heuristics. We also provide methods for establishing the star-convexity of a semialgebraic set by finding inner and outer approximations of its kernel.
