Раздел 4. Численные методы нелинейного программирования

Рассмотрим численные методы решения задачи поиска без­условного минимума функции /(ж), заданной на всем простран­стве Кп. Релаксационными называются методы, в которых стро­ится последовательность векторов ж0, ж1,..., хк1..., удовлетворя­ющая условию

1(х°)>/(х1)>...>/(хк)>....

В этих методах векторы хк вычисляются по формуле

хк+1 = хк + акрк,

где рк — направление спуска, ак — длина шага вдоль этого на­правления.

Важнейшей характеристикой численных методов является их скорость сходимости. При оценке качества метода говорят о ли­нейной скорости сходимости, если для к = 0,1,...

\\хк+1 - х*\\ < д \\хк - х*\\

или о сходимости со скоростью геометрической прогрессии

где ж* — минимум функции /(ж), ад — некоторая константа, О < д < 1. Скорость сходимости сверхлинейна, если

\\хк+1 - х*\\ < дк \\хк - ж*||,

где дк —т- 0 при к —т- со, и квадратична, если

\\хк+1 - х*\\ < С \\хк - х*\\2,С > 0.

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