!

Предупреждение: Статья находится в процессе написания. На текущий момент рассмотрены следующие алгоритмы одномерного поиска: Метод сканирования; Метод дихотомии.

Теоретический минимум

В задачах одномерного поиска аналитическое выражение исследуемой функции неизвестно. Для нахождения оптимального решения используются некие правила, по которым проводятся эксперименты (вычисления значений функции). Совокупность таких правил называется стратегией поиска. Пассивными стратегиями будем называть такие стратегии поиска, где все эксперименты определены априори (т.е. точки проведения экспериментов определены заранее). Активными стратегиями будем называть те, в которых последовательность проведения экспериментов зависит от полученных ранее результатов. Также активные стратегии поиска будем называть последовательными стратегиями поиска. Для обеспечения сходимости требуется унимодальность оптимизируемой функции. Функция считается строго унимодальной на интервале , если при она строго убывает (возрастает), а при – строго возрастает (убывает), где – точка минимума (максимума) функции. Суть описанных ниже методов одномерного поиска состоит в нахождении отрезка, содержащего оптимальную точку . В процессе решения задачи этот отрезок уменьшается по выбранному закону в зависимости от метода решения. Уменьшение отрезка происходит за счет деления этого отрезка (согласно выбранному методу) и отсечения тех его частей, которые не содержат экстремальных точек. Ответом для задач такого типа считается интервал неопределенности (отрезок), содержащий оптимальную точку. Чем отрезок меньше, тем лучше, т.к. точнее определяется положение экстремума, но при этом необходимо увеличивать количество экспериментов, которые могут быть дорогостоящими по времени, по цене. Будут рассмотрены следующие методы одномерного поиска:
1) метод сканирования;
2) метод дихотомии;
3) метод золотого сечения;
4) метод Фибоначчи;
5) метод поиска по дискретам;
6) метод Пауэлла.

Метод сканирования
Найти на заданном интервале экстремум унимодальной функции при заданной точности (различимости экспериментов) Метод сканирования использует пассивную стратегию поиска, при которой точки экспериментов определяются заранее. Основные шаги метода приведены ниже.
1. Задается требуемая точность нахождения экстремума ( ).
2. Рассчитывается длина шага
3. Определяются точки экспериментов внутри интервала на расстоянии .
4. Проводятся эксперименты во всех точках, определенных в п.3.
5. Определяется точка с наилучшим значением функции.
6. Результат – интервал неопределенности длины , содержащий в качестве внутренней наилучшею точку п.5, границами которого являются соседние точки проведения экспериментов или границы (граница) исходного интервала.
Пример 1. Найти минимум функции методом сканирования. Интервал неопределенности . Требуемая точность нахождения экстремума задана величиной .
Рассчитаем длину шага . Определим точки проведения экспериментов на интервале на расстоянии друг от друга. Для этого разобьем начальный интервал отрезком . В данном случае в результате разбиения у нас появится множество точек , где . Затем проведем эксперименты во всех точках, созданных на предыдущем шаге, т.е. в точках , где .
Точки, в которых проводятся эксперименты, и значения функции в этих точках приведены в Таблице.

Определим точку с наилучшим значением функции (в данном случае с минимальным), в нашем примере это точка . Определим интервал неопределенности длиной , содержащий в качестве внутренней наилучшею точку , границами которого являются соседние точки проведения экспериментов. Ответ к задаче: , интервал неопределенности – это отрезок .

Метод Дихотомии
Этот метод получил название дихотомии в связи с делением отрезка пополам.
Найти на заданном интервале экстремум унимодальной функции при – интервале различимости (минимальном расстоянии, на котором имеет смысл проводить эксперименты).
Метод дихотомии использует активную стратегию поиска. Ниже приведено описание шага метода (на каждом шаге метода проводится два эксперимента).
1. Создать отрезок , равный половине интервала неопределенности на предыдущем шаге (для нулевого шага это исходный интервал неопределенности) и отрезок , равный половине заданной различимости экспериментов .
2. Определить точки проведения первого и второго экспериментов: отложить отрезок от середины отрезка в обе стороны.
3. Провести эксперименты в точках, заданных в п.2.
4. Определить точку с наилучшим значением функции.
5. Выделить интервал неопределенности, содержащий наилучшее значение функции в качестве внутренней точки.
6. Взять интервал, выбранный в п.5., за исходный и перейти к п.1.
Критерии останова метода дихотомии:
1. Выполнено заданное количество шагов.
2. Достигнута требуемая точность.
Пример 2. Найти минимум функции , интервал неопределенности , – интервал различимости (минимальное расстояние, на котором имеет смысл проводить эксперименты). Выполнить два шага метода дихотомии.
Создадим отрезок, равный половине исходного интервала неопределенности. В данном случае это отрезок .
Создадим отрезок . Создадим точку – середину отрезка – это точка . Отложим отрезок от середины начального отрезка в обе стороны. Получим точки проведения эксперимента – это точки и .

Затем проведем эксперименты в отложенных точках: .

Выберем интервал неопределенности, содержащий наилучшее значение функции в качестве внутренней точки. В данном случае это интервал . Так как критерий останова не выполняется (не сделано заданное количество шагов), переходим к следующему шагу.
Найдем середину текущего интервала неопределенности. В данном случае это . Отложим отрезок от середины отрезка в обе стороны. Получим точки проведения эксперимента – это точки и . Затем проведем эксперименты в отложенных точках: . Так как в условии задачи задано выполнить два шага метода дихотомии, далее следует выделить последний интервал неопределенности, содержащий наилучшее значение функции в качестве внутренней точки. В данном случае это будет отрезок
Ответ к задаче: , интервал неопределенности – отрезок .

По материалам Садчикова С.М.​