View article

We consider a polynomial programming problem $\P$ on a compact basic semialgebraic set $\K\subset\R^n$, described by m polynomial inequalities , and with criterion $f\in\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 , where with (resp., ) being the maximum number of variables appearing in the monomials of f (resp., appearing in a single constraint ). (b) The largest size of the linear matrix inequalities (LMIs) is . This is to compare with the respective number of variables and LMI size 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 …