# Suggestions needed: global binary optimization

**URL:** <https://discourse.julialang.org/t/suggestions-needed-global-binary-optimization/40952>\
**Category:** General Usage\
**Tags:** optimization\
**Created:** [June 7, 2020, 9:21pm UTC](https://discourse.julialang.org/t/suggestions-needed-global-binary-optimization/40952 "2020-06-07T21:21:39Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Chong\_Wang](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chong_wang/32/20307_2.png) [@Chong\_Wang](https://discourse.julialang.org/u/Chong_Wang)\
**Post date:** [June 7, 2020, 9:21pm UTC](https://discourse.julialang.org/t/suggestions-needed-global-binary-optimization/40952/1 "2020-06-07T21:21:39Z")

</div>

The problem is very simple: x is a vector taking value from 0 or 1; S is a real symmetric matrix. The object is to minimize `dot(x.+c, S, x.+c)` with the constraint `sum(x)=N`, where N is an integer smaller than `length(x)` and c is just a real float number.

The issue is: the length of x is very large (~10^4) and I believe a deterministic solution is not possible (maybe I am wrong?). I have little knowledge in mathematical optimization and could use some suggestions on what algorithms I should spend time to investigate to solve such a problem.

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [June 8, 2020, 5:40am UTC](https://discourse.julialang.org/t/suggestions-needed-global-binary-optimization/40952/2 "2020-06-08T05:40:05Z")

</div>

What if you do an eigenvalue decomposition of `S` and pick the x non-zero for the N largest eigenvalues?

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [June 8, 2020, 7:54am UTC](https://discourse.julialang.org/t/suggestions-needed-global-binary-optimization/40952/3 "2020-06-08T07:54:37Z")

</div>

> [@baggepinnen](#):
>
> What if you do an eigenvalue decomposition of `S` and pick the xx non-zero for the NN largest eigenvalues?

I didn’t quite understand that. Which eigenvalue decomposition do you suggest to use? Here’s a non-optimal snippet which minimizes the function by brute force for a random S and c. And a list of eigenvalues. How does your suggested algorithm pick the first and fourth position?

```julia
using LinearAlgebra                                                                                   
using Combinatorics                                                                                   
import Random                                                                                         
                                                                                                      
Random.seed!(42)                                                                                      
M = 4                                                                                                 
N = 2                                                                                                 
A = rand(M,M)                                                                                         
S = A + A'                                                                                            
c = rand()                                                                                           
                                                                                                      
f(x) = dot(x .+ c, S, x .+ c)                                                                         
                                                                                                      
function fc(f, cmb)                                                                                   
    x = zeros(M)                                                                                      
    x[cmb] .= 1                                                                                       
    f(x)                                                                                              
end                                                                                                   
val, x = minimum( (fc(f,cmb), cmb) for cmb in combinations(1:M, N))                                   
println("minimum: x=$x, val=$val")                                                                  
                                                                                                      
println(eigvals(S))

```

output:

```julia
minimum: x=[1, 4], val=16.61444763159244
[-0.023080673209075427, 0.3946150562493981, 1.0832708395200012, 4.200607767705681]

```

---

<div class="post-metadata">

**Author:** ![CarloLucibello](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carlolucibello/32/3278_2.png) [@CarloLucibello](https://discourse.julialang.org/u/CarloLucibello)\
**Post date:** [June 8, 2020, 8:44am UTC](https://discourse.julialang.org/t/suggestions-needed-global-binary-optimization/40952/4 "2020-06-08T08:44:26Z")

</div>

Given the size the problem, probably you will have to resort to heuristics methods such Simulated Annealing or Extremal Optimization. You will find an implementation of extremal optimization in  
[https://carlobaldassi.github.io/RRRMC.jl/dev/algorithms/#RRRMC.extremal\_opt](https://carlobaldassi.github.io/RRRMC.jl/dev/algorithms/#RRRMC.extremal_opt)  
and simulated annealing can be easily coded using the same repo to implement a MCMC with decreasing temperature

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [June 8, 2020, 10:09am UTC](https://discourse.julialang.org/t/suggestions-needed-global-binary-optimization/40952/5 "2020-06-08T10:09:07Z")

</div>

> [@sgaure](#):
>
> I didn’t quite understand that. Which eigenvalue decomposition do you suggest to use?

I though about it a bit more and realized it’s much more complex. If it was a norm constraint on x, and `c` was 0, you’d select the eigenvector belonging to the largest eigenvalue. Now, you could start by soling the norm-constrained quadratic program, and then projecting the solution onto the feasible set, but I do not believe that this will always give you the optimal solution.

---

<div class="post-metadata">

**Author:** ![Chong\_Wang](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chong_wang/32/20307_2.png) [@Chong\_Wang](https://discourse.julialang.org/u/Chong_Wang)\
**Post date:** [June 8, 2020, 5:49pm UTC](https://discourse.julialang.org/t/suggestions-needed-global-binary-optimization/40952/6 "2020-06-08T17:49:13Z")

</div>

> [@baggepinnen](#):
>
> projecting the solution onto the feasible set

I believe the feasible set does not form a vector space. What do you mean by projection?

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [June 8, 2020, 5:58pm UTC](https://discourse.julialang.org/t/suggestions-needed-global-binary-optimization/40952/7 "2020-06-08T17:58:05Z")

</div>

> [@Chong\_Wang](#):
>
> What do you mean by projection?

I simply mean a reasonable transformation that takes a vector and produces another one that is close in some sense. For example, keeping the N values closest to 1, the N largest values etc.

---

<div class="post-metadata">

**Author:** ![Chong\_Wang](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chong_wang/32/20307_2.png) [@Chong\_Wang](https://discourse.julialang.org/u/Chong_Wang)\
**Post date:** [June 8, 2020, 6:03pm UTC](https://discourse.julialang.org/t/suggestions-needed-global-binary-optimization/40952/8 "2020-06-08T18:03:55Z")

</div>

Thank you. I’ll take a look.

---

<div class="post-metadata">

**Author:** ![francesco.alemanno](https://avatars.discourse-cdn.com/v4/letter/f/e8c25b/32.png) [@francesco.alemanno](https://discourse.julialang.org/u/francesco.alemanno)\
**Post date:** [June 9, 2020, 3:31pm UTC](https://discourse.julialang.org/t/suggestions-needed-global-binary-optimization/40952/9 "2020-06-09T15:31:40Z")

</div>

> **[Population-based incremental learning](https://en.wikipedia.org/wiki/Population-based_incremental_learning)**
>
> In computer science and machine learning, population-based incremental learning (PBIL) is an optimization algorithm, and an estimation of distribution algorithm. This is a type of genetic algorithm where the genotype of an entire population (probability vector) is evolved rather than individual members. The algorithm is proposed by Shumeet Baluja in 1994. The algorithm is simpler than a standard genetic algorithm, and in many cases leads to better results than a standard genetic algorithm.\[ In PB...