# Optimizing along a cube $s=\{0,1\}^n$

I am doing an optimization on a n-dimensional cube. That means that every solution is a set of $0$ and $1$, hence $s=\{0,1\}^n$. Most optimization algorithms though need a differential to work. E.g. going down a Slope

Examples for algorithms that i cannot use: Newton's method, Quasi-Newton method, Finite difference, Approximation theory, and Numerical analysis

However on a cube those do not work. My problem size is $n=20$ and higher, so a breadth first search is out of the question.

What is a working optimization strategy for optimization on a cube? What would be its running time? I hope to get better than just a brute-force optimization that needs me to iterate through all possible combinations.

Edit: Here is my problem fleshed out. I am interested in a theoretical analysis and would like to have - as stated in the question - an algorithm that tackles this along with the runtime analysis.

I have a combination of lightwaves. Each lightwave $L$ has a interaction with all other lightwaves. Meaning there is a relation $REL_{L_i,L_j} = func(Li,Lj)$ matrix. What i can do now is remove lightwaves, to remove interactions between waves. I would like to have the most lightwaves possible, while keeping the sum of the relations low.

The problem turns into a $(0,1)^n$ optimization, where $0$ is exclusion of a lightwave, $1$ is inclusion.

I hope this clarifies the problem up a bit and made sense.

Edit 2: I am optimizing for the term $\sum$ of relations divided by the number of lightwaves since a full pareto optimization would be useful, but impractical to display as a solution. (thanks Tsuyoshi Ito)

• What kind of function are you trying to optimize? We can't give you a reasonable answer without this information. (I'm not the downvoter, but as it stands, this question cannot be answered.) – Peter Shor Sep 10 '12 at 17:08
• The problem is that your question is too general. Pretty much any discrete optimization problem can be phrased as optimization over the cube, but there are wildly different solution strategies depending on the problem – Suresh Venkat Sep 10 '12 at 18:11
• Translated into theoretical computer science lingo, I believe your question is: You have a graph with non-negative edge weights. You want to add as many vertices as possible, while keeping the sum of the edge weights of the induced subgraph small. This is an NP-complete problem in general (there is any easy reduction from maximum independent set), but it might be quite interesting in terms of approximation algorithms. I don't know whether it's been investigated. – Peter Shor Sep 14 '12 at 15:03
• (1) As is stated in Edit 2 in revision 5, you can easily achieve the optimal value 0 by including only one lightwave, so I do not think that the objective function you stated is what you intend. (2) You do not have to keep all the history in the question. Instead, please try to make the question as a whole as readable as possible. Adding more and more “Edit” sections makes the question difficult to read. – Tsuyoshi Ito Sep 14 '12 at 15:32
• the reason there are no upvotes is because we still do not know what the question is. as stated now, the objective is minimized by a single lightwave. maybe an upper bound on the sum of relations should be a constraint? – Sasho Nikolov Sep 14 '12 at 18:30