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

I have a polynomial:

$$f(x_1 \dots x_n) = \prod_{i=1}^n (c_ix_i + 1) - \frac{1}{2}c_0\sum_{i=1}^nx_i^2$$

Given some values for $c_0 \dots c_n$, I'd like to choose the maximizing values for $x_1 \dots x_n$. I'm not concerned with the actual maximum value of $f(x_1 \dots x_n)$, only the values of the inputs $x_1 \dots x_n$, so if there is an equivalent function maximized at the same values I value the solution just as much. The values for any $c$ and any $x$ can be any real value.

I'm not familiar with any easy ways to do this with a polynomial of this type. My best guess is gradient ascent, but I'm not sure the function is convex.

Can anyone tell me if the function is convex, or failing that, if there's another way to find an (approximate) global argmax?

share|improve this question
2  
What values are these variables allowed to take? –  Gjergji Zaimi Jan 10 '12 at 6:43
3  
Note that if there are at least 3 nonzero coefficients among $c_1\dots c_n$ then $f$ is unbounded, both from above and from below. –  Pietro Majer Jan 10 '12 at 9:56
    
@Pietro Majer - I'm missing something; Can you explain why this is the case? –  Charles Parker Jan 11 '12 at 1:22
    
@Gjergji Zaimi - The variables must take real values. I've edited the question. –  Charles Parker Jan 11 '12 at 1:25
    
Presumably you want the subscripts in your product and sum to range over $i=1,\ldots,n$, rather than have each term pinned to its value at sub$_n$. –  Joseph O'Rourke Jan 11 '12 at 12:03
show 3 more comments

1 Answer

up vote 2 down vote accepted

As noted by Pietro in the comments only a few combinations of $n$ and coefficients will even have a finite maximum, unless you bound your domain. For example, consider $c_0=-2$ and all other $c_i=0$. Even this is unbounded above.

Now, let's assume you either bound your domain, or have ensured that the polynomial is bounded above. The problem of finding the argmax is computationally "difficult" for large $n$ (as in: the cryptography guys worry about this stuff a lot at least in finite fields), so numerical optimization methods do probably make sense. Assuming your coefficients are sufficiently generic, a sequential quadratic programming technique will definitely work much better than gradient-climbing.

Your main problem is going to be the perennial one of having lots of local argmaxes without necessarily finding the best of them. You'll have to find them by combining your local optimization with something like a simulated annealer or differential evolution. In principle, with a polynomial, you get to count roots and therefore know whether you have them all.

share|improve this answer
    
Just to be absolutely clear, the answer in the bounded domain world is: 1.) Use sequential quadratic programming to optimize instead of gradient ascent and 2.) The function is, in general, non-convex, though root counting may help sort through local maxima. –  Charles Parker Jan 23 '12 at 1:10
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.