In this article, optimization problems over the cone of nonnegative trigonometric polynomials are described. We focus on linear constraints on the coefficients that represent interpolation constraints. For these problems, the complexity of solving the dual problem is shown to be almost independent of the number of constraints, provided that an appropriate preprocessing has been done. These results can be extended to other curves of the complex plane (real axis, imaginary axis), to nonnegative matrix polynomials and to interpolation constraints on the derivatives.