Lifting-Free Quadratic Sum-Of-Squares Programming

Abstract

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.