Algorithm 883: SparsePOP - A sparse semidefinite programming relaxation of polynomial optimization problems

Hayato Waki, Sunyoung Kim, Masakazu Kojima, Masakazu Muramatsu, Hiroshi Sugimoto

Research output: Contribution to journalArticlepeer-review

99 Scopus citations

Abstract

SparsePOP is a Matlab implementation of the sparse semidefinite programming (SDP) relaxation method for approximating a global optimal solution of a polynomial optimization problem (POP) proposed by Waki et al. [2006]. The sparse SDP relaxation exploits a sparse structure of polynomials in POPs when applying "a hierarchy of LMI relaxations of increasing dimensions" Lasserre [2006]. The efficiency of SparsePOP to approximate optimal solutions of POPs is thus increased, and larger-scale POPs can be handled.

Original languageEnglish
Pages (from-to)1-13
Number of pages13
JournalACM Transactions on Mathematical Software
Volume35
Issue number2
DOIs
StatePublished - 1 Jul 2008

Keywords

  • Global optimization
  • Matlab software package
  • Polynomial optimization problem
  • Semidefinite programming relaxation
  • Sparsity
  • Sums-of-squares optimization

Fingerprint

Dive into the research topics of 'Algorithm 883: SparsePOP - A sparse semidefinite programming relaxation of polynomial optimization problems'. Together they form a unique fingerprint.

Cite this