Lifting-Free Quadratic Sum-Of-Squares Programming
For researchers and practitioners in system identification and machine learning, this work provides a more efficient and scalable approach to solving QSOS problems, which are common in these fields.
This paper tackles the computational bottleneck in Quadratic Sum-Of-Squares (QSOS) optimization by introducing a lifting-free regularization that preserves the original conic structure. The method achieves up to 40% faster performance than existing solvers like SCS and handles larger problems than MOSEK, with memory scaling only in the number of equality constraints.
Quadratic Sum-Of-Squares (QSOS) optimization problems appear in system identification and machine learning, but standard Schur-complement and second-order cone liftings enlarge conic dimensions and create computational bottlenecks for interior-point methods. This paper introduces a lifting-free regularization that preserves the original conic structure by adding a norm penalty to SOS variables, yielding closed-form primal updates and an unconstrained, concave dual with Lipschitz-continuous gradient. Accelerated first-order methods efficiently maximize this dual, and convergence analysis shows non-asymptotic recovery of the solution. Numerical experiments on constrained regression problems show the proposed method can be 40\% faster than existing solvers such as SCS and handle larger problems than MOSEK, with memory scaling only in the number of equality constraints.