Методы нахождения условного и безусловного экстремума

х(5) = [-2.5822;0,9533]T; х(6) = [-0.9533;-2.5822]T; х(7) = [2.2474; 2.2474]T

f(x(5))= 50.149;

f(x(6))= 50.149;

f(x(7))= 11.194.

Так как f(x(5))= f(x(6))=max, то заменить можно x(5) и x(6). Заменим x(6).

х(8) = х(5) + х(7) ‑ х(6);             

х(8) = [-1.2881; 5.7829]T.             

7-я итерация:

х(5) = [-2.5822;0,9533]T; х(7) = [2.2474; 2.2474]T; х(8) = [-1.2881; 5.7829]T.

f(x(5))= 50.149; – max => заменяем

f(x(7))= 11.194;

f(x(8))= 23.6938.

х(9) = х(7) + х(8) ‑ х(5);

х(9) = [3.5415; 7.077]T.

8-я итерация:

х(7) = [2.2474; 2.2474]T; х(8) = [-1.2881; 5.7829]T; х(9) = [3.5415; 7.077]T.

f(x(7))= 11.194;

f(x(8))= 23.6938;

f(x(9))= 34.741. – max

Так как наибольшее значение целевой функции соответствует х(9), которое получено на предыдущей итерации, отбрасываем х(8).

х(10) = х(7) + х(9) ‑ х(8);

х(10) = [7.077; 3.5415]T.

9-я итерация:

х(7) = [2.2474; 2.2474]T; х(9) = [3.5415; 7.077]T; х(10) = [7.077; 3.5415]T.

f(x(7))= 11.194;

f(x(9))= 34.741;

f(x(10))= 34.741;

Так как f(x(9))= f(x(10))=max, то заменить можно x(9) и x(10). Заменим x(9).

х(11) = х(7) + х(10) ‑ х(9);             

х(11) = [5.7829;-1.2881]T.

10-я итерация:

х(7) = [2.2474; 2.2474]T; х(10) = [7.077; 3.5415]T; х(11) = [5.7829;-1.2881]T.

f(x(7))= 11.194;

f(x(10))= 34.741 – max => заменяем

f(x(11))= 23.6938.

х(12) = х(7) + х(11) ‑ х(10);             

x(12) = [0.9533;-2.5822]T = x(6).

11-я итерация:

х(7) = [2.2474; 2.2474]T; x(11) = [5.7829;-1.2881]T; х(12) = [0.9533;-2.5822]T.

f(x(7))= 11.194;

f(x(11))= 23.6938;

f(x(12))= 50.146 – max

Так как наибольшее значение целевой функции соответствует х(12), которое получено на предыдущей итерации, отбрасываем х(11).

х(13) = х(7) + х(12) ‑ х(11);

x(13) = [-2.5822; 0.9533]T = х(5).

Симплекс сделал 1 оборот в области расположения точки х(7), т.е. точку х(7) при заданных условиях можно считать точкой минимума целевой функции f(x1,x2) (для получения более точного решения необходимо уменьшить размер симплекса).

Таким образом, точка = [2.2474; 2.2474]Т – точка минимума, значение функции в которой f() = 11.194.

Рис 2.  Графическое пояснение метода равномерного симплекса

4.3 Метод Хука-Дживса

Описание алгоритма

Процедура Хука-Дживса представляет собой комбинацию “исследующего” поиска с циклическим изменением переменных и ускоряющего поиска по найденному образцу. Исследующий поиск ориентирован на выявление характера локального поведения целевой функции и определение направления вдоль “оврагов”. Полученная в результате исследующего поиска информация используется затем в процессе поиска по образцу при движении по “оврагам”. 

Исследующий поиск:

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

Поиск по образцу:

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

xр(к + 1) = x(к) + [x(к) - x(к - 1)].

Как только движение по образцу не приводит к уменьшению целевой функции, точка xр(к + 1)  фиксируется в качестве временной базовой точки и выполняется исследующий поиск. При уменьшении значения целевой функции эта точка рассматривается как новая базовая точка. Если же исследующий поиск не дал результата, необходимо вернуться в предыдущую точку и провести исследующий поиск заново. Если такой поиск не приводит к успеху необходимо уменьшить величину шага. Поиск завершается, когда величина шага приращения становится достаточно малой.

Шаг1. Задать:

              1. Начальную точку х(0);

              2. Приращение  Di , i=1,2…,N;

              3. Коэффициент уменьшения шага a>1;

              4. Параметр окончания поиска e>0.

Шаг2. Произвести исследующий поиск.             

Шаг3. Поиск удачный

                            Да:              Перейти к шагу 5;

                            Нет:              продолжить.

Шаг4. Проверка на окончание поиска. ||D||<e ?

                            Да:              прекратить поиск;

                            Нет:              уменьшить приращение по формуле    Di=Di/a,  i=1,2…N;

                                          Перейти к шагу 2.

Шаг5. Провести поиск по образцу              xр(к + 1) = x(к) + [x(к) - x(к - 1)]

Шаг6. Провести исследующий поиск, используя xр(к + 1) в качестве базовой точки ; x(к + 1)  - полученная в результате точка.

