Semidefinite characterization of sum-of-squares cones in algebras

Dávid Papp, Farid Alizadeh

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

We extend Nesterov's semidefinite programming characterization of squared functional systems, and Faybusovich's abstraction to bilinear symmetric maps, to cones of sum-of-squares elements in general abstract algebras. Using algebraic techniques such as isomorphism, linear isomorphism, tensor products, sums, and direct sums, we show that many concrete cones are in fact sum-of-squares cones with respect to some algebra and thus are epresentable by the cone of positive semidefinite matrices. We also consider nonnegativity with respect to a proper cone K and show that in some cases cones of K-nonnegative functions are either sum of squares or at least semidefinite representable. For example, we show that some well-known Chebyshev systems, when extended to Euclidean Jordan algebras, induce cones that are semidefinite representable. Finally we will discuss some concrete examples and applications, including minimum ellipsoid enclosing given space curves, minimization of eigenvalues of polynomial matrix pencils, approximation of functions by shapeconstrained functions, and approximation of combinatorial optimization problems by olynomial programming.

Original languageEnglish (US)
Pages (from-to)1398-1423
Number of pages26
JournalSIAM Journal on Optimization
Volume23
Issue number3
DOIs
StatePublished - Oct 29 2013

Fingerprint

Sum of squares
Algebra
Cones
Cone
Isomorphism
Chebyshev System
Euclidean Jordan Algebra
Abstract algebra
Matrix Pencil
Space Curve
Polynomial Matrices
Positive Semidefinite Matrix
Approximation of Functions
Nonnegativity
Semidefinite Programming
Combinatorial optimization
Ellipsoid
Combinatorial Optimization Problem
Direct Sum
Tensor Product

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science

Keywords

  • Nonnegative polynomials
  • Semidefinite programming
  • Semidefinite representability
  • Sum of squares
  • Sum-of-squares functional systems

Cite this

@article{dfd9778c79e442338e35815531fac0e5,
title = "Semidefinite characterization of sum-of-squares cones in algebras",
abstract = "We extend Nesterov's semidefinite programming characterization of squared functional systems, and Faybusovich's abstraction to bilinear symmetric maps, to cones of sum-of-squares elements in general abstract algebras. Using algebraic techniques such as isomorphism, linear isomorphism, tensor products, sums, and direct sums, we show that many concrete cones are in fact sum-of-squares cones with respect to some algebra and thus are epresentable by the cone of positive semidefinite matrices. We also consider nonnegativity with respect to a proper cone K and show that in some cases cones of K-nonnegative functions are either sum of squares or at least semidefinite representable. For example, we show that some well-known Chebyshev systems, when extended to Euclidean Jordan algebras, induce cones that are semidefinite representable. Finally we will discuss some concrete examples and applications, including minimum ellipsoid enclosing given space curves, minimization of eigenvalues of polynomial matrix pencils, approximation of functions by shapeconstrained functions, and approximation of combinatorial optimization problems by olynomial programming.",
keywords = "Nonnegative polynomials, Semidefinite programming, Semidefinite representability, Sum of squares, Sum-of-squares functional systems",
author = "D{\'a}vid Papp and Farid Alizadeh",
year = "2013",
month = "10",
day = "29",
doi = "10.1137/110843265",
language = "English (US)",
volume = "23",
pages = "1398--1423",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

Semidefinite characterization of sum-of-squares cones in algebras. / Papp, Dávid; Alizadeh, Farid.

In: SIAM Journal on Optimization, Vol. 23, No. 3, 29.10.2013, p. 1398-1423.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Semidefinite characterization of sum-of-squares cones in algebras

AU - Papp, Dávid

AU - Alizadeh, Farid

PY - 2013/10/29

Y1 - 2013/10/29

N2 - We extend Nesterov's semidefinite programming characterization of squared functional systems, and Faybusovich's abstraction to bilinear symmetric maps, to cones of sum-of-squares elements in general abstract algebras. Using algebraic techniques such as isomorphism, linear isomorphism, tensor products, sums, and direct sums, we show that many concrete cones are in fact sum-of-squares cones with respect to some algebra and thus are epresentable by the cone of positive semidefinite matrices. We also consider nonnegativity with respect to a proper cone K and show that in some cases cones of K-nonnegative functions are either sum of squares or at least semidefinite representable. For example, we show that some well-known Chebyshev systems, when extended to Euclidean Jordan algebras, induce cones that are semidefinite representable. Finally we will discuss some concrete examples and applications, including minimum ellipsoid enclosing given space curves, minimization of eigenvalues of polynomial matrix pencils, approximation of functions by shapeconstrained functions, and approximation of combinatorial optimization problems by olynomial programming.

AB - We extend Nesterov's semidefinite programming characterization of squared functional systems, and Faybusovich's abstraction to bilinear symmetric maps, to cones of sum-of-squares elements in general abstract algebras. Using algebraic techniques such as isomorphism, linear isomorphism, tensor products, sums, and direct sums, we show that many concrete cones are in fact sum-of-squares cones with respect to some algebra and thus are epresentable by the cone of positive semidefinite matrices. We also consider nonnegativity with respect to a proper cone K and show that in some cases cones of K-nonnegative functions are either sum of squares or at least semidefinite representable. For example, we show that some well-known Chebyshev systems, when extended to Euclidean Jordan algebras, induce cones that are semidefinite representable. Finally we will discuss some concrete examples and applications, including minimum ellipsoid enclosing given space curves, minimization of eigenvalues of polynomial matrix pencils, approximation of functions by shapeconstrained functions, and approximation of combinatorial optimization problems by olynomial programming.

KW - Nonnegative polynomials

KW - Semidefinite programming

KW - Semidefinite representability

KW - Sum of squares

KW - Sum-of-squares functional systems

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

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

U2 - 10.1137/110843265

DO - 10.1137/110843265

M3 - Article

AN - SCOPUS:84886289336

VL - 23

SP - 1398

EP - 1423

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 3

ER -