Convergent SDP-relaxations in polynomial optimization with sparsity

We consider a polynomial programming problem P on a compact basic semialgebraic set K subset of R-n, described by m polynomial inequalities g(j) (X) >= 0, and with criterion f is an element of R[X]. We propose a hierarchy of semidefinite relaxations in the spirit of those of Waki et al. [SIAM J. Optim., 17 ( 2006), pp. 218-242]. In particular, the SDP-relaxation of order r has the following two features: (a) The number of variables is O(K-2r), where K = max[K-1, K-2] with K-1 ( resp., K-2) being the maximum number of variables appearing in the monomials of f (resp., appearing in a single constraint g(j) (X) >= 0). (b) The largest size of the linear matrix inequalities (LMIs) is O(K-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 [J. B. Lasserre, SIAM J. Optim., 11 (2001), pp. 796-817]. Therefore, great computational savings are expected in case of sparsity in the data {g(j), f}, i.e, when K is small, a frequent case in practical applications of interest. The novelty with respect to [H. Waki, S. Kim, M. Kojima, and M. Maramatsu, SIAM J. Optim., 17 (2006), pp. 218-242] 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 compact basic semialgebraic set, a sparse version of Putinar's Positivstellensatz [ M. Putinar, Indiana Univ. Math. J., 42 ( 1993), pp. 969-984].