Тернарный поиск: максимум функции, которая растёт, а потом падает

Если ты умеешь искать максимум унимодальной функции, знаешь, почему поиск по наклону и золотое сечение дешевле тернарного и почему плато всё ломает, листай до «Теперь сам».

Как думаешь, можно ли искать максимум двоичным поиском

Магазин подбирает цену. При цене x товар покупают 1000000 − x раз, выручка x·(1000000 − x). Слишком дешёво - мало денег с покупки, слишком дорого - мало покупок. Где-то посередине максимум.

Массива нет, есть функция, и одно её вычисление дорого: в жизни это может быть запуск симуляции или неделя эксперимента. Двоичный поиск из прошлых уроков требует монотонного признака «да, да, да, нет, нет». Прежде чем читать дальше, ответь себе: какой признак здесь монотонен? Подсказка - он есть, и его не видно, если смотреть на одно значение f.

На что это похоже

Ты в тумане на горном хребте и ищешь вершину. Высоту видно только в точке, где стоишь. Если сделать шаг вперёд и стало выше - вершина впереди, назад можно не смотреть. Если ниже - вершина позади. Одна пара соседних замеров говорит, по какой склон горы ты стоишь. Тернарный поиск ставит двух разведчиков в трети и в двух третях пути и сравнивает их высоты; поиск по наклону ставит одного разведчика и смотрит, куда идёт склон под его ногами.

Механизм: три способа сузить отрезок

f унимодальна на [lo, hi]: строго растёт до вершины, строго падает после

ТЕРНАРНЫЙ: m1 = lo + (hi−lo)/3,  m2 = hi − (hi−lo)/3
    f(m1) < f(m2)  →  вершина правее m1:  lo = m1 + 1
    иначе          →  вершина левее m2:   hi = m2 − 1
    отрезок × 2/3 за шаг, 2 вычисления f за шаг

ПО НАКЛОНУ (целые x): признак «f(m) < f(m+1)» - «ещё растёт»
    он монотонен: да, да, ..., да, нет, нет  - и вершина на границе
    обычный двоичный поиск: отрезок × 1/2 за шаг, 2 вычисления

ЗОЛОТОЕ СЕЧЕНИЕ (вещественные x): точки в долях 0.382 и 0.618
    после сужения одна старая точка попадает ровно на новую долю -
    её значение уже известно: 1 вычисление за шаг, отрезок × 0.618

Почему тернарный поиск верен: пусть f(m1) < f(m2). Если бы вершина была левее m1, то на отрезке [m1, m2] функция бы уже падала, и f(m1) > f(m2). Противоречие - значит, вершина правее m1. Здесь используется СТРОГОСТЬ: при равенстве значений вывода нет.

Почему золотое сечение экономит точку: доля k = 0.618… удовлетворяет k² = 1 − k. Если оставили левую часть длиной k, её точка на доле k от начала совпадает со старой точкой на доле 1 − k = k² от начала исходного отрезка.

Правило

Максимум строго унимодальной функции ищут сужением отрезка. Тернарный поиск сравнивает f в точках 1/3 и 2/3 и выбрасывает треть: около 2·log_{1.5} n ≈ 3.4·log₂ n вычислений. На целых выгоднее двоичный поиск по признаку «f(m) < f(m+1)» - он монотонен, и вершина на его границе: 2·log₂ n вычислений. На вещественных выгоднее золотое сечение: одна новая точка на шаг, отрезок умножается на 0.618. Всем трём нужна строгость: на плато, где f(m1) = f(m2), вывод о направлении сделать нельзя, и вершина может быть выброшена.

Разбор: три поиска на одной функции

Программа ищет максимум выручки x·(1000000 − x) на целых 0..1000000 и максимум −(x − 0.3)² на [0, 1] с точностью 10⁻⁹, считая вычисления функции.

import math

vyzovy = 0


def f(x):                       # выручка от цены x: растёт, потом падает
    global vyzovy
    vyzovy += 1
    return x * (1000000 - x)


def ternarnyj(lo, hi):          # максимум на [lo, hi], целые x
    while hi - lo > 2:
        m1 = lo + (hi - lo) // 3
        m2 = hi - (hi - lo) // 3
        if f(m1) < f(m2):
            lo = m1 + 1         # максимум правее m1
        else:
            hi = m2 - 1         # максимум левее m2
    return max(range(lo, hi + 1), key=f)


def po_naklonu(lo, hi):         # первая точка, где f перестала расти
    while lo < hi:
        m = (lo + hi) // 2
        if f(m) < f(m + 1):
            lo = m + 1
        else:
            hi = m
    return lo


