Введение
Метод нахождения стационарных точек функции
В математическом анализе метод Ньютона (также называемый методом Ньютона — Рафсона) — это итеративный метод для нахождения корней дифференцируемой функции F, которые являются решениями уравнения F(x) = 0. Таким образом, метод Ньютона может быть применен к производной f′ дважды дифференцируемой функции f для нахождения корней производной (решений уравнения f′(x) = 0), также известных как критические точки f. Эти решения могут быть минимумами, максимумами или седловыми точками; см. раздел "Несколько переменных" в статье "Критическая точка (математика)", а также раздел "Геометрическая интерпретация" в этой статье. Это применимо в оптимизации, целью которой является поиск (глобальных) минимумов функции f.
Геометрическая интерпретация
Геометрическая интерпретация метода Ньютона состоит в том, что на каждой итерации он сводится к построению параболы, касательной к графику функции f в текущем приближении, имеющей тот же наклон и кривизну, что и график в этой точке, и затем переходу к максимуму или минимуму этой параболы (в многомерном случае это может быть и седловой точкой), см. ниже. Следует отметить, что если f является квадратичной функцией, то точный экстремум находится за один шаг.
Сближение
Если f — строго выпуклая функция с липшицевым гессианом, то при условии, что достаточно близко к , последовательность, генерируемая методом Ньютона, будет сходиться к (единственному) минимизатору f квадратично быстро. То есть,
Вычисление направления Ньютона
Нахождение обратной матрицы Гессиана в высоких размерностях для вычисления направления Ньютона может быть вычислительно дорогостоящей операцией. В таких случаях, вместо непосредственного обращения Гессиана, предпочтительнее вычислить вектор как решение системы линейных уравнений, которую можно решить различными разложениями или приближённо (но с высокой точностью) с использованием итерационных методов. Многие из этих методов применимы только к определённым типам уравнений, например, разложение Холецкого и метод сопряжённых градиентов будут работать только если Гессиан является положительно определённой матрицей. Хотя это может показаться ограничением, это часто является полезным индикатором неисправности; например, если решается задача минимизации и Гессиан не является положительно определённым, то итерации сходятся к седловой точке, а не к минимуму. С другой стороны, если выполняется оптимизация с ограничениями (например, с использованием множителей Лагранжа), задача может сводиться к поиску седловой точки, в этом случае Гессиан будет симметричным неопределённым, и решение системы необходимо искать методом, подходящим для таких матриц, как вариант разложения Холецкого или метод сопряжённых остатков. Существуют также различные квазиньютоновские методы, в которых приближение Гессиана (или его обратной матрицы) строится на основе изменений градиента. Если Гессиан близок к необратимой матрице, обратная матрица Гессиана может быть численно неустойчивой, и решение может расходиться. В этом случае в прошлом предпринимались различные попытки решения проблемы, с переменным успехом для разных задач. Можно, например, модифицировать Гессиан, добавив корректирующую матрицу, чтобы сделать его положительно определённым. Один из подходов заключается в диагонализации Гессиана и выборе такой матрицы, чтобы она имела те же собственные векторы, что и Гессиан, но с заменой каждого отрицательного собственного значения на . Подход, используемый в алгоритме Левенберга — Марквардта (который использует приближённый Гессиан), заключается в добавлении к Гессиану масштабированной единичной матрицы, , при этом масштаб корректируется на каждой итерации по мере необходимости. Для больших и малых Гессианов итерации будут вести себя как градиентный спуск с шагом размера . Это приводит к более медленной, но более надёжной сходимости, когда Гессиан не предоставляет полезной информации.
which may be solved by various factorizations or approximately (but to great accuracy) using iterative methods. Many of these methods are only applicable to certain types of equations, for example the Cholesky factorization and conjugate gradient will only work if is a positive definite matrix. While this may seem like a limitation, it is often a useful indicator of something gone wrong; for example if a minimization problem is being approached and is not positive definite, then the iterations are converging to a saddle point and not a minimum. On the other hand, if a constrained optimization is done (for example, with Lagrange multipliers), the problem may become one of saddle point finding, in which case the Hessian will be symmetric indefinite and the solution of will need to be done with a method that will work for such, such as the variant of Cholesky factorization or the conjugate residual method. There also exist various quasi Newton methods, where an approximation for the Hessian (or its inverse directly) is built up from changes in the gradient. If the Hessian is close to a non invertible matrix, the inverted Hessian can be numerically unstable and the solution may diverge. In this case, certain workarounds have been tried in the past, which have varied success with certain problems. One can, for example, modify the Hessian by adding a correction matrix so as to make positive definite. One approach is to diagonalize the Hessian and choose so that has the same eigenvectors as the Hessian, but with each negative eigenvalue replaced by
An approach exploited in the Levenberg–Marquardt algorithm (which uses an approximate Hessian) is to add a scaled identity matrix to the Hessian, , with the scale adjusted at every iteration as needed. For large and small Hessian, the iterations will behave like gradient descent with step size This results in slower but more reliable convergence where the Hessian doesn't provide useful information.