Presentation UCL 19/02/2013

You will find here the slides of my presentation, but before that, here are some precisions about the talk.

The main reference for the talk is Jean Bernard Lasserre’s book “Moments, Positive Polynomials and Their Applications“, Imperial College Press, 2009. ISBN 978-1-84816-445-1. This book presents an overview of the moment approach in its first few chapters, then details some specific applications in the remaining chapters. Global optimization on polynomials is presented on chapter 5, and application to bounded controls is presented on chapter 10.

For the software part, the Matlab toolbox I used for polynomial optimization is GloptiPoly developped by Didier Henrion, Jean Bernard Lasserre and Johan Loefberg. The add-on for Polynomial Optimal Control Problems, POCP, was developped by Didier Henrion, Jean Bernard Lasserre and Carlo Savorgnan.

Now, the questions I had. Concerning flat extensions in the multi-dimensionnal case, I follow theorem 3.7 in Jean Bernard Lasserre’s book. It states that we have this “stalled rank condition” on moment matrices if and only if the moment sequence has a representing measure that is k (= the rank)-atomic. Hence if we observed this stalled rank condition at some relaxation order, then flat extensions (= adding moments one order up while preserving positive semi-definiteness) exist and are unique. The theorem for real moments comes straight from Curto and Fialkow as I mentioned, see for instance theorem 2.19 of Truncated K-moment problems in several variables  Journal of Operator Theory 54(2005), 101-138. Some earlier results by the same authors exist for complex moments sequences.

Concerning the numerical stability of the extraction algorithm to perturbed data, well, the bad news is that it might not be excellent for two reasons. The good news is that we don’t have any moment sequences, but ones that comes from a particular problem of polynomial optimization. So what are the sources of numerical errors? As I mentioned, one of the operation behind the linear algebra routine is not numerically stable (although it has been observed to behave statistically well, see Lasserre’s book at the end of section 4.3). Another reason was raised during the questions, about the poor conditioning of the moment matrix in the monomial basis, which is problematic yet not dramatic as we never reach high relaxation orders in practice. Note that both these technical problems can be lifted by changing the implementation of the software, but at a cost of much greater coding complexity. So can this problem be circumvented easily in some way? The answer is yes, because once we have extracted our solutions, we can always inject them in our original polynomial optimization problem, check their admissibility and their cost compared to the lower bound that was given, and reject those solutions if not satisfactory. This was the choice made for GloptiPoly, to keep software complexity at a minimum.

And before the slides, let me thank again Raphaël Jungers for the invitation!

NB: to advance animations, press space. To advance slides with all the animations performed, press the right arrow.