Гибридный квазиньютоновский алгоритм

Заданы g: →R, x ₀:

for k =0, 1, 2, … do

Решить, необходим ли останов; если нет, то:

Построить локальную модель, описывающую поведение g вблизи x_k и найти x_N – приближенное решение модельной задачи.

а) решить, взять ли x_{k +1} = x_N; если нет, то: б) выбрать x_{k +1}, используя глобальную стратегию (здесь как можно реже прибегать к решению модельной задачи.

Критерии останова:

,

где typ x — типичное значение x; masheps — машинная точность определяемая с помощью алгоритма

masheps =1.0

while 1.0+ masheps >1.0 do { masheps = masheps/ 2}.

Если производные не заданы, то можно использовать либо конечно-разностный метод, либо метод секущих (последний обычно медленнее)

,

или

,

если велико.

В методе секущих

,

Если h_с =const — сходимость линейная, если h_с = h_c^k и { h_c^k }→0, при k →∞, то сходимость сверхлинейная.

Собственно минимизация это решение уравнения f¢ (x) = 0 методом Ньютона с глобальной стратегией по условию while f (x ₊) ≥ f (x _c).

Строим квадратичную модель

.

Экстремальная точка квадратичной модели совпадает с решением по методу Ньютона уравнения f¢ (x) = 0

.