Шаг7. Выполняется ли f(x(k+1))<f(x(k))?

Да:              положить x(к - 1)= хк;  xк= x(к + 1);

Перейти к шагу 5; 

Нет:              Перейти к шагу 4.             

Нахождение минимума целевой функции методом Хука-Дживса.

Исходные данные:

f(х1,х2)=(х1–4)2+(х2–4)2 +х1·х2.

x(0) = [-10,-10]T – начальная точка;

х =1 – векторная величина приращения;

 – коэффициент уменьшения шага.

Минимизируем значение целевой функции до первого сокращения шага поиска:

1).

х(0)=[-10;-10]T Þ f (x(0))= 492.

Исследующий поиск вокруг базовой точки х(0):

фиксируя х2, даём приращение переменной х1:

х2=-10;              х1=-10+1=-9 Þ f(-9;-10) = 455<492 - поиск удачен;

фиксируя х1, даём приращение переменной х2:

х1=-9;               х2=-10+1=-9 Þ f(-9;-9) = 419<455 - поиск удачен.

х(1) = [-9;-9]T; Þ f(х(1))= 419, х(1) – базовая точка.

Т.к. поиск  удачен, переходим к поиску по образцу:

хp(2) = 2·х(1) – х(0);

хp(2) = [-8;-8]TÞ f (xp(2))= 352<f(х(1))= 419.

2).

Исследующий поиск вокруг точки хp (2):

фиксируя х2, даём приращение переменной х1:

х2=-8;              х1=-8+1=-7 Þ f(-7;-8) = 321< f (xp(2))=352 - поиск удачен;

фиксируя х1, даём приращение переменной х2:

х1=-7;               х2=-8+1=-7 Þ f(-7;-7) = 291<321 - поиск удачен.

х(2) = [-7;-7]T; Þ f(х(2))=291<f(х(1))=419 Þ х(2) – новая базовая точка.

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (3) = 2·х(2) – х(1);

хp (3) = [-5;-5] Þ f(хp (3)) =187<f(х(2))=291.

3).

Исследующий поиск вокруг точки хp (3):

фиксируя х2, даём приращение переменной х1:

х2=-5;              х1=-5+1=-4 Þ f (-4;-5)=165< f(хp (3)) =187 - поиск удачен;

фиксируя х1, даём приращение переменной х2:

х1=-4;    х2=-5+1=-4 Þ f (-4;-4)=144<165 - поиск удачен.

х(3) = [-4;-4]T; Þ f(х(3))=144<f(х(2))=291 Þ х(3) – новая базовая точка.

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (4) = 2·х(3) – х(2);

хp (4) = [-1;-1]T Þ f(хp (4))=51<f(х(3))=144.

4).

Исследующий поиск вокруг точки хp (4):

фиксируя х2, даём приращение переменной х1:

х2=-1;              х1=-1+1=0 Þ f (0;-1)=41<f(хp (4))=51 - поиск удачен;

фиксируя х1, даём приращение переменной х2:

х1=0;    х2=-1+1=0 Þ f (0;0)=32<41 - поиск удачен.

х(4) = [0;0]T; Þ f(х(4))=32<f(х(3))=144 Þ х(4) – новая базовая точка.

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (5) = 2·х(4) – х(3);

хp (5) = [4;4]T Þ f(хp (5)) =16<f(х(4))=32.

5).

Исследующий поиск вокруг точки хp (5):

фиксируя х2, даём приращение переменной х1:

х2=4;              х1=4+1=5Þ f(5;4) =21>f(хp (5))=16 - поиск  неудачен;

х2=4;              х1=4-1=3Þ f(3;4) =13<f(хp (5)) =16 - поиск  удачен;

фиксируя х1, даём приращение переменной х2:

х1=3;              х2=4+1=5Þ f(3;5) =17>13 - поиск  неудачен;

х1=3;              х2=4-1=3 Þ f(3;3) =11<13 - поиск  удачен.

х(5) = [3;3]T; Þ f(х(5))=11<f(х(4))=32 Þ х(5) – новая базовая точка.

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (6) = 2·х(5) – х(4);

хp (6) = [6;6]T Þ f(хp (6))=44 >f(х(5))=11.

Значение целевой функции увеличилось, поэтому возьмём последнюю точку за временную базовую и проведём исследующий поиск.

6).

Исследующий поиск вокруг точки хp (6):

фиксируя х2, даём приращение переменной х1:

х2=6;              х1=6+1=7 Þ f(7;6)=55>f(хp (6))=44 - поиск  неудачен;

х2=6;              х1=6-1=5 Þ f(5;6)=35<f(хp (6))=44 - поиск  удачен;

фиксируя х1, даём приращение переменной х2:

х1=5;              х2=6+1=7 Þ f(5;7)=45>35 - поиск  неудачен;

х1=5;              х2=6-1=5 Þ f(5;5)              =27<35 - поиск  удачен.

х(6) = [5;5]T; Þ f(х(6))=27>f(х(5))=11 Þ возврат в точку х(5).

7).

Исследующий поиск вокруг точки х(5):

