Напомним, что в большинстве случаев численные методы минимизации основываются на построении итерационной последовательности { 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)|< e 1, или выполняется система
где e 1, e 2 - заданные положительные числа, или k ³ k 0, где k 0 - предельное число итераций. Дополнительно необходимо провести исследование вопроса, является ли найденная точка действительным приближением искомой функции.
Более подробно:
1. Задать X 0, e 1>0, e 2>0, k 0. Найти градиент функции Ñ f (X)= 
, …, 
(Напоминаем, что в отношение вектора возможно одновременное применение в качестве обозначений как строки, так и столбца. При чтении произведений типа AX или XA, где X - вектор, а A - (m ´ n)-матрица, разночтений быть не должно: в первом случае - это столбец с n элементами, во втором - строка с m элементами).
2. Положить k =0.
3. Вычислить Ñ f (Xk).
4. Проверить критерий окончания |Ñ f (Xk)|£ e 1:
а) если критерий выполнен, то расчёт закончен: X *= Xk;
б) если критерий не выполнен, то перейти к шагу 5.
5. Проверить выполнение неравенства k ³ k 0:
а) если неравенство выполнено, то расчёт окончен: 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)< e 2 и | f (Xk +1)- f (Xk)|< e 2:
а) если оба условия выполнены при текущем значении k и k -1, то расчёт окончен: X *= Xk;
б) если хотя бы одно условие не выполнено, то положить k = k +1 и перейти к шагу 3.
Вопрос о сходимости последовательности { Xk } к решению X * решается в общем в случае с помощью так называемого условия Липшица. Мы ограничимся тем фактом, что если f (X) - сильно выпуклая функция, то при любом выборе X 0 последовательность { Xk }, полученная методом градиентного спуска, сходится к точке X *. Поэтому прежде, чем начинать строить последовательность { Xk }, необходимо проверить условие сильной выпуклости функции.
После окончания процедуры нахождения X *» Xk, необходимо проверить, что найденная точка, действительно, является приближением решения задачи.
Если f (X) - дважды непрерывно дифференцируемая (а мы ограничимся именно этим классом задач), то при H (Xk)>0 точка Xk является приближением искомой точки.
Пример I. Найти локальный минимум функции
f (x 1, x 2)=3 
+2 x 1 x 2+2 
.
Решение. Прежде всего убедимся, что функция выпукла. Так как H (X)= 
, то H (X)>0 и функция сильно выпукла, и сходимость итерационного процесса гарантирована.
I. Найдём Xk.
1. Зададим X 0=(1, 1), e 1=0,1, e 2=0,1, k 0=10 и найдём градиент Ñ f (X)=(6 x 1+2 x 2, 2 x 1+4 x 2).
2. Положим k =0.
3.0. Вычислим Ñ f (X 0)=(8; 6).
4.0. Вычислим |Ñ f (X 0)| и проверим критерий окончания: |Ñ f (X 0)|= 
=10>0,1. Переходим к шагу 5.
5.0. Проверим условие k > k 0: k =0<10= k 0. Переходим к шагу 6.
6.0. Зададим h 0=0,2.
7.0. Вычислим X 1= X 0-0,2Ñ f (X 0)=(1; 1)-0,2(8; 6)=(-0,6; -0,2).
8.0. Проверим выполнение условия f (X 1)- f (X 0)<0. Так как f (X 1)=1,4, f (X 0)=7, то условие выполняется. Переходим к шагу 9.
9.0. Проверим условия r (X 1, X 0)<0,1 и | f (X 1)- f (X 0)|<0,1. Второе условие не выполняется: | f (X 1)- f (X 0)|=5,6>0,1. Полагаем k =1 и переходим к шагу 3.
3.1. Вычислим Ñ f (X 1)=(-4; -2).
4.1. Вычислим |Ñ f (X 1)| и проверим критерий окончания: |Ñ f (X 1)|= 
= 
>0,1. Переходим к шагу 5.
5.1. Проверим условие k > k 0: k =1<10= k 0. Переходим к шагу 6.
6.1. Зададим h 1=0,2.
7.1. Вычислим X 2= X 1-0,2Ñ f (X 1)=(-0,6; -0,2)-0,2(-4; -2)=(0,2; 0,2).
8.1. Проверим выполнение условия f (X 2)- f (X 1)<0. Так как f (X 2)=0,28, f (X 1)=1,4, то условие выполняется: f (X 2)- f (X 1)=0,28-1,4=-1,12. Переходим к шагу 9.
9.1. Проверим условия r (X 2, X 1)<0,1 и | f (X 2)- f (X 1)|<0,1. Второе условие не выполняется: | f (X 2)- f (X 1)|=1,12>0,1. Полагаем k =2 и переходим к шагу 3.
3.2. Вычислим Ñ f (X 2)=(1,6; 1,2).
4.2. Вычислим |Ñ f (X 1)| и проверим критерий окончания: |Ñ f (X 1)|= 
=2>0,1. Переходим к шагу 5.
5.2. Проверим условие k > k 0: k =2<10= k 0. Переходим к шагу 6.
6.2. Зададим h 2=0,2.
7.2. Вычислим X 3= X 2-0,2Ñ f (X 2)=(0,2; 0,2)-0,2(1,6; 1,2)=(-0,12; -0,04).
8.2. Проверим выполнение условия f (X 3)- f (X 2)<0. Так как f (X 3)=0,056, f (X 2)=0,28, то условие выполняется: f (X 3)- f (X 2)=-0,224. Переходим к шагу 9.
9.2. Проверим условия r (X 3, X 2)<0,1 и | f (X 3)- f (X 2)|<0,1. Второе условие не выполняется: | f (X 3)- f (X 2)|=0,224>0,1. Полагаем k =3 и переходим к шагу 3.
3.3. Вычислим Ñ f (X 3)=(-0,8; -0,4).
4.3. Вычислим |Ñ f (X 3)| и проверим критерий окончания: |Ñ f (X 3)|=0,8944>0,1. Переходим к шагу 5.
5.3. Проверим условие k > k 0: k =3<10= k 0. Переходим к шагу 6.
6.3. Зададим h 3=0,2.
7.3. Вычислим X 4= X 3-0,2Ñ f (X 3)=(-0,12; -0,02)-0,2(-0,8; -0,4)=(0,04; 0,04).
8.3. Проверим выполнение условия f (X 4)- f (X 3)<0. Так как f (X 4)=0,0112, f (X 3)=0,056, то условие выполняется: f (X 4)- f (X 3)=-0,0448. Переходим к шагу 9.
9.3. Проверим условия r (X 4, X 3)<0,1 и | f (X 4)- f (X 3)|<0,1. Второе условие выполняется: | f (X 4)- f (X 3)|=0,0448<0,1. Для первого имеем
r (X 4, X 3)= 
= 
»0,1789>0,1,
и условие не выполняется. Полагаем k =4 и переходим к шагу 3.
3.4. Вычислим Ñ f (X 4)=(0,32; 0,24).
4.4. Вычислим |Ñ f (X 4)| и проверим критерий окончания: |Ñ f (X 4)|=0,4>0,1. Переходим к шагу 5.
5.4. Проверим условие k > k 0: k =4<10= k 0. Переходим к шагу 6.
6.4. Зададим h 4=0,2.
7.4. Вычислим X 5= X 4-0,2Ñ f (X 4)=(0,04; 0,04)-0,2(0,32; 0,24)=(-0,024; -0,008).
8.4. Проверим выполнение условия f (X 5)- f (X 4)<0. Так как f (X 5)=0,0022, f (X 4)=0,0112, то условие выполняется: f (X 5)- f (X 4)=-0,009. Переходим к шагу 9.
9.4. Проверим условия r (X 5, X 4)<0,1 и | f (X 5)- f (X 4)|<0,1. Второе условие выполняется: | f (X 5)- f (X 4)|=0,009<0,1. Для первого имеем
r (X 5, X 4)= 
= 
»0,08<0,1,
и условия выполняются. Условия должны выполняться для текущего k и k -1. Поэтому полагаем k =5 и переходим к шагу 3.
3.5. Вычислим Ñ f (X 5)=(-0,16; -0,08).
4.5. Вычислим |Ñ f (X 5)| и проверим критерий окончания: |Ñ f (X 5)|=0,1799>0,1. Переходим к шагу 5.
5.5. Проверим условие k > k 0: k =5<10= k 0. Переходим к шагу 6.
6.5. Зададим h 5=0,2.
7.5. Вычислим
X 6= X 5-0,2Ñ f (X 4)=(-0,024; -0,008)-0,2(-0,16; -0,08)=(0,008; 0,008).
8.5. Проверим выполнение условия f (X 6)- f (X 5)<0. Так как f (X 6)=0,0005, f (X 5)=0,0022, то условие выполняется: f (X 6)- f (X 5)=-0,0017. Переходим к шагу 9.
9.5. Проверим условия r (X 6, X 5)<0,1 и | f (X 6)- f (X 5)|<0,1. Второе условие выполняется: | f (X 6)- f (X 5)|=0,0017<0,1. Для первого имеем
r (X 6, X 5)= 
»0,0358<0,1.
Так как оба условия выполнены при текущем значении k =5 k -1=4, то расчёт окончен: X *= X 5=(-0,024; -0,008).
II. Анализ точки X 5.
Функция f (x 1, x 2)=3 +2 x 1 x 2+2 является дважды дифференцируемой. Так как матрица Гессе - постоянна и является положительно определённой, то точка X 5 является точкой локального минимума, а значение f (X 5)=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. Задать X 0, e 1>0, e 2>0, k 0 - предельное число итераций. Найти Ñ f (X 0) и H (X 0).
2. Положить k =0.
3. Вычислить Ñ f (Xk).
4. Проверить условие выполнения критерия окончания |Ñ f (Xk)|< e 1:
а) если неравенство выполнено, то расчёт закончен: X *= Xk;
б) если критерий не выполнен, то перейти к шагу 5.
5. Проверить выполнение неравенства k ³ k 0:
а) если неравенство выполнено, то расчёт окончен: 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)< e 2 и | f (Xk +1)- f (Xk)|< e 2:
а) если оба условия выполнены при текущем значении k и k -1, то расчёт окончен: X *= Xk;
б) если хотя бы одно условие не выполнено, то положить k = k +1 и перейти к шагу 3.
Как и в случае метода градиентного спуска, сходимость метода Ньютона гарантируется для сильно выпуклых функций. Поэтому также необходимо проверять, является ли найденная точка приближением искомой X *.
Пример II. Решить задачу из примера I методом Ньютона.
Решение. Мы уже убедились (при решении примера I), что сходимость итерационного процесса гарантирована. Так что, осталось найти X * и провести его анализ.
I. Найдём Xk.
1. Зададим X 0=(1, 1), e 1=0,1, e 2=0,1, k 0=10 и найдём градиент Ñ f (X)=(6 x 1+2 x 2, 2 x 1+4 x 2) и H (X)= (см. решение примера I).
2. Положим k =0.
3.0. Вычислим Ñ f (X 0)=(8; 6).
4.0. Проверим критерий окончания: |Ñ f (X 0)|=10>0,1. Переходим к шагу 5.
5.0. Проверим условие k > k 0: k =0<10= k 0. Переходим к шагу 6.
6.0. Вычислим матрицу H (X 0)= .
7.0. Вычислим матрицу H (X 0)= 
= 
.
8.0. Проверим выполнение условия H (X 0)>0. Так как D1=0,2, D2= 
=0,05>0, то условие выполнено. Переходим к шагу 9.
9.0. Определим D 0:
D 0=- H (X 0)Ñ f (X 0)=- 
= 
.
10.0. Определим X 1= X 0+ h 0 D 0, полагая h 0=1 (так как D 0=- H (X 0)Ñ f (X 0)): X 1=(1; 1)+(-1; -1)=(0; 0).
11.0. Проверим условия r (X 1, X 0)<0,1 и | f (X 1)- f (X 0)|<0,1. Имеем
r (X 1, X 0)= 
= 
>0,1,
то есть первое условие не выполнено. Полагаем k =1 и переходим к шагу 3.
3.1. Вычислим Ñ f (X 1)=(0; 0).
4.1. Проверим критерий окончания |Ñ f (X 1)|<0,1: |Ñ f (X 1)|=0. Расчёт окончен: X *= X 1=(0; 0).
II. Анализ точки X 1.
Функция f (x 1, x 2)=3 +2 x 1 x 2+2 является строго выпуклой, так как матрица Гессе - постоянна и является положительно определённой. Поэтому точка X 1 является точкой локального минимума, а значение f (X 1)=0 - приближённое значение локального минимума (на самом деле это - точное значение локального минимума).
Ответ: точкой локального минимума является точка X *=(0; 0), f (X *)=0 - локальный минимум.