Sum of squares method for sensor network localization

We formulate the sensor network localization problem as finding the global minimizer of a quartic polynomial. Then sum of squares (SOS) relaxations can be applied to solve it. However, the general SOS relaxations are too expensive to implement for large problems. Exploiting the special features of this polynomial, we propose a new structured SOS relaxation, and discuss its various properties. When distances are given exactly, this SOS relaxation often returns true sensor locations. At each step of interior point methods solving this SOS relaxation, the complexity is , where n is the number of sensors. When the distances have small perturbations, we show that the sensor locations given by this SOS relaxation are accurate within a constant factor of the perturbation error under some technical assumptions. The performance of this SOS relaxation is tested on some randomly generated problems.     

Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals

This paper studies the representation of a positive polynomial f(x) on a noncompact semialgebraic set S={x∈Rⁿ:g₁(x)≥0,…,g_s(x)≥0} modulo its KKT (Karush-Kuhn-Tucker) ideal. Under the assumption that the minimum value of f(x) on S is attained at some KKT point, we show that f(x) can be represented as sum of squares (SOS) of polynomials modulo the KKT ideal if f(x)>0 on S; furthermore, when the KKT ideal is radical, we argue that f(x) can be represented as a sum of squares (SOS) of polynomials modulo the KKT ideal if f(x)≥0 on S. This is a generalization of results in [J. Nie, J. Demmel, B. Sturmfels, Minimizing polynomials via sum of squares over the gradient ideal, Mathematical Programming (in press)], which discusses the SOS representations of nonnegative polynomials over gradient ideals.     

可除的四元数代数上多项式环的Grobner基

设F是一个特征不等于2的域,A是,上的一个可除代数。本文研究了A上多项式环A[x1,X2,…,xn]中理想是有限生成的,以及它的Grobner基;也表明F[x1,x2,…,xn]中有限子集G是F[x1,x2,…,xn]的Griobner基当且仅当G是A[x1,x2,…,xn]中的Grobner基。     

The problem of the motion of a solid in an ideal fluid. Integration of the Clebsch's case

This paper deals with a geometric approach to the integration of Clebsch's case of equations describing the motion of a solid body in an ideal fluid. This problem is defined by a nonlinear system of 6 differential equations admitting 4 polynomial first integrals. We show that the intersection of surface levels of these integrals can be completed to an abelian surface, i.e., a 2-dimensional algebraic torus. Also, we prove that the problem can be linearized, i.e., can be written in terms of abelian integrals, on a Prym variety of a genus 3 curve obtained naturally. Received August 1998     

Polynomial interpolation in several variables,cubature formulae,and ideals[*]Supported by the National Science Foundation under Grant DMS-9802265.

We discuss polynomial interpolation in several variables from a polynomial ideal point of view. One of the results states that if I is a real polynomial ideal with real variety and if its codimension is equal to the cardinality of its variety, then for each monomial order there is a unique polynomial that interpolates on the points in the variety. The result is motivated by the problem of constructing cubature formulae, and it leads to a theorem on cubature formulae which can be considered an extension of Gaussian quadrature formulae to several variables. This revised version was published online in June 2006 with corrections to the Cover Date.     

High-order sum-of-squares structured tensors:theory and applications

Tensor decomposition is an important research area with numerous applications in data mining and computational neuroscience.An important class of tensor decomposition is sum-of-squares(SOS)tensor decomposition.SOS tensor decomposition has a close connection with SOS polynomials,and SOS polynomials are very important in polynomial theory and polynomial optimization.In this paper,we give a detailed survey on recent advances of high-order SOS tensors and their applications.It first shows that several classes of symmetric structured tensors available in the literature have SOS decomposition in the even order symmetric case.Then,the SOS-rank for tensors with SOS decomposition and the SOS-width for SOS tensor cones are established.Further,a sharper explicit upper bound of the SOS-rank for tensors with bounded exponent is provided,and the exact SOS-width for the cone consists of all such tensors with SOS decomposition is identified.Some potential research directions in the future are also listed in this paper.     

基于符号数值混合计算的混成系统Lyapunov函数构造

基于平方和松弛和有理向量恢复,提出了一种符号数值混合计算方法来构造多项式Lyapunov函数以判定非线性混成系统的稳定性,首先,为Lyapunov函数预定一个给定次数的多项式模板,则Lyapunov函数构造问题可转化为相应的带参数的多项式优化问题,然后运用平方和松弛方法求得一个近似的数值多项式Lyapunov函数,再应用高斯-牛顿精化和有理向量恢复将数值多项式转化为验证的有理多项式Lyapunov函数.     

切换多项式非线性系统的输入-状态稳定性

利用耗散不等式研究了切换多项式非线性系统的输入-状态稳定性分析问题,在任意切换信号下,给出了使得切换多项式非线性系统输入-状态稳定的充分条件.采用平方和分解方法来寻找切换多项式非线性系统的输入-状态稳定共同Lyapunov函数.数值算例验证了所提方法的可行性.     

幂格的理想与素理想

研究了幂格的理想和素理想,建立了格的理想与格上幂格的理想的一种联系,获得了格的理想(素理想)与它的商格的理想(素理想)之间的关系。     

A facial reduction algorithm for finding sparse SOS representations

The facial reduction algorithm reduces the size of the positive semidefinite cone in SDP. The elimination method for a sparse SOS polynomial [M. Kojima, S. Kim, H. Waki, Sparsity in sums of squares of polynomials, Math. Program. 103 (2005) 45-62] removes monomials which do not appear in any SOS representations. In this paper, we establish a relationship between a facial reduction algorithm and the elimination method for a sparse SOS polynomial.     

