Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets
- 주제(키워드) Global continuous optimization , Semidefinite programming relaxations , Sparse polynomial optimization , Structured sparsity , Sums of squares polynomials
- 관리정보기술 faculty
- 등재 SCIE, SCOPUS
- 발행기관 Kluwer Academic Publishers
- 발행년도 2016
- 총서유형 Journal
- URI http://www.dcollection.net/handler/ewha/000000119162
- 본문언어 영어
- Published As http://dx.doi.org/10.1007/s10898-015-0356-6
초록/요약
We propose a hierarchy of semidefinite programming (SDP) relaxations for polynomial optimization with sparse patterns over unbounded feasible sets. The convergence of the proposed SDP hierarchy is established for a class of polynomial optimization problems. This is done by employing known sums-of-squares sparsity techniques of Kojima and Muramatsu Comput Optim Appl 42(1):31–41, (2009) and Lasserre SIAM J Optim 17:822–843, (2006) together with a representation theorem for polynomials over unbounded sets obtained recently in Jeyakumar et al. J Optim Theory Appl 163(3):707–718, (2014). We demonstrate that the proposed sparse SDP hierarchy can solve some classes of large scale polynomial optimization problems with unbounded feasible sets using the polynomial optimization solver SparsePOP developed by Waki et al. ACM Trans Math Softw 35:15 (2008). © 2015 Springer Science+Business Media New York
more