фиксируя х2, даём приращение переменной х1:

х2=3;              х1=3+1=4 Þ f(4;3)=13>f(х(5))=11 - поиск  неудачен;

х2=3;              х1=3-1=2 Þ f(2;3)=11=f(х(5))=11 - поиск  неудачен;

фиксируя х1, даём приращение переменной х2:

х1=3;              х2=3+1=4 Þ f(3;4)=13>f(х(5))=11 - поиск неудачен;

х1=3;              х2=3-1=2 Þ f(3;2)              =11=f(х(5))=11 - поиск неудачен.

В результате исследующего поиска не было достигнуто уменьшение значения целевой функции, т.е. значение шага нужно уменьшить до х = 1/2=0.5.

Таким образом, точка = [3;3]Т – точка минимума, значение функции в которой f() = 11.

Для более точного решения необходимо произвести исследующий поиск вокруг точки х(5) = [3;3], используя новое значение приращения х =0.5.

Итерации продолжаются, пока величина шага не укажет на окончание поиска в окрестности точки минимума.

Рис 3.  Графическое пояснение метода Хука-Дживса

4.4 Метод сопряженных направлений Пауэлла

Описание алгоритма

Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, если квадратичная функция

              q(x) = a + bTx + ½ xT C x

приводится к виду суммы полных квадратов

              Q(x) = xT C x,

то процедура нахождения оптимального решения сводится к N одномерным поискам по преобразованным координатным направлениям.

В методе Пауэлла поиск реализуется в виде

              х(k+1) = x(k) + l×s(j)

вдоль направлений s(j),  j = 1,2,...,N, называемых C-сопряженными при линейной независимости этих направлений.

Сопряженные направления определяются алгоритмически. Для нахождения экстремума квадратичной функции N переменных необходимо выполнить N2 одномерных поисков.

Шаг 1. задать исходные точки х(1), х(2) и направление d. В частности, направление d может совпадать с направлением координатной оси;

Шаг 2. произвести одномерный поиск из точки х(1) в направлении d и получить точку y(1), являющуюся точкой экстремума на заданном направлении;

Шаг 3. произвести поиск из точки х(2) в направлении d и получить точку y(2);

Шаг 4. вычислить направление (y(2) – y(1));

Шаг 5. провести одномерный поиск из точки у(1) (либо у(2)) в направлении (y(2) – y(1)) с выходом в точку х*.

Нахождение минимума целевой функции методом сопряжённых направлений Пауэлла.

Исходные данные:

f(х1,х2)=(х1–4)2+(х2–4)2 +х1·х2.

x(0) = [-10,-10]T – начальная точка.

f(х(0) ) = 492;

ШАГ 1:

s( 1 ) = [1;0]T, s( 2 ) = [0;1]T.

ШАГ 2:

а) Найдём значение λ, при котором f(х) минимизируется в направлении s(1):

x=x(0) + λ·s(1) = [-10;-10]Т + λ·[1;0]Т.

Откуда х1=-10 + λ,  х2=-10.

Значение функции в этой точке: f(λ) = λ2 – 38·λ + 492.

Продифференцировав полученное выражение по λ, получим:

df/dλ =2·λ-38. Приравняв его к нулю, находим λ* = 19;

Получили  х(1) = [-10;-10]Т + 19·[1;0]Т= [9;-10] Т.

f(x(1) ) = 131.

б) Аналогично находим значение λ, минимизирующее функцию в направлении s(2).

x=x(1) + λ·s(2) = [9;-10]Т + λ·[0;1]Т;

Откуда х1=9,  х2 = -10+λ.

Значение функции в этой точке: f(λ) = λ2 - 19·λ + 131.

Продифференцировав полученное выражение по λ, получим:

df/dλ = 2·λ-19. Приравняв его к нулю, находим λ* = 9.5;

Получили  х(2) = [9;-10]Т + 9.5·[0;1]Т= [9;-0.5] Т.

f(x(2) ) = 40.75.

в) Найдём значение λ, минимизирующее f(x(2) + λ·s(1) ):

x=x(2) + λ·s(1) = [9;-0.5]Т + λ·[1;0]Т

Откуда х1=9 + λ,  х2 = -0.5.

Значение функции в этой точке: f(λ) = λ2+9.5·λ+40.75.

Продифференцировав полученное выражение по λ, получим:

df/dλ = 2·λ+9.5. Приравняв его к нулю, находим λ* = -4.75;

Получили  х(3) = [4.25 ; -0.5]T.

f(x(3) ) = 18.1875.

ШАГ 3:

s(3) = x(3) – x(1) = [4.25-9; -0.5-(-10)]T = [-4.75; 9.5]T .

ШАГ 4:

Найдем такое λ, при котором f(х(3)  + λ·s(3) ) минимально.

x(4)=x(3) + λ·s(3) = [4.25 ; -0.5]Т + λ·[-4.75 ; 9.5]Т.

Откуда х1=4.25-4.75·λ,  х2 = -0.5+9.5·λ.

Подставим эти значения в выражение целевой функции:

f(λ) = 67.6875·λ2-45.125·λ+18.1875.