1. Необходимые и достаточные условия безусловного экстремума. Численные методы поиска безусловного экстремума. Методы первого порядка (8 практических занятий с сайта кафеды 805), страница 2

Перейдем к шагу 5.5 2 . Проверим условие k  M : k  2  10  M , перейдем к шагу 6.6 2 . Зададим t 2  0,25 .7 2 . Вычислим x 3 : x 3    0,094; 0,25  0,25   0,126; 0,406TT    0,063; 0,15 ;f x 3  0,021 .      x и f x   f x  : 0,105  0,15 ;f x   f x   0,035  0,15 .82 . Сравним f x 3 и f x 2 . Вывод: f x 3  f x 2 . Перейдем к шагу 9.92 . Вычислим x 3x3  x223232Вывод: положим k  3 и перейдем к шагу 3.   f x  : f x 33 .

Вычислим f x 3 : f x 3    0,102; 0,237 .43 . Вычислим33T 0,257  0,1 . Перейдем к шагу 5.53 . Проверим условие k  M : k  3  10  M , перейдем к шагу 6.63 . Зададим t3  0,25 .153T73 . Вычислим x 4 : x 4    0,063; 0,15  0,25   0,102; 0,237T T   0,038; 0,091 ;Tf x 4  0,0076 .      9 . Вычислим x  x , f x   f x  :x  x  0,064  0,15 ;f x   f x   0,015  0,15 .  f x    выполнены при k  2,3 . РасчетУсловияxx  ,f xокончен.

Найдена точка x    0,038; 0,091 ; f  x   0,0076 .83 . Сравним f x 4 и f x 3 : f x 4  f x 3 .344k 13433k4k 123k2T44II. Проведем анализ точки x 4 . Функция f  x   2 x12  x1x 2  x 2 2 является дваждыдифференцируемой, поэтому проведем проверку достаточных условий минимума в точке 4 1x 4 . Для этого проанализируем матрицу Гессе H   . Матрица является постоянной 1 2и положительно определенной (т.е. H  0 ), так как оба ее угловых минора  1  4 и 2  7 положительны. Следовательно, точка x 4    0,038; 0,091Tесть найденное при- ближение точки локального минимума x   0,0 , а значение f x 4  0,0076 есть найT денное приближение значения f x   0 . Б.

МЕТОД НАИСКОРЕЙШЕГО ГРАДИЕНТНОГО СПУСКААлгоритмШаг 1. Задать x 0 , 1  0 ,  2  0 , предельное число итераций M. Найти градиентT  f (x ) f (x )  .функции в произвольной точке f ( x )  ,...,xx1n Шаг 2. Положить k  0 . Шаг 3. Вычислить f x k . Шаг 4. Проверить выполнение критерия окончания f x kа) если критерий выполнен, то x   x k ;б) если критерий не выполнен, то перейти к шагу 5.Шаг 5. Проверить выполнение неравенства k  M :а) если неравенство выполнено, то x   x k ;б) если нет, то перейти к шагу 6.Шаг 6.

Вычислить величину шага t k из условия.   mintt k   f x k  t k f x kk154 1 : Шаг 7. Вычислить x k 1  x k  t k f x k .Шаг 8. Проверить выполнение условийx k 1  x k   2 ,  f x k 1  f x k 2 :а) если оба условия выполнены при текущем значении k и k  k  1 , то расчетокончен, x   x k 1 ;б) если хотя бы одно из условий не выполнено, то положить k  k  1 и перейти кшагу 3.Геометрическая интерпретация метода для n  2 приведена на рис.

2.C1  C 2x2f ( x )  C1x0 f ( x 0 )x1f (x )  C 2x1Рис. 2Пример 2. Найти локальный минимум функцииf  x   2 x12  x1x 2  x 2 2 . I. Определим точку x k , в которой выполнен по крайней мере один из критериевокончания расчетов.1. Зададим x 0 , 1 ,  2 , M : x 0  0,5;1 ; 1  0,1;  2  0,15; M  10 . Найдем граTдиент функции в произвольной точке f ( x )  (4 x1  x 2 ; x1  2 x 2 )T .2.

