Главная Обратная связь
Дисциплины:
Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)
Метод градиентного спуска с постоянным шагом
|
|
Напомним, что в большинстве случаев численные методы минимизации основываются на построении итерационной последовательности {Xk}, обладающей свойством f(Xk+1)<f(Xk), (k=0, 1, …), по формулам Xk+1=Xk+hkDk, Dk - направление спуска, hk - величина шага. Если Dk=-Ñf(Xk), то метод называется градиентным. Если величину шага hk оставлять постоянной (до тех пор, пока функция убывает в точках последовательности), то метод называется методом градиентного спуска с постоянным шагом. Убывание контролируется путём проверки выполнения условия f(Xk+1)-f(Xk)<0. Построение последовательности {Xk} заканчивается в точке Xk, для которой |Ñf(Xk)|<e1, или выполняется система
где e1, e2 - заданные положительные числа, или k³k0, где k0 - предельное число итераций. Дополнительно необходимо провести исследование вопроса, является ли найденная точка действительным приближением искомой функции.
Более подробно:
1. Задать X0, e1>0, e2>0, k0. Найти градиент функции Ñf(X)= 
, …, 
(Напоминаем, что в отношение вектора возможно одновременное применение в качестве обозначений как строки, так и столбца. При чтении произведений типа AX или XA, где X - вектор, а A - (m´n)-матрица, разночтений быть не должно: в первом случае - это столбец с n элементами, во втором - строка с m элементами).
2. Положить k=0.
3. Вычислить Ñf(Xk).
4. Проверить критерий окончания |Ñf(Xk)|£e1:
а) если критерий выполнен, то расчёт закончен: X*=Xk;
б) если критерий не выполнен, то перейти к шагу 5.
5. Проверить выполнение неравенства k³k0:
а) если неравенство выполнено, то расчёт окончен: X*=Xk;
б) если нет, то перейти к шагу 6.
6. Задать величину шага hk.
7. Вычислить Xk+1=Xk-hkÑf(Xk).
8. Проверить выполнение условия f(Xk+1)-f(Xk)<0:
а) если условие выполнено, то перейти к шагу 9;
б) если условие не выполнено, то положить hk= 
и перейти к шагу 7.
9. Проверить условия r(Xk+1, Xk)<e2 и |f(Xk+1)-f(Xk)|<e2:
а) если оба условия выполнены при текущем значении k и k-1, то расчёт окончен: X*=Xk;
б) если хотя бы одно условие не выполнено, то положить k=k+1 и перейти к шагу 3.
Вопрос о сходимости последовательности {Xk} к решению X* решается в общем в случае с помощью так называемого условия Липшица. Мы ограничимся тем фактом, что если f(X) - сильно выпуклая функция, то при любом выборе X0 последовательность {Xk}, полученная методом градиентного спуска, сходится к точке X*. Поэтому прежде, чем начинать строить последовательность {Xk}, необходимо проверить условие сильной выпуклости функции.
После окончания процедуры нахождения X*»Xk, необходимо проверить, что найденная точка, действительно, является приближением решения задачи.
Если f(X) - дважды непрерывно дифференцируемая (а мы ограничимся именно этим классом задач), то при H(Xk)>0 точка Xk является приближением искомой точки.
Пример I. Найти локальный минимум функции
f(x1, x2)=3 
+2x1x2+2 
.
Решение. Прежде всего убедимся, что функция выпукла. Так как H(X)= 
, то H(X)>0 и функция сильно выпукла, и сходимость итерационного процесса гарантирована.
I. Найдём Xk.
1. Зададим X0=(1, 1), e1=0,1, e2=0,1, k0=10 и найдём градиент Ñf(X)=(6x1+2x2, 2x1+4x2).
2. Положим k=0.
3.0. Вычислим Ñf(X0)=(8; 6).
4.0. Вычислим |Ñf(X0)| и проверим критерий окончания: |Ñf(X0)|= 
=10>0,1. Переходим к шагу 5.
5.0. Проверим условие k>k0: k=0<10=k0. Переходим к шагу 6.
6.0. Зададим h0=0,2.
7.0. Вычислим X1=X0-0,2Ñf(X0)=(1; 1)-0,2(8; 6)=(-0,6; -0,2).
8.0. Проверим выполнение условия f(X1)-f(X0)<0. Так как f(X1)=1,4, f(X0)=7, то условие выполняется. Переходим к шагу 9.
9.0. Проверим условия r(X1, X0)<0,1 и |f(X1)-f(X0)|<0,1. Второе условие не выполняется: |f(X1)-f(X0)|=5,6>0,1. Полагаем k=1 и переходим к шагу 3.
3.1. Вычислим Ñf(X1)=(-4; -2).
4.1. Вычислим |Ñf(X1)| и проверим критерий окончания: |Ñf(X1)|= 
= 
>0,1. Переходим к шагу 5.
5.1. Проверим условие k>k0: k=1<10=k0. Переходим к шагу 6.
6.1. Зададим h1=0,2.
7.1. Вычислим X2=X1-0,2Ñf(X1)=(-0,6; -0,2)-0,2(-4; -2)=(0,2; 0,2).
8.1. Проверим выполнение условия f(X2)-f(X1)<0. Так как f(X2)=0,28, f(X1)=1,4, то условие выполняется: f(X2)-f(X1)=0,28-1,4=-1,12. Переходим к шагу 9.
9.1. Проверим условия r(X2, X1)<0,1 и |f(X2)-f(X1)|<0,1. Второе условие не выполняется: |f(X2)-f(X1)|=1,12>0,1. Полагаем k=2 и переходим к шагу 3.
3.2. Вычислим Ñf(X2)=(1,6; 1,2).
4.2. Вычислим |Ñf(X1)| и проверим критерий окончания: |Ñf(X1)|= 
=2>0,1. Переходим к шагу 5.
5.2. Проверим условие k>k0: k=2<10=k0. Переходим к шагу 6.
6.2. Зададим h2=0,2.
7.2. Вычислим X3=X2-0,2Ñf(X2)=(0,2; 0,2)-0,2(1,6; 1,2)=(-0,12; -0,04).
8.2. Проверим выполнение условия f(X3)-f(X2)<0. Так как f(X3)=0,056, f(X2)=0,28, то условие выполняется: f(X3)-f(X2)=-0,224. Переходим к шагу 9.
9.2. Проверим условия r(X3, X2)<0,1 и |f(X3)-f(X2)|<0,1. Второе условие не выполняется: |f(X3)-f(X2)|=0,224>0,1. Полагаем k=3 и переходим к шагу 3.
3.3. Вычислим Ñf(X3)=(-0,8; -0,4).
4.3. Вычислим |Ñf(X3)| и проверим критерий окончания: |Ñf(X3)|=0,8944>0,1. Переходим к шагу 5.
5.3. Проверим условие k>k0: k=3<10=k0. Переходим к шагу 6.
6.3. Зададим h3=0,2.
7.3. Вычислим X4=X3-0,2Ñf(X3)=(-0,12; -0,02)-0,2(-0,8; -0,4)=(0,04; 0,04).
8.3. Проверим выполнение условия f(X4)-f(X3)<0. Так как f(X4)=0,0112, f(X3)=0,056, то условие выполняется: f(X4)-f(X3)=-0,0448. Переходим к шагу 9.
9.3. Проверим условия r(X4, X3)<0,1 и |f(X4)-f(X3)|<0,1. Второе условие выполняется: |f(X4)-f(X3)|=0,0448<0,1. Для первого имеем
r(X4, X3)= 
= 
»0,1789>0,1,
и условие не выполняется. Полагаем k=4 и переходим к шагу 3.
3.4. Вычислим Ñf(X4)=(0,32; 0,24).
4.4. Вычислим |Ñf(X4)| и проверим критерий окончания: |Ñf(X4)|=0,4>0,1. Переходим к шагу 5.
5.4. Проверим условие k>k0: k=4<10=k0. Переходим к шагу 6.
6.4. Зададим h4=0,2.
7.4. Вычислим X5=X4-0,2Ñf(X4)=(0,04; 0,04)-0,2(0,32; 0,24)=(-0,024; -0,008).
8.4. Проверим выполнение условия f(X5)-f(X4)<0. Так как f(X5)=0,0022, f(X4)=0,0112, то условие выполняется: f(X5)-f(X4)=-0,009. Переходим к шагу 9.
9.4. Проверим условия r(X5, X4)<0,1 и |f(X5)-f(X4)|<0,1. Второе условие выполняется: |f(X5)-f(X4)|=0,009<0,1. Для первого имеем
r(X5, X4)= 
= 
»0,08<0,1,
и условия выполняются. Условия должны выполняться для текущего k и k-1. Поэтому полагаем k=5 и переходим к шагу 3.
3.5. Вычислим Ñf(X5)=(-0,16; -0,08).
4.5. Вычислим |Ñf(X5)| и проверим критерий окончания: |Ñf(X5)|=0,1799>0,1. Переходим к шагу 5.
5.5. Проверим условие k>k0: k=5<10=k0. Переходим к шагу 6.
6.5. Зададим h5=0,2.
7.5. Вычислим
X6=X5-0,2Ñf(X4)=(-0,024; -0,008)-0,2(-0,16; -0,08)=(0,008; 0,008).
8.5. Проверим выполнение условия f(X6)-f(X5)<0. Так как f(X6)=0,0005, f(X5)=0,0022, то условие выполняется: f(X6)-f(X5)=-0,0017. Переходим к шагу 9.
9.5. Проверим условия r(X6, X5)<0,1 и |f(X6)-f(X5)|<0,1. Второе условие выполняется: |f(X6)-f(X5)|=0,0017<0,1. Для первого имеем
r(X6, X5)= 
»0,0358<0,1.
Так как оба условия выполнены при текущем значении k=5 k-1=4, то расчёт окончен: X*=X5=(-0,024; -0,008).
II. Анализ точки X5.
Функция f(x1, x2)=3 +2x1x2+2 является дважды дифференцируемой. Так как матрица Гессе - постоянна и является положительно определённой, то точка X5 является точкой локального минимума, а значение f(X5)=0,0022 - приближённое значение локального минимума.
Ответ: точкой локального минимума является точка X*=(-0,024; -0,008), f(X*)=0,0022 - локальный минимум.
Метод Ньютона
В методе Ньютона точки последовательности {Xk} вычисляются по формуле Xk+1=Xk+Dk, где направление спуска Dk определяется для каждого значения k по формуле
Dk=-H 
(Xk)Ñf(Xk) (3.1)
Если H(Xk)>0, то формула (3.1) гарантирует выполнение условия f(Xk+1)<f(Xk). Если для каких-то значений kH(Xk) не является положительно определённой, то для соответствующих значений k точка Xk+1 вычисляется по методу градиентного спуска Xk+1=Xk-hkÑf(Xk) с выбором величины hk из условия f(Xk-hkÑf(Xk))<f(Xk). Построение {Xk} заканчивается в точке Xk, для которой выполняются условия завершения, как и в методе градиентного спуска.
Таким образом, алгоритм метода - следующий:
1. Задать X0, e1>0, e2>0, k0 - предельное число итераций. Найти Ñf(X0) и H(X0).
2. Положить k=0.
3. Вычислить Ñf(Xk).
4. Проверить условие выполнения критерия окончания |Ñf(Xk)|<e1:
а) если неравенство выполнено, то расчёт закончен: X*=Xk;
б) если критерий не выполнен, то перейти к шагу 5.
5. Проверить выполнение неравенства k³k0:
а) если неравенство выполнено, то расчёт окончен: X*=Xk;
б) если нет, то перейти к шагу 6.
6. Вычислить матрицу H(Xk).
7. Вычислить матрицу H (Xk).
8. Проверить выполнение условия H (Xk)>0:
а) если H (Xk)>0, то перейти к шагу 9;
б) в противном случае перейти к шагу 10, положив Dk=-Ñf(Xk).
9. Определить Dk=-H (Xk)Ñf(Xk).
10. Определить Xk+1=Xk+hkDk, положив hk=1, если Dk=-H (Xk)Ñf(Xk) или выбрав hk из условия f(Xk+1)<f(Xk), если Dk=-Ñf(Xk).
11. Проверить условий r(Xk+1, Xk)<e2 и |f(Xk+1)-f(Xk)|<e2:
а) если оба условия выполнены при текущем значении k и k-1, то расчёт окончен: X*=Xk;
б) если хотя бы одно условие не выполнено, то положить k=k+1 и перейти к шагу 3.
Как и в случае метода градиентного спуска, сходимость метода Ньютона гарантируется для сильно выпуклых функций. Поэтому также необходимо проверять, является ли найденная точка приближением искомой X*.
Пример II. Решить задачу из примера I методом Ньютона.
Решение. Мы уже убедились (при решении примера I), что сходимость итерационного процесса гарантирована. Так что, осталось найти X* и провести его анализ.
I. Найдём Xk.
1. Зададим X0=(1, 1), e1=0,1, e2=0,1, k0=10 и найдём градиент Ñf(X)=(6x1+2x2, 2x1+4x2) и H(X)= (см. решение примера I).
2. Положим k=0.
3.0. Вычислим Ñf(X0)=(8; 6).
4.0. Проверим критерий окончания: |Ñf(X0)|=10>0,1. Переходим к шагу 5.
5.0. Проверим условие k>k0: k=0<10=k0. Переходим к шагу 6.
6.0. Вычислим матрицу H(X0)= .
7.0. Вычислим матрицу H (X0)= 
= 
.
8.0. Проверим выполнение условия H (X0)>0. Так как D1=0,2, D2= 
=0,05>0, то условие выполнено. Переходим к шагу 9.
9.0. Определим D0:
D0=-H (X0)Ñf(X0)=- 
= 
.
10.0. Определим X1=X0+h0D0, полагая h0=1 (так как D0=-H (X0)Ñf(X0)): X1=(1; 1)+(-1; -1)=(0; 0).
11.0. Проверим условия r(X1, X0)<0,1 и |f(X1)-f(X0)|<0,1. Имеем
r(X1, X0)= 
= 
>0,1,
то есть первое условие не выполнено. Полагаем k=1 и переходим к шагу 3.
3.1. Вычислим Ñf(X1)=(0; 0).
4.1. Проверим критерий окончания |Ñf(X1)|<0,1: |Ñf(X1)|=0. Расчёт окончен: X*=X1=(0; 0).
II. Анализ точки X1.
Функция f(x1, x2)=3 +2x1x2+2 является строго выпуклой, так как матрица Гессе - постоянна и является положительно определённой. Поэтому точка X1 является точкой локального минимума, а значение f(X1)=0 - приближённое значение локального минимума (на самом деле это - точное значение локального минимума).
Ответ: точкой локального минимума является точка X*=(0; 0), f(X*)=0 - локальный минимум.
|
Просмотров 966 |
|
|
