Hello everyone. Today I would like to introduce you to a new technique — ternary search on non-unimodal functions. I came up with it during ROI 2024 and it helped me to become a prize winner.

The motivation

There are many examples in CP where we need to maximise or minimise the value of some function $$$f$$$. If the function is unimodal, there is no problem using ternary search. But if it's not, there's nothing to do. Of course, if $$$f$$$ is random, we should check all its values. Fortunately, intuition tells us that if the function is often close to unimodal, we can also use ternary search on a large part of its area of definition.

The intuition

Consider the unimodal function $$$0.03x^2$$$ after adding some noise ($$$sin (x)$$$) to it:

Intuition suggests that if the noise is not strong, we can still use a ternary search away from the global minimum.

In this example, we can put it more formally — the derivative of the function is $$$0.06x + cos(x)$$$, and when $$$|x| > \frac{1}{0.06} \approx 16.67$$$, adding cosine does not change the sign of the derivative.

The first optimisation

So, the first idea is to run the ternary search using not while (r - l > eps) but while (r - l > C) and then bruteforce all values between $$$l$$$ and $$$r$$$ with some precision. In many cases when $$$f$$$ takes an integer argument there will be no precision issue at all.

The second optimisation

I should mention this blog. It tells us a similar idea of splitting all argument values into blocks and applying ternary search on them.

This is the only thing related to the blog that I found. I tried googling and asking people involved in CP, but none of them knew about it before.

Testing

The function from the example is boring, so consider a more interesting function: Weierstrass function

We zoom in and find that the maximum is about $$$1.1628$$$

We will search for maximum on the interval (-1, 1).

#include <bits/stdc++.h>
#define M_PI 3.14159265358979323846
using namespace std;
#define ld long double
ld Weierstrass(ld x) {
    ld y = 0;
    for (int i = 0; i < 30; i++) y += pow(0.14, i) * cos(pow(51, i) * M_PI * x);
    return y;
}
ld Classical_ternary(ld f(ld), ld l = -1, ld r = 1, ld eps = 1e-7) {
    while (r - l > eps) {
        ld midl = l + (r - l) / 3;
        ld midr = r - (r - l) / 3;
        if (f(midl) > f(midr)) r = midl;
        else l = midl;
    }
    return f(l);
}
int main() {
    cout << Classical_ternary(Weierstrass) << endl;
}

This gives us $$$1.07203$$$. Let's split arguments into blocks. Since the arguments are real, in fact we are not going to split them explicitly into blocks, we will take the minimum in some range near the argument.

ld Blocks(ld f(ld), ld l = -1, ld r = 1, ld eps = 1e-7) {
    int cnt_blocks = 20000;
    while (r - l > eps) {
        ld midl = l + (r - l) / 3;
        ld midr = r - (r - l) / 3;
        ld vall = 2e9, valr = 2e9;
        for (ld x = midl; x < midl + 1.0 / cnt_blocks; x += eps) vall = min(vall, f(x));
        for (ld x = midr; x < midr + 1.0 / cnt_blocks; x += eps) valr = min(valr, f(x));
        if (vall > valr) r = midl;
        else l = midl;
    }
    return f(l);
}

It gives $$$1.07228$$$, $$$1.07245$$$, $$$1.07457$$$, $$$1.07203$$$ with block number = $$$2e4$$$, $$$2e5$$$, $$$2e6$$$, $$$2e7$$$, respectively. Not a good improvement, and somehow the result for the maximum number of blocks is the worst.