2
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$ Jan 10, 2012 at 9:56
  • $\begingroup$ @Pietro Majer - I'm missing something; Can you explain why this is the case? $\endgroup$ Jan 11, 2012 at 1:22
  • $\begingroup$ Following up on Pietro's comment: Suppose wlog that $c_1,c_2,c_3\neq 0$. Consider the behaviour of $f$ along the line $\{(x,x,x,0,\dots,0)|x\in\mathbb{R}\}$: It reduces to $g(x) = c_1c_2c_3x^3+h(x)$, where $h$ is quadratic, so $g$, and therefore also $f$, is unbounded in both directions. $\endgroup$ Jan 11, 2012 at 12:14
  • $\begingroup$ @Klaus Draeger - Yes, I spent some time thinking about Pietro's comment yesterday and came to understand it as you explain; $L_2$ regularization is too weak for this problem. It was force of habit that caused me to reach for it right away. If you or Pietro would like to post something like your comment as an answer to the problem I'll accept it. If I figure out a reasonable way to regularize here I'll post a new question. Thanks! $\endgroup$ Jan 13, 2012 at 6:33

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jan 23, 2012 at 1:10

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.