## Thursday, February 26, 2009

### Finding all roots with GAMS

> How do I find all roots of x^3-x^2-x=0 with GAMS.

GAMS is more geared towards solving large-scale nonlinear programming problems, where just one, hopefully optimal, solution is reported. The typical NLP solvers under GAMS support this single solution paradigm (they are using numerical optimization algorithms). A symbolic math package such as Mathematica would be ideally suited for a problem of finding all roots of a polynomial.

Update: See comment for a good solution using GAMS/BARON.

1. I tried two formulations to get the roots in gams.
It's interesting to note that from the nlp solvers I tested only baron seemed to work.

**** formulation 1
Scalar myeps / 1e-3 /;
Free Variable x;
Equation px_eq_zero;
px_eq_zero .. x*x*x - x*x - x =e= 0;

Model m_find_root / all /;

Option nlp=baron;

Solve m_find_root minimizing x using nlp;
Display x.l;

x.lo = x.l + myeps;
Solve m_find_root minimizing x using nlp;
Display x.l;

x.lo = x.l + myeps;
Solve m_find_root minimizing x using nlp;
Display x.l;

x.lo = x.l + myeps;
Solve m_find_root minimizing x using nlp;
Display x.l;

*** formulation 2

Scalar myeps / 1e-3 /;
Free Variable x;
Free Variable mytol;

Equation
px_eq_zero_b1
px_eq_zero_b2
;
px_eq_zero_b1 .. mytol =g= (x*x*x - x*x - x);
px_eq_zero_b2 .. mytol =g= -(x*x*x - x*x - x);

Model m_find_root / all /;

Option nlp=baron;

Solve m_find_root minimizing mytol using nlp;
Display x.l;

x.lo = x.l + myeps;
Solve m_find_root minimizing mytol using nlp;
Display x.l;

2. Great! Yes, you probably need a global solver for this (the usual NLP solvers will get stuck in a local optimum), and Baron is probably one of the best for for this (see http://www.mat.univie.ac.at/~neum/ms/comparison.pdf).

3. Is barron computationally very expensive when solving NLP or MINLPs comparing with other solvers?

4. Yes, Baron is much more demanding in terms of CPU time and memory usage than local NLP solvers like Conopt. As a result, local solvers can solve larger models. In return you get global solutions with Baron.

5. Baron can guarantee global? Can u mention a little bit ?
It is pitty I can ask Grossmann in a conference but I missed....

6. See: http://archimedes.cheme.cmu.edu/baron/baron.html