Определение 1.1.4. Унимодальная функция

Методы одномерной безусловной оптимизации

Основные понятия

Пусть на множестве X Ì E₁, где E₁ – множество всех действительных чисел, определена функция f(x). Требуется найти x^* Î X, для которого выполнено условие

f(x^*) = min f(x). (1.1.1)

x Î X

Задачу (1.1.1) называют задачей одномерной минимизации.

Отметим, что для определения максимума функции j (x) достаточно взять функцию f(x) = –j (x) и найти минимум функции f(x) на заданном множестве X. Поэтому в дальнейшем будет рассматриваться только задача минимизации (1.1.1), что не умаляет их общности.

При решении задачи используется следующая терминология:

– f(x) – функция цели или целевая функция;

– "x Î E₁ – решение задачи (1.1.1);

– X – множество допустимых решений задачи (1.1.1);

– x^* – оптимальное решение задачи (1.1.1).

Если X совпадает с E₁, то задачу (1.1.1) называют задачей безусловной одномерной минимизации, так как на значения аргумента x не накладывается никаких условий и он может принимать значения на всей числовой оси.
В противном случае задача (1.1.1) называется задачей условной одномерной минимизации, потому что условие x Î X ограничивает выбор допустимых значений аргумента функции f(x). В дальнейшем предполагается, что X – открытое множество.

Определение 1.1.1. Локальный минимум

x^* Î X – точка локального минимума функции f(x) на множестве X, если найдется такое число e > 0, при котором будет выполнено условие

f(x^*) < f(x) " x:ïx – x^*ï < e, x ¹ x^*.

Определение 1.1.2. Многоэкстремальная функция

Функция f(x) называется многоэкстремальной[1] на множестве X, если она имеет более одного локального минимума на этом множестве. В противном случае функция f(x) называется одноэкстремальной на множестве X.

Для многоэкстремальной функции на множестве X целесообразно
ввести понятие глобального минимума.

Определение 1.1.3. Глобальный минимум

x^* Î X – точка глобального минимума функции f(x) на множестве X, если выполнено условие

f(x^*) < f(x) "x Î X, x ¹ x^*.

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

К одноэкстремальным функциям на интервале (a, b) относятся, в частности, унимодальные на этом интервале.

Определение 1.1.4. Унимодальная функция

Пусть x^* Î (a, b) – точка минимума функции f(x). Функция f(x) называется унимодальной на интервале (a, b), если для любой пары точек x₁, x₂ (таких что x₁ < x₂) интервала (a, b), выполнены условия: f(x₁) < f(x₂), если x₁ > x^* f(x₁) > f(x₂), если x₂ < x^*.

Существенно, что понятие унимодальной функции не требует ее дифференцируемости.

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

Для решения задачи (1.1.1) необходимы условия, позволяющие идентифицировать оптимальное решение – локальный экстремум функции f(x). Такие условия называются условиями (признаками) оптимальности.

Сформулируем условия оптимальности для случая дифференциру-емой на множестве X функции f(x), которые являются необходимыми
и достаточными условиями наличия локального экстремума функции, дифференцируемой в некоторой окрестности точки x Î X.