GitHub - JuliaNLSolvers/Optim.jl: Optimization functions for Julia has a bfgs. it’s not a perfect though.
Probably all the BFGS implementations follow the rules that make them convergent. If there is a pure-Julia implementation, I don´t know.
I think I misread the claim above. I use that implementation often, but I would have been surprised if it claimed to find the global optimum, which was not claimed (my bad).
Excuse me for being pedantic.
Theoretically speaking, finding (or simply verifying) a global minimizer for a nonconvex problem is hard, and, in contrast to common misconceptions, finding (or simply verifying) a local minimizer is not easier [1].
All the algorithms discussed here up to now (Powell’s methods, BFGS, Nelder-Mead) are local optimization methods. They do not ensure whatever kind of convergence to global minimizers — it is simply impossible unless we are talking about a special class of problems. The reality is indeed much worse, which will be explained in the sequel.
Many people may believe that a globally convergent (local) optimization method can guarantee convergence to a local minimizer. This is unfortunately wrong in general. Instead, such a method normally can only ensure that the iterates asymptotically achieve some stationarity conditions, e.g., the gradient converges to zero in the unconstrained smooth case, which is wildly different from “converging to a local minimizer” — the iterates may not even have an accumulation point at all. See, e.g., [2, Section 1.3].
I am pretty sure that none of the methods mentioned above can ensure convergence (in the sense you want) to a local minimizer for a general nonconvex problem, even though such convergence is typically observed in practice. How to bridge this theory-practice gap is another question on which I prefer to write a paper rather than continue my elaboration here.
References
[1] K. G. Murty and S. N. Kabadi. “Some NP-complete problems in quadratic and nonlinear programming.” Math. Program. 39 (1987), pages 117–129
[2] T. M. Ragonneau. Model-Based Derivative-Free Optimization Methods and Software. PhD thesis, The Hong Kong Polytechnic University, Hong Kong, China, 2022.
N.B.: Reference [2] is the thesis of my former PhD student. It is by no means an authoritative reference for optimization theory. I refer to it simply because I am familiar with it. Similar discussions can be found in any standard optimization textbook.
6 Likes
Your second link is broken, the correct one is https://theses.lib.polyu.edu.hk/handle/200/12294
2 Likes
You are right. Thank you for pointing this out and posting the new link.
Adding to the pool of packages with Nelder-Mead:
3 Likes
According to [1], the hard case is when the Hessian is not PSD at the minimum (for the unconstrained case) — in the common case where the Hessian is PSD at the local minimum, it’s not NP hard. Am I misunderstanding?
2 Likes