Reimplementing constraint solver

Discussion about the development of the Assembly workbench.
triplus
Posts: 9475
Joined: Mon Dec 12, 2011 4:45 pm

Re: Reimplementing constraint solver

Postby triplus » Fri Mar 27, 2020 7:12 pm

Any clue on why Tau setting for LevenbergMarquardt is by default set to 0.001?

https://forum.freecadweb.org/viewtopic. ... 20#p381364
User avatar
DeepSOIC
Posts: 7810
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Fri Mar 27, 2020 8:12 pm

triplus wrote:
Fri Mar 27, 2020 7:12 pm
Any clue on why Tau setting for LevenbergMarquardt is by default set to 0.001?
Tau is initial value for damping factor. Low damping factor means "solve using gauss-newton steps". High damping factor means "solve using gradient descent". A value in between means "do something in between".

Damping factor is changing as the iterations progress. If an attempted step does not reduce error, or error reduction is smaller than expected, damping factor is increased (system is highly nonlinear, gradient descent is preferred as being more robust, I assume). If the reduction is so-so, damping factor is not changed. If the change is close to expectation, damping is decreased (system is decently linear, use gauss-newton for its faster convergence).

If you are experimenting on very simple sketches, the problem might be extremely linear, and thus gauss-newton may solve it in just one iteration. This might explain why it gets more flip resistant that way. But I'm not sure.
User avatar
DeepSOIC
Posts: 7810
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Sat Mar 28, 2020 4:13 pm

@abdullah
I know you can use sage. Can you please figure out average value of fourth derivative of sqrt(sq(a*cos(u)) + sq(b*sin(u))) across the period? I'm trying to find out, how many slices should I take for length integration for arc ellipse to achieve a cretain precision, using Simpson's rule.
triplus
Posts: 9475
Joined: Mon Dec 12, 2011 4:45 pm

Re: Reimplementing constraint solver

Postby triplus » Sat Mar 28, 2020 5:52 pm

First thanks for explanation. I read some additional papers regarding LevenbergMarquardt and Tau. In addition, due to this being a rather standard approach, one can look in documentation of other software.
The Levenberg Marquardt algorithm is an iterative algorithm that takes a step in the direction of decreasing function values on each iteration. The initial step size is determined by the parameter tau. Tau related to the size of the elements in the Jacobian matrix of the minimized function evaluated at the starting point, x0, of the iteration. The algorithm is not very sensitive to the choice of tau, but as a rule of thumb, one should use a small value, e.g. tau = 10^-6, is x0 is believed to be a good approximation to the final solution x. Otherwise, use tau = 10^-3 or even tau = 1. The default value is tau = 10^-3.
https://www.centerspace.net/doc//NMathS ... er_Tau.htm

I did some tests and following such rule of thumb indeed a value of 10^-6 should suffice in most Sketcher oriented tasks. Basically what it does it increases the area. Hence if LevenbergMarquardt with Tau set at 0.001 starts to flip geometry at lets say 400 mm, setting Tau to 10^-6 further prevents the flip if one for example enters a value of 40 m.
Mark Szlazak
Posts: 424
Joined: Tue Apr 04, 2017 6:06 pm
Location: SF Bay Area, California

Re: Reimplementing constraint solver

Postby Mark Szlazak » Sat Mar 28, 2020 9:35 pm

DeepSOIC wrote:
Sat Mar 28, 2020 4:13 pm
@abdullah
I know you can use sage. Can you please figure out average value of fourth derivative of sqrt(sq(a*cos(u)) + sq(b*sin(u))) across the period? I'm trying to find out, how many slices should I take for length integration for arc ellipse to achieve a cretain precision, using Simpson's rule.
You can use Wolfram Alpha online.
https://www.wolframalpha.com/
I got this mess for an exact value.
Screenshot (1159).png
Screenshot (1159).png (58.23 KiB) Viewed 325 times
You can add the interval by typing "from value1 to value2" last in the expression text box to get a numerical value.
User avatar
DeepSOIC
Posts: 7810
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Sat Mar 28, 2020 9:49 pm

Mark Szlazak wrote:
Sat Mar 28, 2020 9:35 pm
I got this mess for an exact value.
Thanks, but it's not very useful. I need some clue on what maximum or average of this thing gets to. I actually would prefer an approximation rather than an exact value, something like "4th derivative is about a*100 in magnitude". Any ideas?
User avatar
DeepSOIC
Posts: 7810
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Sat Mar 28, 2020 10:23 pm

Mark Szlazak wrote:
Sat Mar 28, 2020 9:35 pm
...
Actually, that is quite useful. It took me a while, but I estimated that the value will not exceed 40*b in magnitude, probably somewhat less that that in fact, as I mostly assumed that sin^2 and cos^2 are +1, and I flipped quite a few minuses with pluses along the way.
Mark Szlazak
Posts: 424
Joined: Tue Apr 04, 2017 6:06 pm
Location: SF Bay Area, California

Re: Reimplementing constraint solver

Postby Mark Szlazak » Sat Mar 28, 2020 10:25 pm

OH OK.

Anyway, here is some more.

Wolfram Alpha has some widgets for Simpson's rule and others that might help. I have never used them.

http://blog.wolframalpha.com/2013/07/11 ... tegration/
Last edited by Mark Szlazak on Sun Mar 29, 2020 3:37 pm, edited 1 time in total.
User avatar
DeepSOIC
Posts: 7810
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Sat Mar 28, 2020 10:51 pm

okay, so from my estimate above, I arrived at that to achieve a tolerance of 1e-6*b, I should sibdivide a quadrant of the ellipse into 22 segments for integration. Ok... I probably should give it a try, to see if the value of the integral changes with subdivision by more or less than expected.
User avatar
DeepSOIC
Posts: 7810
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Sat Mar 28, 2020 10:53 pm

tried.

Code: Select all

def integrate_ellipse(n):
    import math
    from math import sin, cos, sqrt
    x1 = 0; x2 = math.tau/4
    x_samples = [x1 + i/n*(x2-x1) for i in range(n+1)]
    a = 0.5; b = 1
    y_samples = [sqrt((a*cos(x))**2 + (b*sin(x))**2) for x in x_samples]
    import scipy.integrate
    return scipy.integrate.simps(y_samples, x_samples)

The error gets smaller than 1e-6 from 10 subdivision onwards. Looks like my estimate is somewhat wrong...