# Best way to improve local minimas in nonlinear optimization?

**URL:** <https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215>\
**Category:** Optimization (Mathematical)\
**Tags:** question, jump\
**Created:** [January 26, 2022, 7:30am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215 "2022-01-26T07:30:59Z")\
**Posts on this page:** 10\
**Page:** 2

<div class="post-metadata">

**Author:** ![Tomas\_Pevny](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomas_pevny/32/25466_2.png) [@Tomas\_Pevny](https://discourse.julialang.org/u/Tomas_Pevny)\
**Post date:** [January 28, 2022, 8:29pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/21 "2022-01-28T20:29:19Z")

</div>

What is the sentiment about this method?

> **[A Global Optimization Algorithm Worth Using](http://blog.dlib.net/2017/12/a-global-optimization-algorithm-worth.html)**
>
> Here is a common problem: you have some machine learning algorithm you want to use but it has these damn  hyperparameters . These are number...

It looks cool, might be slow though. I know there was a sequel that has combined it with bayesian optimization. Can find it if someone would be interested in.

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [January 28, 2022, 10:44pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/22 "2022-01-28T22:44:13Z")

</div>

Hyper-parameter optimisation typically relies on derivative-free optimisation algorithms. Asking for an algorithm (especially derivative free) that can handle optimising many hyper-parameters for almost any problem without having many or any hyper-parameters of its own is a bit unrealistic in my view. You can pretty much always formulate worst case problems for any algorithm to make it behave pathologically compared to other algorithms. Even gradient based solvers typically require a fair bit of fiddling with to get their best hyper-parameters. So this problem sounds a lot like: I want the best optimisation algorithm that works well all the time with very little effort on my side. If such an algorithm existed, people would have stopped studying optimisation long time ago 🙂 That’s not saying the method linked above is bad but it will have to be more thoroughly benchmarked against other algorithms in the same class (which are many) for a wide range of problems to be named a winner if a winner can even be named.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 28, 2022, 10:54pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/23 "2022-01-28T22:54:06Z")

</div>

> [@Tomas\_Pevny](#):
>
> It looks cool, might be slow though. I know there was a sequel that has combined it with bayesian optimization. Can find it if someone would be interested in.

This algorithm ([AdaLIPO](https://arxiv.org/pdf/1703.02628.pdf)) looks very similar in spirit to the [DIRECT algorithm](https://link.springer.com/article/10.1007/s10898-020-00952-6), albeit with a more stochastic approach, and indeed on their test problems it is usually within a factor of 2 of DIRECT. Unfortunately this also means that it is probably only practical in low dimensions.

---

<div class="post-metadata">

**Author:** ![ctkelley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ctkelley/32/10684_2.png) [@ctkelley](https://discourse.julialang.org/u/ctkelley)\
**Post date:** [January 28, 2022, 11:32pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/24 "2022-01-28T23:32:09Z")

</div>

DIRECT is not without problems. Ref 14 of the paper @stevengj points to explains one of them. Having said that, I’ve had decent luck with DIRECT on a few problems (see ref 5 in the paper). In the limit, DIRECT explores all of design space, so it is (as D. Jones, the inventor says) a global algorithm. That is not great news, as randomly throwing darts will do the same thing.

If you understand that the goal of algorithms like this is to find a better point that what you have, rather than spend far too much time to obtain a true global optimum, algorithms like this can make your life better.

There are a few papers that claim DIRECT is useful for large problems, but I’m not convinced.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 28, 2022, 11:42pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/25 "2022-01-28T23:42:02Z")

</div>

> [@ctkelley](#):
>
> That is not great news, as randomly throwing darts will do the same thing.

Yes, but DIRECT tends to be much faster than [pure random search](https://link.springer.com/chapter/10.1007/978-1-4419-9182-9_2) and also helps ensure solution diversity — it essentially prioritizes searching not-yet-visited regions that have a combination of large diameter and low function value.

---

<div class="post-metadata">

**Author:** ![ctkelley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ctkelley/32/10684_2.png) [@ctkelley](https://discourse.julialang.org/u/ctkelley)\
**Post date:** [January 28, 2022, 11:43pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/26 "2022-01-28T23:43:13Z")

</div>

Correct. DIRECT is one of many methods that perform better than theory predicts.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 29, 2022, 12:24pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/27 "2022-01-29T12:24:55Z")

</div>

> [@ctkelley](#):
>
> one of many methods that perform better than theory predicts.

I don’t know what predictions you’re referring to. For general objective functions, AFAIK theory can only predict _whether_ an algorithm converges and certain asymptotic properties — even for _local_ optimization, you can devise problems where the algorithm takes arbitrarily long to converge (you only get stronger results about local-optimization convergence rate asymptotically when the objective is approximately quadratic, or for other special cases like LP etc.).

---

<div class="post-metadata">

**Author:** ![ctkelley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ctkelley/32/10684_2.png) [@ctkelley](https://discourse.julialang.org/u/ctkelley)\
**Post date:** [January 29, 2022, 12:51pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/28 "2022-01-29T12:51:43Z")

</div>

Methods such as Anderson acceleration ,for example, often do better than the asymptotic theory predicts. Asymptotic theory is not intended to descript the midrange of the iteration where a lot of good things can happen. Quasi-Newton methods with line searches are another example, as is the good performance of DIRECT (when it’s happy). The Nelder-Mead algorithm, for which there is very little theory, is yet another.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 29, 2022, 12:57pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/29 "2022-01-29T12:57:15Z")

</div>

> [@ctkelley](#):
>
> Asymptotic theory is not intended to descript the midrange of the iteration where a lot of good things can happen

Right, you have in mind examples of algorithms doing well in cases where the theory makes _no_ predictions. To me, this is not “doing better than the theory” because there _is_ no theory.

---

<div class="post-metadata">

**Author:** ![Kevin\_Shen1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kevin_shen1/32/33160_2.png) [@Kevin\_Shen1](https://discourse.julialang.org/u/Kevin_Shen1)\
**Post date:** [January 31, 2022, 10:23am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/30 "2022-01-31T10:23:03Z")

</div>

> [@stevengj](#):
>
> The real problem is probably that MLSL only supports bound constraints (not equality or nonlinear constraints).
> 
> (Maybe, since `A` matrix is so small, you can explicitly [eliminate this constraint](https://nlopt.readthedocs.io/en/latest/NLopt_Introduction/#elimination) through a change of variables.)

My Ax=b constraint was just a toy example. Our actual problem is more complex. Do you have a recommendation for a global optimization algorithm that’ll handle equality constraints? My linear algebra is a bit rusty, I’ll look into elimination procedure if there isn’t an easier option.

[Previous page](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215.md?page=1)