AC-OPF (Alternative Current - Optimal Power Flow) aims at minimizing the operating costs of an AC power grid. It is well-known to be a difficult optimization problem in general, as it reformulates as a nonconvex QCQP (Quadratically Constrained Quadratic Program).

The moment-SOS (Sums-Of-Squares) hierarchy has proved relevant to solve AC-OPF instances to global optimality. However, obtaining the convergence of the hierarchy may requires to go beyond the first step of the involved sequence of SDP (Semidefinite Programming) relaxations and thus to solve semidefinite programs whose size grows drastically at each step of the hierarchy. Thus, the application of such relaxations to large scale AC-OPF problems (with thousands of variables) remains a challenging computing task.

Large polynomial optimization problems can be tackled efficiently if they are sufficiently sparse. In this talk, we present a new sparsity pattern, that we call minimal sparsity, inspired by the specific structure of the AC-OPF problem.

We show that minimal sparsity enables the computation of second order moment-SOS relaxations on large scale AC-OPF instances with far less computing resources --- i.e. RAM and time --- than the standard correlative sparsity pattern. Experimentally, we observe that it also provides tight lower bounds to certify the global optimality of AC-OPF solutions.

Sum-of-squares (SOS) polynomials with rational coefficients in the interior of the SOS cones are sums of rational squares, meaning that they can be written as a sum of squares of rational polynomials, allowing for easy certification of their nonnegativity. The complexity of these certificates is measured by their bit sizes but are challenging to bound even in the univariate case. We study this problem in the context of dual certificates, which are rational vectors from the dual-SOS cone that can be interpreted as efficiently verifiable nonnegativity certificates.

The talk will outline a very simple algorithm to compute a sequence of SOS lower bounds converging linearly to the optimal SOS lower bound and corresponding "small" rational dual certificates, whose bit sizes can be bounded as a function of interpretable parameters such as the degree and the number of variables of the polynomials, or their distance from the boundary of the cone. After providing a general complexity bound, we explore a few frequently studied special cases.