11.2. АЛГОРИТМЫ

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

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

Если то процедура останавливается. В противном случае из соотношения выбирается следующая точка

Последовательность как алгоритм. Одним из достоинств такого определения алгоритма является то, что любая последовательность в V может быть интерпретирована как алгоритм. Определим множества в

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

Предыдущий абзац иллюстрирует общность нового определения алгоритма, заключающегося в том, что даже произвольная последовательность может стать алгоритмом. Кроме того, интерпретация последовательностей как алгоритмов будет очень полезной в следующих главах. В виде иллюстрации допустим, что некоторый сложный алгоритм для задачи НЛП вырабатывает последовательность точек Чтобы доказать сходимость этого алгоритма, часто легче определить эту последовательность как некоторый другой алгоритм и установить сходимость этого второго алгоритма. Ясно, что из сходимости второго алгоритма к подходящей точке вытекает сходимость первоначального алгоритма.

11.2.1. Сходящийся алгоритм

До сих пор мы употребляли термин «сходимость» в чисто интуитивном смысле, теперь нам следует дать ему точное определение.

Определение сходящегося алгоритма. Для данных задачи и множества подходящих точек сходящийся алгоритм — это алгоритм со следующими свойствами:

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

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

Замечания. Пункт (а) определения сходимости постулирует поведение алгоритма в такой ситуации, когда ему следует на некоторой итерации определить, что является подходящей точкой. По существу пункт (а)

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

Пункт (б) относится к случаю, когда ни одна из точек не является решением. Следует обратить внимание на значение компактности; множество должно быть непустым только в том случае, если все вырабатываемые точки входят в компактное множество. Это несколько ослабляет прежние требования, заключающиеся в том, чтобы вообще все точки входили в компактное множество, но в то же время обеспечивает соответствующее поведение последовательностей.

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