From coefficients to samples: a new approach to SOS optimization
From coefficients to samples: a new approach to SOS optimization
复制标题
从系数到样本：SOS 优化的新方法
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
P. Parrilo
中科院分区：
文献类型：
--
作者：
Johan Löfberg;P. Parrilo
我们介绍了一种新的方法来数值求解由多元多项式的平方和(SOS)分解引起的半定松弛。该方法基于一种新的SOS表示法，其中多项式由离散采样点的一组有限值来表示。这些技术具有非常吸引人的理论和数值性质；相关的半定程序条件更好，并且具有秩1性质，使得内点方法中搜索方向的快速计算成为可能。用实例说明了结果，并与以前的技术进行了初步的比较。
We introduce a new methodology for the numerical solution of semidefinite relaxations arising from the sum of squares (SOS) decomposition of multivariate polynomials. The method is based on a novel SOS representation, where polynomials are represented by a finite set of values at discrete sampling points. The techniques have very appealing theoretical and numerical properties; the associated semidefinite programs are better conditioned, and have a rank one property that enables a fast computation of the search directions in interior point methods. The results are illustrated with examples, and a preliminary implementation is compared with previous techniques.