5. Одномерная оптимизация. Постановка задачи. Метод Ньютона-Рафсона.

Постановка задачи.

Дана непрерывно дифференцируемая функция F(x1,x2,...,xn) n переменных. Необходимо найти хотя бы 1 точку локального оптимума этой функции: F(x) ---> opt , (1) где x = (x1,x2,...,xn). В том случае, когда функция гладкая и доступны для вычисления значения производных, то применяются методы спуска, использующие вычисление производных для выбора направления спуска и шага, которые удовлетворяют условию спуска, состоящее в том, что F_k+1< F_k. Так как доступна первая производная, то данная задача в общем виде сводится к задаче определения стационарных точек, которые затем проверяются на оптимальность. Стационарные точки можно найти из решения системы, приравниванием к 0 всех частных производных или вектора-градиента оптимизируемой функции. g(x)= 0 или

, I=1...n

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

Пусть функция f(x) - унимодальная, по крайней мере, на отрезке [a,b] и известны ее значения на концах этого отрезка. Т.е. минимум локализован и необходимо определить его как можно точнее, с наименьшим возможным интервалом неопределенности, но при этом возможно выполнить только n вычислений функции? Как следует выбрать n точек x_k, k=1,..,N вычисления функции на отрезке [a,b], чтобы как можно точнее определить минимум

Метод Ньютона-Рафсона

Выбор x0 (начального приближения), eps_g и eps_x (точности решения по градиенту и аргументу). iter:= 0. (инициализация счетчика итераций) Аналитическое определение всех частных производных функции f(x) - g_j(x), т.е. вектора градиента и J(x) - матрицы 2-ых производных - для оптимизируемой функции. Расчет g(x0). Расчет J(x0). Решение системы, например, методом Гаусса или методом Зейделя, т.е. определение р=Dx - шага. x:= x0 + р ; iter: =iter+1. расчет g(x). Если |р|< eps_x (точность по аргументу) или |g(x)|< eps_g , x0:= x ; g(x0):=g(x). Оценка погрешностей измерения значения функции df и определения оптимума dx. Печать векторов x и g(x) , значения оптимизируемой функции f(x) и количества итераций iter.

6. Одномерная оптимизация. Постановка задачи. Метод квадратической аппроксимации.

Постановка задачи: Пусть функция f(x) - унимодальная, по крайней мере, на отрезке [a,b] и известны ее значения на концах этого отрезка. Т.е. минимум локализован и необходимо определить его как можно точнее, с наименьшим возможным интервалом неопределенности, но при этом возможно выполнить только n вычислений функции? Как следует выбрать n точек x_k, k=1,..,N вычисления функции на отрезке [a,b], чтобы как можно точнее определить минимум?

Алгоритм метода квадратической аппроксимации.

α₀=0? h-шаг, fo=f(α₀)

1. while |f’(α₀)|>e_g

1.1 α₁:= α₀+h; f₁=f(α₁)

1.2 if f1>f0 then h:=-h\2 : goto 1.1

1.3 α2= α₀+2h; f2=f(α2)

1.4 построение параболы и поиск минимума параболы

fm=f(α_min)

1.5 α_on=argmin(f1,f2,fn)

1.6 if fo<f(α_on) then h:=h\10: goto 1.1

1.7 α_o := α_on