Reimplementing constraint solver

Discussion about the development of the Assembly workbench.
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
Post Reply
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: Reimplementing constraint solver [LM solver is up!]

Post by DeepSOIC »

BFGS solver is up!

Interestingly, it fails on my simple test problem. Yet if I change c.dist.Value to 4, it does the job. Maybe there is some bug in the implementation, but I suspect it's just unluck, combined with the lack of maxstep restriction. Seems ok otherwise.
User avatar
fosselius
Posts: 381
Joined: Sat Apr 23, 2016 10:03 am
Contact:

Re: Reimplementing constraint solver [BFGS solver is up!]

Post by fosselius »

benchmark time?
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: Reimplementing constraint solver [BFGS solver is up!]

Post by DeepSOIC »

fosselius wrote: Fri Nov 29, 2019 6:09 pm benchmark time?
i'm lazy. but yeah, now is a good time to compare performance against sketcher solver. Any suggestions for a problem? Right now, I have only points and distance constraints.

I don't have a clear idea on what solver will win. My version has quite a substantial overhead due to parameter scaling and deep dereference chains for value lookup. Yet it has a benefit of knowing where there are definite zeros in matrices, so it does less computation.
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: Reimplementing constraint solver [dogleg solver is up!]

Post by DeepSOIC »

ickby wrote: Thu Nov 28, 2019 6:19 am back in the days when I implemented dogleg and LM solvers I closely followed a paper (or excerpt of a bock, not sure anymore).
This one, maybe? https://link.springer.com/chapter/10.10 ... 22742-3_18
Mark Szlazak
Posts: 439
Joined: Tue Apr 04, 2017 6:06 pm
Location: SF Bay Area, California

Re: Reimplementing constraint solver [dogleg solver is up!]

Post by Mark Szlazak »

DeepSOIC wrote: Sat Nov 30, 2019 12:22 am
ickby wrote: Thu Nov 28, 2019 6:19 am back in the days when I implemented dogleg and LM solvers I closely followed a paper (or excerpt of a bock, not sure anymore).
This one, maybe? https://link.springer.com/chapter/10.10 ... 22742-3_18
I have this one. Might help.
https://drive.google.com/file/d/1Z_rX5 ... tjp_RH63MU
ickby
Veteran
Posts: 3116
Joined: Wed Oct 05, 2011 7:36 am

Re: Reimplementing constraint solver [BFGS solver is up!]

Post by ickby »

sorry, can't find it anymore. IO had i local on my machine, but seems I deleted the paper collection I had
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: Reimplementing constraint solver [BFGS solver is up!]

Post by DeepSOIC »

Mark Szlazak wrote: Sat Nov 30, 2019 6:29 am I have this one. Might help.
https://drive.google.com/file/d/1Z_rX5 ... tjp_RH63MU
Thank you, now I got it. Unfortunately, it isn't the exact book I was after. The book I found was "Numerical Optimization" by Jorge Nocedal and Stephen J. Wright. The one you sent me is "Numerical-Methods-for-Unconstrained-Optimization-and-Nonlinear-Equations" by Dennis and Schnabel. It's not as helpful, but I'll take a look anyway.
Mark Szlazak
Posts: 439
Joined: Tue Apr 04, 2017 6:06 pm
Location: SF Bay Area, California

Re: Reimplementing constraint solver [BFGS solver is up!]

Post by Mark Szlazak »

DeepSOIC wrote: Sat Nov 30, 2019 10:27 pm
Mark Szlazak wrote: Sat Nov 30, 2019 6:29 am I have this one. Might help.
https://drive.google.com/file/d/1Z_rX5 ... tjp_RH63MU
Thank you, now I got it. Unfortunately, it isn't the exact book I was after. The book I found was "Numerical Optimization" by Jorge Nocedal and Stephen J. Wright. The one you sent me is "Numerical-Methods-for-Unconstrained-Optimization-and-Nonlinear-Equations" by Dennis and Schnabel. It's not as helpful, but I'll take a look anyway.
Great. Glad you found what you where looking for. That book i referenced is kind of popular and does write about dogleg methods.
Here are another couple references on an apparently better choice than dogleg called the Steinhaug method.
http://www.numerical.rl.ac.uk/people/ni ... slides.pdf
https://optimization.mccormick.northwe ... on_methods
Good luck.
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: Reimplementing constraint solver [BFGS solver is up!]

Post by DeepSOIC »

SQP solver that solves two sets of constraints differing in priority is up! All solver algos are finished.

This one took me longer than others primarily because I was taking a break.

The monster diagnose routine is not even started.

Now I want to reformulate solver api a little bit, and then I probably start implementing some geometry. There is a lot of trickiness involved with assembly support, and I feel like I will go for a structure similar to opencascade's TopoDS_Shape + TopoDS_TShape.
User avatar
saso
Veteran
Posts: 1920
Joined: Fri May 16, 2014 1:14 pm
Contact:

Re: Reimplementing constraint solver [all solvers implemented]

Post by saso »

Part of the reason why I have made this post https://forum.freecadweb.org/viewtopic.php?f=8&t=40775 was also because I have hoped that some of the links in it could be helpful also for the development of our 2D and 3D solvers... Not the preCICE, since it is about FEM, but projects like DifferentialEquations.jl, SUNDIALS and CasADi are all about researching, prototyping, benchmarking and implementing the best algorithms for all sorts of different solvers, here are for example two pages from the DifferentialEquations.jl docs that have references to the dogleg, LM and BFGS https://docs.juliadiffeq.org/dev/solvers/bvp_solve/#, https://docs.juliadiffeq.org/dev/analys ... stimation/# one can also find references on Dual Numbers and other stuff... I am no expert on this, but the folks from the DifferentialEquations.jl project hang around at https://gitter.im/JuliaDiffEq/Lobby

Modia is in general also not directly interesting for this, but its Modia3D is an implementation of an 3D geometry "assembly environment" and there seem to be some interesting information and links on its implementation... https://github.com/ModiaSim/Modia3D.jl and its docs https://modiasim.github.io/Modia3D.jl/stable/

There is also another, somewhat related topic on Julia https://forum.freecadweb.org/viewtopic.php?f=8&t=42400
Last edited by saso on Sat Feb 01, 2020 8:22 pm, edited 2 times in total.
Post Reply