def zolotoe(a, b, eps):         # вещественный x, одна новая точка на шаг
    k = (math.sqrt(5) - 1) / 2  # 0.618...
    x1, x2 = b - k * (b - a), a + k * (b - a)
    f1, f2 = g(x1), g(x2)
    while b - a > eps:
        if f1 < f2:
            a, x1, f1 = x1, x2, f2
            x2 = a + k * (b - a)
            f2 = g(x2)
        else:
            b, x2, f2 = x2, x1, f1
            x1 = b - k * (b - a)
            f1 = g(x1)
    return (a + b) / 2


def g(x):
    global vyzovy
    vyzovy += 1
    return -(x - 0.3) ** 2


def ternarnyj_vesch(a, b, eps):
    while b - a > eps:
        m1, m2 = a + (b - a) / 3, b - (b - a) / 3
        if g(m1) < g(m2):
            a = m1
        else:
            b = m2
    return (a + b) / 2


for imya, poisk in (("тернарный", ternarnyj),
                    ("по наклону", po_naklonu)):
    vyzovy = 0
    x = poisk(0, 1000000)
    print(f"{imya:13} x = {x}, вызовов f: {vyzovy}")
for imya, poisk in (("тернарный", ternarnyj_vesch),
                    ("золотое", zolotoe)):
    vyzovy = 0
    x = poisk(0.0, 1.0, 1e-9)
    print(f"{imya:13} x = {x:.9f}, вызовов g: {vyzovy}")

тернарный     x = 500000, вызовов f: 64
по наклону    x = 500000, вызовов f: 38
тернарный     x = 0.300000000, вызовов g: 104
золотое       x = 0.300000000, вызовов g: 46

Числа совпадают с оценками. На миллионе целых тернарному оценка обещает log_{1.5} 10⁶ ≈ 34 шага; на деле их 30 (сдвиг границ на единицу дорезает отрезок быстрее), по два вычисления, плюс три точки досмотра - 64. Поиску по наклону хватает 19 шагов по два вычисления - 38. На вещественных до точности 10⁻⁹ тернарному нужно 2·log_{1.5} 10⁹ ≈ 102 вычисления, золотому сечению - log_{1.618} 10⁹ ≈ 43 плюс две стартовые точки. Если одно вычисление - это час работы симуляции, разница между 104 и 46 - это два с половиной дня.

Разбор: плато ломает все три

x:     0  1  2  3  4  5  6  7  8
f(x):  1  2  2  2  2  2  2  5  1

функция не убывает, потом не возрастает - но НЕ строго.
тернарный: lo = 0, hi = 8, m1 = 2, m2 = 6
    f(2) = 2,  f(6) = 2  →  «не меньше» → hi = 5
    вершина x = 7 выброшена, ответ 2 - неверен

по наклону: m = 4, f(4) = 2, f(5) = 2 → «не растёт» → hi = 4
    тоже ушли влево от вершины

Ни один из поисков не виноват: по двум равным значениям в середине плато нельзя понять, с какой стороны вершина - справа от плато она может быть, а может и не быть. Если плато бывают только на самой вершине, поиск по наклону остаётся верным (он найдёт начало плато), а вот плато на склоне делает задачу неразрешимой быстрее перебора: противник может спрятать вершину в любую точку за плато.

Что ломается без этого

Тернарный поиск применяют к функции, не проверив унимодальность: у выручки с оптовыми скидками, у времени ответа сервера в зависимости от числа потоков бывает несколько горбов. Поиск честно находит ОДИН из локальных максимумов - и никак не сообщает, что есть выше. Вторая ошибка - целые m1 и m2 без сдвига на единицу (lo = m1 вместо lo = m1 + 1): при hi − lo = 2 выходит (hi − lo)/3 = 0, m1 = lo, m2 = hi, отрезок перестаёт сужаться, и цикл крутится вечно. Поэтому в программе границы сдвигаются за точку, а последние три точки досматриваются перебором. Третья - плато из-за округления: целочисленная функция с делением даёт равные значения на соседних точках там, где у настоящей функции склон.

Зачем это в работе

Подбор одного параметра по дорогой оценке встречается постоянно: размер пачки при загрузке в базу (маленькие пачки - много накладных расходов, большие - память и блокировки), число потоков, таймаут повтора, коэффициент в модели. Если зависимость гладкая и с одним горбом, золотое сечение находит лучший параметр за десятки замеров вместо сотен. Любая выпуклая функция одной переменной (стоимость, которая сначала падает от экономии на масштабе, а потом растёт от перегрузки) унимодальна - и к ней эти поиски применимы без оговорок. И всегда первым вопросом идёт тот же: точно ли горб один?

Теперь сам

Функция на целых 0..100 строго растёт до x = 73, потом строго падает. Сделай первый шаг тернарного поиска и первый шаг поиска по наклону: какие точки сравниваются и какой отрезок остаётся?