Suggestions needed: global binary optimization

General Usage
1

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.

2

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

1 Like
3

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?

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:

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

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
and simulated annealing can be easily coded using the same repo to implement a MCMC with decreasing temperature

5

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.

6

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

7

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.

8

Thank you. I’ll take a look.

9