Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables

Abstract

We propose general notions to deal with large scale polynomial optimization\nproblems and demonstrate their efficiency on a key industrial problem of the\ntwenty first century, namely the optimal power flow problem. These notions\nenable us to find global minimizers on instances with up to 4,500 variables and\n14,500 constraints. First, we generalize the Lasserre hierarchy from real to\ncomplex to numbers in order to enhance its tractability when dealing with\ncomplex polynomial optimization. Complex numbers are typically used to\nrepresent oscillatory phenomena, which are omnipresent in physical systems.\nUsing the notion of hyponormality in operator theory, we provide a finite\nconvergence criterion which generalizes the Curto-Fialkow conditions of the\nreal Lasserre hierarchy. Second, we introduce the multi-ordered Lasserre\nhierarchy in order to exploit sparsity in polynomial optimization problems (in\nreal or complex variables) while preserving global convergence. It is based on\ntwo ideas: 1) to use a different relaxation order for each constraint, and 2)\nto iteratively seek a closest measure to the truncated moment data until a\nmeasure matches the truncated data. Third and last, we exhibit a block diagonal\nstructure of the Lasserre hierarchy in the presence of commonly encountered\nsymmetries. To the best of our knowledge, the Lasserre hierarchy was previously\nlimited to small scale problems, while we solve a large scale industrial\nproblem with thousands of variables and constraints to global optimality.\n