Comments (8)
Backtracking returns only FuncEvaluation, but at present Bisection needs both at the same time. Splitting it will require some changes and perhaps a bit of thought. If the step satisfies Armijo, then it is easy, just return GradEvaluation. If not, then it is not so clear. If maxStep has not been found yet, then probably the right thing is to halve the step and try again with another FuncEvaluation. If the step has already been bounded, then ... ?
Anyway, when this is done, I will be this close from suggesting to drop the ORability of evaluation operations. Just saying (although I am afraid it was me who came up with the idea).
from optimize.
I tried to come up with something for Bisection that would actually save some work if a step does not satisfy the Armijo condition. But needing both values simultaneously is essential for the algorithm, so either we don't save work or it will be a different algorithm. Do you see another way, @btracey ?
If we just want to issue FuncEvaluation and GradEvalaution separately, it can be done easily, though.
from optimize.
That's exactly what I have in mind. Request function value. If it passes, request gradient. If not, update
from optimize.
But update needs gradient too, so we don't save anything.
from optimize.
Continuing the previous discussion from closed #137:
I do think that our line searches should evaluate individually (for example, so gradient computations can be saved).
... One was to see if gradient computations can be saved if we know that the point does not satisfy even Armijo. It is obvious to me now that they cannot, the algorithm simply needs the derivative at the midpoint to decide which side to subdivide. We could modify the algorithm but then it would not be the same thing, it is not clear how to modify it and whether it is worth it. If we modified the bracketing phase not to use g, only f, then we could save them during that phase because the action does not need g, it is always: go forward.
... but Backtracking does not ask for the gradient and Bisection cannot do without it.
That's not true on Bisection. If the function value is higher, then we always know which direction to push. If the function value is lower then the gradient is needed to decide which way to slide.
The very first check in Bisection is g < 0 so as it is now we always need the derivative. We can remove it, though, and make the bracketing phase derivative-free (slide forward until the midpoint has lower value than the two end points). Perhaps we should. Also, shouldn't we fail earlier than when b.step == step? Just asking.
from optimize.
First, let's say the initial bracketing phase. There are four cases
- Decrease in f, g < 0
- Decrease in f , g > 0
- Increase in f, g < 0
- Increase in f, g > 0
Both cases 3 and 4 mean that a minimum has been bracketed, as the function value has increased. So there we do not need to check the gradient.
When it is bracketed and we look at a new point, again, if the function value is higher we will always cut toward the best minimum. It is only when the function value is lower that the gradient value is needed.
from optimize.
Both cases 3 and 4 mean that a minimum has been bracketed, as the function value has increased. So there we do not need to check the gradient.
Yes. But currently the first test in Bisection during bracketing is g > 0
. To do what you are aiming at the first test must be f >= b.minF
(or f > b.f
if we are updating all three points while sliding forward).
When it is bracketed and we look at a new point, again, if the function value is higher we will always cut toward the best minimum. It is only when the function value is lower that the gradient value is needed.
Oh, I have just realized what was not fitting in and was thus confusing me: the current code stores the derivative in b.minGrad and b.maxGrad so it makes it seem as if those derivates are needed. But in fact they are not! They are just stored and never used, so yes, we can save gradient evaluations in some cases. Uf.
Do you want to put this together or should I take a stab at it?
from optimize.
Fixed by #143
from optimize.
Related Issues (20)
- Change from Function et al. interfaces + magic to input functions struct HOT 5
- Clearly define meaning of the various iteration types HOT 5
- Make optimize silent by default
- Method does not need ProblemInfo HOT 1
- LinesearchMethod.Iterate() is subtly wrong HOT 6
- Better name for ErrNonNegativeStepDirection
- Linesearchers should test function decrease to within a tolerance HOT 2
- Pass a copy of X to evaluation routines HOT 2
- Change the order of arguments for evaluation routines like Grad() and Hess()
- Remove Linesearcher.Finished()
- Change FunConst and GradConst to DecreaseFactor and CurvatureFactor
- [question] MajorIterations settings HOT 4
- optimize: curve-fitting - implement Levenberg-Marquardt algorithm (damped least-squares) HOT 7
- optimize: Add CMA-ES optimization algorithm HOT 3
- optimize: Repo description should not end with a "." HOT 4
- optimize: NewPrinter should accept an io.Writer HOT 1
- optimize: allow constrained optimization HOT 6
- Update of OptLoc on every iteration causes flaky optimization runs HOT 11
- Statuser docs are not accurate
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from optimize.