### Abstract

Language | English |
---|---|

Pages | 399–422 |

Journal | SIAM Journal on Optimization |

Volume | 29 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2019 |

### Fingerprint

### Keywords

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

### Cite this

*SIAM Journal on Optimization*,

*29*(1), 399–422. https://doi.org/10.1137/18M1172843

}

*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.

Research output: Contribution to journal › Article › Scientific › peer-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

T2 - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 1

ER -