13.3. ТЕОРЕМА СХОДИМОСТИ ДЛЯ МЕТОДОВ ВОЗМОЖНЫХ НАПРАВЛЕНИЙ

Придадим теперь математическую строгость качественным рассуждением о предотвращении заклинивания, сформулировав теорему сходимости для методов возможных направлений. Теорема будет доказана прямым применением леммы 13.1, хотя это можно было бы сделать также с помощью теоремы сходимости (упр. 10).

Теорема сходимости для методов возможных направлений. Рассмотрим задачу НЛП с непрерывно дифференцируемой целевой функцией и допустим, что задано множество подходящих точек.

Предположим, что алгоритм возможных направлений для этой задачи удовлетворяет следующим условиям.

1. Если алгоритм завершает поиск, то только в подходящей точке.

2. Если существует сходящаяся подпоследовательность

где не является подходящей точкой, то имеется некоторое , такое, что

в) существует такое что для любого допустимая точка для

Тогда алгоритм, удовлетворяющий этим условиям, либо завершает поиск в подходящей точке, либо пределом любой сходящейся подпоследовательности будет подходящая точка.

Доказательство. Утверждение (13.16) и условия 2а, 2б и 2в представляют собой перефразировку трех условий леммы 13.1. Поэтому не может существовать подпоследовательность которая сходится к точке не являющейся решением. Теорема доказана.

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

Условие 2а запрещает такие аномалии, как при

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

Требование 26 можно считать условием, вызванным тем, что не является подходящей точкой. Тогда является хорошим направлением для увеличения

Наконец, 2в является условием против заклинивания. Оно гарантирует, что при движении в окрестности не будет встречена граница.

Теорема сходимости для методов возможных направлений будет использована для доказательства сходимости алгоритма, приведенного в следующем параграфе.