Sparsity in sums of squares of polynomials

Masakazu Kojima; Sunyoung Kim; Hayato Waki

doi:10.1007/s10107-004-0554-3

Sparsity in sums of squares of polynomials

Masakazu Kojima, Sunyoung Kim, Hayato Waki

Department of Mathematics

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

71 Scopus citations

Abstract

Representation of a given nonnegative multivariate polynomial in terms of a sum of squares of polynomials has become an essential subject in recent developments of sums of squares optimization and semidefinite programming (SDP) relaxation of polynomial optimization problems. We discuss effective methods to obtain a simpler representation of a "sparse" polynomial as a sum of squares of sparse polynomials by eliminating redundancy.

Original language	English
Pages (from-to)	45-62
Number of pages	18
Journal	Mathematical Programming
Volume	103
Issue number	1
DOIs	https://doi.org/10.1007/s10107-004-0554-3
State	Published - May 2005

Keywords

Polynomial optimization problem
Semidefinite program
Sparsity
Sums of squares of polynomial

Access to Document

10.1007/s10107-004-0554-3

Cite this

@article{49e87dc492994356b35e6a84fbc9dd38,

title = "Sparsity in sums of squares of polynomials",

abstract = "Representation of a given nonnegative multivariate polynomial in terms of a sum of squares of polynomials has become an essential subject in recent developments of sums of squares optimization and semidefinite programming (SDP) relaxation of polynomial optimization problems. We discuss effective methods to obtain a simpler representation of a {"}sparse{"} polynomial as a sum of squares of sparse polynomials by eliminating redundancy.",

keywords = "Polynomial optimization problem, Semidefinite program, Sparsity, Sums of squares of polynomial",

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

year = "2005",

month = may,

doi = "10.1007/s10107-004-0554-3",

language = "English",

volume = "103",

pages = "45--62",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1",

}

TY - JOUR

T1 - Sparsity in sums of squares of polynomials

AU - Kojima, Masakazu

AU - Kim, Sunyoung

AU - Waki, Hayato

PY - 2005/5

Y1 - 2005/5

N2 - Representation of a given nonnegative multivariate polynomial in terms of a sum of squares of polynomials has become an essential subject in recent developments of sums of squares optimization and semidefinite programming (SDP) relaxation of polynomial optimization problems. We discuss effective methods to obtain a simpler representation of a "sparse" polynomial as a sum of squares of sparse polynomials by eliminating redundancy.

AB - Representation of a given nonnegative multivariate polynomial in terms of a sum of squares of polynomials has become an essential subject in recent developments of sums of squares optimization and semidefinite programming (SDP) relaxation of polynomial optimization problems. We discuss effective methods to obtain a simpler representation of a "sparse" polynomial as a sum of squares of sparse polynomials by eliminating redundancy.

KW - Polynomial optimization problem

KW - Semidefinite program

KW - Sparsity

KW - Sums of squares of polynomial

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

U2 - 10.1007/s10107-004-0554-3

DO - 10.1007/s10107-004-0554-3

M3 - Article

AN - SCOPUS:17444428545

SN - 0025-5610

VL - 103

SP - 45

EP - 62

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -

Sparsity in sums of squares of polynomials

Abstract

Keywords

Access to Document

Fingerprint

Cite this