Постановка задачи оптимизации

Постановка задачи оптимизации: заданы множество Х и функция f(x), определенная на Х; требуется найти точки минимума или максимума функции f на X. Задачу на минимум будем записывать в виде

f(x) ® min, хÎ Х. (1.1)

При этом f будем называть целевой функцией, Х — допустимым множеством, любой элемент х Î Х — допустимой точкой задачи (1.1).

В основном приходится иметь дело с конечномерными задачами опти­мизации, т.е. задачами, допустимое множество которых лежит в евклидовом пространстве Rⁿ.

Дадим определение понятия точки минимума, т.е. решения задачи (1.1).

Точка х* Î Х называется:

1) точкой глобального минимума функции f на множестве X, или глобальным решением задачи (1.1), если

f(x*) £ f(x) при всех хÎ Х; (1.2)

2) точкой локального минимума f на X, или локальным решением задачи (1.1), если существует число e > 0 такое, что

f(x*) £ f(x) при всех x Î X , (1.3)

где – шар радиуса e >0 с центром в х*.

Если неравенство в (1.2) или (1.3) выполняется как строгое при х ¹ х*, то говорят, что х* — точка строгого минимума (строгое решение) в глобальном или локальном смысле.

Глобальное решение является и локальным; обратное неверно.

Для отражения того факта, что точка х* Î Х является точкой глобального минимума функции f на X, будет использоваться запись

или эквивалентная ей запись

.

При этом говорят также, что точка х* реализует величину , т. е. минимальное значение функции f на X. Множество всех точек глобального минимума f на Х обозначим через

.

Таким образом, — это просто произвольная точка из множества .

По аналогии с (1.1) будем записывать задачу максимизации функции f на множестве Х в виде

f(x) ® max, хÎ Х (1.4)

Заменяя в данных выше определениях слово «минимум» на «максимум» и заменяя знак неравенств в (1.2), (1.3) на противопо­ложный, получаем соответствующие понятия для задачи (1.4).

Решения задач (1.1), (1.4), т. е. точки минимума и максимума функции f на X, называют также точками экстремума, а сами задачи (1.1), (1.4) — экстремальными, задачами.

Ясно, что задача (1.4) эквивалентна задаче

–f(x) ® min, хÎ Х,

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

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

Теорема 1.1 (Вейерштрасса). Пусть X - компакт в Rⁿ (то есть замкнутое ограниченное множество), f - непрерывная функция на X. Тогда точка глобального минимума функции f на Х (глобальное решение задачи (1.1)) существует.

В дальнейшем окажется полезной и несколько иная форма дан­ной теоремы.

Теорема 1.1'. Пусть X - замкнутое множество в Rⁿ, f - не­прерывная функция на X, причем при некотором х⁰ Î Х множество

ограничено. Тогда точка глобального минимума функции f на Х существует.

Классификацию задач оптимизации можно проводить по нескольким признакам в зависимости от вида функции f и множе­ства X. Далее мы выделим наиболее важные для теории и прило­жений оптимизационные задачи.