The Complexity of Computing the Hilbert Polynomial of Smooth Equidimensional Complex Projective Varieties

We continue the study of counting complexity begun in [13], [14], [15] by proving upper and lower bounds on the complexity of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number of complex common zeros of a finite set of multivariate polynomials. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. Moreover, we prove that the more general problem of computing the Hilbert polynomial of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower bound in Bach [1].     

BCK-代数的模糊代数理想

在有界可换BCK-代数上引入了Fuzzy代数理想的概念,给出了Fuzzy代数理想的某些特征,讨论了Fuzzy理想与Fuzzy代数理想的关系。最后描述了全体Fuzzy集的BCK-代数特征。     

Output-feedback synchronization of chaotic systems based on sum-of-squares approach

This paper investigates the synchronization of chaotic systems using an output feedback polynomial controller. As only output system states are considered, it makes the controller design and system analysis more challenging compared to the full-state feedback control schemes. To study the system stability and synthesize the output feedback polynomial controller, Lyapunov stability theory is employed. Sufficient stability conditions are derived in terms of sum of squares (SOS) conditions to guarantee the system stability and aid the controller synthesis. A genetic algorithm-based SOS technique is proposed to find the solution to the SOS conditions and the parameter values of the output feedback polynomial controller. A simulation example is employed to illustrate the effectiveness of the proposed approach.     

An SOS-QE Approach to Nonlinear Gain Analysis for Polynomial Dynamical Systems

Combined use of the method of sum of squares (SOS) and quantifier elimination (QE) is discussed with regard to the problem of nonlinear gain analysis for a class of dynamical systems. SOS, a numerical method, is used to search for the structure of a gain function quickly, and QE, a symbolic method, determines all gain functions in the structure to find the minimum gain function. QE can also be used for the infeasibility check of gain structures. A proposed analysis procedure for polynomial dynamical systems prevents unnecessary searching for a gain structure. Two illustrative examples show the effectiveness of the proposed gain analysis procedure.     

REAL PIECEWISE ALGEBRAIC VARIETY

We give definitions of real piecewise algebraic variety and dimension.By using the techniques of real radical ideal,P-radical ideal,affine Hilbert polynomial,Bernstein-net from of polynomials on simplex,and decomposition of semi-algebraic set,etc.,we deal with the dimension of the real piecewise algebraic variety and real Nullstellensatz in C^μ spline ring.     

分块平方和分解

本文定义了分块平方和可分解多项式的概念.粗略地说,它是这样一类多项式,只考虑其支撑集(不考虑系数)就可以把它的平方和分解问题等价地转换为较小规模的同类问题(换句话说,相应的半正定规划问题的矩阵可以分块对角化).本文证明了近年文献中提出的两类方法—分离多项式(split polynomial)和最小坐标投影(minimal coordinate projection)—都可以用分块平方和可分解多项式来描述,证明了分块平方和可分解多项式集在平方和多项式集中为零测集.     

A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones

This short note extends the sparse SOS (sum of squares) and SDP (semidefinite programming) relaxation proposed by Waki, Kim, Kojima and Muramatsu for normal POPs (polynomial optimization problems) to POPs over symmetric cones, and establishes its theoretical convergence based on the recent convergence result by Lasserre on the sparse SOS and SDP relaxation for normal POPs. A numerical example is also given to exhibit its high potential. Research of M. Kojima supported by Grant-in-Aid for Scientific Research on Priority Areas 16016234. Research of M. Muramatsu supported in part by Grant-in-Aid for Young Scientists (B) 15740054.     

多项式组的特征分解

任一多项式理想的特征对是指由该理想的约化字典序Grobner基G和含于其中的极小三角列C构成的有序对(G,C).当C为正则列或正规列时,分别称特征对(G,C)为正则的或正规的.当G生成的理想与C的饱和理想相同时,称特征对(G,C)为强的.一组多项式的(强)正则或(强)正规特征分解是指将该多项式组分解为有限多个(强)正则或(强)正规特征对,使其满足特定的零点与理想关系.本文简要回顾各种三角分解及相应零点与理想分解的理论和方法,然后重点介绍(强)正则与(强)正规特征对和特征分解的性质,说明三角列、Ritt特征列和字典序Grobner基之间的内在关联,建立特征对的正则化定理以及正则、正规特征对的强化方法,进而给出两种基于字典序Grobner基计算、按伪整除关系分裂和构建、商除可除理想等策略的(强)正规与(强)正则特征分解算法.这两种算法计算所得的强正规与强正则特征对和特征分解都具有良好的性质,且能为输入多元多项式组的零点提供两种不同的表示.本文还给出示例和部分实验结果,用以说明特征分解方法及其实用性和有效性.     

Minimum Ellipsoid Bounds for Solutions of Polynomial Systems via Sum of Squares

We study ellipsoid bounds for the solutions of polynomial systems of equalities and inequalities. The variable μ can be considered as parameters perturbing the solution x. For example, bounding the zeros of a system of polynomials whose coefficients depend on parameters is a special case of this problem. Our goal is to find minimum ellipsoid bounds just for x. Using theorems from real algebraic geometry, the ellipsoid bound can be found by solving a particular polynomial optimization problem with sums of squares (SOS) techniques. Some numerical examples are also given.     

An algorithmic approach to the Polydegree Conjecture for plane polynomial automorphisms

We study the interaction between two structures on the group of polynomial automorphisms of the affine plane: its structure as an amalgamated free product and as an infinite-dimensional algebraic variety. We introduce a new conjecture, and show how it implies the Polydegree Conjecture. As the new conjecture is an ideal membership question, this shows that the Polydegree Conjecture is algorithmically decidable. We further describe how this approach provides a unified and shorter method of recovering existing results of Edo and Furter.