Все формулы РФ

Математика / Начала анализа

Тернарный поиск минимума непрерывной унимодальной функции

Тернарный поиск сравнивает функцию в двух точках, делящих интервал на трети. При унимодальности одно сравнение позволяет удалить крайнюю треть и сохранить интервал, содержащий минимум.

Опубликовано: Обновлено:

Оптимизация и исследование операцийЧисленные методыМатематический анализСтраницы с задачами и решениямиЕсть историческая справка

Формула

$$u=a+\frac{b-a}{3},\quad v=b-\frac{b-a}{3},\quad [a,b]\leftarrow\begin{cases}\left[u,b\right],&f(u)>f(v),\\\left[a,v\right],&f(u)\le f(v),\end{cases}\quad L_n=(2/3)^nL_0$$
Схема Тернарный поиск: две крайние трети
Тернарный поиск: две крайние третиТернарный поиск: две крайние трети[0; 9] → u = 3, v = 6 → f: 2 и 17[0; 6] → u = 2, v = 4 → f: 1 и 5[0; 4] содержит минимум x = 2Длины: 9 → 6 → 4

На каждом из показанных шагов отбрасывается правая треть.

Обозначения

$a,b$
концы интервала, единица аргумента
$u,v$
точки на одной и двух третях интервала, единица аргумента
$L_n$
длина после n обычных сокращений, единица аргумента
$f$
целевая функция, единица результата

Условия применения

Рассматривается непрерывная функция, строго убывающая до минимума и строго возрастающая после него. Сравнения выполняются без ошибки, меняющей их порядок. В этой записи аргумент вещественный: правила завершения дискретного поиска по индексам требуют отдельной обработки оставшихся целых точек.

Ограничения

На плоских участках с последующим новым спадом обычное правило равенства может удалить лучший минимум, поэтому одной слабой монотонности недостаточно. Схема обычно требует два свежих вычисления за шаг. При шуме близкие значения нельзя уверенно упорядочить; фиксированное число шагов не устраняет ошибку данных.

Подробное объяснение

Название связано с тремя частями интервала, но после сравнения обычно сохраняются две из них. Если f(u) больше f(v), минимум не расположен в левой трети: строго убывающая ветвь должна продолжаться хотя бы до более низкого правого значения. При противоположном сравнении удаляется правая треть.

При точном равенстве внутренних значений строгая унимодальность помещает минимум между u и v. Можно сохранить только центральную треть. Приведённая единообразная версия оставляет [a,v], что тоже безопасно, но сокращает интервал лишь в отношении 2/3. Поэтому формула длины относится именно к этой версии алгоритма.

После n обычных шагов Lₙ = (2/3)ⁿL₀. Оценку числа шагов получают логарифмированием, не забывая, что ln(2/3) отрицателен. Для заданной ошибки середины ε достаточно Lₙ ≤ 2ε. Проверка ближайшего целого числа подстановкой надёжнее округления логарифма на границе.

У золотого сечения внутренние точки выбирают так, чтобы одна из них точно сохранилась в новой конфигурации. У деления на трети такого совпадения обычно нет. Поэтому тернарная схема проще геометрически, но может оказаться дороже при трудоёмком вычислении функции.

Задача минимизации отличается от решения f(x) = 0. Функция (x−2)²+7 не обращается в нуль на вещественной оси, однако её минимум прекрасно находится сравнением высот. Значение минимума и положение минимизатора следует записывать раздельно.

Как пользоваться формулой

  1. Выберите вещественный интервал и подтвердите строгую унимодальность; определите допустимую ошибку положения минимума.
  2. Найдите точки u и v на одной и двух третях текущего отрезка; вычислите функцию в обеих точках без грубого округления.
  3. Сравните высоты: при большем левом значении отбросьте левую треть, иначе правую; сохраните замкнутый интервал.
  4. Проверьте длину оставшегося отрезка и верните его середину, когда половина длины станет не больше заданного допуска.

Историческая справка

Сокращение интервала по сравнению пробных значений относится к алгоритмической традиции одномерной оптимизации XX века. Её основной вопрос — какую область можно уверенно исключить после ограниченного числа вычислений функции. Университетское изложение золотого сечения в CS 357 формулирует тот же принцип исключения через две внутренние точки; деление на трети получается при их фиксированном выборе на 1/3 и 2/3 длины. Здесь тернарная схема представлена как прямое следствие унимодальности, без приписывания отдельного открытия конкретному математику. Различие с золотым сечением относится прежде всего к повторному использованию значений и расходу вычислений, а не к новой теории экстремумов.

