I've come across a rather unusual (at least to me) optimization problem. That problem is this:
Given a blackbox function $f(\mathbf{x})$ (meaning we can only evaluate it at given points - can't derive a gradient) and a starting $D$-dimensional vector $\mathbf{x}_0$ such that $f(\mathbf{x}_0)>c$ (where c is some given threshold value), find the shortest vector $\mathbf{b}^*$ such that $f(\mathbf{x}_0+\mathbf{b}^*)\leq c$
My idea was to grow a sphere out from $\mathbf{x}_0$ and sample points on that sphere. Then take the first point that yields a value below our threshold. The problem with this is the surface of the sphere grows with exponent $D$. The consequence of that is it finds solutions that have high norms.
I expect a good solution would take into account the evaluations of $f(\cdot)$ and use that to determine where to search next. I'd like to be able to frame this as something that can be plugged into some optimization packages.
Any intelligence is appreciated! Thank you