4.2 What can be expressed via linear matrix inequalities?

As in the previous lecture, the first thing to realize when speaking about the SDP universe is how to recognize that a convex optimization program

can be cast as a semidefinite program. Just as in the previous lecture, this question actually asks whether a given convex set or function is semidefinite representable (SDr). The definition of the latter notion is completely similar to the one of a CQr set or function:

We say that a convex set X ? R ⁿ is SDr if there exists an affine mapping ( x, u) ? ? B: R ⁿ _x R ^k _u ? S ^m such that

in other words, is SDr if there exists LMI

in the original design vector and a vector u of additional design variables such that is a projection of the solution set of the LMI onto the x-space. An LMI with this property is called semidefinite representation (SDR) of the set X.

A convex function f: R ⁿ ? R ? {+ ?} is called SDr if its epigraph

is an SDr set. An SDR of the epigraph of f is called an SDR of f.

By exactly the same reasons as in the case of conic quadratic problems, one has the following:

1. If f is an SDr function, then all its level sets { x/ f( x) ? a