Modified newtons method #1068
Modified newtons method #1068
Conversation
… to converge in 1 under 1000 steps
… guess so that the following conditions are all met: 1. Hessian is indefinite 2. Directional Derivative is negative 3. The initial guess is between a local maximum and a global minimum This causes Newton's method with and without line search to converge to the local maximum
…te by reversing negative eigenvalues. Added optional enum parameter to NewtonMinimizer class to allow for future implementations of other methods of Hessian modification.
|
@cdrnet, Would it be possible to get this pull request reviewed? |
|
@jvangael, @jkalias, @JohanLarsson, I think you are also listed as member of the Math.Net team. Would any of you be willing to consider this pull request? |
|
@strMikhailPotapenko I would be more than happy to. The problem is that I can only merge PRs for the MathNet.Spatial project, for the Numerics only @cdrnet has the relevant rights to. |
|
@jkalias Ah I didn't know that, sorry about that and thank you for the response. Just looking at open issues and pull requests it does seem like there isn't a lot of activity with this repo, which is too bad because I have been using this library quite often lately and have been pretty satisfied with it. Do you happen to have any information on the plans of @cdrnet as far as actively maintaining this repo or any way to request that information from him? |
|
@strMikhailPotapenko nothing to be sorry about :) I have no information on whether/when @cdrnet will continue to actively maintain this repo. On the other hand, it's an open source project, so there is no obligation to do so, and rightfully so. |
|
@jkalias Very true! |
| public enum HessianModifiers | ||
| { | ||
| None, | ||
| ReverseNegativeEigenValues |
There was a problem hiding this comment.
I would spell this as ReverseNegativeEigenvalues, with a small v
| /// </summary> | ||
| /// <param name="objective"></param> | ||
| /// <returns></returns> | ||
| static Vector<double> ReverseNegativeEigenValuesAndSolve(IObjectiveFunction objective) |
There was a problem hiding this comment.
Here also with small v, ReverseNegativeEigenvaluesAndSolve
| { | ||
| if (evd.EigenValues[i].Real < double.Epsilon) | ||
| { | ||
| evd.EigenValues[i] = Math.Max(-evd.EigenValues[i].Real, double.Epsilon); |
There was a problem hiding this comment.
You can skip the if condition altogether, if you write this as evd.EigenValues[i] = Math.Max(Math.Abs(evd.EigenValues[i].Real), double.Epsilon);
My proposed solution which resolves #1067.
I added an option to Newton Minimizer which forces the Hessian to be positive definite by reversing negative eigenvalues. This method is described in
Philip E. Gill, Walter Murray, and Margaret H. Wright, Practical Optimization, 1981, 107–8.
I also added a unit test, FindMinimum_SixHumpCamel_IndefiniteHessian(), to demonstrate the benefit of this modification. If the optional argument is changed to HessianModifiers.None then the test fails.
Please see the issue for further illustration of the use case.
I made the optional argument an enum because this method of forcing positive definiteness can be improved upon in terms of efficiency and this gives some future developer the hooks to be able to do so.
Regards,
Mikhail