Стратегия поиска

Стратегия метода Марквардта [ Marquardt D. W.] состоит в построении последовательности точек { xk }, k = 0, 1,..., таких, что f (xk + 1) < f (xk), k = 0, l,...

Точки последовательности { xk } вычисляются по правилу

xk + 1 = xk – [ H (xk) + μ kE ]–1∇ f (xk), k = 0, 1,..., (7.7)

где точка х 0задается пользователем, Е — единичная матрица, μ k — последовательность положительных чисел, таких, что матрица [ H (xk) + μ kE ]–1положительно определена. Как правило, число μ0назначается как минимум на порядок больше, чем самый большой элемент матрицы H (х 0), а в ряде стандартных программ полагается μ0= 104. Если f (xk – (H (xk) + μ kE)–1∇ f (xk)) < f (xk), то В противном случае μ k +1= 2 μ k. Легко видеть, что алгоритм Марквардта в зависимости от величины μ k на каждом шаге по своим свойствам либо приближается к алгоритму Ньютона, либо к алгоритму градиентного спуска.

Построение последовательности { xk } заканчивается, когда либо || ∇ f (xk)|| < ε1, либо число итераций k ≥ М, где ε1 — малое положительное число, а М — предельное число итераций.

Вопрос о том, может ли точка xk рассматривается как найденное приближение искомой точки минимума, решается путем проведения дополнительного исследования, которое описано ниже.