# 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:** 20\
**Page:** 1

<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 26, 2022, 7:30am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/1 "2022-01-26T07:30:59Z")

</div>

I’m trying to reduce the number of times NLP is returning a local minima instead of global minima (I know theoretically this is impossible if the objective is difficult enough). Currently I’m just doing a for-loop where I rerun the model with a different initialization of variables (below). Is there a better way to do this?

```julia
runs = []

for i in range(1, restarts)
  model = Model(Ipopt.Optimizer)
  
  @variable(model, 1>= x[1:4] >= 0)
  x0 = rand(.......
  set_start_value.(x, x0)
  
  @constraint(model, ........)
  
  # my_objective(x...) = .........
  
  register(model, :mobj, length(x), my_objective; autodiff = true)
  @NLobjective(model, Min, mobj(x...))
  
  optimize!(model)
  push!(runs, model)
end

select_best_run(runs)

```

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [January 26, 2022, 8:18am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/2 "2022-01-26T08:18:19Z")

</div>

Why not just save the solutions? No need to rebuild the model every time.

```nohighlight
runs = Any[]
for i in 1:restarts
    x0 = rand(4)
    set_start_value.(x, x0)
    optimize!(model)
    push!(runs, value.(x))
end

```

---

<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 26, 2022, 8:34am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/3 "2022-01-26T08:34:43Z")

</div>

How does scoping work for variable x? I tried putting this for-loop into a helper function but x wasn’t avaiable. So I tried passing x in as an argument but it seems to have been converted to a Float64?

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [January 26, 2022, 9:19am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/4 "2022-01-26T09:19:56Z")

</div>

```nohighlight
using JuMP, Ipopt
runs = Any[]
model = Model(Ipopt.Optimizer)
@variable(model, 0 <= x[1:4] <= 1)
my_objective(x...) = sum(sin((x[i] - i) / 10) for i in 1:4)
register(model, :mobj, length(x), my_objective; autodiff = true)
@NLobjective(model, Min, mobj(x...))
for i in 1:5
    x0 = rand(4)
    set_start_value.(x, x0)
    optimize!(model)
    push!(
        runs, 
        (
            obj = objective_value(model), 
            x = value.(x),
            x0 = x0,
        )
    )
end
obj, index = findmin(r -> r.obj, runs)
runs[index]

```

---

<div class="post-metadata">

**Author:** ![cvanaret](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cvanaret/32/11594_2.png) [@cvanaret](https://discourse.julialang.org/u/cvanaret)\
**Post date:** [January 26, 2022, 9:30am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/5 "2022-01-26T09:30:51Z")

</div>

When using gradient-based methods (such as Ipopt) on a nonconvex problem, the best you can do is multistart, as my colleagues suggested.

Alternatively, since your problem seems small, you can use interval methods: [https://github.com/JuliaIntervals/IntervalOptimisation.jl](https://github.com/JuliaIntervals/IntervalOptimisation.jl)  
These are global methods that explore the whole search space and produce the global minimum. They’re significantly more expensive than local methods, but on a small problem, you can afford it.

---

<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 26, 2022, 9:32am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/6 "2022-01-26T09:32:57Z")

</div>

Thank you for the suggestion! We’re thinking about scaling up the problem so it may not be feasible. But it could be useful in a future setting. What’s the asymptotic run-time of interval methods? At which point does it become less efficient than N restarts of gradient-methods?

---

<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 26, 2022, 9:33am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/7 "2022-01-26T09:33:47Z")

</div>

Thank you! This example is very useful for me and I’m sure others who find this post. For completeness of understanding, then based on how variable scopes work in JuMP, there’s no way to throw the for-loop into a helper function and access x?

---

<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 26, 2022, 10:36am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/8 "2022-01-26T10:36:47Z")

</div>

> [@Kevin\_Shen1](#):
>
> Is there a better way to do this?

The timing of this question is almost too perfect. I have been working on a paper on this with my colleague @yijiangh and the draft is almost ready and will be made public in the next few days. Will post it here then so check back in a few days.

---

<div class="post-metadata">

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

</div>

In the worst case, global methods have an exponential complexity, because they (usually) do branch and bound. However, you get the optimal solution with a certificate of global optimality (robust to roundoff errors for interval methods). If your problem ends up large, you can also try out classical global methods, such as BARON and Couenne.

Doing multistart **raises the probability** of obtaining the global minimum, but it really gives you no guarantee at all in this regard. All (good) local methods can guarantee is local optimality (or local optimality of the constraint violation if the problem is locally/globally infeasible).

---

<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 26, 2022, 12:36pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/10 "2022-01-26T12:36:31Z")

