Метод одномерной оптимизации

Свойства функции одной переменной. Монотонность функции. Функцияявляется монотонной, если для любых x₁ и x₂ из области определения функции выполняется, таких, что  выполняется неравенство , если функция монотонно возрастающая  или , если функция монотонно убывающая.

Унимодальность.

Функцияявляется унимодальной на отрезке , если она монотонна по обе стороны от единственной на отрезке точки , то есть

или

Критерии оптимальности для функций одной переменной.

Определение глобального минимума

Функция, определённая на множестве  достигает глобального минимума в точке , если  для всех .

Определение локального минимума.

Функция, определённая на множестве  имеет локальный минимум в точке , если существует такая -окрестность точки , что для всех  из этой -окрестности   .

, , 

Если функция  не унимодальна, то наименьший из локальных минимумов будет глобальным (аналогично – наибольший из локальных максимумов будет глобальным максимумом).

НЕОБХОДИМЫЕ УСЛОВИЯ ОПТИМАЛЬНОСТИ

Чтобы точка  была точкой локального минимума (или максимума) дважды дифференцируемой функции  на отрезке  необходимо, чтобы выполнялись следующие условия:

1.             

2.              (минимум) или  (максимум)

 

Стационарной точкой называется , в которой выполняется .

Это точки максимума, минимума и перегиба.

Достаточные условия оптимальности.

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

Алгоритм:

 

1. Найти 1-ю производную и станционарные точки.
2. Найти следующую производную, не равную нулю.
3. Анализировать найденную производную, как указано выше.

 

Методы одномерной оптимизации можно разделить на:

 

• методы исключения интервалов;
• методы точечного оценивания (полиномиальной аппроксимации);
• методы с использованием производных.

 

Методы ориентированы на нахождение точки оптимума внутри заданного интервала и основаны на свойстве унимодальности функции.

Правила исключения интервалов.

Пусть  унимодальна на интервале  и достигает минимума в точке . Рассмотрим точки  и  такие, что если , то точка  принадлежит интервалу  , а интервал  исключается.

Если , то исключаются оба интервала  и , а точка оптимума находится принадлежит интервалу .

Достоинства метода.

 

• единственное ограничение на функцию – её унимодальность;
• требуется вычисления только значений функции.

 

В процессе применения этих методов можно выделить два этапа:

 

1. этап установления границ интервалов:
2. этап уменьшения интервалов.

 

Рассмотрим эти этапы.

Этап установления границ интервалов.

 

1. Выбирается исходная точка
2. С помощью эвристических приёмов строятся границы интервала.

 

Эвристический метод.

, где 

- произвольно выбранная точка

- шаг, определяется путём сравнения значений , ,

Если  то  правее, чем  и .

Если  то  левее, чем  и .

Если  то  лежит между точками  и  и поиск завершён.

Если при поиске минимума оказывается, что  , то функция не унимодальна.

Этап  установления интервала

Этап  установления интервала основан на минимаксной стратегии поиска. Размещение пробных точек должно обеспечивать уменьшение интервала в одном и том же отношении, и это отношение должно быть максимальным.

МЕТОД ДЕЛЕНИЯ ПОПОЛАМ

На каждой итерации исключается половина интервала.

1.       Найти  и . Вычислить .

2.       Найти  и . Вычислить  и .

3.       Если , то исключается интервал , при этом ; перейти к п. 5.  Иначе перейти к п. 4.

4.       Если , то исключается интервал , при этом ; перейти к п. 5.  Иначе исключить интервалы и , то есть ; перейти к п. 4.

5.       Вычислить . Если , то закончить поиск. Иначе перейти к п. 2.

Достоинства метода:

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

МЕТОД ЗОЛОТОГО СЕЧЕНИЯ

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

Длина остающегося после исключения интервала всегда равна . Пусть исключается правый интервал.

Для того, чтобы симметрия образца сохранилась расстояние  должно составлять  часть от длинны интервала, который, в свою очередь составляет .

(Золотое сечение можно вычислить как )

Если исходный интервал имеет единичную длину, длина интервала после  вычислений равна .

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