Convex Optimization · Problem 2.37

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · nonnegative-polynomials-and-hankel-lmis

Problem

Nonnegative polynomials and Hankel LMIs. Let

K_{\mathrm{pol}}

be the set of (coefficients of) nonneg\-ative polynomials of degree

2k

\mathbf{R}

K_{\mathrm{pol}} = \{x \in \mathbf{R}^{2k+1} \mid x_1 + x_2 t + x_3 t^2 + \cdots + x_{2k+1} t^{2k} \geq 0 \text{ for all } t \in \mathbf{R}\}.

((a)) Show that

K_{\mathrm{pol}}

is a proper cone. ((b)) A basic result states that a polynomial of degree

2k

is nonneg\-ative on

\mathbf{R}

if and only if it can be expressed as the sum of squares of two polynomials of degree

k

or less. In other words,

x \in K_{\mathrm{pol}}

if and only if the polynomial

p(t) = x_1 + x_2 t + x_3 t^2 + \cdots + x_{2k+1} t^{2k}

can be expressed as

p(t) = r(t)^2 + s(t)^2

, where

r

and

s

are polynomials of degree

k

. Use this result to show that

K_{\mathrm{pol}} = \left\{ x \in \mathbf{R}^{2k+1} \,\middle|\, x_i = \sum_{m+n=i+1} Y_{mn} \text{ for some } Y \in \mathbf{S}^{k+1}_+ \right\}.

In other words,

p(t) = x_1 + x_2 t + x_3 t^2 + \cdots + x_{2k+1} t^{2k}

is nonneg\-ative if and only if there exists a matrix

Y \in \mathbf{S}^{k+1}_+

such that

\begin{aligned} x_1 &= Y_{11} \\ x_2 &= Y_{12} + Y_{21} \\ x_3 &= Y_{13} + Y_{22} + Y_{31} \\ &\vdots \\ x_{2k+1} &= Y_{k+1,k+1}. \end{aligned}

((c)) Show that

K^*_{\mathrm{pol}} = K_{\mathrm{han}}

where

K_{\mathrm{han}} = \{z \in \mathbf{R}^{2k+1} \mid H(z) \succeq 0\}

and

H(z) = \begin{bmatrix} z_1 & z_2 & z_3 & \cdots & z_k & z_{k+1} \\ z_2 & z_3 & z_4 & \cdots & z_{k+1} & z_{k+2} \\ z_3 & z_4 & z_5 & \cdots & z_{k+2} & z_{k+4} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ z_k & z_{k+1} & z_{k+2} & \cdots & z_{2k-1} & z_{2k} \\ z_{k+1} & z_{k+2} & z_{k+3} & \cdots & z_{2k} & z_{2k+1} \end{bmatrix}.

(This is the Hankel matrix with coefficients

z_1, \ldots, z_{2k+1}

.) ((d)) Let

K_{\mathrm{mom}}

be the conic hull of the set of all vectors of the form

(1, t, t^2, \ldots, t^{2k})

, where

t \in \mathbf{R}

. Show that

y \in K_{\mathrm{mom}}

if and only if

y_1 \geq 0

and

y = y_1(1, \mathbf{E}\, u, \mathbf{E}\, u^2, \ldots, \mathbf{E}\, u^{2k})

for some random variable

u

. In other words, the elements of

K_{\mathrm{mom}}

are nonneg\-ative multiples of the moment vectors of all possible distributions on

\mathbf{R}

. Show that

K_{\mathrm{pol}} = K^*_{\mathrm{mom}}

. ((e)) Combining the results of (c) and (d), conclude that

K_{\mathrm{han}} = \mathbf{cl}\, K_{\mathrm{mom}}

. As an example illustrating the relation between

K_{\mathrm{mom}}

and

K_{\mathrm{han}}

, take

k = 2

and

z = (1, 0, 0, 0, 1)

. Show that

z \in K_{\mathrm{han}}

z \notin K_{\mathrm{mom}}

. Find an explicit sequence of points in

K_{\mathrm{mom}}

which converge to

z