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.
Citation
Technical report #05-612, LAAS, Toulouse, France (2005); To appear in Siam J. Optimization
Article
View Convergent SDP-relaxations in polynomial optimization with sparsity