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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- lecture 6 anova
- tutortube sum or squares standard spring 2021 deviation
- types of sums of squares
- on numbers which are the sum of two squares
- type i and type iii sums of squares
- lecture 13 extra sums of squares purdue university
- euler s calculation of the sum of the reciprocals of the
- sum of squares sos techniques an introduction
- sum of squares stanford university
- sum of four squares via the hurwitz quaternions
Related searches
- sum of squares in excel
- total sum of squares excel
- residual sum of squares excel
- minimize sum of squares excel
- regression sum of squares excel
- how to find sum of squares error
- sum of squares formula
- sum of squares calculator
- residual sum of squares calculator
- calculate the total sum of squares calculator
- sum of squares anova
- sum of squares total calculator