Sum-of-squares programming via optimization on manifolds

Details

Supervisors

Absil, Pierre-Antoine ; Legat, Benoît

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées, à finalité spécialisée

Abstract

enFor decades, the nonnegativity of polynomials has been of concern to mathematicians across several fields: global optimization, control theory, probability, game theory, operations research, etc. Nevertheless, in the general case, determining whether a polynomial is nonnegative or not is a NP-hard problem. For univariate polynomials however, nonnegativity is equivalent to being a sum of two squares: there exist two polynomials such that the sum of their squares equals the given polynomial. A few years ago, Legat et al. derived an algorithm for finding a sum-of-squares decomposition of a univariate polynomial satisfying a set of linear constraints. The novel contribution of this Master’s thesis is the introduction of a linear objective we aim to minimize. This problem is traditionally modelled as an SDP and solved using, for instance, an Interior Point Method. However, SDPs quickly become intractable due to the number of variables, which grows quadratically in the size of the problem. Hence, we rely on an idea proposed by Burer and Monteiro at the beginning of the 21st century, by considering an equivalent nonlinear formulation whose variables are the two polynomials of the sum-of-squares decomposition. Among the various methods that exist to solve such problems (Augmented Lagrangian, Projected Gradient, etc.), we opted for an approach based on manifolds. To this end, we study the feasible set in depth, in order to understand its structure. This allows us to derive a first-order Riemannian optimization algorithm, when the feasible set is a smooth manifold. The algorithm of Legat et al. is then used to obtain a feasible point from which the iterates will start. Although the feasible set is surprisingly smooth in many cases (when the constraint operator is bijective, or near pairs of polynomials sharing at most one common root), it turns out that it is not a smooth manifold for every set of linear constraints defining it. We demonstrate this by showing that the tangent cone is not a vector space at certain points of the set, for a specific set of constraints, around a pair of polynomials sharing two common roots. On such non-smooth sets, further work remains to be done, though we offer some insight by showing that they form stratified sets.