Sum of Squares (SOS) - Lecture 02: Sum of Squares (SOS)

Sum of Squares (SOS)

Matthew M. Peet

Arizona State University

Lecture 02: Sum of Squares (SOS)

The Dual Problem of Polynomial Programming

Polynomial Programming (NOT CONVEX): n decision variables

min

x¡ÊRn

f (x)

gi (x) ¡Ý 0

? f and gi must be convex for the problem to be convex.

Optimization of Polynomials IS Convex: Lifting to a higher-dimensional

space

max

g,¦Ã

¦Ã

f (x) ? ¦Ã = g(x)

for all

x ¡Ê Rn

g(x) ¡Ý 0

for all x ¡Ê {x ¡Ê Rn : h(x) ¡Ý 0}

? The decision variables are functions (e.g. g)

I Infinite Dimensional Contraints: One constraint for every value of x.

? But how to parameterize functions????

? How to enforce an infinite number of constraints???

? Advantage: Problem is convex, even if f, g, h are not convex.

M. Peet

Lecture 02: SOS and Global Stability Analysis

1 / 101

2019-06-04

Lecture 02

SOS and Global Stability Analysis

The Dual Problem of Polynomial Programming

Polynomial Programming (NOT CONVEX): n decision variables

min

x¡ÊRn

f (x)

gi (x) ¡Ý 0

? f and gi must be convex for the problem to be convex.

Optimization of Polynomials IS Convex: Lifting to a higher-dimensional

space

The Dual Problem of Polynomial Programming

max

g,¦Ã

¦Ã

f (x) ? ¦Ã = g(x)

for all

x ¡Ê Rn

g(x) ¡Ý 0

for all x ¡Ê {x ¡Ê Rn : h(x) ¡Ý 0}

? The decision variables are functions (e.g. g)

I Infinite Dimensional Contraints: One constraint for every value of x.

? But how to parameterize functions????

? How to enforce an infinite number of constraints???

? Advantage: Problem is convex, even if f, g, h are not convex.

? Hopefully you know what convexity is.

? Parameterize functions as polynomials.

? feasibility of a point x is easy to show.

? Infeasibility of a constraint requires a certificate

For Polynomial Programming

? feasibility of a point x is easy to show.

? Infeasibility of a constraint requires a certificate

For Optimization of Polynomials

? infeasibility is easy to show (give a counterexample).

? Feasibility of a function requires a certificate

Optimization of Polynomials:

Some Examples: Matrix Copositivity

Stability of Systems with Positive States: Not all states can be negative...

? Cell Populations/Concentrations

? Volume/Mass/Length

We want:

V (x) = xT P x ¡Ý 0

T

for all

T

V? (x) = x (A P + P A)x ¡Ü 0

x¡Ý0

for all

x¡Ý0

Formulation:

? Matrix Copositivity (An NP-hard Problem)

Verify:

T

x Px ¡Ý 0

for all

x¡Ý0

Implementation: sosdemo4p.m

M. Peet

Lecture 02: SOS and Global Stability Analysis

2 / 101

Optimization of Polynomials:

Some Examples: Robust Control

Recall: Systems with Uncertainty

x?(t) = A(¦Ä)x(t) + B1 (¦Ä)w(t) + B2 (¦Ä)u(t)

y(t) = C(¦Ä)x(t) + D12 (¦Ä)u(t) + D11 (¦Ä)w(t)

Theorem 1.

There exists an F (¦Ä) such that kS(P (¦Ä), K(0, 0, 0, F (¦Ä)))kH¡Þ ¡Ü ¦Ã for all

¦Ä ¡Ê ? if there exist Y > 0 and Z(¦Ä) such that





Y A(¦Ä)T + A(¦Ä)Y + Z(¦Ä)T B2 (¦Ä)T + B2 (¦Ä)Z(¦Ä)

?T

?T

B1 (¦Ä)T

?¦ÃI

?T

< 0 for all ¦Ä ¡Ê ?

C1 (¦Ä)Y + D12 (¦Ä)Z(¦Ä)

D11 (¦Ä)

?¦ÃI

Then F (¦Ä) = Z(¦Ä)Y ?1 .

M. Peet

Lecture 02: SOS and Global Stability Analysis

3 / 101

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

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

Google Online Preview   Download