Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Minimization on level sets

  1. Jul 23, 2010 #1
    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 [itex] f: \mathbb R^n \to \mathbb R [/itex] and let [itex] S=f^{-1}(0) [/itex]. I want to find
    [tex] \min_{\vec x \in S} \| x \|_2 [/tex]
    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.
  2. jcsd
  3. Jul 23, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
  4. Jul 23, 2010 #3
    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 [itex] \epsilon>0 [/itex] sufficiently small we can take [itex] S = f^{-1}(\epsilon) [/itex]. 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.
    Last edited: Jul 23, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook