This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let ${\cal E}$ and ${\cal E}_+$ be a finite dimensional real vector space and a symmetric cone embedded in ${\cal E}$; examples of $\calE$ and $\calE_+$ include a pair of the … Read more
We discuss in detail an additive structure of cones of trigonometric polynomials nonnegative on the union of finite number of pairwise disjoint segments of the unit circle. We derive new descriptions of these cones in terms of semidefinite constraints. We explain the results of M. Krein and A. Nudelman providing a description of dual cones … Read more
The notion of weighted centers is essential in V-space interior-point algorithms for linear programming. Although there were some successes in generalizing this notion to semidefinite programming via weighted center equations, we still do not have a generalization that preserves two important properties — 1) each choice of weights uniquely determines a pair of primal-dual weighted … Read more
We consider here the problem of minimizing a polynomial function on $\oR^n$. The problem is known to be hard even for degree $4$. Therefore approximation algorithms are of interest. Lasserre \cite{lasserre:2001} and Parrilo \cite{Pa02a} have proposed approximating the minimum of the original problem using a hierarchy of lower bounds obtained via semidefinite programming relaxations. We … Read more
Let $I=(g_1,…, g_n)$ be a zero-dimensional ideal of $ \R[x_1,…,x_n]$ such that its associated set $G$ of polynomial equations $g_i(x)=0$ for all $i=1,…,n$, is in triangular form. By introducing multivariate Newton sums we provide a numerical characterization of polynomials in the radical ideal of $I$. We also provide a necessary and sufficient (numerical) condition for … Read more
Considering that preprocessing is an important phase in linear programming, it should be systematically more incorporated in semidefinite programming solvers. The conversion method proposed by the authors (SIAM Journal on Optimization, vol.~11, pp.~647–674, 2000, and Mathematical Programming, Series B, vol.~95, pp.~303–327, 2003) is a preprocessing of sparse semidefinite programs based on matrix completion. This article … Read more
We present a unifying framework to establish a lower-bound on the number of semidefinite programming based, lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by … Read more
The goal of this paper is to formulate and solve structural optimization problems with constraints on the global stability of the structure. The stability constraint is based on the linear buckling phenomenon. We formulate the problem as a nonconvex semidefinite programming problem and introduce an algorithm based on the Augmented Lagrangian method combined with the … Read more
Interior-point methods (IPMs), originally conceived in the context of linear programming have found a variety of applications in integer programming, and combinatorial optimization. This survey presents an up to date account of IPMs in solving NP-hard combinatorial optimization problems to optimality, and also in developing approximation algorithms for some of them. The surveyed approaches include … Read more
Density estimation is a classical and important problem in statistics. The aim of this paper is to develop a new computational approach to density estimation based on semidefinite programming (SDP), a new technology developed in optimization in the last decade. We express a density as the product of a nonnegative polynomial and a base density … Read more