sum of squares (sos) – Optimization Online

Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets

Published: 2007/10/15, Updated: 2008/05/19

Semi-definite Programming (strictly) quasi-concavity, convex hull, convex set, irredundancy, linear matrix inequality (lmi), nonsingularity, positive curvature, semialgebraic set, semidefinite programming, singularity, smoothness, sos-concavity, sum of squares (sos)

The article proves sufficient conditions and necessary conditions for SDP representability of convex sets and convex hulls by proposing a new approach to construct SDP representations. The contributions of this paper are: (i) For bounded SDP representable sets $W_1,\cdots,W_m$, we give an explicit construction of an SDP representation for $conv(\cup_{k=1}^mW_k)$. This provides a technique for … Read more

Sum of Squares Method for Sensor Network Localization

Published: 2006/06/19, Updated: 2006/11/27

Jiawang Nie

Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Network Optimization distance geometry, error bound, graph realization, polynomials, semidefinite programming, sensor network localization, sum of squares (sos)

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, … Read more