Квази

[experimenter]

чего-то я не-пойму, что за чудо берут в квази-Ньютоновском методе поиска минимума вместо обратной матрицы Н(Г?)ессе, которая фигурирует в Ньютоновском методе. какую-то матрицу с волной. откуда она взялась? с потолка?

Сообщение отредактировано: experimenter - 29.05.03, 13:21

[PAV]

Цитата EXPERIMENTER, 29.05.03, 17:21:01

какую-то матрицу с волной. откуда она взялась? с потолка?

Никогда не слышал, а где она упоминается?

[experimenter]

ну, вот алгоритм Нютона, измененый
xk+1 = xk - sk*H^(-1)(xk)grad f(xk),где
H^(-1)(xk) обратная мытрицы Хессе в точке xk,
sk - величина шага,
gradf(xk) - градиент функции в точке xk.
так вот в квази-Ньютоновском методе вместо H^(-1)(xk) используется некая матрица
H(xk), только как я понимаю отличная от матрицы Хессе, а что за матрица я не знаю.

[Vesper]

Если Н^-1(x_k) обратная Хессе, то Н(x_k) есть сама матрица Хессе. Только я вообще еще не слышал о матрице Хессе...

[PAV]

Матрица Гессе (мне так привычней) строиться из частных производных второго порядка,
в квазиньютоновском методе вторые производные вычисляются через КР. Таким образом матрицы Гессе для квазиньютоновского и ньютоновском не равны друг другу при одинаковых целевых функциях.  ;)

[experimenter]

ммм. а что такое КР? и что такое целевая функция?

[PAV]

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

[experimenter]

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

[PAV]

Так в том то все и дело, что производные полученные аналитически и через КР разности, в общем случае не равны.

[experimenter]

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

Сообщение отредактировано: experimenter - 02.06.03, 08:49

[PAV]

Да, это так и есть. Можно сравнить на примере производной от e^x.
при x=10, аналитическая проиводная 22026.5, правая КР (Delta=0.001) =22037.5.
Для одномерной оптимизации это не страшно, но при многомерной, когда фунция имеет вид "кривых оврагов", небольшая ошибка (при определении направления спуска) значительно замедляет сходимость алгоритма. Для проверки работы алгоритмов оптимизации используют тестовые функции. Наиболее простая функция -- Розенброка "банан" (что вроде Y=(X1*X2)^2+ 100(X1-X2)^2 точно не помню и, скорее всего, записано с ошибкой), если интересно посмотрю в литературе и напишу.
Эта функция имеет минимум в т. (1,1).