Convex Optimization · Problem 4.44

Duality — Boyd & Vandenberghe

Mathematics — Optimization · optimization-over-polynomials

Problem

Optimization over polynomials. Pose the following problem as an SDP. Find the polynomial

p : \mathbf{R} \to \mathbf{R}

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

that satisfies given bounds

l_i \leq p(t_i) \leq u_i

, at

m

specified points

t_i

, and, of all the polynomials that satisfy these bounds, has the greatest minimum value:

\begin{aligned} \text{maximize} & \quad \inf_t\, p(t) \\ \text{subject to} & \quad l_i \leq p(t_i) \leq u_i, \quad i = 1, \ldots, m. \end{aligned}

The variables are

x \in \mathbf{R}^{2k+1}

. Hint. Use the LMI characterization of nonnegative polynomials derived in exercise 2.37, part (b).