I have an expensive-to-evaluate high-dimensional ($n=22$) objective function $f$ that I need to minimize numerically without taking derivatives. The function $f$ can be expressed as a sum of several functions $h_i$. For the sake of simplicity, lets say $n=2$, then we could express $f$ like this, but note there are many more variables and also more than two $h$-functions: $$ f(x,y) = h_1(x) + h_2(x,y)$$ The $h_i$ have a strictly positive value set, and $h_2 < h_1$ usually holds. EDIT: more details at [1] down below.
I believe this structure of $f$ to be highly exploitable for optimization because conceptually I could do two things:
- compute $h_1(x)$ to figure out which $x$-values are sensible
- get several evaluations for $f$ out of one evaluation of $h_1$, only recomputing $h_2$
My previous attempts to optimize the function are a black-box-approach: only passing $f$ to a quality radial-basis-function-optimizer without using the hierarchical structure explained above. However, this converges very slowly, wasting lots of time with terrible $x$-values.
Is there an Optimization-Algorithm that allows me to exploit this known hierarchical structure? Alternatively, just finding out if this kind of problem has a name would probably already help greatly.
EDIT
what I need: I am looking for ideas and heuristics on algorithms. I have compared several, but they all seem to assume I can only evaluate one objective function $f$.
[1] the functions: $h_1$ tends to have plateaus of low value, not sharp valleys, and the choice of $x$ matters for computing $h_2$ which can not be facorized into $x$ and $y$ contributions (in any way that I know of). It is true that if $(x_0, y_0)$ minimizes $f$, then $h_1(x_0)$ must be a low value, but it does not have to be the minimum of $h_1$, just close to it.
answering the commenters:
- "function has a single global minimum?" -> This is a problem from engineering, it is not important if I find 'the' global minimum or just a very good solution. That being said, all input variables are bounded so suppose a global minimum should exist.
- "known upper bounds on the values of the summed functions?" -> There are and I could calculate them, though it would be much easier to estimate them.
- "more worthwile to find a tiny delta to x than a big delta to y" -> I do not have a way to calculate $h_i(x+\delta)$ from $h_i(x)$ no matter the size of the $\delta$, it is always a full recompute. Also, I very much do care about $y$, $h_2$ can not be neglected and only $(x,y)$ is a real solution to the problem.
- "doing this as a series of 1D optimizations" -> This is computationally efficient, but the solution quality will drop. The problem is that in regions where $h_1$ is low and relatively flat, I can not just pick the minimum of $h_1$ as that will constrain $h_2$ too much.