The moment hierarchy in polynomial optimization: introduction and application to power systems

Abstract

The moment-SOS hierarchy reformulates polynomial optimization problems — for which the objective and constraints are encoded by polynomial functions — as linear problems over infinite dimensional spaces. Such reformulations can then be tackled by a sequence of finite dimensional convex (semidefinite) problems. Under standard assumptions, this sequence benefits from theoretical convergence guarantees [1]. The moment-SOS approach is thus a promising technique to compute global minima for polynomial optimization problems, which are nonconvex in general. Indeed, for such problems, standard nonlinear solvers are only guaranteed to converge to a local solution. In this talk, I will give an introduction to the field of the moment-SOS hiearchy and will cover both theoretical and practical aspects of the method. To make the presentation more concrete, I will illustrate my talk with applications to the AC-OPF (Alternative Current - Optimal Power Flow) problem arising in power systems economics and engineering. The AC-OPF problem aims at minimizing operational costs of a power grid while satisfying powerflow equations enforcing the balance between production and consumption. This problem is known to be NP hard — due to the nonlinearity of the balance equations. However, in practice, the moment hierarchy has proved relevant to compute the global minimum of AC-OPF instances [2]. I will also present some numerical test cases based on real data collected by transmission system operators.