Convex Ternary Quartics Are SOS-Convex
Article Download View Convex Ternary Quartics Are SOS-Convex
Pablo A. Parrilo
Sum of squares certificates for stability of planar, homogeneous, and switched systems
We show that existence of a global polynomial Lyapunov function for a homogeneous polynomial vector field or a planar polynomial vector field (under a mild condition) implies existence of a polynomial Lyapunov function that is a sum of squares (sos) and that the negative of its derivative is also a sum of squares. This result … Read more
On the local stability of semidefinite relaxations
In this paper we consider a parametric family of polynomial optimization problems over algebraic sets. Although these problems are typically nonconvex, tractable convex relaxations via semidefinite programming (SDP) have been proposed. Often times in applications there is a natural value of the parameters for which the relaxation will solve the problem exactly. We study conditions … Read more
Stability of Polynomial Differential Equations: Complexity and Converse Lyapunov Questions
We consider polynomial differential equations and make a number of contributions to the questions of (i) complexity of deciding stability, (ii) existence of polynomial Lyapunov functions, and (iii) existence of sum of squares (sos) Lyapunov functions. (i) We show that deciding local or global asymptotic stability of cubic vector fields is strongly NP-hard. Simple variations … Read more
Approximate cone factorizations and lifts of polytopes
In this paper we show how to construct inner and outer convex approximations of a polytope from an approximate cone factorization of its slack matrix. This provides a robust generalization of the famous result of Yannakakis that polyhedral lifts of a polytope are controlled by (exact) nonnegative factorizations of its slack matrix. Our approximations behave … Read more
Lifts of Convex Sets and Cone Factorizations
In this paper we address the basic geometric question of when a given convex set is the image under a linear map of an affine slice of a given closed convex cone. Such a representation or ‘lift’ of the convex set is especially useful if the cone admits an efficient algorithm for linear optimization over … Read more
A Complete Characterization of the Gap between Convexity and SOS-Convexity
Our first contribution in this paper is to prove that three natural sum of squares (sos) based sufficient conditions for convexity of polynomials via the definition of convexity, its first order characterization, and its second order characterization are equivalent. These three equivalent algebraic conditions, henceforth referred to as sos-convexity, can be checked by semidefinite programming … Read more
Joint Spectral Radius and Path-Complete Graph Lyapunov Functions
We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of … Read more
NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems
We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic … Read more
Convex Graph Invariants
The structural properties of graphs are usually characterized in terms of invariants, which are functions of graphs that do not depend on the labeling of the nodes. In this paper we study convex graph invariants, which are graph invariants that are convex functions of the adjacency matrix of a graph. Some examples include functions of … Read more