gonum / optimize Goto Github PK
View Code? Open in Web Editor NEWPackages for solving minimization problems [DEPRECATED]
Packages for solving minimization problems [DEPRECATED]
Due to floating-point arithmetic, when getting close to a minimum of some functions, Backtracking eventually generates a step for which xNext == ls.initX
in Linesearch
. In such situation, Armijo condition holds, the step is accepted, MajorIteration is signalled, next descent direction (identical to the previous one) is generated and the process repeats leading to an infinite loop.
It would avoid having to pass it to update() (although the function might be removed in the future), to minimize() and it would be close to Stats.Runtime. Any downsides?
Less magic and more composibility by switching to something like what @btracey proposes:
type Problem struct {
Func func([]float64) float64
Grad func([]float64, []float64)
Hess func([]float64, *mat64.SymDense)
Constraints func(x, equality, inequality []float64)
ConstraintGrad func(x []float64, eq, ineq *mat64.Dense) // maybe Matrix
LinearEq struct{A mat64.Dense, b []float64}
LinearIneq struct{A mat64.Dense, b []float64}
Bounds []struct{Min, Max float64}
}
The signature of Method.Iterate() is
Iterate(l *Location, xNext []float64) (EvaluationType, IterationType, error)
and it performs two tasks. One is returning IterationType that says what kind of iteration was concluded at the Location l. The other is returning in xNext the next point at which the objective function should be evaluated and what kind of evaluation should that be (in EvaluationType).
Wouldn't it be better to separate these two tasks into two functions? Reason: If IterationType is MajorIteration, then l is checked for convergence. If convergence is detected, then xNext should not be generated because 1) it is not necessary 2) generating xNext can fail (e.g., because the search direction is not a descent direction). With the current Method.Iterate() xNext is always generated.
just a follow-up on:
https://www.reddit.com/r/golang/comments/4atete/levenbergmarquardt_or_gaussnewton_go
https://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm
Paraphrasing the above wikipedia link:
LMA is used to solve non-linear least squares problems.
The LMA is used in many software applications for solving generic curve-fitting problems.
... and how that effects us maintaining OptLoc and testing for convergence
We should also decide what to do when incomplete initial information is provided, i.e., when InitialGradient and/or InitialHessian is nil. I think it should not be an error (as it is now), we should always take the function value and evaluate the missing information. Non-nil but incorrectly sized gradient or Hessian should be naturally an error (or panic).
Reproducing case: http://play.golang.org/p/JDn004ekkD
The Rastrigin function is many modal. In one of the bisection searches, the linesearch jumps over the closest minimum, and finds a point in the next valley. Bisecting between these two locations, the linesearch finds the minimum closest to the nearest point, which has a lower value than the origin point of the linesearch, but a higher value than the other valley found. In numbers, the initial point is
201.32956023853234
-252.10162965126193
The bounding point found is
F = 89.99490432365724
ProjG = 294.0993005447343
While the function value is low, the gradient is high, and so the Wolfe conditions are not satisfied. The linesearch continues, eventually finding
f = 116.94945683564991
d = 127.80472382674293
This point satisfies the linesearch conditions. The optimization continues, eventually finding the local minimum in this trough, which has a function value higher than 90. However, optLoc was updated to the 90 location, which has a high gradient value, and the optimization never converges.
On the one hand, this is clearly suboptimal behavior by Bisection, and it should be improved, but at the same time this should be acceptable behavior for a Linesearch method. A local minimum was correctly found, and it should converge when the low gradient location was found.
Repo descriptions are headings and should not include a "."
It is impossible to handle this change with a pull request and so this issue will be used for coordinating the change. PTAL
I spend a lot of time working on optimization algorithms. I think our package will be great for this given that outside optimizers can take advantage of the full framework. One thing that I would like is to have a bunch of pre-defined functions that are already implemented with their gradients that I can use to experiment with. Well, we already have this -- the function suite @vladimir-ch put together. The problem with the current PR is that those functions are scheduled to be in optimize_test which is not importable. I would suggest that we have a "testopt" package that contains these functions, and possibly some form of tests. At the very least, if the functions themselves are in their own package, they could be used by anyone.
Method.Init() should not return IterationType because there is simply no iteration to conclude. Moreover, the initial location should be dealt with before calling Method.Init() which should be invoked only if the initial location does not satisfy the convergence criteria.
Described here: link
Love the matrix library you guys provide though!
Should it be called InitialIteration
or just InitIteration
?
I want to use Sourcegraph code search and code review with optimize. A project maintainer needs to enable it to set up a webhook so the code is up-to-date there.
Could you please enable optimize on @sourcegraph by going to https://sourcegraph.com/github.com/gonum/optimize and clicking on Settings? (It should only take 15 seconds.)
Thank you!
We should have a gradient-free optimizer.
Thanks for all the awesome work on all of these awesome numerical packages!
I have a simple question about MajorIterations
optimization settings.
I have noticed that sometimes when I set the settings.MajorIterations
to a small number, let's say 5, objective function Func
is called more than 5 times? I tested this on several values using the same objective function and noticed the same thing. What's even more interesting sometimes optimize.Local
fails to converge after calling the objective Func
method approximately 100 times despite settings.MajorIterations
set to 5?
My intuition and expectation was that settings.MajorIterations
should stop iterating once the set number of iterations are reached and return IterationLimit
?
I don't know if this is a bug, or a feature or my total misunderstanding of this setting. What I've noticed though is that for some problems I tried to use it for it does seem to work based on the intuition I described above i..e. Func
really is called only settings.MajorIterations
times.
I don't like the name very much. It is long and we don't use "step direction" anywhere else. What about changing it to one of
ErrNonDescentDirection
ErrNonDecreasingDirection
ErrInvalidDirection // Mmm, not very descriptive
?
Many problems have a gradient that's expensive to compute. The line searchers we implement should check that the function value has decreased before asking for the gradient.
I've just typed:
go get github.com/gonum/matrix/mat64
and
go get github.com/gonum/optimize
is returning the following errors:
github.com/gonum/optimize/bfgs.go:136: undefined: mat64.Inner
github.com/gonum/optimize/bfgs.go:161: b.invHess.RankOne undefined (type *mat64.Dense has no field or method RankOne)
is there a specific fork from mat64 that I should be using?
The linesearches we implement should not test for strict function decrease (fnew <= fmin), but instead test within a tolerance. This helps get closer to the true minimum (based on the gradient norm), as the function value converges faster than the gradient for a smooth problem near the optimum.
This was originally part of the line search, but was removed because of confusion with updating OptLoc. Now that the optimizer is strictly in charge of updating OptLoc, we can add this test back in.
It should be a tunable parameter. It should work properly with #127 .
Much nicer names. Already in MoreThuente, should be changed in other linesearchers.
Quasi-Newton methods are great, but Newton methods are better if you have a real Hessian.
I have been giving it more thought and I am still not convinced that passing ProblemInfo
to Method.Init()
makes sense. Methods already announce what they need via Needs()
and we allocate fields of Location
exactly according to this information. Evaluation types issued by Method should/have to match this information. So ProblemInfo will convey what Needs() returned plus perhaps something more but Method cannot use that information anyway, it cannot issue evaluation types beyond Needs(). Comments, @btracey ?
Also Method
can implement Status()
which is checked in Local()
before calling Method.Iterate()
.
Working on #103 I noticed a possible subtle issue in LinesearchMethod.Iterate()
. It is in a sense a consequence of another unclear definition/promise: that the location passed to Iterate() is always the same struct and that Methods are supposed to (or can) construct its fields gradually.
In linesearch.go:60
we compute the gradient projected onto the search direction and then pass it to Linesearcher.Finished()
together with loc.F:
projGrad := floats.Dot(loc.Gradient, ls.dir)
if ls.Linesearcher.Finished(loc.F, projGrad) {
However, if only one of loc.F and loc.Gradient was evaluated previously, the other is NaN (because fortunately we invalidate). It obviously works, but I think it is more of a coincidence rather than intentional design. Backtracking requests only FuncEvaluation and checks only Armijo condition (so NaNs in the gradient don't bother it). Bisection requests FuncEvaluation | GradEvaluation, so projGrad = NaN never happens. The question is what would happen if we (or another external Linesearcher) started to issue the evaluations separately and request GradEvaluation only if the Armijo condition passes.
In general, I think we should not form projGrad and call Linsearcher.Finished() until we know that we have all the data for it but we do not (cannot) know that. It seems to me that it should be Linesearcher that announces to us that it has finished in a similar way how Method announces MajorIteration because Linesearcher best knows when it has all the data.
Comments, rebuttal, @btracey ?
As a side note, the change in Method interface as discussed in #103 basically precludes the *Location
passed to Iterate() to be used as it is being used now, so it is a good thing. On the other hand, the snowball effect of changing the Method interface and merging IterationType and EvaluationType is pretty big. I may submit a trial PR sometime this week.
The function comparison trickiness in Bisection causes difficulty with the operation of the rest of the package. Furthermore, it doesn't even work in the general case -- the floating point noise depends on the specific function. It's just not possible to converge a general non-linear function that far. Instead, we should at least describe (and possibly provide) a simple way to converge the gradient past 1e-10 if the user is willing to assume the function is locally quasi-convex.
As discussed before, Linesearcher.Finished()
can be removed and replaced with MajorIteration
returned from Linesearcher.Iterate()
. It fits better the whole reverse communication design.
Pass a copy of X to evaluation routines so that Problem
cannot overwrite it either by mistake or on (misguided) purpose.
The result struct we return has FunctionEvals which is the specific number of times F() is evaluated Reporting such information is useful, but we may need to think of a rename. It's confusing that MaxFunEvals is Function + FunctionGradient, but the result struct is just Function.
Default Printer reports NaNs as objective function values when GradientDescent is used and every iteration printer. The reason is that Backtracking requires only FunctionEval, so when the step is finished, GradientEval is requested. evaluate() for this evalType puts math.NaN() into location.F unconditionally (original location.F is then restored back by Backtracking).
One option would be to test if xNext is different from location.X and put NaN into location.F only if it is. However, this implies extra work when Dim is large. Any other options?
NewPrinter should allow the input to be written to a different writer if desired.
Change the order of arguments for evaluation routines like Grad() and Hess() so that they follow the gonum rule that answer receivers are the first inputs.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.