Date: Friday, October 9

Time: 11:30 am – 12:30 pm

Room location: GHC 4405

Zoom link: https://cmu.zoom.us/j/9873588831

Title: AdaSoS: Escaping the Exponential Cost of Higher-Order Sum-of-Squares Relaxations

Abstract:

Many problems in robotics, power systems, and machine learning are nonconvex polynomial optimization problems; local solvers return an answer but cannot tell you how far it is from the best one. The Sum-of-Squares (SoS) hierarchy fixes this with a sequence of convex semidefinite relaxations that give certified lower bounds and, at high enough degree, the global optimum. The catch is cost. Each step up the hierarchy grows the relaxation exponentially, which puts higher-order SoS out of reach for real problems such as AC optimal power flow (AC-OPF), the problem of scheduling generators on the electric grid.

This talk presents Adaptive-SoS (AdaSoS), which gets the tightness of a higher-order relaxation without building it. AdaSoS checks whether the current low-order solution could extend to a valid higher-degree one. When it cannot, the failure itself identifies which polynomial directions are missing, and AdaSoS adds only those. We prove that AdaSoS reaches the full higher-order bound in finitely many steps. On our largest AC-OPF relaxation, it certifies the global optimum 13× faster than the full higher-order relaxation, with a 77% smaller semidefinite block. At the highest degree we solve, it matches or improves on the bounds of existing approaches such as TSSOS, CS-TSSOS, and the adaptive hierarchy of Josz and Molzahn, typically with a much smaller semidefinite block. AdaSoS can also start from cheaper sparse relaxations, which lets it scale: on the IEEE 300-bus system, where the dense higher-order relaxation does not fit in memory, AdaSoS started from a sparse degree-1 relaxation tightens its bound to within 0.14% of the best known AC-OPF solution.

Dr. Geoff Gordon (advisor)

Dr. Drew Bagnell

Dr. Changliu Liu

Xinyu Li