Damp the Newton step in the solver when the full step makes things worse. Fixes #1247 - #1748
Damp the Newton step in the solver when the full step makes things worse. Fixes #1247#1748ruevs wants to merge 2 commits into
Conversation
…rse. NewtonSolve() took the whole Newton step on every iteration, but that step is only as good as the linearization of the constraint equations about the current operating point. In tc7000's sketch from solvespace#1247, a right triangle with one leg dimensioned and the hypotenuse at an angle, the step from the 60 degree solution towards the 30 degree one overshoots the root at h = 100*tan(30) = 57.7 mm and lands at h = 4.2 mm, right next to the critical point of the angle equation f(h) = 100/sqrt(100^2 + h^2) - cos(30 degrees), f'(0) = 0 where the direction cosine is stationary. The step from there is enormous, and after a few more the triangle's vertices are 1.9e6 mm apart, the steps collapse to nothing, and the solve gives up with a residual of cos(30 degrees) left over. That is why the failure is threshold shaped: 60 to 40 lands at h = 50 mm and converges fine, 60 to 30 lands on the critical point and runs away. The Newton step is a descent direction for |F|^2, so if the full step increases the residual then a short enough step along the same direction decreases it. Backtrack, halving up to eight times, and if nothing along that direction is an improvement then take the full step anyway, so that we never reject a step that the old code would have taken. Sweeping this sketch over 138 pairs of before and after angles, the 32 pairs that used to fail all solve now, and none that used to solve stopped solving. Also add a regression test, with tc7000's sketch as its fixture, that checks the geometry after each solve and not just the result code, since the angle equation is even in h and could be satisfied by the mirrored triangle. Fixes solvespace#1247. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
The interesting solver failures depend on the previous solution being the initial guess for the next solve, so they can't be reproduced by loading a file: the dimension has to be edited and the sketch re-solved, the way the GUI does it. Add a `solve` command that does that for a list of values and reports the solve result and the geometry after each one, and a `sweep` command that runs the same two step sequence over a range of values. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
|
Keep in mind the discussion: |
|
Written by Claude Opus 5 — both this text and the code it describes; posted by @BoykoNeov. @ruevs Your objection sent me back to measure, and it turned into a better fix than this one. It is on my fork as You were right about the mechanism and, I think, wrong about the price. You said you could not see how to get predictability "apart from internally animating each change in smaller steps and solving multiple times", and did not like it. The steps that need to be smaller are not the user's edit — they are the solver's Newton steps. Shrinking those costs almost nothing: So instead of the line search in this PR, Measured against master, same 1° grid of start × target angle (6480 pairs, driven through the edit-a-dimension-and-re-solve path)
Scoped deliberately: zero flips wherever master has an answer at all. Across the whole grid there are still 417, and every one of them is inside the 818 pairs master cannot solve — there is no previous behaviour there to be surprising relative to. So it is a large improvement on the axis you named, not flip-freedom. Two things I should not let you discover on your own: It is not a guarantee. Animating the constraint value is continuation in the parameter, and under regularity that genuinely tracks a branch. A trust region limits step length in the state and tracks nothing — it exploits the same locality intuition without the theorem. 85° → 30° still crosses to the mirror: the offending step is a legitimate descent step that even a textbook ρ-ratio rule accepts. Landing on the nearer root is a policy preference, and no branch-blind descent method gets it for free. It gives up this PR's best safety argument. The line search only engages when the full step increases the residual, so its set of trajectories is a strict superset of today's — that is a complete argument by itself, and it is why I would understand you preferring it. The trust region clips the first step unconditionally, so every solve takes a different path, and the defence is empirical: 0 regressions on the grid above, a 12-model NURBS boolean corpus whose output is byte-identical to master (triangle counts and volumes to every digit), suite iteration count 957 against master's 956 over the 263 pre-existing cases, and green in Debug and Release. Suite is 265 cases / 941 checks with two new regression cases; both fail on master's Cost in the regime that actually matters, since If that per-frame iteration bothers you, there is an obvious lever I chose not to pull, and you are better placed to judge it than I am. Finally, a retraction. On BoykoNeov#3 I offered you a post-solve branch preference and said it would need "no double-solving". That was wrong on its own terms — picking a different mirror after the fact needs either a second solve or a reflection, and "the mirror" only exists for specially structured systems. It also turned out to be unnecessary: the step rule delivers the preference, so there is nothing left to select afterwards. One correction to the record in the other direction, offered as data rather than as a rebuttal: your specific case is exactly as you describe — 59° → 25° flips here and not on master. But master flips on 619 of the 5662 pairs it solves, so the predictability is not a property it has today either; both solvers land where the iteration happens to take them, and the trust region is the first of the three that lands there on purpose. |
|
The damping is a textbook solution to nonconvergence in a Newton's method. I don't think there should be any significant speed penalty in cases where this isn't helping, since the inner loop stepping the relaxation factor will then exit after the first iteration. So this looks like a basically promising approach to me. In the case where the minimum step still makes the error worse, this code takes the maximum step and keeps iterating. It justifies that as a fallback to the previous behavior so that "nothing that converges now can start failing", but I don't think that's obviously true--if we took a damped step on a prior outer iteration then we're now linearized about a different point and who knows what might happen. So my intuition would probably have been to take the minimum step in that case, or just fail entirely. Their minimum step size seems reasonable to me, though it would be interesting to see the actual step sizes on a diverse set of problematic sketches. Is there any benefit to still checking (the misnamed) |
|
BoykoNeov#7 / #1749 is a better solution in my opinion, so I'm converting this to a draft for now. |
|
Written by Claude Opus 5 — both this text and the code it describes; posted by @BoykoNeov. @jwesthues — a correction to my comment above, and one to a claim I made for this PR. I wrote that the line search "only engages when the full step increases the residual, so its set of trajectories is a strict superset of today's — that is a complete argument by itself." That is wrong. You had already said why, in this thread, before I measured anything:
You were right. On a breadth sweep I ran for #1749, this branch regresses Also superseded from that comment: the cost figure "957 against 956" was measured on the test suite, which is 263 mostly-trivial solves. Over 5662 real solves it is +5.6% Jacobian+least-squares for the trust region (4.47 → 4.72 per solve). That is the number to use. None of this makes this PR the worse of the two — on breadth it is clearly the better one. Two separate corpora, and it matters which is which, because the regression above is in the second one:
So "0 regressions" and "regresses |
Based on BoykoNeov#3. Original PR text from Claude Opus 5:
Fixes #1247 — @tc7000's sketch where changing an angle dimension from 60° to 30° reports "didn't converge", while 60° → 40° is fine, and the same 30° works if you approach it in smaller steps.
It is not a rank or redundancy problem
That was my first hypothesis, and it is wrong.
rankOkis true at every failure, andTestRank/CalculateRanknever fire on this model — theDIDNT_CONVERGEcomes straight out ofSystem::NewtonSolve(). Worth saying explicitly, because the symptoms (a threshold that depends on the previous value, order dependence) look exactly like a redundancy problem and it's a natural place to start digging.Root cause: an undamped Newton step lands on a critical point
After substitution this sketch reduces to
m = 2, n = 4, effectively one-dimensional in the heighthof the triangle, withf'(0) = 0— the function is flat at the origin. Solving for 30° means findingh = 57.735, and from the 60° solution the full Newton step overshoots it and lands ath ≈ 4.2, right on top of that critical point. With the derivative there near zero, the next steps are 161 mm, then 349 mm, and the geometry runs out to ±1.9e6 mm, where the parameters are so large that steps collapse to ~1e-16 and the solver gives up with the residual still atcos 30°.60° → 40° lands at
h = 50, where the derivative is healthy, and converges in four iterations. That is the whole "threshold-shaped, order-dependent" story: whether the full step happens to clear the flat spot.The fix
A backtracking line search in
System::NewtonSolve()(src/system.cpp): tryrelax = 1, ½, ¼ … 1/128, and accept the first that strictly reduces‖F‖₂². If none does, take the full step exactly as before — so no step the old code would have taken is ever rejected, and a model that converges today cannot start failing because of this.IsReasonable()failures now shrink the step instead of aborting the solve outright. (Note for anyone reading that function: it is misnamed upstream — it returns true when the value is unreasonable.)Regression test
test/core/solver/angle_step_over_critical_point— set 60°, then 30°, and check both solve and that the triangle really has the right height, not just that a result code came back OKAY. Fails at the 30° step without the fix.The repro is path-dependent: the previous solution is the next solve's initial guess, so it cannot be reproduced by editing the
.slvsand reloading. The second commit therefore teachestest/debugtool.cppto load a sketch and then set a dimension and re-solve repeatedly (solve), and to sweep a range of start/target pairs (sweep). That is what produced the numbers above and it is useful for any solver issue of this shape.Verification
src/system.cppreverted, the new test fails at the 30° step.Concerns you may want to raise
‖F‖₂²sums dimensionless cosine residuals from angle constraints — which themultfactor can gain up to ~1000× near 0°/180° — together with mm-valued distance residuals. This is harmless for a decrease-only acceptance test with a full-step fallback (the worst case is that a good step is judged "not an improvement" and we fall back to exactly today's behaviour), but it is not a principled merit function, and a residual scaling pass would be a real improvement. I did not attempt one.This PR is independent of my other three and can be taken on its own. In particular, note that a failed solve on this branch still deletes the constraints that failed — that is a separate bug with its own PR, deliberately not mixed in here.
Please fetch and fast-forward this branch rather than using the merge button on my fork — that keeps it a clean fast-forward for upstream.
🤖 Generated with Claude Code