Лекция: Гибридный квазиньютоновский алгоритм.
Заданы g: →R, x0:
for k=0, 1, 2, … do
Решить, необходим ли останов; если нет, то:
Построить локальную модель, описывающую поведение g вблизи xk и найти xN – приближенное решение модельной задачи.
а) решить, взять ли xk+1 = xN; если нет, то: б) выбрать xk+1, используя глобальную стратегию (здесь как можно реже прибегать к решению модельной задачи.
Критерии останова:
,
где typ x — типичное значение x; masheps — машинная точность определяемая с помощью алгоритма
masheps=1.0
while 1.0+masheps>1.0 do {masheps=masheps/2}.
Если производные не заданы, то можно использовать либо конечно-разностный метод, либо метод секущих (последний обычно медленнее)
,
или
,
если велико.
В методе секущих
,
Если hс=const — сходимость линейная, если hс=hck и {hck}→0, при k→∞, то сходимость сверхлинейная.
Собственно минимизация это решение уравнения f¢ (x) = 0 методом Ньютона с глобальной стратегией по условию while f(x+) ≥ f(xc).
Строим квадратичную модель
.
Экстремальная точка квадратичной модели совпадает с решением по методу Ньютона уравнения f¢ (x) = 0
.