- •1. Задачи оптимизации
- •1.1. Основные понятия
- •1.2. Постановка задачи оптимизации
- •1.2.1 Задача безусловной оптимизации
- •1.2.2. Задача условной оптимизации
- •1.2.3. Классическая задача на условный экстремум
- •1.2.4. Понятия выпуклого множества и выпуклой функции
- •1.2.5. Выпуклая задача оптимизации
- •1.2.6. Задача математического программирования
- •1.2.7. Задачи выпуклого программирования
- •1.2.8. Задачи линейного и квадратичного программирования
- •1.2.9. Задача дискретной оптимизации
- •1.2.10. Задачи оптимального управления
- •2.Начальные сведения о численных методах оптимизации
- •2.1. Понятие о численных методах оптимизации
- •2.2. Сходимость методов оптимизации
- •2.3. Условия остановки (критерии окончания счета)
- •2.4. Направление убывания и методы спуска
- •2.5. Выбор длины шага из условия минимизации функции вдоль заданного направления
1.2. Постановка задачи оптимизации
Постановка задачи оптимизации: заданы множество Х и функция f(x), определенная на Х; требуется найти точки минимума или максимума функции f на X. Задачу на минимум будем записывать в виде
f(x) min, х Х. (1.1)
При этом f будем называть целевой функцией, Х — допустимым множеством, любой элемент х Х — допустимой точкой задачи (1.1).
В основном приходится иметь дело с конечномерными задачами оптимизации, т.е. задачами, допустимое множество которых лежит в евклидовом пространстве Rn.
Дадим определение понятия точки минимума, т.е. решения задачи (1.1).
Точка х* Х называется:
1) точкой глобального минимума функции f на множестве X, или глобальным решением задачи (1.1), если
f(x*) f(x) при всех х Х; (1.2)
2) точкой локального минимума f на X, или локальным решением задачи (1.1), если существует число > 0 такое, что
f(x*) f(x) при всех x X , (1.3)
где – шар радиуса >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 - компакт в Rn (то есть замкнутое ограниченное множество), f - непрерывная функция на X. Тогда точка глобального минимума функции f на Х (глобальное решение задачи (1.1)) существует.
В дальнейшем окажется полезной и несколько иная форма данной теоремы.
Теорема 1.1'. Пусть X - замкнутое множество в Rn, f - непрерывная функция на X, причем при некотором х0 Х множество
ограничено. Тогда точка глобального минимума функции f на Х существует.
Классификацию задач оптимизации можно проводить по нескольким признакам в зависимости от вида функции f и множества X. Далее мы выделим наиболее важные для теории и приложений оптимизационные задачи.