<p>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</p>

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

<p>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. </p>

<p>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. </p>

<p><strong>Edit</strong>:
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. </p>

<p>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. </p>

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

<p>I hope this clarifies the problem up a bit and made sense. </p>

<p><strong>Edit 2</strong>:
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)</p>

CC BY-SA 3.0
2012-09-10T14:39:59.073Z
reason for downvote?
tarrasch
CC BY-SA 3.0
2012-09-10T17:08:34.860Z
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 
CC BY-SA 3.0
2012-09-10T18:11:00.363Z
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
CC BY-SA 3.0
2012-09-10T18:54:17.910Z
recently it occurred to me wrt another question there is probably a fairly natural extension/simplification of [powells method](http://en.wikipedia.org/wiki/Powell%27s_method) over a single fixed-width binary vector, where each bit value is considered a component of the vector, but have not seen it written up anywhere-- anyone else? part of the point/advantage of powells method is that it doesnt need to evaluate derivatives (it basically numerically estimates them on its own).
vzn
CC BY-SA 3.0
2012-09-11T06:26:34.040Z
ok, i will elaborate my problem a bit more. i was hoping for some general approaches that i could then flesh out.
tarrasch
CC BY-SA 3.0
2012-09-11T14:29:26.027Z
The only _general_ approach is the brute-force algorithm.  This informal statement can be formulated and proved in terms of query complexity.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-14T14:28:28.180Z
In the edit in revision 3, you stated _two_ objective functions: maximizing the number of lightwaves and minimizing the sum of the relations.  Clearly these two objective functions cannot be optimized simultaneously in general.  What do you exactly want?  Is one of the two criteria a constraint instead of an objective function (such as “maximize the number of lightwaves so that the sum of the relations is at most 10”)?  (more)
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-14T14:29:01.567Z
(cont’d)  Or is there a function which defines the trade-off you want (such as “maximize the number of lightwaves minus the sum of the relations”)?  Or do you want to know all non-dominated solutions in the [multi-objective optimization](http://en.wikipedia.org/wiki/Multi-objective_optimization) sense?
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-14T14:42:15.227Z
i think i am combining the two objectives in my summarizing equation by just doing \sum/#lightwaves
tarrasch
CC BY-SA 3.0
2012-09-14T15:03:00.587Z
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 
CC BY-SA 3.0
2012-09-14T15:32:33.773Z
(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
CC BY-SA 3.0
2012-09-14T15:34:48.670Z
This has the flavor of a sparsest subgraph problem. but the standard sparsest X problems are usually minimizing the cut size.
Suresh Venkat
CC BY-SA 3.0
2012-09-14T15:36:04.217Z
tarrasch, like the question & think theres a heuristic, a generalization of powells method as I write above, & would like to write it up here. but unf there is controversy on TCS.se about [whether heuristics are part of TCS or the TCS.se scope](http://meta.cstheory.stackexchange.com/questions/73/which-metaheuristic-methods-are-admissible-for-discussion) [hence maybe the reason you still have no votes on this question]. so fyi maybe you will get more receptive audience/response on [computational science](http://scicomp.stackexchange.com/) or [cross validated](http://stats.stackexchange.com/)
vzn
CC BY-SA 3.0
2012-09-14T18:30:42.353Z
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
CC BY-SA 3.0
2012-09-14T21:55:29.963Z
tarrasch didnt really specify the cost function very well in the writeup above it seems, and maybe he can figure out how to better/formally describe it ("_func_" is not defined), & am somewhat interested in exactly what it is also, but meantime, thats part of the point of heuristic methods-- they treat the cost function as a "black box" thats left up to the practitioner to get right.. a feature, not a bug..
vzn
CC BY-SA 3.0
2012-09-15T12:49:25.823Z
The exact cost function **doesn't matter**. When you're faced with a question like this in real life, often what you want to do is find the trade-off curve—the whole range of possible (lightwave, interaction) pairs. Since this is NP-complete, all you can hope to do is approximate this curve. Nearly *any* algorithm giving an approximate solution to some version of this problem can be used to approximate the trade-off curve, using interpolation and binary search. For example, fixing the number of lightwaves, approximately optimize the interaction strength, or vice versa, would be useful answers.
Peter Shor 
CC BY-SA 3.0
2012-09-15T16:46:22.700Z
are we saying the same thing? ps clarification, basically its NP complete if the cost function can be computed in P right? which reminds me of the thm that characterizes NP via certificates etc. but also note different algorithms are empirically better suited depending on the exact nature of the cost fn & possible bias in statistical distribution of the data/optimum(s).
vzn
CC BY-SA 3.0
2012-09-15T18:18:22.687Z
@vzn: I'm saying there are some cost functions which are NP-complete; I can't show that every one is, but it wouldn't surprise me.
Peter Shor 
CC BY-SA 3.0
2012-09-16T18:27:24.350Z
@peter, ok, think there are some related nonobvious (research?) questions raised here which havent seen treated sytematically. maybe there is some general view. the search space has a complexity (due to its "size"), the cost function has a complexity, and finding the global optimum has a complexity, and overall complexity is a combination of the 3... many probs seem to be able to be broken down in this "pattern". & seems fair to say that sometimes the cost fn or search space complexity alone could be high & push the problem out of NP complete etc...
vzn
<ds.algorithms><optimization><simplex>
Optimizing along a cube $s=\{0,1\}^n$
tarrasch
# Optimizing along a cube $s=\{0,1\}^n$

(Asked by: username_0 on 2012-09-10)

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

**Tags:** ds.algorithms, optimization, simplex

> **Comments:**
> **username_0**: reason for downvote?  
> **username_1**: 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.)  
> **username_2**: 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  
> **username_3**: recently it occurred to me wrt another question there is probably a fairly natural extension/simplification of [powells method](http://en.wikipedia.org/wiki/Powell%27s_method) over a single fixed-width binary vector, where each bit value is considered a component of the vector, but have not seen it written up anywhere-- anyone else? part of the point/advantage of powells method is that it doesnt need to evaluate derivatives (it basically numerically estimates them on its own).  
> **username_0**: ok, i will elaborate my problem a bit more. i was hoping for some general approaches that i could then flesh out.  
> **username_4**: The only _general_ approach is the brute-force algorithm.  This informal statement can be formulated and proved in terms of query complexity.  
> **username_4**: In the edit in revision 3, you stated _two_ objective functions: maximizing the number of lightwaves and minimizing the sum of the relations.  Clearly these two objective functions cannot be optimized simultaneously in general.  What do you exactly want?  Is one of the two criteria a constraint instead of an objective function (such as “maximize the number of lightwaves so that the sum of the relations is at most 10”)?  (more)  
> **username_4**: (cont’d)  Or is there a function which defines the trade-off you want (such as “maximize the number of lightwaves minus the sum of the relations”)?  Or do you want to know all non-dominated solutions in the [multi-objective optimization](http://en.wikipedia.org/wiki/Multi-objective_optimization) sense?  
> **username_0**: i think i am combining the two objectives in my summarizing equation by just doing \sum/#lightwaves  
> **username_1**: 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.  
> **username_4**: (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.  
> **username_2**: This has the flavor of a sparsest subgraph problem. but the standard sparsest X problems are usually minimizing the cut size.  
> **username_3**: username_0, like the question & think theres a heuristic, a generalization of powells method as I write above, & would like to write it up here. but unf there is controversy on TCS.se about [whether heuristics are part of TCS or the TCS.se scope](http://meta.cstheory.stackexchange.com/questions/73/which-metaheuristic-methods-are-admissible-for-discussion) [hence maybe the reason you still have no votes on this question]. so fyi maybe you will get more receptive audience/response on [computational science](http://scicomp.stackexchange.com/) or [cross validated](http://stats.stackexchange.com/)  
> **username_5**: 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?  
> **username_3**: username_0 didnt really specify the cost function very well in the writeup above it seems, and maybe he can figure out how to better/formally describe it ("_func_" is not defined), & am somewhat interested in exactly what it is also, but meantime, thats part of the point of heuristic methods-- they treat the cost function as a "black box" thats left up to the practitioner to get right.. a feature, not a bug..  
> **username_1**: The exact cost function **doesn't matter**. When you're faced with a question like this in real life, often what you want to do is find the trade-off curve—the whole range of possible (lightwave, interaction) pairs. Since this is NP-complete, all you can hope to do is approximate this curve. Nearly *any* algorithm giving an approximate solution to some version of this problem can be used to approximate the trade-off curve, using interpolation and binary search. For example, fixing the number of lightwaves, approximately optimize the interaction strength, or vice versa, would be useful answers.  
> **username_3**: are we saying the same thing? ps clarification, basically its NP complete if the cost function can be computed in P right? which reminds me of the thm that characterizes NP via certificates etc. but also note different algorithms are empirically better suited depending on the exact nature of the cost fn & possible bias in statistical distribution of the data/optimum(s).  
> **username_1**: @username_3: I'm saying there are some cost functions which are NP-complete; I can't show that every one is, but it wouldn't surprise me.  
> **username_3**: @peter, ok, think there are some related nonobvious (research?) questions raised here which havent seen treated sytematically. maybe there is some general view. the search space has a complexity (due to its "size"), the cost function has a complexity, and finding the global optimum has a complexity, and overall complexity is a combination of the 3... many probs seem to be able to be broken down in this "pattern". & seems fair to say that sometimes the cost fn or search space complexity alone could be high & push the problem out of NP complete etc...  

---

## 0 answers

