  We propose a homogeneous primal-dual interior-point method to solve
sum-of-squares optimization problems by combining non-symmetric conic
optimization techniques and polynomial interpolation. The approach optimizes
directly over the sum-of-squares cone and its dual, circumventing the
semidefinite programming (SDP) reformulation which requires a large number of
auxiliary variables. As a result, it has substantially lower theoretical time
and space complexity than the conventional SDP-based approach. Although our
approach avoids the semidefinite programming reformulation, an optimal solution
to the semidefinite program can be recovered with little additional effort.
Computational results confirm that for problems involving high-degree
polynomials, the proposed method is several orders of magnitude faster than
semidefinite programming.
