Глава 4. ПЕРВАЯ ТЕОРЕМА СХОДИМОСТИ
В предшествующих главах построены процедуры идентификации оптимальной точки. Показано, что условия Куна — Таккера вместе, скажем, с предположением о вогнутости функций дают достаточные условия для проверки допустимой точки на оптимальность. Теперь мы должны исследовать вопрос о том, как двигаться из неоптимальной точки к оптимальной с помощью некоторого алгоритма.
В этой главе мы исследуем причины, заставляющие вырабатываемую алгоритмом последовательность решений сходиться, и доказываем основную теорему о сходимости — теорему сходимости А. Доказательство основано на понятии точечно-множественного отображения, поэтому в заключении главы приведено подробное исследование замкнутости и свойств композиций подобных отображений.
4.1. АЛГОРИТМ
Будем рассматривать алгоритмы и итерационные процессы, при помощи которых вычисляется последовательность точек Ядром алгоритма является рекурсивный процесс получения по данной точке
последующей точки
Таким образом, отправляясь от начальной точки 2, мы можем вычислить всю последовательность.
Понятие алгоритмов или итерационных процессов описанного типа является весьма общим и включает почти все мыслимые рекурсивные процедуры. Однако нас в основном интересуют алгоритмы, которые
сходятся, другими словами, алгоритмы, которые либо вычисляют оптимальную точку, либо определяют ее в смысле предельной точки.
Конечная сходимость. Только в частных случаях, таких как линейное программирование (ЛП) или квадратичное программирование (КП), можно надеяться определить оптимальную точку за конечное число вычислительных операций. Это происходит благодаря тому, что для этих двух задач условия Куна — Таккера могут быть выражены при помощи систем конечного числа линейных уравнений (упр. 1). Несмотря на это, из-за ошибок округления даже такие задачи не могут быть точно решены за конечное число операций.
Для общих задач НЛП, если мы случайно не найдем оптимальную точку, сходимость имеет место лишь в предельном смысле. Этот общий нелинейный случай мы и будем в основном рассматривать.