# Global, non-convex, smooth and differentiable optimisation?

**URL:** <https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460>\
**Category:** Optimization (Mathematical)\
**Created:** [May 3, 2021, 12:54pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460 "2021-05-03T12:54:01Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [May 3, 2021, 12:54pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/1 "2021-05-03T12:54:02Z")

</div>

I do have a loss function that :

- Is expressed as \lVert \mathbf y - \mathbf A'\mathbf p(\mathbf x)\rVert\_2^2, where \mathbf y is a simple vector, \mathbf A is a simple matrix (lower-triangular), and p\_1,...,p\_m are nasty polynomials.
- Polynomials p\_1,...,p\_m are computed through a recursive implementation, say a function `p(m,x)` that computes all of them at once and which should be considered a black box (the number of coefficients of the polynomials are in the millions if we try to express them explicitely…).

Moreover:

- The loss is written in pure julia and automatic differentiation can pass through
- But the very polynomial nature of the loss gives it a huge amount of local minimas, and any gradient descent (e.g. `Optim.LBFGS()`) gets stuck on the nearest local minimum.

For all these reasons, I am currently optimizing through `Optim.ParticleSwarm()`, which is a global algorithm for non-convex non-differentiable functions. It works well but it’s quite slow.

Is there somewhere a global optimization algorithm that is more adapted to problems where:

- The loss function is clearly non-convex with a lot of local minima.
- But it is ‘smooth’ and automatic differentiation can pass through, and therefore local gradient descent are possibles.

It is required that the optimisation routines are implemented in pure julia as i use BigFloats. Furthermore if linear equality and bound contraints are posible it’s a bonus 🙂

---

<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:** [May 3, 2021, 3:21pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/2 "2021-05-03T15:21:52Z")

</div>

> [@lrnv](#):
>
> Is there somewhere a global optimization algorithm that is more adapted to problems where:
> 
> - The loss function is clearly non-convex with a lot of local minima.
> - But it is ‘smooth’ and automatic differentiation can pass through, and therefore local gradient descent are possibles.

I tend to use MLSL for this sort of problem: it is a multi-start algorithm where you repeatedly use a local optimizer (which can be e.g. BFGS) from different starting points, and which includes some techniques to prevent it from repeatedly searching the same local optima. e.g. NLopt includes an MLSL implementation. It requires some experimentation to choose good termination tolerances for the local search.

You didn’t say how many parameters you have, however. In high dimensions global optimization becomes pretty hard by any method!

> It is required that the optimisation routines are implemented in pure julia as i use BigFloats.

NLopt is calling an external C library and only handles `Float64`; you’d have to re-implement MLSL or some similar algorithm.

You should really try to see whether you can avoid BigFloats. For example, there are lots of ways of working with polynomials that are numerically unstable (e.g. using a monomial basis, Lagrange interpolation, etcetera) and might at first seem to require `BigFloat`, but which can be reformulated in a stable fashion (Chebyshev-polynomial bases, barycentric interpolation, etcetera) that works fine in double precision.

---

<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:** [May 3, 2021, 3:40pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/3 "2021-05-03T15:40:02Z")

</div>

If you are willing to write your problem as a JuMP model, give [GitHub - PSORLab/EAGO.jl: A development environment for robust and global optimization](https://github.com/PSORLab/EAGO.jl) or [GitHub - lanl-ansi/Alpine.jl: A Julia/JuMP-based Global Optimization Solver for Non-convex Programs](https://github.com/lanl-ansi/Alpine.jl) a try.

Edit: I plan to add these to Nonconvex.jl, automatically extracting the functions’ expressions but when I get sometime to integrate Nonconvex with ModelingToolkit.

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [May 3, 2021, 4:22pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/4 "2021-05-03T16:22:20Z")

</div>

Can a Jump model use a standard julia function as an objective function ? In which case, it might be easy to write it as a Jump model and i’ll try those two optimizers, for sure 🙂

---

<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:** [May 3, 2021, 4:25pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/5 "2021-05-03T16:25:48Z")

</div>

> [@lrnv](#):
>
> Can a Jump model use a standard julia function as an objective function ?

It’s not impossible but only EAGO may work then. See [Nonlinear Modeling · JuMP](https://jump.dev/JuMP.jl/v0.21.1/nlp/). If you don’t mind waiting, check Nonconvex again in a few weeks.

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [May 3, 2021, 4:25pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/6 "2021-05-03T16:25:53Z")

</div>

> [@stevengj](#):
>
> You should really try to see whether you can avoid BigFloats. For example, there are lots of ways of working with polynomials that are numerically unstable (e.g. using a monomial basis, Lagrange interpolation, etcetera) and might at first seem to require `BigFloat` , but which can be reformulated in a stable fashion (Chebyshev-polynomial bases, barycentric interpolation, etcetera) that works fine in double precision.

No we already did a lot of investigations, and found out that multiple precision is indeed needed for this problem. The polynomials themselves are _dense_, in the sense that they have millions/billions of coefficients in the standard monomial basis (I cannot even compute them). The algo i have for the loss is currently stable with BigFloats, and that’s the reason i’m on Julia. MultiFloats.jl also works well.

If there are no MLSL that are Julia-native then this is not a solution for me 😕

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [May 3, 2021, 4:26pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/7 "2021-05-03T16:26:40Z")

</div>

> [@mohamed82008](#):
>
> It’s not impossible but only EAGO may work then. See [Nonlinear Modeling · JuMP](https://jump.dev/JuMP.jl/v0.21.1/nlp/). If you don’t mind waiting, check Nonconvex again in a few weeks.

I do mind waiting, but i’ll definitely check it. Is there already a repo with some details about the infrastruture you are implementing ?

---

<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:** [May 3, 2021, 4:29pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/8 "2021-05-03T16:29:51Z")

</div>

The work will be in [https://github.com/mohamed82008/Nonconvex.jl](https://github.com/mohamed82008/Nonconvex.jl). There is no description other than that I want to run ModelingToolkit on the function, extract its expression and pass it to MathOptInterface for JuMP-based solvers to have access to it.

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [May 3, 2021, 4:34pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/9 "2021-05-03T16:34:33Z")

</div>

> [@mohamed82008](#):
>
> The work will be in [GitHub - mohamed82008/Nonconvex.jl: Toolbox for non-convex constrained optimization.](https://github.com/mohamed82008/Nonconvex.jl). There is no description other than that I want to run ModelingToolkit on the function, extract its expression and pass it to MathOptInterface for JuMP-based solvers to have access to it.

Looks perfect for what I want to do: allows me to specify my objective function as a genuine Julia function. Definitely tell me when you have a first working version 🙂

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [May 3, 2021, 4:58pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/10 "2021-05-03T16:58:38Z")

</div>

Isn’t this basically what GalacticOptim.jl is doing?

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [May 3, 2021, 5:14pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/11 "2021-05-03T17:14:52Z")

</div>

So many solvers and packages ! Everyday i found a new one at least.

So i’m trying EAGO through JuMP, but it seems like BigFloats are not possible… I do not find how to specify that i want my variables to be BigFloats.

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [May 3, 2021, 5:57pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/12 "2021-05-03T17:57:32Z")

</div>

JuMP only supports Float64 currently (ref [Generic numeric type in JuMP · Issue #2025 · jump-dev/JuMP.jl · GitHub](https://github.com/jump-dev/JuMP.jl/issues/2025))

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [May 3, 2021, 5:59pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/13 "2021-05-03T17:59:18Z")

</div>

Thanks a lot I did not found it myself. Thus JuMP is not for me. I’m stuck with `Optim.ParticleSwarm()` for the moment then.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [May 3, 2021, 6:32pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/14 "2021-05-03T18:32:12Z")

</div>

You can use EAGO directly without JuMP.

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [May 3, 2021, 7:00pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/16 "2021-05-03T19:00:38Z")

</div>

I’m sorry but i did not found an example without JuMP. As JuMP standards and syntax is quite new to me, I assumed that EAGo could not be used by itself. Do you have some kind of example ? I found nothing in the documentation (by a quick glance).

---

<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:** [May 3, 2021, 7:33pm UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/17 "2021-05-03T19:33:49Z")

</div>

> [@dpsanders](#):
>
> Isn’t this basically what GalacticOptim.jl is doing?

Note that I know of.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 4, 2021, 7:59am UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/18 "2021-05-04T07:59:31Z")

</div>

> [@lrnv](#):
>
> If there are no MLSL that are Julia-native then this is not a solution for me 😕

There is a WIP PR at

> <https://github.com/tpapp/MultistartOptimization.jl/pull/18>
>
> This is part of my GSoC project which I plan to work on this summer. This PR is …for the implementation of the MLSL (Multi-Level Single-Linkage) algorithm.

which will hopefully be finished soon, under GSOC.

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [May 4, 2021, 8:09am UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/19 "2021-05-04T08:09:54Z")

</div>

As I understood this relies on Nlopt.jl for local searches, so no Bigfloats ? Is there the possibility to use native Julia local searches (like Optim.LBFGS for example), to allow the whole thing to be type-agnostic ?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 4, 2021, 8:14am UTC](https://discourse.julialang.org/t/global-non-convex-smooth-and-differentiable-optimisation/60460/20 "2021-05-04T08:14:26Z")

</div>

> [@lrnv](#):
>
> Is there the possibility to use native Julia local searches (like Optim.LBFGS for example)

Yes, you can use any local method you want, just use a closure. I will need to document it, but in the meantime look at the source.

> <https://github.com/tpapp/MultistartOptimization.jl/issues/21>
>
> After #20, this should be easy. Add examples for both.