4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I'm not familiar enough with this topic to answer sensibly; but I know these kinds of questions have been studied and are definitely non-trivial in general. So don't worry, you're not missing anything obvious! $\endgroup$
    – Zen Harper
    Aug 12, 2010 at 5:15
  • $\begingroup$ Also, there is a very large amount of stuff about this; do you have any additional information about the coefficients? If so, there's a higher chance of being able to do something. $\endgroup$
    – Zen Harper
    Aug 12, 2010 at 5:17
  • $\begingroup$ Nope, I can't think of any structure in the polynomials that can be exploited; I already mentioned the problem being somewhat easier if the polynomial had real coefficients. $\endgroup$ Aug 12, 2010 at 5:20
  • $\begingroup$ I probably should hasten to add that for the time being, I'm assuming $p_n(z)$ is represented in the monomial basis ($p_n(z)=c_n z^n+c_{n-1}z^{n-1}+\ldots$), but it would probably be better if the method can be made "basis-agnostic", e.g. if the polynomial is in fact represented as a Chebyshev series, so that one would not have to perform a basis conversion which can be ill-conditioned. $\endgroup$ Aug 12, 2010 at 7:21

4 Answers 4

6
$\begingroup$

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

$\endgroup$
3
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Yes, you're right, it is the square of the modulus that is a trigonometric polynomial and not the modulus itself, sorry. (I was typing from handwritten notes in a hurry). I guess my pessimism that this would be easier than root-finding was well-placed. From limited tests, even with the restriction of $\theta$ to $[0,2\pi)$ (or $[0,\pi]$ for the real-coefficient case), the objective function gets more oscillatory with increasing degree. The only sampling I have done is through FFT, but I still can't help but feel one can do better... $\endgroup$ Aug 12, 2010 at 14:06
  • $\begingroup$ The approach I had been taking so far was to sample the circle at $2^j$ points (starting with the least power of 2 greater than the degree of the polynomial) with FFT, cache the smallest values found and the associated angles, repeat by doubling the number of sample points... as you might be able to tell, I am unable to use an FFT implementation (e.g. FFTW) that can handle data lengths not a power of 2. Even with a subsequent polishing with golden section search, I seem to be unable to capture global minima. I also feel this sampling technique is doing a lot of redundant computations. $\endgroup$ Aug 12, 2010 at 14:22
  • 1
    $\begingroup$ The will only be 2n changes of direction in the size so son you will know of n intervals on which it changes some place in the interior from decreasing to increasing. Then you can limit the search to those. If you just want the absolute minimum then you might be able decide that some intervals do not need to be further searched. If trig function evaluations take time then you could change to a polynomial in terms of $\cos(\theta))$ or $\tan(\theta/2)$ and then resolve for $\theta$ at the end. Note that you can stick to the unit circle by just absorbing powers of $\rho$ into the coefficients. $\endgroup$ Aug 12, 2010 at 17:03
  • $\begingroup$ If I do that cosine variable substitution, that might mean that I will have to use a fast DCT (discrete cosine transform) instead of an FFT; I'll have to figure out how to manipulate my array of coefficients so that it represents a cosine polynomial... and I knew I forgot something elementary, you're right about the problem being reducible to just looking at the unit circle! Thank you! $\endgroup$ Aug 12, 2010 at 22:13
  • $\begingroup$ After looking through my notes again, I now recall why I explicitly did not do the absorption of powers of $\rho$ in the coefficients of the monomial basis: I was hoping the method to be basis-agnostic. If my polynomial were a Chebyshev or Bernstein series for instance, it's going to be complicated absorbing them into the basis polynomials, and as mentioned basis conversion can be a bad idea in inexact arithmetic. $\endgroup$ Aug 14, 2010 at 6:20
1
$\begingroup$

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.

$\endgroup$
3
0
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ Well in the application I'm considering, it can happen that the polynomial has roots in the disk, so I suppose reciprocation will net me unsightly poles... :( I just need minima on the circle, not inside the disk. $\endgroup$ Aug 14, 2010 at 5:37
  • $\begingroup$ What if you took a narrow annulus just inside (or just outside, you might have to experiment) the circle and performed the optimization there? (maybe mapping it to a strip if that makes the arithmetic earlier) The nice thing about analytic functions is that the maximum modulus will not be inside the disk: it will be on the boundary (en.wikipedia.org/wiki/Maximum_modulus_principle). So you should be able to conveniently "forget" that you're maximizing over $\mathbb{C}$ and use $\mathbb{R}^2$ methods with an objective function that just "happens to" have a maximum on the boundary. $\endgroup$
    – JCK
    Aug 15, 2010 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.