Non-linear equations solver

[KP]

Hi all,

Don't know if there are still any active members reading the group. I
recently created an "online" non-linear equations solver at
xyzsolve.appspot.com. It's not a full-fledged equation solving
environment but it's quite useful for one-off problems. Please let me
know if anyone finds this useful.

Thanks,
Kiran

[Dudley, Jeremy]

I Played with your provided examples, and it looks nice - it can do with
more documentation about setting up problems. For example, does f.min =
0 mean that f should never have a value below 0, or that the aim is to
minimise f? (I'm guessing the former). Did you write the solver, or are
you a front-end to a Google-provided solver?


J Dudley
+44 (0)1793 865049

-------------------------------------------------------------------------------------------
To read our latest newsletter visit http://www.wrcplc.co.uk/default.aspx?item=835 - Keeping our clients up-to-date with WRc's business developments
-------------------------------------------------------------------------------------------
Visit our websites www.wrcplc.co.uk and www.wrcnsf.com, as well as www.waterportfolio.com for collaborative research projects.
-------------------------------------------------------------------------------------------
The Information in this e-mail is confidential and is intended solely for the addressee. Access to this e-mail by any other party is unauthorised. If you are not the intended recipient, any disclosure, copying, distribution or any action taken in reliance on the information contained in this e-mail is prohibited and maybe unlawful. When addressed to WRc Clients, any opinions or advice contained in this e-mail are subject to the terms and conditions expressed in the governing WRc Client Agreement.
-------------------------------------------------------------------------------------------
WRc plc is a company registered in England and Wales. Registered office address: Frankland Road, Blagrove, Swindon, Wiltshire SN5 8YF. Company registration number 2262098. VAT number 527 1804 53.
-------------------------------------------------------------------------------------------

[KP]

The .min indicates a minimum for that variable. For example, x.min=1
will make sure than x is always greater than 1.
I wrote the solver myself. It's a variation of the modified-Powell
method with bounds support. I guess more documentation
is necessary but I wanted to keep it as simple and flexible as
possible. I'm interested to see what kinds of problems
pose difficulties for the solver. Glad to see people are still kicking
around on this list :)

KP

On Aug 26, 10:19 am, "Dudley, Jeremy" <jeremy.dud...@wrcplc.co.uk>
wrote:

