Convergent SDP-relaxations in polynomial optimization with sparsity

Jean B. Lasserre (lasserrelaas.fr)

Abstract: We consider a polynomial programming problem P on a compact basic semi-algebraic set K described by m polynomial inequalities $g_j(X)\geq0$, and with polynomial criterion $f$. We propose a hierarchy of semidefinite relaxations in the spirit those of Waki et al. [9]. In particular, the SDP-relaxation of order $r$ has the following two features: (a) The number of variables is $O(\kappa^{2r})$ where $\kappa=\max[\kappa_1,\kappa_2]$ witth $\kappa_1$ (resp. $\kappa_2$) being the maximum number of variables appearing the monomials of $f$ (resp. appearing in a single constraint $g_j(X)\geq0$). (b) The largest size of the LMI's (Linear Matrix Inequalities) is $O(\kappa^r)$. This is to compare with the respective number of variables $O(n^{2r})$ and LMI size $O(n^r)$ in the original SDP-relaxations defined in Lasserre [11]. Therefore, great computational savings are expected in case of sparsity in the data, i.e. when $\kappa$ is small, a frequent case in practical applications of interest. The novelty with respect to Waki et al. [9] is that we prove convergence to the global optimum of P when the sparsity pattern satisfies a condition often encountered in large size problems of practical applications, and known as the "running intersection property" in graph theory. In such cases, and as a by-product, we also obtain a new representation result for polynomials positive on a basic closed semi-algebraic set, a "sparse" version of Putinar's Positivstellensatz.

Keywords: polynomial programming; SDP-relaxations; sparsity

Category 1: Global Optimization (Theory )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical report #05-612, LAAS, Toulouse, France (2005); To appear in Siam J. Optimization

Download: [PDF]

Entry Submitted: 04/12/2006
Entry Accepted: 04/13/2006
Entry Last Modified: 08/09/2006

Modify/Update this entry