a broader class of convex Lyapunov functions that are constructed from combining several sos-convex polynomials. These extensions are still amenable to semidefinite programming and have connections to the theory of path-complete graph Lyapunov functions proposed in [@ajpr-sicon].

Sos-convex polynomials {#section:sos-convex}
======================

A multivariate polynomial $p(x)\mathrel{\mathop:}=p(x_1,\ldots,x_n)$ is said to be *nonnegative* or *positive semidefinite* (psd) if $p(x)\geq0$ for all $x\in\mathbb{R}^n$. We say that $p$ is a *sum of squares* (sos) if it can be written as $p=\sum_i q_i^2$, where each $q_i$ is a polynomial. It is well known that if $p$ is of even degree four or larger, then testing nonnegativity is NP-hard, while testing existence of a sum of squares decomposition, which provides a sufficient condition and an algebraic certificate for nonnegativity, can be done by solving a polynomially-sized semidefinite program [@PhD:Parrilo],[@sdprelax].

A polynomial $p\mathrel{\mathop:}=p(x)$ is *convex* if its Hessian $\nabla^2p(x)$ (i.e., the $n\times n$ polynomial matrix of the second derivatives) is positive semidefinite matrix for all $x\in\mathbb{R}^n$. This is equivalent to the scalar-valued polynomial $y^T\nabla^2p(x)y$ in $2n$ variables $(x_1,\ldots,x_n,y_1,\ldots,y_n)$ being nonnegative. It has been shown in [@NPhard_Convexity] that testing if a polynomial of degree four is convex is NP-hard in the strong sense. This motivates the algebraic notion of 