Основные определения. Численные методы безусловной оптимизации нулевого порядка

Численные методы безусловной оптимизации нулевого порядка

Решение многих теоретических и практических задач сводится к отысканию экстремума (наибольшего или наименьшего значения) скалярной функции f(х) n -мерного векторного аргументах. В дальнейшем под x будем понимать вектор-столбец (точку в n -мерном пространстве):

Вектор-строка получается путем применения операции транспонирования:

.

Оптимизируемую функцию f(x) называют целевой функцией или критерием оптимальности.

В дальнейшем без ограничения общности будем говорить о поиске минимального значения функции f(x) записывать эту задачу следующим образом:

f(x) --> min.

Вектор х*, определяющий минимум целевой функции, называют оптимальным.

Отметим, что задачу максимизации f(x) можно заменить эквивалентной ей задачей минимизации или наоборот. Рассмотрим это на примере функции одной переменной (Рис. 2.1). Если х * - точка минимума функции y = f(x), то для функции y =- f(x) она является точкой максимума, так как графики функций f(x) и - f(x), симметричны относительно оси абсцисс. Итак, минимум функции f(x) и максимум функции - f(x) достигаются при одном и том же значении переменной. Минимальное же значение функции f(x), равно максимальному значению функции - f(x), взятому с противоположным знаком, т.е. min f(x) =-max (f(x)).

Рассуждая аналогично, этот вывод нетрудно распространить на случай функции многих переменных. Если требуется заменить задачу минимизации функции f(x₁, …, x_n) задачей максимизации, то достаточно вместо отыскания минимума этой функции найти максимум функции f(x₁, …, x_n). Экстремальные значения этих функций достигаются при одних и тех же значениях переменных. Минимальное значение функции f(x₁, …, x_n) равно максимальному значению функции - f(x₁, …, x_n), взятому с обратным знаком, т.е. min f(x₁, …, x_n) =max f(x₁, …, x_n). Отмеченный факт позволяет в дальнейшем говорить только о задаче минимизации.

Рис. 2.1. Экстремум

В реальных условиях на переменные x_j, i=1, …. n, и некоторые функции g_i (х), h_i(х), характеризующие качественные свойства объекта, системы, процесса, могут быть наложены ограничения (условия) вида:

g_i (х) = 0, i=1, …. n,

h_i (х) < = 0, i=1, …. n,

a < = x < = b,

где

;

Такую задачу называют задачей условной оптимизации. При отсутствии ограничений имеет место задача безусловной оптимизации.

Каждая точка х в n-мерном пространстве переменных х₁, …, х_n, в которой выполняются ограничения, называется допустимой точкой задачи. Множество всех допустимых точек называют допустимой областью G. Решением задачи (оптимальной точкой) называют допустимую точку х*, в которой целевая функция f (х) достигает своего минимального значения.

Точка х* определяет глобальный минимум функции одной переменной f(x), заданной на числовой прямой Х, если x ^* X и f(x^*) < f(x) для всех x^* X (Рис. 2.2, а). Точка х * называется точкой строгого глобального минимума, если это неравенство выполняется как строгое. Если же в выражении f(х*) < = f(x) равенство возможно при х, не равных х*, то реализуется нестрогий минимум, а под решением в этом случае понимают множество х* = [ x ^* X: f(x) = f(x^*) ] (Рис. 2.2, б).

Рис. 2.2. Глобальный минимум. а - строгий, б - нестрогий

Точка х* Х определяет локальный минимум функции f(x) на множестве Х, если при некотором достаточно малом e > 0 для всех х, не равных х*, x X, удовлетворяющих условию ¦ х - х* ¦< = e, выполняется неравенство f(х*) < f(х). Если неравенство строгое, то х* является точкой строгого локального минимума. Все определения для максимума функции получаются заменой знаков предыдущих неравенств на обратные. На Рис. 2.3 показаны экстремумы функции одной переменной f(х) на отрезке [a, b]. Здесь х₁, х₃, х₆ - точки локального максимума, а х₂, х₄ - локального минимума. В точке х₆ реализуется глобальный максимум, а в точке х₂ - глобальный минимум.

Рис. 2.3. Экстремумы функции