[WeaselNo7]

I don't speak fluent maths, but i'm extremely interested. Is anyone in a position to explain what the initial equation for U(x) means? I'll be in your debt forever!

[contravariant]

A Lipschitz function is one that doesn't change to quickly, such that the difference between two values |f(x) - f(y)| is at most as large as the distance between x and y times a constant k i.e. |f(x) - f(y)| <= k|x-y|. In particular this implies that:

f(x) - f(y) <= k|x-y|

hence

f(x) <= f(y) + k|x-y|.

Therefore the function:

u(x) = f(y) + k|x-y|

is an upper bound for the function f(x). Repeating this for multiple points x1, x2, x3,... you can construct a stricter upper bound by taking the minimum:

U(x) = min_i f(xi) + k|x - xi|

[WeaselNo7]

Wonderful answer, very intuitive, thank you so much!

[sp332]

U(x) starts by evaluating f(x), but instead of checking for every value of x, it only checks certain values x1, x2, x3... xt. Then U(x) gives an upper bound for what f(x) might be for any x between the ones you actually calculated. Take the difference between any x and the nearest xi for which you know f(xi), and multiply it by the maximum possible slope. Add that to f(xi), and you have the upper bound for how high f(x) might be.

[WeaselNo7]

Much appreciated!

[math_and_stuff]

Consider the case where f is an elementary function of one variable and you know that its slope between any two points is at most k and at least -k. And suppose you want an upper bound on f(0) but you know the values of f(-2) and f(3). Then f(0) <= f(-2) + 2 * k and f(0) <= f(3) + 3 * k. Taking the minimum of these two right-hand sides leads to a formula analogous to the one for U(x) that you're asking about (with the norm || x - x_i || taking the place of |0 - (-2)| and |0 - 3| in our example).

[WeaselNo7]

Very kind, thank you for the explanation!

[enriquto]

if you can program, you can read maths (understanding its purpose is a different issue)

this formula defines a function U(x). This means that it gives a recipe that takes a number x and produces a number U(x). The recipe depends on an already prepared set of ingredients: a set of numbers x1, x2, ..., xt, k, and another function f. Now, given a number x, to compute U(x), you first compute all the numbers f(xi)-k*|x-xi|, and then you pick the smallest one. This smallest value is then U(x).

The graph below the formula displays its interpretation. The graph of the function f is the red curve, the points (xi, f(xi)) are the black dots, and U(x) is in green.

[WeaselNo7]

Wonderful, thank you!

[bumbledraven]

The doc uses x to refer to the new point, and x_i for the ith previously evaluated point. To reduce ambiguity, i'll use a capital X to refer to the new point.

The equation says that U(X) is equal to the minimum value of the expression f(x_i) + k * (Euclidean distance from x to x_i), where i ranges over integers 1 to t.

In Go pseudo-code:

  func U(X []float64, x [][]float64, f func([]float64) float64, k float64) float64 {
    min := math.Inf(1)
    for _, x_i := range x {
      e := f(x_i) + k * EuclideanDistance(X, x_i)
      if e < min {
        min := e
      }
    }
    return min
  }