Sum-Of-Squares Approach to Global Stability and Control of Fluid Flows

The Sum of Squares Decomposition

 

In this section we give a brief introduction to sum of squares polynomials technique introduced in Pablo Parrilo’s thesis in 2000 [1], and show how the existence of a sum of squares decomposition can be verified using semidefinite programming.

Note: Semidefinite programming is a subfield of convex optimization concerned with the optimization of a linear objective function (that is, a function to be maximized or minimized) over the intersection of the cone of positive semidefinite matrices with an affine space.

Definition: for х ϵ Rⁿ a multivariate polynomial p(x)is a sum of squares if there exist polynomials f_i(x)  i=1, … ,M such that p(x)=

Proposition: A polynomial p(x) of degree 2d is a sum of squares if and only if there exists a positive semidefinite matrix Q and a vector of monomials Z(x), containing monomials of the form ax₁^r₁x₂^r₂...x_n^r_n, where r₁+...r_n ≤ d such that p(x)=Z^T(x)QZ(x).

In general, the monomials in Z(x) are not algebraically independent. Expanding Z^T(x)QZ(x) and equating the coefficients of the resulting monomials to the ones in p(x), we obtain a set of affine relations in the elements of Q. The problem of finding a semi-definite matrix Q, the elements of which satisfy the obtained affine relations, can be solved using semi-definite programming. As soon as we find that for p(x) there exists a corresponding positive-semidefinite matrix Q, it is proved that p(x) can be represented as a sum of squares.

---

Info:

1. 1. A self-adjoint matrix is a square complex-valued matrix that is equal to its own conjugate transpose: A^T=A. That is, a_ij=a_ji for any i and j.
2. A n×n self-adjoint matrix A is said to be positive semi-definite if x^TAx ≥0 for all х ϵ Rⁿ.
3. The number λ is called the eigenvalue or a characteristic value of А, and a vector x≠0 is called an eigenvector or a characteristic vector of А, if Ах=λx.
4. A self-adjoint matrix has only real eigenvalues, and there exists an orthonormal basis e₁,…,e_n such that e₁,…,e_n are the eignevectors of this matrix. In this basis the matrix is diagonal: that is a_ij=0 if i≠j, and λ₁, … , λ_n are the eigenvalues of A.
5. A diagonal matrix А is positive-semidefinite if and only if its eigenvalues are non-negative. For proving this it suffices to consider the expression x^TAx for any x ϵ Rⁿ:

   х^TАх= = +…+ , and +…+ ≥0 is valid for all xif and only if ≥0.

6. A self-adjoint matrix is positive semidefinite if and only if its eigenvalues are nonnegative (directly follows from the statements 5 и 6).

---

            Example (from [2]): Suppose that we want to know whether or not the quartic polynomial in two variables p() = 2+2-+5 is a sum of squares. For this purpose, define Z(x)=^Т and consider the following quadratic form:
p() = 2+2-+5  = Z(x)^ТZ(x) = + + +2 +2 .

From this we get the following relations: Now, using semi-definite programming, we can find  and , satisfying the last equation and such that the matrix Q is positive semi-definite. These conditions are satisfied with  и . After that we find a basis in which matrix Qwill be diagonal. Monomials in Z(x) can be expressed as a linear combination of the basis vectors. By the formula p(x)=Z(x)^TQZ(x) we obtain the following sum of squares decomposition:
p() = .

Note: p(x) being sum of squares implies that p(x)≥0 for all х ϵ Rⁿ. However, the converse is not always true. Not all nonnegative polynomials can be written as sum of squares, apart from three special cases:

1. n=2, i.e. in two-dimensional space.
2. deg(p)=2, i.e. the degree of the polynomial p(x) is two.
3. n=3 and deg(p)=4, i.e. the space is three-dimensional and the degree of the polynomial p(x) is four.

As we have already mentioned, a semidefinite matrix, such that its elements satisfy a given set of affine relations, if exists, can be found using semidefinite programming. This is so because the set of positive-semidefinite matrices is convex.

For verifying this we take two matrices from this set, and verify that the matrix A=+, where 0≤λ≤1, will also be positive semidefinite. Consider x^ТAx= xТ +)x, where 0≤λ≤1. Since the matrices  are positive-semidefinite and because of the conditions on λ, we obtain that x^ТAx≥0, which means that the matrix A is positive semidefinite. Hence, the set of such matrices is indeed convex.

We are looking for a matrix from convex set of positive-semidefinite matrices such that the elements of this matrix satisfy a set of affine relations. Since affine relations form a hyperplane, the desired matrix is located in the intersection of a convex set of positive semidefinite matrces and a hyperplane. This intersection will be convex, so the problem of searching for the matrix can indeed be solved using semidefenite programming.

• The project has ended.
• Paolo Luchini visited us on February 2016.
• Mihailo Jovanovic and Armin Zade visited us during the two weeks 2-15 November 2015.
• All our postdocs secured positions which will allow them to contninue working in cooperation with us: Deqing Huang will be a full professor at the Southwest Jiaotong University, China, Davide Lasagna will be a Frontier Fellow at the Universiy of Southampton, UK, and Giorgio Valmorbida will move to a faculty position at the Supelec and Paris-Sud University, France. Well done!
• Next progress meeting on February 23.2015.
• Remote conference was held on 5.02.2015.
• Sergei was at UCLA attending the Mathematics of Turbulence programme. He gave two presentations about the project.
• Remote conference was held on 30.10.2014.
• Remote conference was held on 09.06.2014.
• A progress meeting was held at Imperial College on 27.03.2014.
• Charles Doering is at Imperial 25-27.03.2014 and in Oxford 27-28.03.2014 He is giving a talk on 26.03, see "Miscellaneous".
• Remote conference was held on 14.03.2014.
• Sergei gave a talk at the NeZaTeGiUs conference NeZaTeGiUs conference on 02.03.2014.
• Deqing went to China 26-30 December and gave a talk at a workshop organized by the State Key Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou.
• Remote conference was held on 20.12.2014 The record is available from Sergei.
• Paul visited London and Oxford for two weeks in October, and took part in the project meeting on 21.10.
• Sergei gave a talk at ICNAAM 2013.
• Remote conference was held on 19.09.2013 The record is available from Sergei.
• Remore conferences were video recorded on 14.05, 06.06, 25.06, 11.07, 16.08, and 21.08.2013 The records are available for the members of the team from Sergei, but the records are not in the repository, to save space.
• July 2013. Deqing gave a talk at the School of Aeronautics and Astronautics, Zhejiang University, Hangzhou, China.
• June 5 and 6, 2013. Our remote conference was spread over 2 days this time.
• May 19-31, 2013. Sergei was in Stockholm, taking part in NORDITA Stability and Transition programme, and the follow-on SIG-33 workshop, where he gave a talk on using SoS in fluid dynamics.
• May 14, 2013. We had our first remote conference. It was interesting, and useful. Giorgio, Davide, and Deqing presented, and we all had a good chat.
• April 22, 2013. SVN repository for the project was created by Paul, hosted at ETH.
• Kick-off meeting on April 18 went fine.
• Paul is here!
• Paul Goulart will be visiting Imperial from April 15 to May 3.
• 30.03.2013 This website opens.
• 28.03.2013 Project mailing list created.
• 11-15.03.2013 Wynn visited Doering in Michigan.
<
• 19.02.2013 Chernyshenko visited Southampton team.