2017/04/24 by Amir Ali Ahmadi, Ahmadi, Amir Ali, Etienne de Klerk +3 · 1 citation
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.1704.07462
openalex publication_date 2017/04/24 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
In this paper, we study polynomial norms, i.e. norms that are the dth root of a degree-d homogeneous polynomial f. We first show that a necessary and sufficient condition for f1/d to be a norm is for f to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from dth 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 testing feasibility of a semidefinite program (of possibly large size). 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-sos-convexity and extend a result of Reznick on sum of squares representation of positive definite forms to positive definite biforms. We conclude with some applications of polynomial norms to statistics and dynamical systems.