A low-rank augmented Lagrangian method for polyhedral-SDP and moment-SOS relaxations of polynomial optimization

• 成果类型: Article; Early Access
• 署名作者: Hou, Di; Tang, Tianyun; Toh, Kim-Chuan
• 署名单位: National University of Singapore; University of Chicago; National University of Singapore
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02395-5
• 发表日期: 2026-07-08
• 关键词: semidefinite programming; augmented Lagrangian; polynomial optimization; semidefinite; binary; cone

摘要

Polynomial optimization problems (POPs) can be reformulated as geometric convex conic programs, as shown by Kim, Kojima, and Toh (SIOPT 30:1251-1273, 2020), though such formulations remain NP-hard. In this work, we prove that several well-known relaxations can be unified under a common polyhedral-SDP framework, which arises by approximating the intractable cone by tractable intersections of polyhedral cones with the positive semidefinite matrix cone. Although effective in providing tight lower bounds, these relaxations become computationally expensive as the number of variables and constraints grows at the rate of Omega(n2 tau) with the relaxation order tau . To address this challenge, we propose RiNNAL-POP, a low-rank augmented Lagrangian method (ALM) tailored to solve large-scale polyhedral-SDP relaxations of POPs. To efficiently handle the Omega(n2 tau) nonnegativity and consistency constraints, we design a tailored projection scheme whose computational cost scales linearly with the number of variables. In addition, we identify a hidden facial structure in the polyhedral-SDP relaxation, which enables us to eliminate a large number of linear constraints by restricting the matrix variable to affine subspaces corresponding to exposed faces of the semidefinite cone. The latter enables us to efficiently solve the factorized ALM subproblems over the affine subspaces. At each ALM iteration, we additionally carry out a single projected gradient step with respect to the original matrix variable to automatically adjust the rank and escape from spurious local minima when necessary. We also extend our RiNNAL-POP algorithmic framework to solve moment-SOS relaxations of POPs. Extensive numerical experiments on various benchmark problems demonstrate the robustness and efficiency of RiNNAL-POP in solving large-scale polyhedral-SDP relaxations.