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