Положим k  0 .   f x  : f x 30 . Вычислим f x 0 : f x 0  3; 2,5 .4 0 . Вычислим00T 3,9  0,1 . Перейдем к шагу 5.5 0 . Проверим условие k  M : k  0  10  M , перейдем к шагу 6.6 0 . Следующую точку найдем по формулеx 1  x 0  t 0 f ( x 0 )  (0,5; 1)T  t 0 (3; 2,5)T  (0,5  3t 0 ; 1  2,5  t 0 )T .155Подставим полученные выражения x11  0,5  3t 0 , x 21  1  2,5  t 0 для координатв f ( x ) : (t 0 )  2  (0,5  3t 0 ) 2  (0,5  3t 0 )  (1  2,5  t 0 )  (1  2,5  t 0 ) 2 . Найдем минимумфункции (t 0 ) по t 0 с помощью необходимых условий безусловного экстремума:d(t 0 )dt 0 4  (0,5  3t 0 )  (3)  (3)  (1  2,5t 0 )  (2,5)  (0,5  3t 0 )  2  (1  2,5  t 0 )  (2,5) d 2 (t 0 ) 63,25  0 , найденное знаdt 02чение шага обеспечивает минимум функции (t 0 ) по t 0 .Заметим, что можно получить формулу для вычисления наилучшей величины шагаt k на любой итерации из условия 15,25  63,25  t 0  0 .

Отсюда t 0  0,24 . Так как.   mintt k   f x k  t k f x kИмеем  f x k  4 x1k  x 2k ; x1k  x 2kTk  2k1k2t k  x  t (4x  x )x  x  t ( x  x ) .(t k )  2 x1k  t k (4 x1k  x 2k )Из условия4 4 x1  x 2k 24 x1k 2 4 x1Определим t 0 : t 0  0,24 .k12k1 k2 t k (x1k  x 2k )  2x 2 kkk 2x 2  2 x2Tk 2.k 2x 2T   0,22; 0,4 .17 0 . Найдем x 1  x 0  t 0 f x 0 : x 1  0,5;1  0,243; 2,5T   :80 .

Вычислим x 1  x 0 : x 1  x 0  0,937  0,15 . Вычислим f x 1  f x 0   f x1  f x 0 1,83  0,15 . Вывод: положим k  1 и перейдем к шагу 3.   f x   0,752  0,1 .31 . Вычислим f x 1 : f x 1    0,48; 0,58 .41 . ВычислимT151 . Проверим условие k  M : k  1  10  M .61 .

Определим t1 : t1  0,546 (см. п. 6 0 ). 71 . Найдем x 2  x 1  t1 f x 1 :x 2    0,22; 0,4  0,546   0,48; 0,58Tx 2  x1 0,04; 0,08 .TT    0,41  0,15 ;f x   f x 81 . Вычислим x 2  x 1 ,f x 2  f x1 :21562k12k2k2  x x x x2kkk1kkd 0 получаемdt kk; x k  t k f x k  x1k  t k 4 x1k  x 2k ; x 2k  t k x1k  x 2k1 0,156  0,15 .T,Положим k  2 и перейдем к шагу 3.   f x  : f x 32 . Вычислим f x 2 : f x 2  0,24; 0,2 .4 2 .

Вычислим22T 0,312  0,1 .5 2 . Проверим условие k  M : k  2  10  M .6 2 . Определим t 2 : t 2  0,24 (см. п. 6 0 ). 7 2 . Найдем x 3  x 2  t 2 f x 2 :x 3  0,04; 0,08 0,24 0,24; 0,2T   0,0176; 0,032 .T   : 0,0749  0,15 ;f x   f x 82 . Вычислим x 3  x 2 ,x3  x2Tf x3  f x232 0,0116  0,15 .Положим k  3 и перейдем к шагу 3.   f x  : f x , f  x   0,00127 .33 . Вычислим f x 3 : f x 3    0,012;  0,0816 .43 .

Вычислим3x 3    0,0176; 0,032T3T 0,082  0,1 . Расчет окончен. Найдена точка3II. Проведем анализ точки x 3 . В примере 1 было показано, что точка x 3 являетсянайденным приближением точки минимума x  . ■В. МЕТОД ГАУССА–ЗЕЙДЕЛЯАлгоритмШаг 1. Задать x 00 , 1  0 ,  2  0 ; предельное число M циклов счета, кратное n ,где n – размерность вектора x . Найти градиент f x  .Шаг 2. Задать номер цикла j  0 .Шаг 3.

Проверить условие j  M :а) если j  M , то расчет окончен и x   x jk ;б) если j  M , то перейти к шагу 4.Шаг 4. Задать k  0 .Шаг 5. Проверить условие k  n  1 :а) если k  n  1 , то перейти к шагу 6;б) если k  n , то положить j  j  1 и перейти к шагу 3. Шаг 6. Вычислить f x jk . Шаг 7. Проверить выполнение условия f x jk 1 :а) если условие выполнено, то расчет окончен и x   x jk ;б) если нет, то перейти к шагу 8.157Шаг 8. Вычислить t k из условия  f x  t k   f  x jk  t k ek 1   min .tk  x k 1  x  x jk  f x   e k 1 .Шаг 9.

