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

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

doi:10.1145/1377612.1377619

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

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

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

103 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 language	English
Pages (from-to)	1-13
Number of pages	13
Journal	ACM Transactions on Mathematical Software
Volume	35
Issue number	2
DOIs	https://doi.org/10.1145/1377612.1377619
State	Published - 1 Jul 2008

Keywords

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

Access to Document

10.1145/1377612.1377619

Cite this

@article{e1dadb0262034422adf1101b551f87eb,

title = "Algorithm 883: SparsePOP - A sparse semidefinite programming relaxation of polynomial optimization problems",

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.",

keywords = "Global optimization, Matlab software package, Polynomial optimization problem, Semidefinite programming relaxation, Sparsity, Sums-of-squares optimization",

author = "Hayato Waki and Sunyoung Kim and Masakazu Kojima and Masakazu Muramatsu and Hiroshi Sugimoto",

year = "2008",

month = jul,

day = "1",

doi = "10.1145/1377612.1377619",

language = "English",

volume = "35",

pages = "1--13",

journal = "ACM Transactions on Mathematical Software",

issn = "0098-3500",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

T1 - Algorithm 883

T2 - SparsePOP - A sparse semidefinite programming relaxation of polynomial optimization problems

AU - Waki, Hayato

AU - Kim, Sunyoung

AU - Kojima, Masakazu

AU - Muramatsu, Masakazu

AU - Sugimoto, Hiroshi

PY - 2008/7/1

Y1 - 2008/7/1

N2 - 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.

AB - 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.

KW - Global optimization

KW - Matlab software package

KW - Polynomial optimization problem

KW - Semidefinite programming relaxation

KW - Sparsity

KW - Sums-of-squares optimization

UR - http://www.scopus.com/inward/record.url?scp=48849097802&partnerID=8YFLogxK

U2 - 10.1145/1377612.1377619

DO - 10.1145/1377612.1377619

M3 - Article

AN - SCOPUS:48849097802

SN - 0098-3500

VL - 35

SP - 1

EP - 13

JO - ACM Transactions on Mathematical Software

JF - ACM Transactions on Mathematical Software

IS - 2

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this