We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the … Read more
Given a Markov process we are interested in the numerical computation of the moments of the exit time from a bounded domain. We use a moment approach which, together with appropriate semidefinite positivity moment conditions, yields a sequence of semidefinite programs (or SDP relaxations), depending on the number of moments considered, that provide a sequence … Read more
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
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
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
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