Optimization Online


Convergent SDP-relaxations in polynomial optimization with sparsity

Jean B. Lasserre (lasserre***at***laas.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society