</div>

> [@cvanaret](#):
>
> When using gradient-based methods (such as Ipopt) on a nonconvex problem, the best you can do is multistart, as my colleagues suggested.

But there are potentially better ways to multistart than just sampling starting points uniformly.

My favorite algorithm for this is MLSL, which has a method to “filter” the starting points that often lets you avoid re-optimizing the same local optimum over and over (with some provable asymptotic guarantees, so it’s not completely heuristic). In low dimensions (here @Kevin_Shen1 is in 4) I’ve had very good results with it.

There are other methods as well, e.g. DIRECT-like branch-and-bound methods that systematically subdivide the parameter space and then do a local optimization in different subregions.

One thing to keep a close eye on is the tolerance of the local optimizer. You often want a fairly coarse tolerance for convergence when doing multistart. Then, at the very end, take your best local optimum and run local optimization again with a fine tolerance to “polish” the optimum.

---

<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 26, 2022, 4:44pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/11 "2022-01-26T16:44:21Z")

</div>

Thanks this is what I was hoping for! What local optimizer and tolerances you use for the “global optimization” and the final local optimization parts? Are you using NLopt? I do see MLSL is implemented in that package.

If you happen to have a code snippet, that’d be very helpful as well!

---

<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 26, 2022, 7:04pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/12 "2022-01-26T19:04:08Z")

</div>

