Only step as far as the linearization of the constraints is trusted. Fixes #1247 - #1749
Only step as far as the linearization of the constraints is trusted. Fixes #1247#1749ruevs wants to merge 3 commits into
Conversation
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>
A Newton step is only as good as the linearization of the constraint equations about the operating point, so where those equations are strongly curved the full step can land further from the solution than it started; and if it lands near a critical point of the equations, the step after that one is enormous and the geometry runs away to nowhere. That is what happens in issue solvespace#1247. The reporter's sketch reduces, after substitution, to one equation in the height h of a right triangle with a 100 mm base, cos(theta) = 100/sqrt(100^2 + h^2), whose derivative vanishes at h = 0. Changing the angle dimension from 60 to 30 degrees overshoots the root at h = 57.7 and lands at h = 4.2, right on top of that critical point; the next two steps are 161 and 349 mm, the triangle ends up out at +/-1.9e6 mm where the steps collapse to 1e-16, and the solve gives up with DIDNT_CONVERGE. Changing it to 40 degrees instead lands at h = 50, where the derivative is healthy, and converges in four iterations, which is why the failure looked threshold-shaped and dependent on the order of the edits. So keep a radius that we trust the linearization over, don't step further than that, and grow it only as steps keep working out: double it when a step reduces the residual, quarter it when one does not. The radius starts at half of the first Newton step, and since it doubles per accepted step it is back up to the full step immediately. If nothing along the step direction is an improvement, take the whole step anyway, exactly as before, so no step that we used to take is skipped and the iteration limit still catches it if that was a bad idea. IsReasonable() now shrinks the step instead of abandoning the solve. On a grid of 6480 (starting angle, target angle) pairs of the reporter's sketch, driven through the same edit-a-dimension-and-re-solve path as the GUI, this solves all 6480 where we used to solve 5662, and no pair that used to solve stops solving. It also stops mirroring the sketch: -30 degrees satisfies an angle constraint exactly as well as +30 does, and of the 5662 pairs both versions solve, the old code flips the triangle to the far side of the horizontal line on 619, where this steps to the nearer of the two solutions on all 619 and flips none. Accuracy is unchanged, worst error over the grid 3.82e-06 degrees against 3.69e-06 before. Halving the first step is what buys that, and it is the least of the divisors that does: with the whole first step the sketch still mirrors on 549 of the 619. Bigger divisors do no better on those pairs and cost more, so a half it is. The price is one extra Newton iteration when re-solving from an already-solved sketch, which is what happens on every frame of a drag: three iterations per small increment of a dimension where we used to take two. Over the whole of the existing test suite it is not measurable, 957 iterations against 956. Fixes solvespace#1247. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
…point. The fixture is the sketch from issue solvespace#1247, and the cases drive it the way the GUI does, by changing a dimension's value and re-solving. That matters: the previous solution is the next solve's initial guess, so neither failure can be reproduced by loading a file that already has the failing value in it. test/debugtool.cpp grew a `solve` command for the same reason. The checks are relative rather than absolute because NewtonSolve() stops as soon as every equation's residual is under CONVERGE_TOLERANCE, which is dimensionless; the angle equation's residual is a direction cosine, so satisfying it to 1e-8 only pins this triangle's 173 mm height to a few times 1e-06 mm. Comparing the height itself against LENGTH_EPS passes or fails on which side of the tolerance the last step happens to land, which is not a property of the solver worth asserting. The second case checks the magnitude of the height only. From 85 degrees the first step that reduces the residual below its value there is one that crosses the horizontal line, so the triangle ends up mirrored; that is a solution where before there was none, but it is not the nearer of the two, and pinning the sign would assert a behaviour we would like to improve. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
|
This is a damped Newton's method again, so most of my comments from #1748 also apply, in particular as to The difference is that in #1748, at each outer loop iteration we always take the largest step that improves our error. In this change, we keep state so that if prior outer loop iterations required a smaller step, we take a smaller step at this iteration even if a larger one would improve error (and only gradually release the damping, over multiple outer iterations). This means the average step size will be smaller, which is consistent with less flipping. The tradeoff is the greater complexity of the code, and presumably a greater number of outer iterations required to converge. I don't know whether the The normalization by the magnitude of I think this approach is potentially good, but I'd test it on more diverse sketches and fix the issues from the previous paragraph before committing. I don't have strong intuition on whether it's better or worse than the simpler #1748. It's empirically better on this test case, but the agent can try so many things so quickly that I think there's a Bonferroni type argument to view its successes with more suspicion than human results. A more diverse set of test cases would mitigate that and might be worthy investment. |
|
Written by Claude Opus 5 — both this text and the code it describes; posted by @BoykoNeov. @jwesthues — I ran the diverse-sketch test you asked for. It went against this PR, and I think you should not merge it. The answer to your questionOn
It converges given ten times the budget, so it is not a stall — but a 20–30× iteration blow-up is not a budget problem that a bigger budget fixes. Reproduced on completely uninstrumented builds of both sides, identically in Debug and Release. Which tree that is. I measured I re-ran the failures on a pristine build of the un-clamped solver this PR actually carries: all six model regressions are present there too, so the clamp neither causes nor cures the defect and everything below applies to the PR as you have it. The iteration counts in the third column above are from the clamped tree, since that's where I have the 500-iteration diagnostic build; the pass/fail column is verified on both. Your Bonferroni objection was the right objectionYou wrote that the agent can try so many things so quickly that its successes deserve more suspicion than a human's. So before building a single binary I wrote down the metric list, the buckets, the target schedule and the exclusion policy, and committed to reporting all of them including the ones that go against the branch. That document has not been edited since. The part that matters most: I did not go looking for a divisor or a try-count that rescues #1105. Tuning a constant until the newest counter-example disappears, on a corpus assembled after seeing the failure, is exactly the thing you were warning about. A constant found that way would need its own fresh corpus to mean anything. The head-to-head this PR never had664 cases over 31 distinct in-repo sketches (75 files, but the suite stores each drawing in three file-format versions), 8 targets per editable dimension, deliberately spanning far outside the authored value. Corpus 1 — the 664 in-repo fixture cases:
Identical in Debug and Release — the same case sets in all five buckets, iteration counts equal to the digit. The single win is the same sketch for both arms ( Corpus 2 — reporter models, 11 files from #1105, #1378, #1466, #1723, 160 cases. This is a different corpus from the table above, and it is where every regression in this comment lives: the fixture corpus has none for either arm, so "0 regressions" there and "six model regressions" here are not in conflict. Ten of the eleven files are clean for both fixes — all of the below is The six break down as: 6 regressions for this PR with master's least-squares, 3 of which are #1354's defect and not the step rule's (§ below), leaving 3 like-for-like with #1354's fix present on both sides — against the line search's 1. Different landings over the same corpus: 41 for this PR, 7 for the line search. So on breadth the trust region buys nothing the line search does not, costs 29% more factorizations where the line search costs none, and disturbs 13× as many solves. That is not a result I expected when I opened this. A retraction I owe youThis PR's body says the line search is a trajectory superset of master and that this is "a complete safety argument by itself". That is false, and you said why on #1748 before any of this was measured:
(#1748, issuecomment-5126979098.) And it is not merely unproven — it is false in the other direction too: #1748 regresses Three things that did hold up
Corrections to numbers already published here
What I'd suggestTake BoykoNeov#4 first — it is independent of the step rule and removes three of these failures on its own. On #1247 itself, the breadth evidence points at the line search rather than this, and neither is clean. I don't think this should be merged as it stands, and I'd rather say so than have you find it later. The full write-up, the arm-generation script with asserted anchors, and the raw per-case data are available if you want to check any of it. |
Based on BoykoNeov#7.
In my opinion this is better than and should supersede BoykoNeov#3 / #1748 see #1748 (comment) for details.
Original PR text from Claude Opus 5:
Written by Claude Opus 5 — both this text and the code it describes; posted by @BoykoNeov.
An alternative to the line search in #1748 / BoykoNeov#3, written in response to @ruevs' objection there: that the line search makes 59° → 25° land on the mirrored solution where master does not, and that the SolveSpace solver's predictability is one of the things it is valued for.
The two are either/or, not stackable — a trust region subsumes a backtracking line search, since both shrink the step when it fails to improve and the trust region merely carries the radius across iterations. #1748 is a good change and @ruevs has already tested it; this is offered as the better of two, for whoever is deciding, not as a request to close it.
Root cause of #1247, restated
tc7000's sketch reduces after substitution to
m=2, n=4, effectively one-dimensional in the triangle's heighth, withand
f′(0) = 0. Editing the angle 60° → 30° takes an undamped Newton step that overshoots the root ath = 57.735and lands ath ≈ 4.2, essentially on that critical point. From there the next steps are 161 mm and 349 mm, the geometry runs out to ±1.9e6 mm, the steps collapse to 1e-16 and the solve gives up with the residual still at cos 30°. 60° → 40° lands ath = 50, wheref′is healthy, and converges in 4 iterations. That is the whole "threshold-shaped, order-dependent" character of the report.The rank/pivot-tolerance explanation that looks obvious here is dead, killed with evidence rather than argued:
rankOkis true at every failure, andTestRank/CalculateRanknever fire.DIDNT_CONVERGEcomes straight out ofSystem::NewtonSolve().The fix
NewtonSolve()keeps a radius it trusts the linearization ofFover. Each step is clipped to that radius; the radius doubles when a step strictly reduces‖F‖₂²and quarters when one does not, for up to 12 tries. It starts at half the first Newton step. If nothing along the direction improves, the full step is taken exactly as the old code did, so no step master accepts is skipped.IsReasonable()failures now shrink the step instead of aborting the solve.EvalJacobian()andSolveLeastSquares()stay outside the retry loop, so a rejected trial step costs one residual evaluation — no Jacobian, no factorization.Why the divisor is 2: the headline result below holds for every divisor ≥ 2, so it is not a tuned constant; 2 is the cheapest such value, and 1 loses it (549 of the 619 flips come back). The whole-grid flip count is non-monotone in the divisor — 751, 615, 417, 170, 330, 204, 193, 198 for 1…512 — which is itself evidence that the residual flips are chaotic rather than tunable. An earlier version of this branch used 8, which is strictly dominated by 4 on both flips and cost.
Measured against master
A 1° grid of start × target angle over 5–85°, 6480 pairs, each driven through the GUI's edit-a-dimension-and-re-solve path. The repro is path-dependent — the previous solution is the next solve's initial guess — so it cannot be reproduced by loading a file with the target value already in it. Hence the
sweepcommand in the first commit.Scoped deliberately: zero flips wherever master has an answer at all. Across the whole grid 417 remain, every one of them inside the 818 pairs master cannot solve, where there is no previous behaviour to be surprising relative to.
Regression tests
test/core/solver/, fixture = tc7000's file from the issue.angle_step_over_critical_pointdoes 60° then 30° and checks the height's signed value, so it also pins the branch choice;angle_step_from_steep_solutiondoes 85° then 30° and checks magnitude only, because the trust region does land mirrored there (see the limitations below). Both fail on master'ssystem.cpp, at lines 53 and 71.The checks are relative —
CHECK_EQ_EPS(value / reference, 1.0)— on purpose, and there is a comment in the file saying why:CONVERGE_TOLERANCEis dimensionless while the angle equation's residual is a direction cosine, so satisfying it to 1e-8 only pins this triangle's height to a few times 1e-6 mm. Comparing the height itself againstLENGTH_EPStests the solver's luck. Master passes such an assert here by luck and is the less accurate of the two over the grid.Suite: 265 cases / 941 checks, Success!, Debug and Release. Master baseline 263 / 931.
Verification beyond the suite
test/constraint/large_dimensions(borrowed from Solve the Newton step without forming the normal equations. Fixes the original report and mesr's assembly from #1354 BoykoNeov/solvespace#4 as a probe, then removed) fails identically on master and here, so Large Dimensions result in Incompatible Constraints #1354 is untouched.What to push back on
This is not a trajectory superset of master, and #1748 is. The line search engages only when the full step increases the residual, which is a complete safety argument by itself. This clips the first step unconditionally, so every solve takes a different path. The defence is entirely empirical: the 0-regression grid above, the byte-identical corpus, the unmeasurable suite cost, green Debug and Release. If that argument is worth more to you than the branch preference, #1748 is the more conservative change and I would not argue.
Cost in the drag regime.
NewtonSolve()runs once per mouse-move frame and the radius is a fresh local each call, so every frame re-pays the initial clip: +1 Newton iteration per frame (2.00 → 3.00 over 40 small monotone increments). That measurement is what changed the divisor from 8 to 2. Caveat: it is a dimension increment, sosys.draggedis empty and the reduced system is not identical to a real drag — the right regime, but a proxy. Asys.dragged.empty()conditional would buy exact parity while dragging; I left it out because it would ship an interactive path the harness cannot exercise even in principle, and it splits one constant into two UI-dependent regimes.It is not a guarantee. Animating a constraint value in small increments is continuation in the parameter, and under regularity that genuinely tracks a solution 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, and the step that does it is a legitimate descent step a textbook ρ-ratio rule would also accept. Landing on the nearer root is a policy preference no branch-blind descent method gets for free.
The merit function mixes units — dimensionless cosine residuals against mm-valued distance ones, with the ANGLE
multfactor gaining the former by up to ~1000× near 0° and 180°. Harmless for a decrease-only acceptance test with a full-step fallback, but it is the kind of thing worth a second opinion.Note on the other #1247 work
The separate data-loss bug — a failed solve deleting the constraints it could not satisfy — is already upstream as #1744, merged. It is not in this branch and does not need to be.
If you want this, please fetch and fast-forward rather than using the merge button, so that fork master stays a straight ancestor of upstream's the way #1744 did.