LP, SOCP, and Optimization-Free Approaches to Polynomial Optimization
summary
Presents LP and SOCP substitutes for sum of squares by enforcing DSOS/SDSOS LP and SOCP relaxations (diagonally dominant or scaled diagonally dominant Gram matrices), an iterative Cholesky-based basis update that often tightens bounds, and an optimization-free Polya-style certificate that proves positivity by constructing a higher‑degree homogeneous polynomial and checking that some power has nonnegative coefficients. Reports control experiments: SDPs for a 6‑link pendulum take hours or millions of variables while LP/SOCP versions solve in ~10 seconds and recover roughly 70% of SDP region volume. Also gives an Artin‑cone meta theorem for convergent hierarchies.
AI-written summary · about