2.4 Методы с использованием производных 2-го порядка
2.4.1. Метод сопряженных направлений.
Методы, использующие сопряженные направления отличаются от метода наискорейшего спуска тем, что одномерный поиск осуществляется в сопряженных направлениях. Важной особенностью является быстрая сходимость за счет того, что при выборе направления используется матрица Гессе, которая описывает область топологии поверхности отклика в отличие от градиента, характеризующего направление только для данной точки. В частности, если целевая функция квадратичная, то можно получить точку минимума не более чем за количество шагов, равных размерности задачи.
Предположим,
что процесс поиска начинается в Х(1)
с произвольным единичным направлением
.
Тогда результатом первого одномерного
поиска будет
X(2) = X(1) + *(1)
,
где *(1)- результат минимизацииf(X(1) + *(1)) по.
Затем
новое направление
выбирается сопряженным с
из условия
В общем случае система n - линейно независимых направлений поиска S(1), S(2), …, S(n-1) называется сопряженной по отношению к некоторой положительно определенной (квадратичной) матрице Q, если
,
0 i j n - 1.
Сопряженность – понятие, аналогичное ортогональности, когда H = 1.
Для
квадратичной функции, преобразованной
к каноническому виду,
,
собственные значения
находятся на диагонали
Значения и знак коэффициентов канонической формы характеризует топологию поверхности, поэтому использование матрицы Гессе и обеспечивает высокую эффективность методов сопряженных направлений.
Пример расчета минимума функции методом сопряженных направлений.
Рассмотрим задачу минимизации функции f(x) = (x1 - 2)4 + (х1 - 2х2)2 из начальной точки Х(1) = [2.5 2.5]Т.
Выберем
произвольное начальное единичное
направление
= [0,87 ‑ 0,50]
и определим длину шага
Тогда
.
Следующее
направление
выбираем сопряженным к
.
Для этого используем два уравнения:
сопряженности и единичной нормировки.
Из этих уравнений следует, что
,
Далее определяем *(2)
и находим следующую точку
Результаты полного расчета методом сопряженных направлений представлены в таблице 2.9. Траектория поиска приведена на рис. 2.9.
Таблица 2.9
Расчет минимума функции f(x) = (x1 - 2)4 + (х1 - 2х2)2методом сопряженных направлений.
|
№ |
x1 |
x2 |
f(Х) |
f'(x1) |
f'(x2) |
f'’(x1) |
f'’(x1,x2) |
f'’(x2) |
s1 |
s2 |
λ |
ε |
|
1 |
2.500 |
2.500 |
6.313 |
-4.500 |
10.000 |
5.000 |
-4.000 |
8.000 |
0.870 |
-0.500 |
-0.9623 |
10.965 |
|
2 |
3.337 |
2.019 |
3.688 |
8.163 |
2.802 |
23.457 |
-4.000 |
8.000 |
0.156 |
0.132 |
3.0210 |
8.6303 |
|
3 |
2.867 |
1.620 |
0.704 |
1.864 |
1.490 |
11.025 |
-4.000 |
8.000 |
0.305 |
-2.193 |
-0.0602 |
2.3863 |
|
4 |
2.886 |
1.488 |
0.623 |
2.598 |
0.361 |
11.411 |
-4.000 |
8.000 |
0.082 |
0.053 |
3.5974 |
2.6226 |
|
5 |
2.590 |
1.297 |
0.121 |
0.815 |
0.014 |
6.180 |
-4.000 |
8.000 |
0.810 |
-6.086 |
0.0017 |
0.8153 |
|
6 |
2.589 |
1.307 |
0.121 |
0.766 |
0.102 |
6.160 |
-4.000 |
8.000 |
0.034 |
0.019 |
5.7630 |
0.7723 |
|
7 |
2.393 |
1.196 |
0.024 |
0.242 |
0.000 |
3.849 |
-4.000 |
8.000 |
0.991 |
-7.413 |
0.0005 |
0.2422 |
|
8 |
2.392 |
1.200 |
0.024 |
0.226 |
0.030 |
3.845 |
-4.000 |
8.000 |
0.030 |
0.016 |
4.3759 |
0.2280 |
|
9 |
2.261 |
1.131 |
0.005 |
0.071 |
0.000 |
2.820 |
-4.000 |
8.000 |
0.999 |
-7.449 |
0.0001 |
0.0715 |
|
10 |
2.261 |
1.132 |
0.005 |
0.067 |
0.009 |
2.819 |
-4.000 |
8.000 |
0.031 |
0.016 |
2.8411 |
0.0674 |
|
11 |
2.174 |
1.087 |
0.001 |
0.021 |
0.000 |
2.364 |
-4.000 |
8.000 |
1.000 |
-7.448 |
0.0000 |
0.0211 |
|
12 |
2.174 |
1.087 |
0.001 |
0.020 |
0.003 |
2.364 |
-4.000 |
8.000 |
0.031 |
0.016 |
1.8672 |
0.0200 |
|
13 |
2.116 |
1.058 |
0.000 |
0.006 |
0.000 |
2.162 |
-4.000 |
8.000 |
1.000 |
-7.446 |
0.0000 |
0.0063 |
Рис.2.9 Графическая иллюстрация поиска минимума методом сопряженных направлений.
ВАРИАНТЫ ЗАДАНИЙ ДЛЯ ВЫПОЛНЕНИЯ ПРАКТИЧЕСКИХ ЗАНЯТИЙ.
Выполнение заданий предусматривает:
для заданной функции поиск экстремума аналитически и его анализ;
построение линий уровня;
поиск минимума функции методами многомерной оптимизации, рассмотренными выше, при заданных параметрах;
выводы об эффективности методов.
Требования к отчету:
В отчете должны быть представлены результаты выполнения указанных этапов и выводы к ним. Отчет представляется индивидуально каждым студентом.
Таблица 3.1
Варианты заданий
|
№ |
Вид функции f(X) |
Начальная точка Х(1) |
Точность | |
|
х1(1) |
х2(1) | |||
|
1 |
(x1+2x2)2+(x2-3)2 |
0 |
10 |
0,01 |
|
2 |
(x1-4x2)2+(x2+5)2 |
10 |
-5 |
0,01 |
|
3 |
(x1-2x2)2+(x2+5)2 |
-15 |
5 |
0,02 |
|
4 |
(x1+x2)2+(x2+4)2 |
9 |
5 |
0,01 |
|
5 |
(x1-3x2)2+(x2-2)2 |
4 |
10 |
0,015 |
|
6 |
(x1-3x2)2+(x2+1)2 |
0 |
8 |
0,01 |
|
7 |
(x1+5x2)2+(x2-1)2 |
8 |
10 |
0,005 |
|
8 |
(x1-2x2)2+(x2-3)2 |
-7 |
-7 |
0,01 |
|
9 |
(x1+x2)2+(x2+2)2 |
6 |
-1 |
0,02 |
|
10 |
(x1+x2)2+(x2+6)2 |
10 |
8 |
0,01 |
|
11 |
(x1+x2)2+(x2-1)2 |
5 |
6 |
0,01 |
|
12 |
(x1-2x2)2+(x2-3)2 |
7 |
6 |
0,02 |
|
13 |
(x1+2x2)2+(x2-4)2 |
-4 |
7 |
0,02 |
|
14 |
(x1-6x2)2+(x2+1)2 |
-5 |
-3 |
0,015 |
|
15 |
(x1-5x2)2+(x2+6)2 |
-10 |
-5 |
0,015 |
|
16 |
(x1+4x2)2+(x2-3)2 |
-5 |
6 |
0,01 |
|
17 |
(x1+6x2)2+(x2+2)2 |
-10 |
7 |
0,01 |
|
18 |
(x1-7x2)2+(x2-2)2 |
8 |
6 |
0,02 |
|
19 |
(x1+3x2)2+(x2+5)2 |
10 |
10 |
0,02 |
|
20 |
(x1-8x2)2+(x2+1)2 |
-5 |
-5 |
0,015 |
|
21 |
(x1-x2)2+(x2-7)2 |
10 |
2 |
0,01 |
|
22 |
(x1+8x2)2+(x2-2)2 |
-10 |
5 |
0,015 |
|
23 |
(x1-5x2)2+(x2+3)2 |
-10 |
-5 |
0,01 |
|
24 |
(x1-2x2)2+(x2-9)2 |
15 |
12 |
0,01 |
|
25 |
(x1-6x2)2+(x2+9)2 |
-6 |
-5 |
0,01 |
|
26 |
(x1+9x2)2+(x2-1)2 |
7 |
3 |
0,015 |
|
27 |
(x1-3x2)2+(x2+5)2 |
-10 |
2 |
0,01 |
|
28 |
(x1-4x2)2+(x2 -1)2 |
5 |
9 |
0,015 |
|
29 |
(x1+4x2)2+(x2+1)2 |
6 |
10 |
0,01 |
|
30 |
(x1-5x2)2+(x2+5)2 |
11 |
1 |
0,01 |
СПИСОК ЛИТЕРАТУРЫ
Мочалов С.П. Методы оптимизации металлургических процессов: Учебное пособие / КузПИ. –Кемерово, 1989.- 81с.
Поляк Б. Т. Введение в оптимизацию. -М.: Наука, 1983.
Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. -М.: Наука, 1975.
Банди. Методы оптимизации. -М.: Радио и связь, 1988.
Курицкий Б.Я. Поиск оптимальных решений средствами Ecxel7.0. –СПб.:BHV– Санкт-Петербург, 1997.- 384с., ил.
Сергей Павлович Мочалов
Инна Анатольевна Рыбенко