can be checked via semidefinite programming (SDP), any of the three equivalent conditions above, and hence sos-convexity of a polynomial, can also be checked by SDP. Even though the polynomials $g_{\frac{1}{2}}$, $g_\nabla$, $g_{\nabla^2}$ above are all in $2n$ variables and have degree $d$, the structure of the polynomial $g_{\nabla^2}$ allows for much smaller SDPs (see [@AAA_PP_CDC10_algeb_convex] for details).

In general, finding examples of convex polynomials that are not sos-convex seems to be a nontrivial task, though a number of such constructions are known [@AAA_PP_not_sos_convex_journal]. A complete characterization of the dimensions and the degrees for which the notions of convexity and sos-convexity coincide is available in [@AAA_PP_table_sos-convexity]. Crucial for our purposes is the fact that semidefinite programming allows us to not only check if a given polynomial is sos-convex, but also search and optimize over the set of sos-convex polynomials of a given degree. This feature enables an automated search over a subset of convex polynomial Lyapunov functions. Of course, a Lyapunov function also needs to satisfy other constraints, namely positivity and monotonic decrease along trajectories. Following the standard approach, we replace the inequalities underlying these constraints with their sum of squares counterparts as well.

Throughout this paper, what we mean 