Constrained black box optimization by iterative refinement

44 Views Asked by At

First of all, horrible title. If anyone finds a better title, please edit. I don't even know what part of mathematics this question is about, so I need some guidance. I've chosen optimization but I don't know.

First: the function is a black box. I have to run a computer program for each combination. (What I think) My problem is finding all possible combinations and a way to walk through them with some order. But the function is continous and I don't need much precission.

Now, imagine I had two variables $x$ and $y$, and the only limitation being $x + y = 1$. If I wanted to see all the possibilities (by hand) I could roughly calculate: $f(1,0)$, $f(.9,.1)$, $f(.8,.2)$, $f(.7,.3)$, $f(.6,.4)$, $f(.5,.5)$, $f(.4,.6)$, $f(.3,.7)$, $f(.2,.8)$, $f(.1,.9)$, $f(0,1)$. And that way I can (roughly) find the best proportion to optimize the function. If I needed more info around one of those values, I could check for example from $f(.20,.80)$ to $f(.30,.70)$ in ten steps and get a finer result.

Now my problem is that I know how to do it with two variables, but I'm interested in seeing some ideas of how to approach when I have 6 variables! I have $x_1$, $x_2$, $x_3$, $x_4$, $x_5$, $x_6$, and the limitation is again that $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 1.$$

What is the way to solve this? What would be the way to approach those many many many different proportions? (e.g, $(1,0,0,0,0,0)$, $(.8,.1,0,0,.1,0)$, etc.)


Understand that I don't know much about math so please if you could help in any way to make this question better, and more useful, that would be great; feel free to add or edit.

2

There are 2 best solutions below

3
On

You could simulate some kind of 'hill-climbing'. Start at some random point. Then, given some point $(x_1,x_2,x_3,x_4,x_5,x_6)$ that you are 'at', picking two variables, add a tiny bit (e.g. $0.01$) to one while subtracting that from the other, and see how much the function increases or decreases. Do this for all possible pairs of variables (${6 \choose 2} = 15$ ... which is not too many) and then pick the pair that gave the largest increase. Lather, rinse, repeat.

Of course, that method can quickly lead to some kind of local maximum, so another method might be some evolutionary algorithm: randomly pick, say, $20$ points, compute the function, and then slightly mutate the best ones to get a new population of $20$ points (maybe throw in a completely different point once and a while). Lather, rinse, repeat.

0
On

Unless your function has some nice property, such as Lipschitz continuity, you should not expect to find the optimal solution. With Lipschitz continuity, there are many results in global optimization such as this simple algorithm.