Вычислить x jk 1  x jk  t k x k 1  x  x jkШаг 10. Проверить выполнение условийx jk 1  x jk   2 ,  f x jk 1  f x jk 2 :а) если оба условия выполнены в двух последовательных циклах с номерами j иj  1 , то расчет окончен, найдена точка x   x jk 1 ;б) если не выполняется хотя бы одно условие, положить k  k  1 и перейти кшагу 5.Геометрическая интерпретация метода для n  2 приведена на рис. 3.x2f ( x )  C1C1  C 2x 01x 00x 02f ( x)  C 2x1Рис. 3Пример 3. Найти локальный минимум функцииf  x   2 x12  x1x 2  x 2 2 . I. Определим точку x jk , в которой выполнен хотя бы один из критериев окончания расчетов.1. Зададим x 00 , 1 ,  2 , M : x 00  0,5;1 , 1  0,1;  2  0,15; M  10 . Найдем граTдиент функции в произвольной точке f ( x )  (4 x1  x 2 ; x1  2 x 2 )T .2.

Зададим j  0 .30 . Проверим выполнение условия j  M : j  0  10  M .4 0 . Зададим k  0 .1585 0 . Проверим выполнение условия k  n  1 : k  0  1  n  1 .  f x 6 0 . Вычислим f x 00 : f x 00  3; 2,5 .7 0 . Проверим условие00T 1 : f x 00 3,9  0,1 .80 . Определим величину шага t 0 из условия  f x    min .t 0   f  x j 0  t 0 e1t0x0j1 x x  f (x )  e1 .Воспользуемся формулой при k  0, j  0 : x 01  x 00  t 0   x1  x  x 00  f (x ) Поскольку  4 x1  x 2x001 x xx  x 00x 01  (0,5; 1)T  t 0  3  (1; 0)T  (0,5  3t 0 ; 1)T 2  1  3 , e1  (1; 0)T , тоили x101  0,5  3t 0 , x 201  1 .

Подставляяполученные выражения в f ( x ) , имеем (t 0 )  2(0,5  3t 0 ) 2  (0,5  3t 0 )  1  1 .d(t 0 )Из необходимого условия экстремума 4  (0,5  3t 0 )  (3)  3  0 илиdt 0d 2 (t 0 )1. Так как 36  0 , то найденное значение шага4dt 0 2обеспечивает минимум функции (t 0 ) по t 0 .Можно показать, что в силу структуры заданной функции f  x  величина шага в36t 0  9  0находим t 0   f (x ) 1направлении   e1 не зависит от x k , является постоянной и равной .4  x1  x  x jk  f x  90 . Определим x 01  x 00  t 0  e1 :x1  x  x 00x 01    0,25;1 .T   f x   f x   0,875  2100 . Проверим условия x 01  x 00   2 ,x 01  x 00  0,25  0,15 ,01f x 01  f x 0000 2 : 1,125  0,15 .Положим k  1 и перейдем к шагу 5.51 .

Проверим условие k  n  1 : k  1  n  1 .  f x 61 . Вычислим f x 01 : f x 01  0;1,75 .71 . Проверим условие01T 1 :81 . Определим величину шага t1 из условияt1   f  x j1  t1 f x 01 1,75  0,1 .  f x  e2   min . x t12  x  x j1159  f (x ) Воспользуемся формулой при k  1, j  0 : x 02  x 01  t1  e2 .  x 2  x  x 01  f (x ) Поскольку  x1  2 x 2 x  x 01   0,25  2  1,75 , e 2  (0; 1)T , тоx2  x  x 01x 02  ( 0,25; 1)T  t1  1,75  (0; 1)T  ( 0,25; 1  1,75  t1 )T или x102   0,25; x202  1  1,75  t1 .Подставляя полученные выражения в f ( x ) , имеем(t1 )  2( 0,25)2  ( 0,25)  (1  1,75  t1 )  (1  1,75  t1 )2 .Из необходимого условия экстремумаd(t1 ) 0,25  1,75  2  (1  1,75  t1 )  (1,75)  0 или 2  1,75 2 t1  1,75 2  0dt1d 2 (t1 )1. Так как 2  1,75 2  0 , то найденное значение шага обеспечива22dt1ет минимум функции (t1 ) по t1 .находим t1 Можно показать, что в силу структуры функции f  x  величина шага в направле  f (x ) нии   e2  x 2  x  x jkостается постоянной и равной1.2  f x  T91 .