Историческая линия формулы

У схемы используется описательное имя: две пробные точки делят отрезок на три части. Приведённое доказательство опирается на унимодальность, как и университетские методы исключения интервала. Единственный автор этой элементарной версии здесь не устанавливается.

Пример

Пусть f(x) = (x−2)²+1, исходный интервал [0,9]. Внутренние точки равны u = 3 и v = 6. Получаем f(3) = 2 и f(6) = 17, поэтому минимум сохраняется на [0,6]. Следующие точки равны 2 и 4, значения — 1 и 5; остаётся [0,4]. Точный минимум x = 2 остаётся внутри обоих интервалов. За два обычных сокращения длина уменьшилась с 9 до 4, что совпадает с 9·(2/3)². Средина последнего интервала случайно совпала с точным ответом, но общая гарантия пока равна лишь половине длины, то есть 2. Совпадение в этом примере не заменяет критерий остановки. Все числа и координаты здесь безразмерны.

Частая ошибка

Не называйте сохраняемую длину одной третью при обычном неравном сравнении: сохраняются две трети. Не переносите вещественное правило остановки на целые индексы без финального перебора. Не разрешайте произвольные плато при заявленной гарантии. Не считайте случайное попадание середины доказательством точности.

Практика

Задачи с решением

Пять шагов

Условие. Исходная длина 27. Какова длина после пяти обычных сокращений?

Решение. Получаем 27·(2/3)⁵ = 32/9 ≈ 3,555556. Это длина, а не ошибка середины.

Ответ. 32/9.

Равные значения

Условие. Для f(x) = (x−3)² на [0,6] сравните точки 2 и 4. Что можно сохранить?

Решение. Оба значения равны 1. При строгой унимодальности минимум лежит в [2,4]; обычное правило также безопасно оставляет [0,4].

Ответ. Можно сохранить [2,4]; стандартная версия оставит [0,4].

Дополнительные источники

  • https://cs357.cs.illinois.edu/textbook/notes/optimization.html
  • https://courses.grainger.illinois.edu/cs357/fa2019/references/ref-12-opt-nd/

Связанные формулы

Математика

Метод золотого сечения: сужение интервала минимума

$\tau=\frac{\sqrt5-1}{2},\quad u=a+(1-\tau)(b-a),\quad v=a+\tau(b-a),\quad L_n=\tau^nL_0$

Золотое сечение находит минимум унимодальной функции без производных. Два внутренних значения позволяют отбросить часть интервала, а удачное отношение длин сохраняет одно вычисление для следующего шага.

Математика

Параболическая интерполяция для поиска минимума функции

$A=\frac{(f_3-f_2)/(x_3-x_2)-(f_2-f_1)/(x_2-x_1)}{x_3-x_1},\quad B=\frac{f_2-f_1}{x_2-x_1}-A(x_1+x_2),\quad x_p=-\frac{B}{2A}$

Через три значения функции строят квадратичный интерполянт и используют его вершину как новую пробную точку минимума. В отличие от деления интервала схема учитывает высоты всех трёх точек.

Математика

Градиентный спуск с постоянным шагом: условие убывания

$x_{k+1}=x_k-\alpha\nabla f(x_k),\quad 0<\alpha<2/L,\quad f(x_{k+1})\le f(x_k)-\alpha(1-L\alpha/2)\|\nabla f(x_k)\|^2$

Постоянный шаг градиентного спуска смещает точку против градиента. При липшицевом градиенте известная граница шага обеспечивает уменьшение функции и объясняет, почему слишком крупный шаг вызывает расходимость.

Математика

Правило Армихо: обратный поиск длины шага спуска

$f(x+\alpha p)\le f(x)+c\alpha\nabla f(x)^Tp,\quad \nabla f(x)^Tp<0,\quad \alpha\leftarrow\beta\alpha,\quad 0<c<1,\ 0<\beta<1$

Обратный поиск по правилу Армихо уменьшает пробный шаг, пока функция не снизится на заданную долю линейного прогноза. Он выбирает длину движения вдоль уже найденного направления спуска.