How can I optimize a function on a non-linear set with unknown points?

[Kreizhn]

Hey all,

I'm doing some research on computing optimal controls in quantum mechanics, and need a numerical algorithm that I can try to adapt to my problem. I'm hoping that if I describe the problem, someone out there can point me in a good direction.

Consider a function f: \mathbb R^n \to \mathbb R and let S=f^{-1}(0). I want to find
\min_{\vec x \in S} \| x \|_2
While we do not have any theoretical results of yet proving this, we empirically believe that S is countable and hence totally disconnected. Furthermore, within a finite radius of the origin, we believe that S is actually finite (and hence this could be seen as a combinatorial optimization problem).

Now I can find a single point in S, but the goal is to minimize the norm without knowing where the other points in S lie. I've been looking into constrained discrete simulated annealing and superficially at level set optimization, but I'm not sure if there's a better way. If anyone knows of an algorithm that is designed to handle this (or something similar) it would be much appreciated.

 

[Hurkyl]

The qualitative properties of f matter a lot; there's pretty much nothing you can do when f is a completely arbitrary function.

e.g. Is f smooth? Piecewise smooth? Does it have a bounded derivative?

 

[Kreizhn]

Sorry, should have included that. The problem is that the function doesn't just depend on x. It depends on many other things that are also allowed to vary (even the dimension of the domain). For our purposes we can hold those other things constant, but they tend to change the qualitative properties a lot making it hard to stipulate general characteristics.

In general the function is only continuous, and S actually represents all points where the gradient is not defined. Hence the derivative is not bounded.

However, we do not think f ever actually attains a value in S, but rather just comes arbitrarily close in infimum. The derivative is still not bounded but the function in this case is smooth. This is fine since numerically, we can only operate to within machine precision and in fact, we are satisfied with approximations far less accurate than that. That is, for \epsilon>0 sufficiently small we can take S = f^{-1}(\epsilon). This set would have non-zero measure by continuity, but then quotient out connected components to make this a discrete problem again.

I hope that helps a bit. In general, assume that

f is bounded above and below (by zero)
f is smooth
[STRIKE]f does not have bounded derivative.[/STRIKE]
f is highly oscillatory (making local extrema populous)
f is "sharply peaked" around extrema

Edit: Actually, the derivative might be bounded, but this would be a very hard result to show. I'll have to think about it a bit more.