Download SOSTOOLS

Transcript
Contents
1 Getting Started with SOSTOOLS
1.1 Sum of Squares Polynomials and Sum of Squares Programs
1.2 What SOSTOOLS Does . . . . . . . . . . . . . . . . . . . .
1.3 System Requirements and Installation Instruction . . . . . .
1.4 Other Things You Need to Know . . . . . . . . . . . . . . .
1.5 What is New . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
5
7
8
9
10
2 Solving Sum of Squares Programs
2.1 Polynomial Representation and Manipulations . . . .
2.2 Initializing a Sum of Squares Program . . . . . . . . .
2.3 Variable Declaration . . . . . . . . . . . . . . . . . . .
2.3.1 Scalar Decision Variables . . . . . . . . . . . .
2.3.2 Polynomial Variables . . . . . . . . . . . . . . .
2.3.3 An Aside: Constructing Vectors of Monomials
2.3.4 Sum of Squares Variables . . . . . . . . . . . .
2.4 Adding Constraints . . . . . . . . . . . . . . . . . . . .
2.4.1 Equality Constraints . . . . . . . . . . . . . . .
2.4.2 Inequality Constraints . . . . . . . . . . . . . .
2.4.3 Exploiting Sparsity . . . . . . . . . . . . . . . .
2.4.4 Multipartite Structure . . . . . . . . . . . . . .
2.5 Setting Objective Function . . . . . . . . . . . . . . .
2.6 Calling Solver . . . . . . . . . . . . . . . . . . . . . . .
2.7 Getting Solutions . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
11
13
13
13
14
15
16
17
17
18
19
20
21
21
22
.
.
.
.
.
.
.
.
25
25
26
28
32
33
35
38
38
3 Applications of Sum of Squares Programming
3.1 Sum of Squares Test . . . . . . . . . . . . . . .
3.2 Lyapunov Function Search . . . . . . . . . . . .
3.3 Global and Constrained Optimization . . . . .
3.4 Matrix Copositivity . . . . . . . . . . . . . . .
3.5 Upper Bound of Structured Singular Value . .
3.6 MAX CUT . . . . . . . . . . . . . . . . . . . .
3.7 Chebyshev Polynomials . . . . . . . . . . . . .
3.8 Bounds in Probability . . . . . . . . . . . . . .
4 List of Functions
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
43
3