Absolutely. Adding to the list, SIMPLE [1] was recently trending on HN [2]. It looks very applicable to hyperparameter optimization.

[1] https://github.com/chrisstroemel/Simple

[2] https://news.ycombinator.com/item?id=16241659

Glad to see someone posted about COIR-OR!

I've been looking at open source solvers for a while now to solve an MIP, and this one seems to be the best.

There is this annoying thing about the whole ecosystem though, aside from the proprietary bits.

I started by looking at GLPK and wrote my MIP in GMPL. For some reason a lot of tools I looked at don't "just work". I have to export it to some other format. It works, but feels like a work-around.

I wish there were a lingua franca in this domain and sort of have support from all major solver implementations, but each one seems to have their own way, or just provide an API (ehem google/or-tools)

I am happy I can make it work, but it may not be as easy for others.

Speaking of optimization libraries, I've been checking out https://developers.google.com/optimization/ for scheduling and assignment problems. The documentation is not... wonderful, but it has a lot of examples and a decent Python API.

I recently did an "Intro to OR" class and most of the tools we used were proprietary. I've been looking for more open source tools (and more info on OR in general, I think it's fascinating!).

Edit: NLOpt (https://nlopt.readthedocs.io/en/latest/) is also a nice suite of optimization algorithms for non-linear optimization.

Thanks for sharing this!

Dlib saved me a few times and I have a lot to thank David.

However I just wish it's Python binding were published as binary wheels. Dlib is very large and the compilation times suck when installing from pip.

In fact, I might as well contact him and help setup this!

Yes indeed! (to this stuff being around a while) And then what it can do is a subset of the interval toolkit (also around a while). Somehow I get the idea that interval methods are underappreciated and thus lesser known - it seems anecdotally that people hear of the outward rounding bounds growth problem and go no further. (maybe evaluation efficiency compared to floats is the other gripe)

About Lipschitz interval methods, as stated here (first googled example, this from 2001): https://link.springer.com/referenceworkentry/10.1007%2F0-306...

"Interval algorithms for constrained and unconstrained optimization are based on adaptive, exhaustive search of the domain. Their overall structure is virtually identical to Lipschitz optimization as in [4], since interval evaluations of an objective function ϕ over an interval vector x correspond to estimation of the range of ϕ over x with Lipschitz constants. However, there are additional opportunities for acceleration of the process with interval algorithms, and use of outwardly rounded interval arithmetic gives the computations the rigor of a mathematical proof."

I'm also curious what this adds that's new. I'll add one other bit: If anyone ever claims they have an efficient global optimization algorithm for continuous optimization, ask whether or not P=NP. We can encode the integer constraint that x \in {0,1} as x(x-1)=0, so if we can find the global optimum to a continuous problem efficiently, then we can do the same for a discrete. That's probably unlikely, so I'm always a bit skeptical.

By the way, the parent mentioned interval arithmetic. If anyone is looking for optimization algorithm look for "interval Newton". It's a cool algorithm.

Quoting from the linked-to page:

> However, if you want to use LIPO in practice there are some issues that need to be addressed. The rest of this blog post discusses these issues and how the dlib implementation addresses them. First, if f(x) is noisy or discontinuous even a little it's not going to work reliably since k will be infinity.

> ... Now each sample from f(x) has its own noise term, σi, which should be 0 most of the time unless xi is really close to a discontinuity or there is some stochasticity.

Is that not what you were pointing out?

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|

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.

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).

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.

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
  }