§ 2.3. Регулярный итеративный метод

Уравнение оптимальности (2.2) в общем случае представляет собой нелинейное уравнение, и надежда получить его решение аналитическим путем отсутствует почти всегда, за исключением множества, как любят говорить математики, пресловутой «меры пуль». Правда, в случае квадратичных критериев оптимальности и линейных ограничений первого рода нелинейные уравнения (2.2) превращаются в линейные, и появляется возможность применить упомянутое выше правило Крамера. Применительно к таким линейным задачам «множество меры нуль» часто превращается в бедствие для читателей специальных технических журналов.

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

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

Основная идея решения уравнения (2.2) с помощью регулярных итеративных методов состоит в следующем. Представим уравнение (2.2) в равносильной форме

,                                                            (2.3)

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

.                   (2.4)

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

.                                                (2.5)

Методы определения , основанные на соотношении (2.4), и называются итеративными методами. Поскольку выбор начального значения  однозначно предопределяет дальнейшее значение последовательности , или, как можно еще говорить, предопределяет решетчатую функцию , то эти итеративные методы мы назовем регулярными, в отличие от вероятностных, которыми мы будем оперировать в гл. III. Различные формы регулярных итеративных методов отличаются друг от друга конкретным выбором .

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