Multi-ordered Lasserre hierarchy for large scale polynomial optimization in real and complex variables
Preprint
Abstract
We propose general notions to deal with large scale polynomial optimization problems and demonstrate their efficiency on a key industrial problem of the twenty first century, namely the optimal power flow problem. These notions enable us to find global minimizers on instances with up to 4,500 variables and 14,500 constraints. First, we generalize the Lasserre hierarchy from real to complex to numbers in order to enhance its tractability when dealing with complex polynomial optimization. Complex numbers are typically used to represent oscillatory phenomena, which are omnipresent in physical systems. Using the notion of hyponormality in operator theory, we provide a finite convergence criterion which generalizes the Curto-Fialkow conditions of the real Lasserre hierarchy. Second, we introduce the multi-ordered Lasserre hierarchy in order to exploit sparsity in polynomial optimization problems (in real or complex variables) while preserving global convergence. It is based on two ideas: 1) to use a different relaxation order for each constraint, and 2) to iteratively seek a closest measure to the truncated moment data until a measure matches the truncated data. Third and last, we exhibit a block diagonal structure of the Lasserre hierarchy in the presence of commonly encountered symmetries. To the best of our knowledge, the Lasserre hierarchy was previously limited to small scale problems, while we solve a large scale industrial problem with thousands of variables and constraints to global optimality.Keywords
All Related Versions
This publication has 50 references indexed in Scilit:
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronizationMathematical Programming, 2016
- On the Implementation and Usage of SDPT3 – A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Version 4.02011
- A generalized flat extension theorem for moment matricesArchiv der Mathematik, 2009
- A note on the representation of positive polynomials with structured sparsityArchiv der Mathematik, 2007
- Truncated Trigonometric Moment Problems and Determinate MeasuresJournal of Mathematical Analysis and Applications, 1999
- The Complex Moment Problem and Subnormality: A Polar Decomposition ApproachJournal of Functional Analysis, 1998
- Nearly Subnormal Operators and Moment ProblemsJournal of Functional Analysis, 1993
- TheK-moment problem for compact semi-algebraic setsMathematische Annalen, 1991
- Normal Dilations and Extensions of Operators1983
- On the representation of hermitian forms as sums of squaresInventiones Mathematicae, 1968