> [@Kevin\_Shen1](#):
>
> What local optimizer and tolerances you use for the “global optimization” and the final local optimization parts? Are you using NLopt?

Yes, we’ve always used the NLopt implementation of MLSL (e.g. [here](http://doi.org/10.1364/OE.17.007505)); but it’s not a very complicated algorithm if someone wants to implement a pure-Julia version. (The hardest part is the nearest-neighbor search in d dimensions, but there are already [packages for this](https://github.com/KristofferC/NearestNeighbors.jl) in Julia. The original MLSL algorithm is for box-constrained optimization only, but there are nonlinearly constrained variants, e.g. [here](https://pubs.acs.org/doi/10.1021/ie800319m) and [here](https://www.sciencedirect.com/science/article/abs/pii/S0305054806001870).)

YMMV on local solvers, but the usual advice holds — if you can possibly get an analytical gradient (either by AD or manually), you should use a local-search algorithm (e.g. LBFGS) that exploits it.

---

<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, 12:02am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/13 "2022-01-28T00:02:42Z")

</div>

> [@mohamed82008](#):
>
> The timing of this question is almost too perfect. I have been working on a paper on this with my colleague @yijiangh and the draft is almost ready and will be made public in the next few days. Will post it here then so check back in a few days.

[Here you go](https://www.researchgate.net/publication/358151220_Simplifying_deflation_for_non-convex_optimization_with_applications_in_Bayesian_inference_and_topology_optimization?_sg%5B0%5D=6aGdNha0JWJY7iadPWsiWyu0S925DTQuTrk8pqRYRoemLYjiFRiFZV30F6-bUtMFKyGVlej79rx6v6HF6FRLciFaquU0yWdVycN6_uV_.GSBMuRoo7JmAB-hVZcno1P46sANAuykv4uYvFWVo5IEt9ucOHN6sR6Vrj9vKoqoESi5oe9Eqx4IWJ6H_s_leRg). I hope you can find it useful. Any feedback is appreciated 🙂

---

<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, 12:43am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/14 "2022-01-28T00:43:02Z")

</div>

> [@mohamed82008](#):
>
> [Here you go](https://www.researchgate.net/publication/358151220_Simplifying_deflation_for_non-convex_optimization_with_applications_in_Bayesian_inference_and_topology_optimization?_sg%5B0%5D=6aGdNha0JWJY7iadPWsiWyu0S925DTQuTrk8pqRYRoemLYjiFRiFZV30F6-bUtMFKyGVlej79rx6v6HF6FRLciFaquU0yWdVycN6_uV_.GSBMuRoo7JmAB-hVZcno1P46sANAuykv4uYvFWVo5IEt9ucOHN6sR6Vrj9vKoqoESi5oe9Eqx4IWJ6H_s_leRg). I hope you can find it useful. Any feedback is appreciated 🙂

This looks like a nice approach to get diverse local minima. Is it also applicable to nonlinear inequality constraints without introducing slack variables? (It would be nice if there were an automated way to choose the dimensionful hyperparameters r and y.)

But if you iterate it over and over like a multistart algorithm, it looks like you aren’t guaranteed to find a global optimum eventually, since the deflation penalty may “push the optimizer away from other nearby locally optimal solutions”? So it’s not strictly comparable to a multistart algorithm like MLSL (which, in theory, eventually finds the global optimum, although it doesn’t provide any certificate of optimality).

---

<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, 12:53am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/15 "2022-01-28T00:53:47Z")

</div>

> [@stevengj](#):
>
> Is it also applicable to nonlinear inequality constraints without introducing slack variables?

Yes.

> [@stevengj](#):
>
> But if you iterate it over and over like a multistart algorithm, it looks like you aren’t guaranteed to find a global optimum eventually, since the deflation penalty may “push the optimizer away from other nearby locally optimal solutions”? So it’s not strictly comparable to a multistart algorithm like MLSL (which, in theory, eventually finds the global optimum, although it doesn’t provide any certificate of optimality).

Correct. But the target users of this approach typically don’t care about global optimality as much as they care about exploring multiple diverse local optima.

---

<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 28, 2022, 10:56am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/16 "2022-01-28T10:56:27Z")

</div>

Very noobie question but why is NLopt complaining,

`ERROR: LoadError: ArgumentError: invalid NLopt arguments: invalid algorithm for constraints`?

```julia
model = Model(NLopt.Optimizer)
set_optimizer_attribute(model, "algorithm", :G_MLSL_LDS)
set_optimizer_attribute(model, "local_optimizer", :LD_LBFGS)

A = [
    1 1 9 5
    3 5 0 8
    2 0 6 13
]

b = [7; 3; 5]

c = [1; 3; 5; 2]

@variable(model, 0<= x[1:4] <=1000)
set_start_value.(x, [1.0, 1, 1, 1])
start_value.(x)

@constraint(model, A * x .== b)

identity(x) = x # the internal functions can be on vectors
C(x, c) = c' * x

myobj2 = function(x...)
    return c' * collect(x) # or it's just sufficient to collect inside the function, main thing is you need to
    # tell JuMP the length of the parameters beforehand
end

register(model, :mobj, length(x), myobj2; autodiff = true)
@NLobjective(model, Min, mobj(x...))

JuMP.optimize!(model)

```

---

<div class="post-metadata">

**Author:** ![cvanaret](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cvanaret/32/11594_2.png) [@cvanaret](https://discourse.julialang.org/u/cvanaret)\
**Post date:** [January 28, 2022, 10:57am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/17 "2022-01-28T10:57:53Z")

</div>

L-BFGS is a method for solving unconstrained problems. For bound constrained problems, there exists L-BFGS-B (no idea if it’s available though).  
For general constraints, you should use something else (e.g. Ipopt, SNOPT, filterSQP, Knitro, etc).

---

<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 28, 2022, 11:15am UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/18 "2022-01-28T11:15:27Z")

</div>

I get the same error with SLSQP: `set_optimizer_attribute(model, "local_optimizer", :LD_SLSQP)`. However, I can optimize with SLSQP alone `set_optimizer_attribute(model, "algorithm", :LD_SLSQP)` without MLSL. Is this expected?

---

<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, 1:03pm UTC](https://discourse.julialang.org/t/best-way-to-improve-local-minimas-in-nonlinear-optimization/75215/19 "2022-01-28T13:03:40Z")

</div>

> [@cvanaret](#):
>
> L-BFGS is a method for solving unconstrained problems. For bound constrained problems, there exists L-BFGS-B (no idea if it’s available though).

`:LD_LBFGS` in NLopt supports bound constraints. But it doesn’t support equality constraints.

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.)

---

<div class="post-metadata">

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

</div>

For constraints one can easily project on, ProximalAlgorithms implements a couple of algorithmic schemes that rely on L-BFGS to solve constrained problems, see for example: [https://juliafirstorder.github.io/ProximalAlgorithms.jl/dev/implemented\_algorithms/#ProximalAlgorithms.PANOCIteration](https://juliafirstorder.github.io/ProximalAlgorithms.jl/dev/implemented_algorithms/#ProximalAlgorithms.PANOCIteration)

(Note that the documentation only refers to the `master` branch, and I’m currently working on a couple of breaking changes there to improve things)

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