Polynomial Optimization via Random Projection and Consensus

2025/09/16 by Etienne Buehrle, Christoph Stiller, Buehrle, Etienne +1
Computer Science · #28A99 #90C22 #93C10 #Data Management and Algorithms #FOS: Mathematics #Logic, programming, and type systems #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2509.12859

openalex publication_date 2025/09/16 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28

Abstract

We propose a black-box approach to reducing large semidefinite programs to a set of smaller semidefinite programs by projecting to random linear subspaces. We evaluate our method on a set of polynomial optimization problems, demonstrating improved scalability.

Citations

• Stochastic Optimal Control via Measure Relaxations
• Solving natural conic formulations with Hypatia.jl
• Sum-of-squares optimization without semidefinite programming
• DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization
• Выпуклая оптимизация
• Nonlinear optimal control via occupation measures and LMI-relaxations
• Decoding by Linear Programming
• Symmetry groups, semidefinite programs, and sums of squares

Related

• Sparse Sub-gaussian Random Projections for Semidefinite Programming Relaxations
• Random projections for conic programs
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Semi-infinite programming using high-degree polynomial interpolants and\n semidefinite programming
• Reducing Stochastic Games to Semidefinite Program Feasibility