Broydens method

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Broydens method

kitwallace
I'm doing some work on geometric tiling (the 15 shades of pentagon) and need
to numerically solve 2 variable functions. Fortunately they are
well-behaved:

<http://forum.openscad.org/file/t229/2dfunction.jpg>

Broyden's method (and refinements) seems to be the thing to use but I wonder
if anyone has an implementation already  - or a different approach to
function optimisation

Chris



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Broydens method

doug.moen
Broyden's method looks tricky to me. Would it be easier to use gradient descent?

On 1 April 2018 at 05:13, kitwallace <[hidden email]> wrote:
I'm doing some work on geometric tiling (the 15 shades of pentagon) and need
to numerically solve 2 variable functions. Fortunately they are
well-behaved:

<http://forum.openscad.org/file/t229/2dfunction.jpg>

Broyden's method (and refinements) seems to be the thing to use but I wonder
if anyone has an implementation already  - or a different approach to
function optimisation

Chris



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Broydens method

kitwallace
Indeed so although its performance is not so good. There are a range of
algorithms implemented in other languages like scipy for Python and the gnu
C libraries. Code for any of these optimisation algorithms would be useful.

Looking around a bit more it looks like the downhill Simplex  
https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method looks quite good
and not too difficult to implement .  For a 2D function it needs 3 initial
points -  I'll give that a go.

Of course the problem with using such functions as you well know is the
inability to pass functions as parameters- I must checkout Curv!







--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Broydens method

kitwallace
I implemented the simplex method as per

https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method

It's been tested on the Rosenbrock function (for degree 2 at least) and on
my own problem in geometry and convergence looks good.

https://github.com/KitWallace/openscad/blob/master/simplex-method.scad



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org