Speaker: Kim-Chuan Toh 教授，新加坡国立大学

Title: A Low-rank Augmented Lagrangian Method for Polyhedral–SDP and Moment-SOS Relaxations of Polynomial Optimization

Language: English

Time & Venue: 2026.07.22 10:00-11:00 南楼N613

Abstract: Polynomial optimization problems (POPs) admit geometric convex conic

reformulations (Kim–Kojima–Toh, SIOPT 30, 2020), though they remain NP-hard. We show that several well-known relaxations can be unified under a polyhedral–SDP framework obtained by approximating the intractable cone with intersections of polyhedral cones and the PSD cone. While yielding tight lower bounds, these relaxations become costly as variable dimensions and number of constraints scale as $\Omega(n^{2\tau})$ with the relaxation order $\tau$.

We introduce RiNNAL-POP, a low-rank augmented Lagrangian method (ALM) to solve these large-scale polyhedral–SDP relaxations. For $\Omega(n^{2\tau})$ nonnegativity and consistency constraints, we design a projection scheme whose cost is linear in the number of variables. We further expose facial structure in the relaxation and restrict the matrix variable to affine subspaces tied to exposed faces of the PSD cone, eliminating many linear constraints and enabling efficient factorized ALM subproblems. Each ALM iteration also applies a single projected-gradient step on the original matrix variable to adapt rank and escape spurious local minima when needed. We also extend the framework to moment- SOS relaxations. Experiments on various benchmarks show that RiNNAL-POP is robust and efficient for large-scale polyhedral–SDP relaxations.

[Based on joint work with Di Hou and Tianyun Tang]