Re: Finding an n-variable polynomial's root.


Robert Israel wrote:
> In article
<5113344.1115919478578.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>,
> Daniel Lichtblau <danl@xxxxxxxxxxx> wrote:
> >This new information indicates a need for a constrained rather than
> >unconstrained optimization approach. Below is a simple example in
> >Mathematica. I'll generate a sum of squares that vanishes on some
corner
> >of the unit hypercube with corners all +-1.
>
> >n = 100;
> >vars = Array[x,n];
> >poly = Sum[(x[j]+2*Random[Integer]-1)^2, {j,n}];
>
> >One way to find the corner where it vanishes is via the function
> >NMinimize, passing the square of the polynomial as objective
function
> >(in this simple example, the polynomial is nonnegative and so need
not
> >be squared), and the constraints that define your cube of interest.
>
> >Timing[{min,s1} =
> > NMinimize[{poly^2, Table[-1<=x[j]<=1,{j,n}]}, vars];]
>
> >I get a result in a few seconds, using whatever is the default
method.
> >For this type of problem (polynomial objective function, linear
> >constraints), it may be best to use an interior point method. In
> >Mathematica this might be done as below.
>
> >Timing[{min2,s2} =
> > NMinimize[{poly^2, Table[-1<=x[j]<=1,{j,n}]},
> > vars, Method->NonlinearInteriorPoint];]
>
> >The quality is not as good (the +-1's are approximated only to about
> >three or four places) but it is about twice as fast. Offhand I do
not
> >know how speed/precision will be for other software but my guess is
a
> >similar relation will hold: IP methods will be generally faster than
> >other methods, but might give results that are not as precise.
>
> It looks to me like this is using a local search method. Your
particular
> example is monotone in each variable, so it won't get stuck in a
local
> minimum, but that won't be true in general. There are global
minimization
> methods, but for a problem in dimension 100 or more they won't be
very
> practical.
>
> Actually a suitable version of the problem is NP-complete: given a
> polynomial P(x_1,...,x_n) in n variables with integer coefficients
such
> that P(x_1,...,x_n) >= 0 on [0,1]^n, is there (x_1,...,x_n) in
{0,1}^n
> where P(x_1,...,x_n) = 0? In fact we can even assume P is quadratic.
>
> One way to see this is to reduce the INDEPENDENT SET problem (which
is
> known to be NP-complete) to this one:
> given a graph with n vertices, and positive integer m, is there
> a set S of size m such that no members of S are joined by an edge?
The
> reduction is made using the quadratic polynomial
>
> P(x_1,...,x_n) = sum_{edges <i,j>} x_i x_j + (sum_i x_i - m)^2
>
> where S is an independent set of size m iff P(x_1,...x_m) = 0
> where x_i = 1 for i in S, 0 otherwise.
>
> Robert Israel israel@xxxxxxxxxxx
> Department of Mathematics http://www.math.ubc.ca/~israel
> University of British Columbia Vancouver, BC, Canada


As regards NMinimize, the default method is global. This of course does
not mean it will not get trapped by local minima. For improved
robustness, Method->DifferentialEvolution will give reasonable results
at dimension 100 but might be too slow much beyond that. On this
example it took about 40 seconds on the same machine that took 7 and 4
seconds respectively for Automatic and NonlinearInteriorPoint.
Experience indicates that, while slower, differential evolution tends
to be far likely to fall into any local tarpits.

The special case of interior point method is indeed local. So I guess
that means it is even more likely to be captured by a local minimum.

I was probably a bit derelict in showing that method. I am told that
the "established" way to use it is as a submethod to a random search
approach. The idea being that one tries many points as starting values
and applies NIP from each. Something like (I'm not sure I have this
exactly correct)

Method->{RandomSearch, SearchPoints->...,
Method->NonlinearInteriorPoint}

Needless to say all this detail is specific to a particular Mathematica
functiom. Your point regarding the difficulty of such problems is well
taken but that does not stop people from proposing practical
methodologies for constrained global optimization. Regardless of
whether NMinimize in Mathematica will adequately handle the problems
the OP had in mind, a similar setup should be applicable for other
optimizers.


Daniel Lichtblau
Wolfram Research

.

Relevant Pages

  • Re: Finding an n-variable polynomials root.
    ... >This new information indicates a need for a constrained rather than>unconstrained optimization approach. ... >constraints), it may be best to use an interior point method. ... As regards NMinimize, ... Needless to say all this detail is specific to a particular Mathematica ...
    (sci.math.symbolic)
  • Re: Behaviour of FMINCON - question.
    ... The large-scale algorithm is a subspace trust region method and is ... Medium-Scale Optimization ... Use equality constraints and the medium-scale method instead. ... Methods for Large-Scale Nonlinear Minimization Subject to Bounds," ...
    (comp.soft-sys.matlab)
  • Re: Non-linear least squares using piece-wise approximation....
    ... "x" by a piecewise linear approximation, ... and if "x" is the value of the optimization variable where the k-th ... Additionally there are mutual exclusivity constraints e.g. x_0 and x_7 ... constrained, nonlinear least-squares solver, but I'm not clear as to ...
    (sci.math.num-analysis)
  • Re: Non-linear least squares using piece-wise approximation....
    ... "x" by a piecewise linear approximation, ... and if "x" is the value of the optimization variable where the k-th ... The problem can now be stated in matrix-vector terms as: ... Additionally there are mutual exclusivity constraints e.g. x_0 and x_7 ...
    (sci.math.num-analysis)
  • Re: Finding an n-variable polynomials root.
    ... I'll generate a sum of squares that vanishes on some corner ... passing the square of the polynomial as objective function ... and the constraints that define your cube of interest. ... >Mathematica this might be done as below. ...
    (sci.math.symbolic)