Polynomial norms

Amirali Ahmadi, Etienne de Klerk, Georgina Hall

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this paper, we study polynomial norms, i.e., norms that are the \$d\$th root of a degree-\$d\$ homogeneous polynomial \$f\$. We first show that a necessary and sufficient condition for \$f^{1/d}\$ to be a norm is for \$f\$ to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from \$d\$th roots of polynomials, we prove that any norm can be approximated arbitrarily well by a polynomial norm. We then investigate the computational problem of testing whether a form gives a polynomial norm. We show that this problem is strongly NP-hard already when the degree of the form is 4, but can always be answered by solving a hierarchy of semidefinite programs. We further study the problem of optimizing over the set of polynomial norms using semidefinite programming. To do this, we introduce the notion of \$r\$-sum of squares-convexity and extend a result of Reznick on sum of squares representations of positive definite forms to positive definite biforms. We conclude with some applications of polynomial norms to statistics and dynamical systems.
Original language English 399–422 SIAM Journal on Optimization 29 1 https://doi.org/10.1137/18M1172843 Published - 2019

Fingerprint

Polynomials
Norm
Polynomial
Positive definite
Sum of squares
Roots
Semidefinite Program
Homogeneous Polynomials
Semidefinite Programming
Strictly Convex
Dynamical systems
Statistics
Convexity
NP-complete problem
Dynamical system
Testing
Necessary Conditions
Sufficient Conditions
Form

Keywords

• polynomial norms
• sum of squares
• polynomials
• convex polynomials
• semidefinitie programming

Cite this

Ahmadi, Amirali ; de Klerk, Etienne ; Hall, Georgina. / Polynomial norms. In: SIAM Journal on Optimization. 2019 ; Vol. 29, No. 1. pp. 399–422.
@article{2122ab0c1f804735962ccf15128611c9,
title = "Polynomial norms",
abstract = "In this paper, we study polynomial norms, i.e., norms that are the \$d\$th root of a degree-\$d\$ homogeneous polynomial \$f\$. We first show that a necessary and sufficient condition for \$f^{1/d}\$ to be a norm is for \$f\$ to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from \$d\$th roots of polynomials, we prove that any norm can be approximated arbitrarily well by a polynomial norm. We then investigate the computational problem of testing whether a form gives a polynomial norm. We show that this problem is strongly NP-hard already when the degree of the form is 4, but can always be answered by solving a hierarchy of semidefinite programs. We further study the problem of optimizing over the set of polynomial norms using semidefinite programming. To do this, we introduce the notion of \$r\$-sum of squares-convexity and extend a result of Reznick on sum of squares representations of positive definite forms to positive definite biforms. We conclude with some applications of polynomial norms to statistics and dynamical systems.",
keywords = "polynomial norms, sum of squares, polynomials, convex polynomials, semidefinitie programming",
author = "Amirali Ahmadi and {de Klerk}, Etienne and Georgina Hall",
year = "2019",
doi = "10.1137/18M1172843",
language = "English",
volume = "29",
pages = "399–422",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "1",

}

Ahmadi, A, de Klerk, E & Hall, G 2019, 'Polynomial norms', SIAM Journal on Optimization, vol. 29, no. 1, pp. 399–422. https://doi.org/10.1137/18M1172843

Polynomial norms. / Ahmadi, Amirali; de Klerk, Etienne; Hall, Georgina.

In: SIAM Journal on Optimization, Vol. 29, No. 1, 2019, p. 399–422.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Polynomial norms

AU - Ahmadi, Amirali

AU - de Klerk, Etienne

AU - Hall, Georgina

PY - 2019

Y1 - 2019

N2 - In this paper, we study polynomial norms, i.e., norms that are the \$d\$th root of a degree-\$d\$ homogeneous polynomial \$f\$. We first show that a necessary and sufficient condition for \$f^{1/d}\$ to be a norm is for \$f\$ to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from \$d\$th roots of polynomials, we prove that any norm can be approximated arbitrarily well by a polynomial norm. We then investigate the computational problem of testing whether a form gives a polynomial norm. We show that this problem is strongly NP-hard already when the degree of the form is 4, but can always be answered by solving a hierarchy of semidefinite programs. We further study the problem of optimizing over the set of polynomial norms using semidefinite programming. To do this, we introduce the notion of \$r\$-sum of squares-convexity and extend a result of Reznick on sum of squares representations of positive definite forms to positive definite biforms. We conclude with some applications of polynomial norms to statistics and dynamical systems.

AB - In this paper, we study polynomial norms, i.e., norms that are the \$d\$th root of a degree-\$d\$ homogeneous polynomial \$f\$. We first show that a necessary and sufficient condition for \$f^{1/d}\$ to be a norm is for \$f\$ to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from \$d\$th roots of polynomials, we prove that any norm can be approximated arbitrarily well by a polynomial norm. We then investigate the computational problem of testing whether a form gives a polynomial norm. We show that this problem is strongly NP-hard already when the degree of the form is 4, but can always be answered by solving a hierarchy of semidefinite programs. We further study the problem of optimizing over the set of polynomial norms using semidefinite programming. To do this, we introduce the notion of \$r\$-sum of squares-convexity and extend a result of Reznick on sum of squares representations of positive definite forms to positive definite biforms. We conclude with some applications of polynomial norms to statistics and dynamical systems.

KW - polynomial norms

KW - sum of squares

KW - polynomials

KW - convex polynomials

KW - semidefinitie programming

U2 - 10.1137/18M1172843

DO - 10.1137/18M1172843

M3 - Article

VL - 29

SP - 399

EP - 422

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 1

ER -