Algorithm to optimize multiple variables more efficiently than trial-and-error

Question

Google's results on this seem to require more advanced maths than I'm familiar with (and I might not be smarter than a fifth grader, but I don't intend to find out).

I'm looking for a general way to solve multivariate optimization problems, preferably in c#, without having to dig into matrices and eigenvectors and normal distributions.

Say I have numeric variables x, y, z, and w, and function f such that w = f(x, y, z). I want to maximize w, and...

• f is unknown
• Codependency between x, y and/or z, if any, is unknown
• In some cases I only have post-hoc data sets
• In other cases I can vary x, y and z and resample w on-demand
• In the a-priori cases, the ideal algorithm maximizes w with the fewest trial permutations of x, y, and z, and chooses the next value for each after every round of sampling

I have rough minimum and maximum bounds for the independent variables. I of course don't want to sample any more of the permutation space than necessary. I'd like the algorithm to have at least a crude ability to detect the most glaring co-dependencies, e.g., diminishing returns when x > 2y, or actual deterioration in w when the sum of x, y, and z exceeds some ceiling, etc.

Most of the math libraries I've looked at assume I know how to perform quantum nergenflip projections over the Boigenfoodle Continuum, and I'm just not there. How would a non-mathematician coder accomplish this?

Answer 1

If you can sample f, you can do some hill climbing. Start at an arbitrary position (x,y,z). Sample f at (x,y,z) and (x+delta,y,z). If it is better at the latter, move there. If not, try some smaller deltas. Also try negative deltas, and deltas on the other two coordinates. When no delta gives you an increase in f, you've reached a maximum.

Note that this will only give you a local maximum, not necessarily a global one. It is also very numerically unstable if your delta is too small.

You can do much better if you know something about f, like if it is a low-degree polynomial in x,y,z. Then you can do a least-squares fit for the coefficients and then maximize the polynomial by setting derivatives equal to zero.

Answer 2

It looks like you can get an implementation of the Nelder-Mead Simplex optimization algorithm for C# from http://www.dotnumerics.com/NumericalLibraries/Optimization/Default.aspx. With this method all you have to do is to give it something that can evaluate the function to be optimized at arbitratry points. It's nothing like as efficient as methods that require derivatives, and in fact it isn't even as mathematically respectable as the Torczon Simplex variant - but people do use it, and I can't find a free Torczon Simplex implementation for C#.

Answer 3

You can try simulated annealing if you don't want to get stuck in the local minima.

Basically, start with some x,y,z. Generate dx, dy and dz randomly from a zero mean distribution (normal or gaussian distribution). If w(x+dx,y+dy,z+dz) > w(x,y,z) then select this new solution. Otherwise select it probability w(x+dx,y+dy,z+dz)/w(x,y,z).

Python code

def simAnneal( w, seed_x, numSteps=100000, sigma=0.01 ):
    optimal_x = [i for i in seed_x]
    optimal_w = w(optimal_x)

    cur_w = w(seed_x)

    for i in range(numSteps):
        new_x = [i+random.gauss(0, sigma) for i in seed_x]
        new_w = w(new_x)

        if (new_w > cur_w) or (random.random() > new_w / cur_w) :
            cur_x = new_x
            cur_w = new_w
            if cur_w > optimal_w:
                optimal_w = cur_w
                optimal_x = cur_x
    return optimal_x