[Math] Minimizing the modulus of a polynomial around a circle

cv.complex-variablesoc.optimization-and-controlpolynomials

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.

Best Answer

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

Related Question