Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity

Hayato Waki; Sunyoung Kim; Masakazu Kojima; Masakazu Muramatsu

doi:10.1137/050623802

Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity

Hayato Waki, Sunyoung Kim, Masakazu Kojima, Masakazu Muramatsu

Department of Mathematics

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

331 Scopus citations

Abstract

Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of the supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite program (SDP) relaxations are obtained. Numerical results from various test problems are included to show the improved performance of the SOS and SDP relaxations.

Original language	English
Pages (from-to)	218-242
Number of pages	25
Journal	SIAM Journal on Optimization
Volume	17
Issue number	1
DOIs	https://doi.org/10.1137/050623802
State	Published - 2007

Keywords

Global optimization
Lagrangian dual
Lagrangian relaxation
Polynomial optimization problem
Semidefinite program relaxation
Sparsity
Sums of squares optimization

Access to Document

10.1137/050623802

Cite this

@article{8a62ac1e8e034987bfa41e22604d05dd,

title = "Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity",

abstract = "Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of the supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite program (SDP) relaxations are obtained. Numerical results from various test problems are included to show the improved performance of the SOS and SDP relaxations.",

keywords = "Global optimization, Lagrangian dual, Lagrangian relaxation, Polynomial optimization problem, Semidefinite program relaxation, Sparsity, Sums of squares optimization",

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

year = "2007",

doi = "10.1137/050623802",

language = "English",

volume = "17",

pages = "218--242",

journal = "SIAM Journal on Optimization",

issn = "1052-6234",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity

AU - Waki, Hayato

AU - Kim, Sunyoung

AU - Kojima, Masakazu

AU - Muramatsu, Masakazu

PY - 2007

Y1 - 2007

N2 - Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of the supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite program (SDP) relaxations are obtained. Numerical results from various test problems are included to show the improved performance of the SOS and SDP relaxations.

AB - Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of the supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite program (SDP) relaxations are obtained. Numerical results from various test problems are included to show the improved performance of the SOS and SDP relaxations.

KW - Global optimization

KW - Lagrangian dual

KW - Lagrangian relaxation

KW - Polynomial optimization problem

KW - Semidefinite program relaxation

KW - Sparsity

KW - Sums of squares optimization

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

U2 - 10.1137/050623802

DO - 10.1137/050623802

M3 - Article

AN - SCOPUS:33847158335

SN - 1052-6234

VL - 17

SP - 218

EP - 242

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 1

ER -

Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity

Abstract

Keywords

Access to Document

Fingerprint

Cite this