Repository navigation
Fix Brent's parabolic step and evaluate the bounds - #1312
Merged
Merged
Conversation
Brent accepts the parabolic step x + p/q only if it lands inside the bracket, p > q*(a - x) and p < q*(b - x), as in Brent's routine and its Fortran translation fmin. The lower test read p < q*(x - a). That rejected valid steps longer than x - a, which then fell back to golden section, and it let steps below a through to the guard that replaces them with a step of x_tol. On exp(0.2x) - 0.2e^0.1 x over [0, 1] the run took 24 evaluations; it now takes 9. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
On a function that is flat over much of the interval, the first interior point can sit on a plateau above one of the bounds, and Brent then shrinks the interval away from the minimum: -sign(x) on [-2, 1] returned 1, and x > 1 ? 2 : x^2 on [-1, 10] returned 2 at x = 3.2 (#828). Evaluate the objective at both bounds as well and start from the lowest of the three points, as NLSolvers' BrentMin does. The search only moves to lower points, so the result is never above either bound. This costs two evaluations; Brent(evaluate_bounds = false) keeps Brent's original method. The docstring described Brent's root finder (bisection, secant, inverse quadratic interpolation). Describe the minimizer, golden-section search with parabolic interpolation, and the new keyword. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
When the proposed step is shorter than x_tol, Brent steps x_tol in its direction, copysign(tol, d) in Brent's routine. The code used step > 0 ? x_tol : -x_tol, which steps down for a step of +0.0 (#1036). Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Contributor
Benchmark Results (Julia vlts)Time benchmarks
Memory benchmarks
A plot of the benchmark results has been uploaded as an artifact at . |
Contributor
Benchmark Results (Julia v1)Time benchmarks
Memory benchmarks
A plot of the benchmark results has been uploaded as an artifact at . |
Codecov Report✅ All modified and coverable lines are covered by tests. Additional details and impacted files@@ Coverage Diff @@
## master #1312 +/- ##
==========================================
+ Coverage 87.86% 87.88% +0.01%
==========================================
Files 52 52
Lines 5052 5059 +7
==========================================
+ Hits 4439 4446 +7
Misses 613 613 ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Three changes to
Brent, one commit each.x + p/qshould be accepted only if it lands inside the bracket:p > q*(a - x)andp < q*(b - x), as in Brent's routine and infmin. The lower test readp < q*(x - a). That rejected valid steps longer thanx - a, which then fell back to golden section, and it let steps belowathrough to the guard that replaces them with a step ofx_tol. Onexp(0.2x) - 0.2e^0.1 xover [0, 1] the run took 24 evaluations; it now takes 9.evaluate_bounds = true. On a function that is flat over much of the interval, the first interior point can sit on a plateau above one of the bounds, and the search then shrinks away from the minimum. This evaluates both bounds and starts from the lowest of the three points, as NLSolvers'BrentMindoes. All seven examples in Brent still broken for flat functions :( #828 now return the minimum. It costs two evaluations, andBrent(evaluate_bounds = false)keeps Brent's original method. Brent remains a local method: this fixes cases where the first interior point lands on a plateau above a bound. The docstring described Brent's root finder (bisection, secant, inverse quadratic interpolation); it now describes the minimizer and the new keyword.x_tolnow goescopysign(x_tol, step), as in Brent's routine.step > 0 ? x_tol : -x_tolstepped down for a step of+0.0.Tests:
evaluate_bounds;evaluate_bounds = false.The full suite passes on Julia 1.13.2.
Closes #828, closes #1036.
🤖 Generated with Claude Code