- •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. Выбор длины шага из условия минимизации функции вдоль заданного направления
2.2. Сходимость методов оптимизации
Важной характеристикой бесконечношаговых методов является сходимость.
Будем говорить, что метод (2.3) сходится, если хk х* при k , где х* – решение задачи (2.1). Если f(хk) f(х*), то иногда также говорят, что метод (2.3) сходится (по функции), при этом последовательность хk называют минимизирующей. Минимизирующая последовательность может и не сходиться к точке минимума. Так, для функции, график которой изображен на рис. 2.1, минимизирующая последовательность xk = k не сходится к точке минимума х* = 0.
В случае, когда точка минимума х* не единственна, под сходимостью метода понимается сходимость последовательности х* к множеству X* точек минимума функции f.
Эффективность сходящегося метода можно охарактеризовать с помощью понятия скорости сходимости.
Пусть хk х* при k . Говорят, что последовательность хk сходится к х* линейно (с линейной скоростью, со скоростью геометрической прогрессии), если существуют такие константы q (0, 1) и k0, что
при k k0. (2.4)
Говорят, что хk сходится к х* сверхлинейно (со сверхлинейной скоростью), если
при k . (2.5)
Наконец, говорят о квадратичной сходимости, если существуют такие константы С 0 и k0, что
при k k0. (2.6)
Установление факта сходимости и оценка скорости сходимости дают существенную информацию о выбранном методе минимизации. Прежде всего, требования, которые приходится накладывать на минимизируемую функцию, показывают область применимости метода. Анализ скорости сходимости дает полезную количественную и качественную характеристику изучаемого метода оптимизации. В то же время реальный процесс оптимизации не может быть бесконечношаговым.
При выборе подходящего метода решения реальных задач приходится во многом руководствоваться здравым смыслом, опытом, интуицией, а также результатами численных экспериментов.
Для задания конкретного вычислительного алгоритма бесконечно-шаговый метод необходимо дополнить условием остановки.
2.3. Условия остановки (критерии окончания счета)
Условие остановки может определяться имеющимися в наличии вычислительными ресурсами. Например, может быть задано число вычислений предусмотренных алгоритмом характеристик минимизируемой функции f.
На практике часто используются следующие условия остановки:
, (2.7)
, (2.8)
, (2.9)
До начала вычислений выбирается одно из условий (2.7)-(2.9) и соответствующее ему малое положительное число i. Вычисления прекращаются после (k+1)-го шага, если впервые оказывается выполненным выбранное условие остановки. На практике также используются критерии, состоящие в одновременном выполнении двух из условий (2.7)-(2.9) или всех трех условий.
Критерий (2.9) относится лишь к задачам безусловной оптимизации. Его выполнение означает, что в точке хk+1 с точностью 3 выполнено условие стационарности. В задаче условной оптимизации критерий (2.9) следует заменить на критерий «-стационарности», соответствующий данной задаче.
Вместо критериев (2.7)-(2.9), основанных на понятии абсолютной погрешности, можно использовать аналогичные критерии, основанные на понятии относительной погрешности:
, (2.10)
, (2.11)
, (2.12)
Отметим, что выполнение указанных критериев и других подобных им эвристических условий остановки, вообще говоря, не гарантирует достижения необходимой точности решения задачи.