Solving polynomial least squares problems via semidefinite programming relaxations

Sunyoung Kim, Masakazu Kojima

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


A polynomial optimization problem whose objective function is represented as a sum of positive and even powers of polynomials, called a polynomial least squares problem, is considered. Methods to transform a polynomial least square problem to polynomial semidefinite programs to reduce degrees of the polynomials are discussed. Computational efficiency of solving the original polynomial least squares problem and the transformed polynomial semidefinite programs is compared. Numerical results on selected polynomial least square problems show better computational performance of a transformed polynomial semidefinite program, especially when degrees of the polynomials are larger.

Original languageEnglish
Pages (from-to)1-23
Number of pages23
JournalJournal of Global Optimization
Issue number1
StatePublished - Jan 2010


  • Nonconvex optimization problems
  • Polynomial least squares problems
  • Polynomial second-order cone programs
  • Polynomial semidefinite programs
  • Sparsity


Dive into the research topics of 'Solving polynomial least squares problems via semidefinite programming relaxations'. Together they form a unique fingerprint.

Cite this