Given the coefficients $a\_0,\ldots,a\_N$, $b\_1,\ldots,b\_N$ of a real trigonometric polynomial: 


$ f(x) = a\_0 + \sum\_{n=1}^N a\_n \cos(nx) + \sum\_{n=1}^N b\_n \sin(nx) $


is there any efficient way to approximately determine $\max\_{x \in R} f(x)$? If so, what is the accuracy versus efficiency tradeoff? 



The maximum of a real trigonometric polynomial
It turns out that it is possible to achieve an arbitrarily small additive error using semidefinite programming. This is from the paper: 


J.W. McLean, H.J. Woerdeman. Spectral factorizations and sums of squares representations via semidefinite programming. SIAM J. Matrix Anal. Appl., 23(3):646--655, 2001. ([link](http://dx.doi.org/10.1137/S0895479800371177))


The result can be rephrased as follows. Let $f(x)=F(e^{ix})$ where $F(z)= \sum\_{n=-N}^N c\_n z^n$, with $c\_n=\frac{1}{2}(a\_n-i\ b\_n)$ and $c\_{-n}=\bar{c}\_n$. Then $\min\_x f(x)$ is equal to $c\_0$ minus the value of the following semidefinite program:
$ min\_F\ tr(F) $ 
such that $F \succeq 0$, and $\sum\_{p=k}^N F\_{p,p-k} = c\_k$ for $k=1,\ldots,N$. 


Since semidefinite programming can achieve an arbitrarily small additive error, we can approximate the minimum (and thus, the maximum) of $f$ within the same bound. 


