Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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! –  Zen Harper Aug 12 '10 at 5:15
    
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. –  Zen Harper Aug 12 '10 at 5:17
    
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. –  J. M. Aug 12 '10 at 5:20
    
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. –  J. M. Aug 12 '10 at 7:21
add comment

4 Answers

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

share|improve this answer
    
"Fejer-Riesz"... thank you kindly, that's one keyword that could help me with my literature searches! I will comb through the resources I have and get back here with what I pull. –  J. M. Aug 12 '10 at 14:01
    
To save other people who may be reading this some legwork, here is the article John was referencing: math.ucsd.edu/~helton/M241/tibi241ClassCut08.pdf –  J. M. Aug 12 '10 at 15:53
    
A copy of the paper can also be found at arxiv.org/abs/math/0612103 –  J.J. Green Dec 29 '13 at 10:26
add comment

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.

share|improve this answer
    
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... –  J. M. Aug 12 '10 at 14:06
    
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. –  J. M. Aug 12 '10 at 14:22
1  
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. –  Aaron Meyerowitz Aug 12 '10 at 17:03
    
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! –  J. M. Aug 12 '10 at 22:13
    
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. –  J. M. Aug 14 '10 at 6:20
add comment

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.

share|improve this answer
    
Your proposal looks like it will be an administrative headache to implement, but I'll consider it. –  J. M. Aug 14 '10 at 5:42
1  
This might help: soliton.vm.bytemark.co.uk/pub/jjg/en/code/maxmod.html –  J.J. Green Aug 16 '10 at 9:47
    
Wow, I found your paper: soliton.vm.bytemark.co.uk/pub/jjg/papers/maxmod.pdf after looking through the refs, I might only have to modify it in a few places to get it to do what I need. Thanks! –  J. M. Aug 17 '10 at 2:42
add comment

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

share|improve this answer
    
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. –  J. M. Aug 14 '10 at 5:37
    
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. –  JCK Aug 15 '10 at 2:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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