Минимизация функции многих переменных методом Ньютона

Метод Ньютона.

Строится последовательность точек {xk}, k=0,1,…, таких, что , k=0,1,… Точки последовательности {xk} вычисляются по правилу xk+1=xk+dk, k=0,1,… Точка х0 задается пользователем с учетом знакопостоянства и невырожденности матрицы Гессе в задаваемой начальной точке и близости выбранной точки к предполагаемой точке минимума. Направление спуска определяется для каждого значения k по формуле dk =-H-1 (xk) grad f (xk), где Н - матрица Гессе.

Применительно к задачам оптимизации

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

где — гессиан функции .

В более удобном итеративном виде это выражение выглядит так:

Следует отметить, что в случае квадратичной функции метод Ньютона находит экстремум за одну итерацию.

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

Дата добавления: 2015-04-24