Tractable fitting with convex polynomials via sum-of-squares
Tractable fitting with convex polynomials via sum-of-squares
复制标题
通过平方和与凸多项式进行易于处理的拟合
DOI：
10.1109/cdc.2005.1582399
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
S. Boyd
中科院分区：
文献类型：
--
作者：
A. Magnani;S. Lall;S. Boyd
我们考虑了给定数据的拟合问题(u<；inf&>；1；/inf&>；，y<；inf&>；1；/inf&>；)，...，(u<；inf&>；m；/inf&>，y<；inf&>；m；/inf&>；)，其中u<；inf&>；i<；/inf&>；∈R∈R具有一个凸多项式f，给出了一种利用平方和多项式来解决这个问题的方法。该技术被扩展为仅在指定区域上强制执行f的凸性。给出了一种用多项式的凸次水平集来拟合点集凸包的算法。该问题是求复盖集合的最小体积椭球体问题的自然推广。该算法与求解最小体积椭球问题的算法一样，具有仿射坐标变换不变的性质。我们将这一技术推广到适合多项式子水平集的任意并集和交集。
We consider the problem of fitting given data (u<inf>1</inf>,y<inf>1</inf>),...,(u<inf>m</inf>,y<inf>m</inf>) where u<inf>i</inf>∈ R<sup>n</sup>and y<inf>i</inf>∈ R with a convex polynomial f. A technique to solve this problem using sum of squares polynomials is presented. This technique is extended to enforce convexity of f only on a specified region. Also, an algorithm to fit the convex hull of a set of points with a convex sub-level set of a polynomial is presented. This problem is a natural extension of the problem of finding the minimum volume ellipsoid covering a set. The algorithm, like that for the minimum volume ellipsoid problem, has the property of being invariant to affine coordinate transformations. We generalize this technique to fit arbitrary unions and intersections of polynomial sub-level sets.