Mathematica: minimize black box function

[noon0788]

I have a user-defined function that doesn't seem to work with NMinimum, FindMinimum, or any of the other optimization commands. I think this is due to the fact that the function uses elliptic integrals and matricies to obtain an output. It has multiple variables, but I want to keep them all constant and minimize one. Does anyone know how to minimize ANY function? We'll just treat it as a black box, receiving inputs and producing outputs.

Oh, and also, the domain of the function is constricted. I don't know how to calculate the domain of the function either.

I've tried using a gradient search method already. I find the gradient at a point by calculating two points and doing it the old-fashioned way. Then I subtract the gradient from its point to get a new point. I keep searching this way until the gradient is relatively small (.000001). However, the code breaks a good deal because when the gradient is extremely large, this sends the calculated, new point out of the function's domain, and everything goes haywire.

Any thoughts? If there was simply a way to determine the function's domain that would be helpful too. Thanks!

 

[Bill Simpson]

When one person needed to minimize a very inconvenient function over an irregular domain I suggested he evaluate the function over a few thousand or a few tens of thousands of points and use the locations of a few dozen of the smallest values as starting points. That should help you minimize ANY function, as long as the domain is bounded.

I seem to remember someone having a very tricky method of determining function domains but I can't seem to locate that at the moment. Barring that I would suggest you look at denominators within your function as a starting place. Denominators being zero should bound your domain. If you are also using built-in functions or other functions that you have created and you are perhaps expecting real valued results then you might consider boundary cases for this, Sqrt[x] is going to be bounded below by zero if you are expecting real results, for example. Beyond that it is difficult to say without any more information about the space of all possible multivariate functions.

 

[aTn]

Here are my 2 cents.

Short answer

NMinimize and FindMinimum don't work with "black-box" functions. The only Mathematica package I know that supports this is Global Optimization for Mathematica.

Long answer

1. Using finite differences to approximate derivatives can lead to disastrous results. I suggest reading a bit on the subject. Any book on numerical optimization covers this subject (e.g. Nocedal, Wright, Numerical Optimization or Biegler, Nonlinear Programming Concepts, Algorithms and Applications to Chemical Engineering).

2. Is your problem unconstrained ? If NOT, then I suggest reading a bit about (e.g. first order) optimality conditions since they do not boil down to asking that the objective function's gradient be zero at a local minimum but rather that (under certain conditions) the objective function's gradient be a linear combination of the constraint gradients. There are also higher order conditions.

3. Mathematica is notoriously lacking when it comes to numerical optimization.

For smooth problems where the objective function and constraints are given in closed form (i.e. via algebraic formulas not involving derivatives, integrals, etc.), I suggest using the AMPL or GAMS platforms and their associated algorithms or open-source algorithms (e.g. see COIN-OR project).

For problems where derivatives of the objective function and constraints don't exist or are not available (e.g. "black box" functions) and where the total number of variables does not exceeed about 100, I suggest considering derivative free optimization (DFO). Numerous open-source DFO codes are available on the internet; for example, simulated annealing, coordinate search (e.g. NOMAD), DFO trust region algorithms, etc.

If you have more time, you may want to couple a differential equation solver (DES) (to compute your integrals) with an optimizer. The DES may pass derivative information to the optimizer.

 

[aTn]

When one person needed to minimize a very inconvenient function over an irregular domain I suggested he evaluate the function over a few thousand or a few tens of thousands of points and use the locations of a few dozen of the smallest values as starting points. That should help you minimize ANY function, as long as the domain is bounded.

What if every function evaluation takes 10 seconds or more ?

This "multi-start" approach is good only as a first rough test in the case of inexpensive function evaluations (in terms of calculation times), but it is rather slow and will fail on many problems.

 

[fyzxfreak]

I've also recently come across the need for black-box optimization. I have some function f[a0, a1, ... an] that I've defined using the delayed notation ":=" (because it consists of numerical integrals that take a couple of seconds each to compute) and I want to minimize it in respect to a0, a1, ... an.
I was wondering if I can do this using some special method (with some evaluation control or something), because grinding out the integrals for each point in the parameter space (with n=5, say) would take quite a while. I'm assuming that directly doing the minimization would be much faster.

 

[aTn]

There are numerous algorithms available for black box optimization (or derivative free optimization as mathematicians and operations research experts call them).

I strongly suggest looking at the following presentation.

http://egon.cheme.cmu.edu/ewocp/docs/SahinidisEWO_DFO2010.pdf

It will give you a good idea of the tools available and their performance on benchmark examples.