Sum of squares - Stanford University

Sums of Squares

Sanjay Lall Stanford University

EE364b April 19, 2011

2 Sum of Squares

polynomial programming A familiar problem

minimize subject to

f0(x) fi(x) 0 hi(x) = 0

S. Lall, Stanford 2011.04.18.01

for all i = 1, . . . , m for all i = 1, . . . , p

in this section, objective, inequality and equality constraint functions are all polynomials

3 Sum of Squares

polynomial nonnegativity

S. Lall, Stanford 2011.04.18.01

does there exist x Rn such that f (x) < 0

? if not, f is called positive semidefinite or PSD f (x) 0 for all x Rn

? the problem is NP-hard, but decidable

4 Sum of Squares

certificates

S. Lall, Stanford 2011.04.18.01

does there exist x Rn such that f (x) < 0

? answer yes is easy to verify; exhibit x such that f (x) < 0

? answer no is hard; we need a certificate or a witness i.e, a proof that there is no feasible point

5 Sum of Squares

Sum of Squares Decomposition

S. Lall, Stanford 2011.04.18.01

f is nonnegative if there are polynomials g1, . . . , gs such that

s

f=

gi2

i=1

a checkable certificate, called a sum-of-squares (SOS) decomposition

? how do we find the gi ? when does such a certificate exist?

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download