A PhD thesis @ NALAG

TW 2014_01

Thanh Hieu Le
Low-rank representations for sum of squares polynomials
January 9, 2014

Advisor(s): Marc Van Barel, Raf Vandebril

Abstract

The purpose of this research is to study the properties, the relations between the cones of non-negative (real or complex) polynomials and their subcones of sums of square magnitudes of (real or complex) polynomials, and to design efficient and accurate algorithms for solving some corresponding optimization problems. More precisely, this thesis presents the study of the Pythagoras number of polynomials, together with their corresponding low-rank representations, from theoretical and practical points of view. The results are used to solve several optimization problems that can be reformulated over non-negative polynomials.

Besides providing a new proof for an existing upper-bound formula on the Pythagoras number of real polynomials, we give lower- and upper-bound formulas for the Pythagoras number of complex Laurent polynomials that are sums of square magnitudes of complex polynomials. These bounds are functions of the number of variables and the degree of the polynomials. The upper bounds’ proofs given in this thesis are based on the well-known results on the upper bound of the ranks of the matrices solving a certain system of quadratic equations. Moreover, we conjecture formulas for the value of the Pythagoras number of (real or complex Laurent) polynomials via the lower bounds. These conjectures are based on the comparison between the number of parameters and the number of conditions for a corresponding sum of squares representation.

From a practical point of view, we propose algorithms for computing the exact value of the Pythagoras number of real and complex Laurent polynomials and the corresponding sos-approximations. Numerical experiments using these algorithms are performed and they numerically confirm our conjectures. The algorithm for computing the Pythagoras number and corresponding low-rank representation of a real polynomial is then combined with Pólya's and Reznick's theorems, to find a decomposition of a non-negative polynomial as a sum of squares of rational functions. Numerical experiments are also performed for several well-known polynomials such as Motzkin polynomials, Choi-Lam polynomials and Robinson polynomials.

The knowledge on the Pythagoras number of (real or complex) polynomials allows us to solve several low-pass filter design problems with finite or infinite impulse response. It is known in the literature that such a filter design problem can be recast as an optimization problem over the real (complex) polynomials that are sums of square magnitudes of real (complex) polynomials. The resulting optimization problem is not convex but its feasibility problem is convex. In the present thesis, we formulate the feasibility problem corresponding to such a filter design problem as a conic linear programming problem. Combined with a bisection rule, an algorithm for minimizing the design parameter in a filter design problem is proposed. A safety margin is introduced to solve the numerical difficulties when solving these types of problems numerically. Numerical experiments illustrate the validity of this approach for larger degrees of the filter compared to similar previous algorithms.