- 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/2006Entry Accepted: 04/13/2006Entry Last Modified: 08/09/2006Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.