This is an interesting bisection algorithm for one function, focused on discover many roots
http://goo.gl/SfTOK

Edit:

I've found the algorithm in fortran for the generalized version I linked above:
paper
fortran code

Edited by user 04 October 2012 20:46:16(UTC)  | Reason: Not specified

Hello w3b5urf3r,

I could see you are close to realizing the optimization (minimization/maximization) algorithms as well rinks:
Of course, derivatives would cause problems sometimes, and it would be quite useful if they could be avoided.

I do not know what can we do about it. I suppose it is a SPAM filter of the Forum issue. Your unfinished versions of this post appeared in the unapproved posts.

If someone else experienced this, just let us know.

Regards,
Radovan

FOR TESTING PURPOSES ONLY

Hi all,

in the attached plugin:

- new function GaussNewton(...) - Gauss-Newton optimization algorithm.
- new functions GoldenSectionSearch.min(...) and GoldenSectionSearch.max(...) - Golden Section Search minimization/maximization algorithms.
- new functions GradientDescent(...) and GradientDescent.GSS(...) - Gradient Descent optimization algorithm (respectively with fixed step length and GoldenSectionSearch-based step length).
- new functions NewtonMethod(...) and NewtonMethod.GSS(...) - Newton Method optimization algorithm (respectively with fixed step length and GoldenSectionSearch-based step length).
- new function Gradient(...) - 1st order derivatives.
- new function Diag(...) - improved SMath diag().
- function Jacobian(...) revisited (now returns only a derivative or a mxn Jacobian)
- solver Bisection(...) revisited (the number of iterations is no longer required, as reported by adiaz)

from previous BETA

- new function LevenbergMarquardt(...) - Levenberg-Marquardt optimization algorithm (previous BETA - fixed issues)
- new function Hessian(...) - 2nd order derivatives (previous BETA - no changes)
- All root-finding algorithms in k variable now accept multiple thresholds (a target precision value for each function) (previous BETA - no changes)
- Fixed "custom decimal symbol" issue of HRE functions. (previous BETA - no changes)

SEE THE ATTACHMENTS FOR ALL DETAILS - PLEASE REPORT ANY ISSUE





I'm considering it, BTW i hope the issue on differentiation order it will be solved ASAP .


best regards,

w3b5urf3r

Edited by user 09 October 2012 02:29:55(UTC)  | Reason: Not specified

Thank you Martin, the "empty stack" issue it's a SMath bug related to the reference function name (now renamed, see the attachments)

BTW I've reuploaded both plugin and examples, with minor changes.


The 2nd description appear when a function have "optional arguments"; indeed there is a boolean parameter to hide the description, but in the dynamic assistance description only; I don't know how (and if there is a way) to hide the second description in the plugin window (however I think it's a feature, not a bug).



best regards,

w3b5urf3r

Edited by user 09 October 2012 16:24:43(UTC)  | Reason: Not specified

Hello w3b5urf3r,

My congratulations for your efforts. Yo have all my respect for that .

But...I must be annoying with nagging so many times about Jacobian, Gradient, Hessian analytically . I become to like the sentence "Jacobian Computation-free" as in your previous post.

This is (again ) my Nonlinear least square test problem. I tried it with LevenberMarquartd(). As might be expected, almost impossible to solve it - large expression and problems with derivatives . I reduced the number of points (n=4) and the LM gave the result. One might try, but it should take more than an hour to get the result. Just wanted to check if this is working. It is working, but that slow and almost useless it this case.

I would kindly ask you just to try, when you have the time, to replace all those derivative dependent things wit some numerical complement. Regarding all those troubles with derivatives, I do not see any other way in order to get out from this very common problem like Nonlinear least squares. I tried to chage your LevenberMarquartd.ref() function and to replace Jacobian() and Gradient() with the numerical ones without success. Gradient() gave me troubles that I could not resolve - Just made it from my Jacnum() function, but it did not work.

Regards,
Radovan

Edited by user 09 October 2012 17:55:01(UTC)  | Reason: Not specified

Hope this can be of any help ^^

Newton-Raphson with finite diferences pages 10-11-12
http://dmaii.etsii.upm.e...ads/Clase_sisno_2_06.pdf

Levenberg–Marquardt with finite diferences page 33
http://www.jldelafuenteo...e_mincua_nolineal_12.pdf

Hybrid method: Levenberg-Marquardt + Quasi-Newton(Broyden-Fletcher-Goldfarb-Shanno)
Matlab code page 81
http://riunet.upv.es/bit.../10251/10343/memoria.pdf

EDIT:

The last document contains 4 methods of least squares written in matlab
(analytic:fast but only for canonical/regular problems; numeric: flexible for many problems but memory/time consuming; hybrid: combines the latter ones)
There are also approximations for Jacobian and Gradient on page 84.

Edited by user 10 October 2012 03:35:47(UTC)  | Reason: Not specified

Thank you, please try again with the new "BETA_testing sm files.zip", I've forgot to replace the ";" in two reference functions.


No problem, I'll do it in the next relase.


regards,

w3b5urf3r

Edited by user 10 October 2012 04:23:08(UTC)  | Reason: javascript:__doPostBack('forum$ctl03$PostReply','')

Please have in mind if you take into account my last document link:
http://riunet.upv.es/bit.../10251/10343/memoria.pdf
that it assumes the function has first and second derivatives and both are continue, otherwise the conditions to calculate the minimum change and so do the algorithms to apply, in that case the author invites the reader to consult:
"Roger Fletcher. Practical Methods of Optimization. John Wiley & Sons, 2001"

Hi omorr,

Seems that the computation efforts are in the Jacobian calculation... BTW I'm implementing Central Differences Gradient/Jacobian/Hessian (in the attachment a test with your primer_47w )


In the attachment a sm file containing the algorithm above... works, but not as expected


regards,

w3b5urf3r

Edited by user 11 October 2012 02:12:39(UTC)  | Reason: Not specified

Hi,

I did some simple testing, here are the results.
The screenshot is generated with standard settings for dec and arg delims.

Broyden and HRE.B generate errors with non-standard settings (dec , and arg . All other errors seem not to be custom settings related.

Quite interesting that solve(4) outperforms them all in the given example.

Most solvers that take intervals as arguments just allow one root in that interval.

Best regards, Martin