Minimizing the modulus of a polynomial around a circle

Question

I'm probably missing something elementary here, but I guess the only way to be sure is to ask here.

Now, I have encountered a situation where given an nth-degree polynomial $p_n(z)$ with complex coefficients, and a positive real number $\rho$, I need to find the value(s) of $\theta$, $0\leq\theta<2\pi$, such that the value of $|p_n(\rho\exp(i\theta))|$ is minimized (i.e., find the lowest point of the absolute value of a complex polynomial around a radius $\rho$ circle). I know about the usual methods for univariate minimization (golden section, Brent's method, Newton"s method), but I am wondering if there may be special methods that can be used that are more efficient, given that the function to be minimized can be turned into a "trigonometric polynomial". Or would finding these minima be of the same level of difficulty as finding the roots of the polynomial itself?

Thus far, the only simplification I have been able to come up with is that if all the coefficients of $p_n(z)$ are real, I can restrict the search for the optimal $\theta$ in the interval $[0,\pi]$, since $p_n(\bar{z})=\overline{p_n(z)}$. A "grid search", using FFT to evaluate the polynomial at equispaced points around the circle was one idea I thought of, but it seemed wasteful of effort since I have been unable to find a way to reuse the effort done by FFT when the number of points around the circle is doubled.

In short: might there be an easier, more obvious way I am missing?

Addendum:

The application where I'm considering this procedure as a subroutine operates as follows:

1. The complex polynomial and an initial estimate of $\rho$ are given.
2. The minimization procedure finds the value of $\theta$ where the objective function is minimized; if there is more than one possible $\theta$, the value nearest to the positive real axis is taken (this is the rather ad hoc portion of the application I'm looking at).

3. The tentative $\theta$ is subjected to an "oracle" that

   a. if a success flag is returned, the algorithm exits, else

   b. a smaller value of $\rho$ is computed through another black-box procedure, and we return to step 2.

Answer 1

There is another way. Every non-negative trigonometric polynomial $f$ on the circle is of the form $|q|^2$, where $q$ is an analytic polynomial. (I mean by this that $f$ is of form $\sum_{-N}^N a_n z^n$ and $q(z) = \sum_0^N b_n z^n$). This is called the Fejer-Riesz theorem.

So, you guess a minimum for $|p|^2$, call it $m$, and then see whether $f = |p|^2 - m$ is the modulus squared of a polynomial (an algebraic identity). If it is, try again with larger $m$; if not, reduce $m$.

For a fuller account, see the survey article by Helton and Putinar:

@incollection {MR2389626, AUTHOR = {Helton, J. William and Putinar, Mihai}, TITLE = {Positive polynomials in scalar and matrix variables, the spectral theorem, and optimization}, BOOKTITLE = {Operator theory, structured matrices, and dilations}, SERIES = {Theta Ser. Adv. Math.}, VOLUME = {7}, PAGES = {229--306}, PUBLISHER = {Theta, Bucharest}, YEAR = {2007}, MRCLASS = {47-02 (14P10 47A13 47A57 47A63 90C22)}, MRNUMBER = {MR2389626 (2009i:47001)}, MRREVIEWER = {Joseph A. Ball}, }

-John E. McCarthy

Answer 2

As you note, given an nth-degree polynomial $p_n(z)$ with complex coefficients, and fixed $\rho$, the (squared) norm $|p_n(\rho\exp(i\theta))|^2$ is a "trigonometric polynomial". Say $f(\cos \theta,\sin \theta)$ for some $f(x,y)$ of degree 2n with real coefficients. Then ask if finding the absolute minimum would be of the same level of difficulty as finding the roots of the polynomial f itself. I would guess that, without further restrictions, it is (at least up to some constant factor like 2n at worse) Certainly the derivative is another such polynomial and one might seek its roots by one method or another. For example one can use trig identities to get this to a single variable polynomial (perhaps in terms of $\tan(\frac{\theta}{2})$ ). Would $f(x,y)$ have any properties that distinguish it from general real polynomials?. Maybe with some sampling one could (usually) search only for the root of the derivative in a certain intervals.

Answer 3

Suppose you have an upper bound for the minimum (the smallest value you have sampled so far). Given an interval on the circle and the value at that interval's midpoint, you should be able to find bounds on the value of the trigonometric polynomial on that interval (using Taylor or whatever). If the lower bound on the interval is bigger than the upper bound on the global minimum then the interval cannot contain the minimum, so reject it. Do this for a set of intervals covering the circle and after rejecting some of them, subdivide the rest and repeat.

Answer 4

This might be naive, but since it's a polynomial, ergo analytic, if there are no roots in the ball of radius $\rho$ then you know that the reciprocal is also analytic, and its maximum modulus over the closed ball is located somewhere on the circle. So maybe you can just pretend that you're maximizing over a domain in $\mathbb{R}^2$ and use something simple like steepest ascent (being sure to stay within the ball, of course).