[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-core-devel
Subject:    Re: Need help for KSpread Maths
From:       Don Sanders <dsanders () cch ! com ! au>
Date:       1999-11-19 4:58:01
[Download RAW message or body]

I'm finding it quite fun too. I had a bit more of a look into it, I tried to
find a public domain implementation of GRG and couldn't, I did find some
interesting stuff.

There is a non-linear programming faq that talks about algorithms like
Generalized Reduced Gradient .

http://www.faqs.org/faqs/nonlinear-programming-faq/

(This talks about global optimization ie finding the minimum of f(x) but this
is similar to solving f(x) = 0, just minimize abs(f(x)) )


It references a number of public domain implementations, most are in fortran
one an implementation of the Hooke and Jeeves method is in c.

ftp://netlib2.cs.utk.edu/opt/hooke.c

/* Nonlinear Optimization using the algorithm of Hooke and Jeeves  */
/*	12 February 1994	 author: Mark G. Johnson 	   */

/* Find a point X where the nonlinear function f(X) has a local    */
/* minimum.  X is an n-vector and f(X) is a scalar.  In mathe-	   */
/* matical notation  f: R^n -> R^1.  The objective function f()    */
/* is not required to be continuous.  Nor does f() need to be	   */
/* differentiable.  The program does not use or require 	   */
/* derivatives of f().						   

The fact f takes a vector as input shouldn't be a problem just use a one
dimensional vector. I don't know why it says "local" minimum I'm quite sure its
designed to find absolute minimums.

Mark has this to say about Hooke and Jeeves
From http://mat.gsia.cmu.edu/GROUP94/0528.html

"Hooke-Jeeves is slow, It is "wasteful". It is also robust
as all get-out. I prefer my program to run for 5 minutes
and converge to the minimum 100% of the time, than for it to
run for 30 seconds and converge to the minimum 75% of the time.
But that's just _my opinion_. Yours may differ."

(I doubt it will take five minutes for normal problems, this was written in
1994 and assumes the function f to have a vector values domain, the hooke.c
example runs in a fraction of a second here).

I had a look at the code (it's only a couple pages long), I think it is exactly
the kind of thing Torben was looking for. The only small drawback is it requires
an extra parameter rho. 

I played with hooke.c a little trying it on the first trig function that fooled
excel (unfortunately I didn't save the six order polynomial). It solved it
fine using the default value of rho which is a good sign.

If nothing else it could be used to get something working quickly and then as a
comparison to the simulated annealing solution Cristian was talking about.

(No problem with the personal email thing)

BFN,
Don.


On Fri, 19 Nov 1999, Roberto Alsina wrote:
> On Fri, 19 Nov 1999, Don Sanders wrote:
> 
> > On Thu, 18 Nov 1999, Roberto Alsina wrote:
> > > On Thu, 18 Nov 1999, Antonio Larrosa wrote:
> > > 
> > > > Roberto Alsina wrote:
> > > > > 
> > > > > > I tried some polynomials I couldn't get it stuck in a cubic, which
> > > > > > indicates it has at least some smarts for getting out of/avoiding rel.
> > > > > > extrema. I did manage to get it stuck in a sixth order polynomial
> > > > > > which indicates it isn't that smart. (Numerical solutions for finding
> > > > > > the roots of any (finite) ordered polynomial to arbitrary precision
> > > > > > exist).
> > > > > 
> > > > > Maybe it uses multiple methods?
> > Probably not too many. From using it I get the impression that every time it
> > computes a new value for f(x) it recalculates the entire spread sheet including
> > updating the screen to show new values for all cells.
> > 
> > It seemed pretty basic to me. Actually it began to annoy me as I didn't actually
> > know what method it was using and it did fail quite often, it made me feel is
> > if it was just a toy that couldn't be relied on for serious work.
> > 
> > (Maybe getting a bit offtopic for kde-core?)
> 
> Maybe, but at least it's geeky and may be useful for a KDE app ;-)
> 
> A quick search in www.microsoft.com for "solver" shows some intriguing
> stuff!
> 
> For example, it seems the solver in Office 2000 is modular and
> replaceable (you can replace it with a VB module, just what all numerics
> expert recommend[1] ;-)
> 
> Anyway, MS is even kind enough to say what algorithm they use!
> 
> http://support.microsoft.com/support/kb/articles/Q82/8/90.ASP
> 
> 
> --------------
>    SUMMARY
> 
>    Microsoft Excel Solver uses the Generalized Reduced Gradient (GRG2)
> Algorithm for optimizing nonlinear problems. This algorithm was developed by Leon Lasdon, of the
> University of Texas at Austin, and Allan Waren, of Cleveland State University. 
> 
>    Linear and integer problems use the simplex method with bounds on the
> variables and the branch and bound method, implemented by John Watson and
> Dan Fylstra, of Frontline Systems, Inc.
> --------------
> 
> I must confess I had never heard of this algorithm before.
> 
> 
> [1] I can imagine the screaming: "Why can't I do it in FORTRAN!!!!"

[prev in list] [next in list] [prev in thread] [next in thread]