  


Convergent SDPrelaxations in polynomial optimization with sparsity
Jean B. Lasserre (lasserrelaas.fr) Abstract: We consider a polynomial programming problem P on a compact basic semialgebraic 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 SDPrelaxation 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 SDPrelaxations 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 byproduct, we also obtain a new representation result for polynomials positive on a basic closed semialgebraic set, a "sparse" version of Putinar's Positivstellensatz. Keywords: polynomial programming; SDPrelaxations; sparsity Category 1: Global Optimization (Theory ) Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Technical report #05612, LAAS, Toulouse, France (2005); To appear in Siam J. Optimization Download: [PDF] Entry Submitted: 04/12/2006 Modify/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  