> I Played with your provided examples, and it looks nice - it can do with
> more documentation about setting up problems. For example, does f.min =
> 0 mean that f should never have a value below 0, or that the aim is to
> minimise f? (I'm guessing the former). Did you write the solver, or are
> you a front-end to a Google-provided solver?
>
> J Dudley
> +44 (0)1793 865049
>
> -----Original Message-----
> From: op...@googlegroups.com [mailto:op...@googlegroups.com] On Behalf
> Of KP
> Sent: 26 August 2009 15:07
> To: Open source Process Simulator
> Subject: Non-linear equations solver
>
> Hi all,
>
> Don't know if there are still any active members reading the group. I
> recently created an "online" non-linear equations solver at
> xyzsolve.appspot.com. It's not a full-fledged equation solving
> environment but it's quite useful for one-off problems. Please let me
> know if anyone finds this useful.
>
> Thanks,
> Kiran
>
> -------------------------------------------------------------------------------------------

> To read our latest newsletter visithttp://www.wrcplc.co.uk/default.aspx?item=835- Keeping our clients up-to-date with WRc's business developments
> -------------------------------------------------------------------------------------------
> Visit our websiteswww.wrcplc.co.ukandwww.wrcnsf.com, as well aswww.waterportfolio.comfor collaborative research projects.

[John Pye]

Hi Kiran

Is there any chance of you releasing the source code for this
interesting little app?

Do you have a good reference that I could read about the modified Powell
algorithm, or does it have other names?

If your solver is going to be FOSS and can be wrapped as a DLL/SO, I'd
be interested to try it out within the ASCEND modelling environment as
an additional solver, perhaps.

Cheers
JP

John Pye
http://ascendwiki.cheme.cmu.edu/

[Dudley, Jeremy]

I agree that bounds support for Powell's method would be interesting to
see. I have implemented this in the past as a simple penalty function,
and would like to see alternate methods.

-------------------------------------------------------------------------------------------
To read our latest newsletter visit http://www.wrcplc.co.uk/default.aspx?item=835 - Keeping our clients up-to-date with WRc's business developments
-------------------------------------------------------------------------------------------
Visit our websites www.wrcplc.co.uk and www.wrcnsf.com, as well as www.waterportfolio.com for collaborative research projects.

[KP]

The bounds support for this method is quite simple. When I predict a
new set of x values during
the iteration, I check to see if any variables violate the bounds. If
they do, I modify the value to
satisfy the bound and keep the same direction. For example, if the
variable x has a bound of 0
and the new value is -1 and the old value was 5. The next iterate of x
has the value of sqrt(-1 + 5).
This works sufficiently well for most cases.

The source is actually already available: http://www.netlib.org/minpack
. The code of interest is
hybrd and hybrdj. It's in fortran and should be quite easy to link
with ASCEND. The bounds
support is the only part you have to add to the code. My code is all
in Python (Google App Engine
does not allow anything but Python or Java).

I am doubtful about this method's performance in an EO modeling
environment like ASCEND.
In my experience, this method is quite inefficient for large/sparse
equation sets. 500 or so variables
is the upper limit. I'm not sure what the typical use case in ASCEND
is.

Cheers,
Kiran






On Aug 27, 4:26 am, "Dudley, Jeremy" <jeremy.dud...@wrcplc.co.uk>

> John Pyehttp://ascendwiki.cheme.cmu.edu/
>
> -------------------------------------------------------------------------------------------
> To read our latest newsletter visithttp://www.wrcplc.co.uk/default.aspx?item=835- Keeping our clients up-to-date with WRc's business developments
> -------------------------------------------------------------------------------------------
> Visit our websiteswww.wrcplc.co.ukandwww.wrcnsf.com, as well aswww.waterportfolio.comfor collaborative research projects.

[Dudley, Jeremy]

I'm still not clear.

I have done both of these in the past:

-- Scale to ensure that bounds are preserved
-- More involved code needed to ensure that preserving lower bounds does not violate upper bounds
Scale = 1
FOR ALL x
IF x > x.Max THEN scale = min(scale, x / x.Max)
NEXT

x = Scale * x

Scale = 1
FOR ALL x
IF x < x.Min THEN scale = min(scale, x.Min / x)
NEXT
X = scale * x

OR (simpler to code!)

FOR ALL x
IF x > x.Max THEN Fmin = Fmin + Weight * (x - x.Max)^2
IF x < x.Min THEN Fmin = Fmin + Weight * (x.Min - x)^2
NEXT

With your code, it looks as if you do

FOR ALL x
IF x < x.Min THEN x = SQRT(x + x.Min) -- Assume that term will be positive
IF x > x.Max THEN x = SQRT(x.Max - x) -- Similar issues
NEXT

This does not appear to be direction-preserving.

To read our latest newsletter visit http://www.wrcplc.co.uk/default.aspx?item=835 - Keeping our clients up-to-date with WRc's business developments
-------------------------------------------------------------------------------------------
Visit our websites www.wrcplc.co.uk and www.wrcnsf.com, as well as www.waterportfolio.com for collaborative research projects.

[KP]

Hi Jeremy:

Thank you for my catching my error in the description. I wrote this
code a while ago and didn't remember what i did exactly. I went back
to the code and this is what i have:

(x[j-1] is the previous valid value)

if lower_bound is not None and new_x < lower_bound:
distance = math.sqrt(abs(x[j-1] - new_x))
new_x = (lower_bound + x[j-1])/distance

elif upper_bound is not None and new_x > upper_bound:
distance = math.sqrt(abs(new_x - x[j-1]))
new_x = (upper_bound - x[j-1])/distance

And now that I think about it, I am not sure this is "direction-
preserving" in the sense of the function gradient. I don't have that
much experience in the numerical solving field, so this was my best
guess at the time I wrote the code. I've only tested the lower-bound
(mostly for non-negative). I see now that my upper bound code could
violate the lower bound. I will try and work in your suggestions into
the code.

Thanks,
Kiran

On Aug 27, 10:22 am, "Dudley, Jeremy" <jeremy.dud...@wrcplc.co.uk>
wrote:

> The source is actually already available:http://www.netlib.org/minpack. The code of interest is hybrd and hybrdj. It's in fortran and should be quite easy to link with ASCEND. The bounds support is the only part you have to add to the code. My code is all in Python (Google App Engine does not allow anything but Python or Java).

> > visithttp://www.wrcplc.co.uk/default.aspx?item=835-Keeping our

> > clients up-to-date with WRc's business developments
> > ----------------------------------------------------------------------
> > --------------------- Visit our

> > websiteswww.wrcplc.co.ukandwww.wrcnsf.com, as well aswww.waterportfolio.comforcollaborative research projects.

> > ----------------------------------------------------------------------
> > --------------------- The Information in this e-mail is confidential
> > and is intended solely for the addressee. Access to this e-mail by any other party is unauthorised. If you are not the intended recipient, any disclosure, copying, distribution or any action taken in reliance on the information contained in this e-mail is prohibited and maybe unlawful. When addressed to WRc Clients, any opinions or advice contained in this e-mail are subject to the terms and conditions expressed in the governing WRc Client Agreement.
> > ----------------------------------------------------------------------
> > --------------------- WRc plc is a company registered in England and
> > Wales. Registered office address: Frankland Road, Blagrove, Swindon, Wiltshire SN5 8YF. Company registration number 2262098. VAT number 527 1804 53.
> > ----------------------------------------------------------------------
> > ---------------------
>
> -------------------------------------------------------------------------------------------

> To read our latest newsletter visithttp://www.wrcplc.co.uk/default.aspx?item=835- Keeping our clients up-to-date with WRc's business developments
> -------------------------------------------------------------------------------------------
> Visit our websiteswww.wrcplc.co.ukandwww.wrcnsf.com, as well aswww.waterportfolio.comfor collaborative research projects.