3 ms·

Newton's method is an algorithm you can use to minimise/maximise/find the root of a differentiable function very quickly if you start with a reasonable guess. T

Newton's method is an algorithm you can use to minimise/maximise/find the root of a differentiable function very quickly if you start with a reasonable guess. There are many variants on Newton's method, e.g. BFGS that does not require the hessian (/2nd order derivative) of the function. A pitfall of Newton's method is that it does not find the global minimum per se, it might just converge to a local minimum if this local minimum is "closer" to your initial guess. Some variants of Newton's method allow you to avoid this pitfall, but they are slow in practice. This seems to be another variant that claims to find the global minimum quicker than other existing methods. I am not experienced enough to verify this claim. I am also not sure how this new algorithm performs in practice; in theory, ellipsoid methods are a lot more efficient than simplex methods for optimising convex functions, while in practice simplex methods are usually an order of magnitude faster. So take this result with a grain of salt.

MauranKilom 5y ago
To clarify, "global" in this context refers to global convergence (as in, it won't diverge no matter the starting point), not global optima. They assume a convex function, i.e. only a single minimum. The paper is unrelated to avoiding local minima.
- abetusk 5y ago
  So isn't the magic here convexity? Convexity is such a huge constraint that I would guess convergence would be hard to avoid.
  - jleahy 5y ago
    Tell that to Newton’s method, which can fail to converge for convex functions.
  - kergonath 5y ago
    There is no way of ensuring that you have found a global minimum if the function is not convex, or if you don’t make equivalent assumptions, in the general case (if the domain of the function is continuous, and/or infinite). If you don’t make assumptions, you would need to consider every single point of the domain, and there is an infinite number of them. The job gets easier the more assumptions you make about the continuous, differentiable, and monotonous character of the function.

MauranKilom 5y ago

To clarify, "global" in this context refers to global convergence (as in, it won't diverge no matter the starting point), not global optima. They assume a convex function, i.e. only a single minimum. The paper is unrelated to avoiding local minima.

abetusk 5y ago
So isn't the magic here convexity? Convexity is such a huge constraint that I would guess convergence would be hard to avoid.
- jleahy 5y ago
  Tell that to Newton’s method, which can fail to converge for convex functions.
- kergonath 5y ago
  There is no way of ensuring that you have found a global minimum if the function is not convex, or if you don’t make equivalent assumptions, in the general case (if the domain of the function is continuous, and/or infinite). If you don’t make assumptions, you would need to consider every single point of the domain, and there is an infinite number of them. The job gets easier the more assumptions you make about the continuous, differentiable, and monotonous character of the function.