Polynomial norms

DOI10.1137/18M1172843MaRDI QIDQ4620456zbMATH OpenOpenAlexFDO

Authors Amir Ali Ahmadi, E. de Klerk, Georgina Hall

Publication date 8 February 2019

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.07462

zbMATH Keywords

convex polynomialspolynomial normssemidefinite programmingsum of squares polynomials

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Approximation by convex sets (52A27) Semidefinite programming (90C22)

Abstract: In this paper, we study polynomial norms, i.e. norms that are the $d^{extth}$ 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^{extth}$ 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.

Recommendations

• scientific article; zbMATH DE number 1975216
• Computational complexity of norm-maximization
• A Variable-Complexity Norm Maximization Problem
• Matrix p-norms are NP-hard to approximate if p1,2,
• Deciding uniqueness in norm maximazation

Cites work

• A complete characterization of the gap between convexity and sos-convexity
• A convex polynomial that is not sos-convex
• A Newton-CG augmented Lagrangian method for semidefinite programming
• A non-commutative real Nullstellensatz and Hilbert's 17th problem
• An elementary and constructive solution to Hilbert’s 17th Problem for matrices
• Analysis of the joint spectral radius via Lyapunov functions on path-complete graphs
• Banach spaces with polynomial norms
• Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations
• Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
• Global optimization with polynomials and the problem of moments
• scientific article; zbMATH DE number 5302815 (Why is no real title available?)
• scientific article; zbMATH DE number 3467247 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1975216 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Linear systems theory.
• Lower bounds on complexity of Lyapunov functions for switched linear systems
• Moments of non-negative mass
• Notions of positivity and the geometry of polynomials. Dedicated to the memory of Julius Borcea
• NP-hardness of deciding convexity of quartic polynomials and related problems
• On duality theory of conic linear problems.
• On the absence of uniform denominators in Hilbert’s 17th problem
• Optimization with sparsity-inducing penalties
• Positive polynomials in control.
• QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
• Regularization methods for SDP relaxations in large-scale polynomial optimization
• Semidefinite Programming
• Semidefinite programming relaxations for semialgebraic problems
• Semidefinite representation of convex sets
• Symmetry groups, semidefinite programs, and sums of squares
• The boundedness of all products of a pair of matrices is undecidable
• The convex geometry of linear inverse problems
• Uniform denominators in Hilbert's seventeenth problem

Cited in

(19)

• On norm attaining polynomials.
• The norm of a skew polynomial
• Normalized polynomials and their multiplication formulas
• On discrete norms of polynomials
• Some Consequences of the Standard Polynomial
• Equivalent norms in polynomial spaces and applications
• scientific article; zbMATH DE number 5152087 (Why is no real title available?)
• scientific article; zbMATH DE number 1975216 (Why is no real title available?)
• Norm-attaining polynomials and differentiability
• Order comparison of norms of polynomials in regions of the complex plane
• On random walks and switched random walks on homogeneous spaces
• Marstrand-Mattila rectifiability criterion for 1-codimensional measures in Carnot groups
• Distributionally robust fractional optimization of probability of exceedance
• Regular pairings for nonquadratic Lyapunov functions and contraction analysis
• Convex ternary quartics are SOS-convex
• Distributionally robust optimization with polynomial robust constraints
• Hunter's positivity theorem and random vector norms
• Safely learning dynamical systems
• Cubic-quartic regularization models for solving polynomial subproblems in third-order tensor methods

Describes a project that uses

Uses Software

• YALMIP
• Mosek
• Robotics
• QSDPNAL
• SPOTless

This page was built for publication: Polynomial norms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4620456)