Re: Algorithm or method for finding maximum of a long polynomial

On Mon, 21 Jul 2008 22:22:15 -0700, "Dann Corbit"
<dcorbit@xxxxxxxxx> wrote:

"Gregor" <ghulok02@xxxxxxxxx> wrote in message
news:3d641dba-2273-4e57-8687-df4c02d35a64@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I've got a polynomial with a couple hundred terms, but less than 30
variables, the variables will have a value of between 1 and 4000, and
I need know the approximate values of the variables at the maximum.

It doesn't have to be fast.

Apparently this could be done by passing it through MathLink to
mathematica using the Maximum function, but I don't have access to
mathematica. (
http://www.scientific-solutions.ch/tech/mathematica/products/mma/newi...
)

I have tried to figure out a suitable method by using graph sketching
techniques from calculus, too, but I'm stumped. I tried to find the
reciprocal-of-the-slope of the normal of a plane or hyperplane, then
find all solutions for when it was zero, then evaluate the polynomial
with those values, like, imagine a bumpy surface (this would be for 2
variables but can be extended), and a plate tangential to the curve at
a point, when the plate is tangential to a point at a valley or a peak
the normal of the plane will be vertical.....

If you mean, as I take you to mean, that you have a polynomial in
multiple variables, then at the maximum all of the partial
derivatives will be zero. Frex

F(x,y) = x+y -x^2 -y^2
dF/dx = 1-2x = 0
dF/dy = 1-2y = 0

with a maximum at (1/2,1/2).

If, as you indicate, there are boundary constraints then things
get a bit messy. The boundary constraints specify a hypercube.
If the maximum is at an interior point then the system of
equations given by the partials will give it. Otherwise the
maximum lies on one of the faces. If that is your problem I
suggest that ask in sci.math.num-analysis.



1. If the polynomial is odd, it does not have a maximum.

2. If the polynomial is even and the largest term is positive it does not
have a maximum.

3. So you are left with even polynomials for which the largest term is
negative.

If you take the derivative of the polynomial (trivial operation) and find
the roots of this new polynomial, then you can evaluate the original
polynomial at these roots. One of them will be the maximum (given the above
3 restrictions).

That's for a polynomial in one variable. If I read his post
correctly, that is not what he is looking for.


Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.

Relevant Pages

  • Re: JSH: Keep it simple
    ... arbitrary rule that you take roots of monic polynomials with integer coefficients. ... integral root is divisible by something that is coprime to ... Your claim regarding rational roots of this polynomial cannot do that, since the standard theory makes no claims regarding common factors among such roots. ...
    (sci.math)
  • Re: Orthogonal polynomials (was Chebyshv, etc.)
    ... Legendre, Chebyshev, Hermite, etc.) have n real roots in the ... This general property of orthogonal polynomials is proved as ... you can simply ignore any zeros ... If alpha is a real root of phi_k, ...
    (sci.math)
  • Re: New paper, algebraic integers, Galois Theory
    ... > Now consider the case that m, f, and u are algebraic integers, then I ... > something about the factors of roots of monic polynomials with integer ... Note that this claim does not require Galois Theory, ...
    (sci.math)
  • Re: Question on algebraic numbers
    ... adjoining to Q the roots of all polynomials over Q. ... extensions of Q which have a solvable Galois group. ... solutions by radicals). ...
    (sci.math)
  • Re: Some math, algebraic integers
    ... >> Like, yeah, the polynomial has rational roots, which is what I already ... are mathematicians as a group as big about their ... > be related to the coefficients of their irreducible polynomials. ... So I said, hey, it all follows in the ring of algebraic integers too! ...
    (sci.math)