УМК (1013374), страница 30
Текст из файла (страница 30)
Определить d k = − H −1 x k ∇f x k .Шаг 10. Найти точку x k +1 = x k + t k d k ,( ) ( )) < f (x ) , если dположив t k = 1 , если d k = − H −1 x k ∇f x k ,(или выбрав t k из условия f x k +1kШаг 11. Проверить выполнение условийx k +1 − x k < ε 2 ,(k( )= −∇f x k .) ( )f x k +1 − f x k< ε2 :а) если оба условия выполнены при текущем значении k и k = k − 1 , то расчетокончен, x ∗ = x k +1 ;б) в противном случае положить k = k + 1 и перейти к шагу 3.178Пример 5. Найти локальный минимум функции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⎛4 1⎞⎟⎟ .диент функции ∇f ( x ) = (4 x1 + x 2 ; x1 + 2 x 2 )T и матрицу Гессе H (x ) = ⎜⎜⎝1 2⎠2. Положим k = 0 .( )( )30 . Вычислим ∇f x 0 : ∇f x 0 = (3; 2,5) .T( )4 0 . Проверим выполнение условия ∇f x 0( )≤ ε1 : ∇ f x 0= 3,9 > 0,1 .
Перей-дем к шагу 5.5 0 . Проверим выполнение условия k ≥ M : k = 0 < 10 . Перейдем к шагу 6.⎛ 4 1⎞6 0 . Вычислим H x 0 : H x 0 = ⎜⎟.⎝ 1 2⎠1⎞⎛ 2− ⎟⎜7⎟.7 0 . Вычислим H −1 x 0 :H −1 x 0 = ⎜ 7⎜− 1 4 ⎟⎜⎟⎝ 7 7 ⎠280 . Проверим выполнение условия H −1 x 0 > 0 . Так как Δ 1 = > 0 ,71Δ 2 = > 0 , то согласно критерию Сильвестра H −1 x 0 > 0 .71⎞⎛ 2− ⎟⎛ 3 ⎞ ⎛ 1⎞⎜7 ⎟ ⎜ ⎟ = ⎜− ⎟ .90 . Определим d 0 = − H −1 x 0 ∇f x 0 = − ⎜ 7214⎟ ⎜⎝ 2,5 ⎟⎠ ⎜⎜ − 1 ⎟⎟⎜−⎜⎟⎝⎠⎝ 7 7 ⎠( ) ( )( )( )( )( )( ) ( )⎛1 ⎞10 .
Вычислим x = ⎜ ,1⎟⎝2 ⎠01T⎛ 1⎞+ ⎜ − ,−1⎟⎝ 2⎠T= (0, 0) .T110 . Проверим выполнение условий x 1 − x 0 < ε 2 ,( ) ( )f x1 − f x 0< ε2 :( ) ( ) = 2 > 0,15 . Положим k = 1 и перейдем к шагу 3.3 . Вычислим ∇f ( x ) : ∇f ( x ) = (0, 0) .x1 − x 0 = 1,12 > 0,15; f x1 − f x 0111T( )41 . Проверим выполнение условия ∇f x 1( )< ε1 : ∇f x 1= 0 < 0,1 .
Расчетокончен. Заметим, что в точке x 1 выполняется необходимое условие первого порядка,поэтому она является стационарной точкой.II. Проведем анализ точки x 1 . Для функции f ( x ) = 2 x12 + x1x 2 + x 2 2 матрица⎛ 4 1⎞вторых производных H = ⎜⎟ > 0 в силу того, что Δ 1 = 4 > 0, Δ 2 = 7 > 0 . Поэто⎝ 1 2⎠му точка x 1 = (0, 0)Tесть точка локального минимума целевой функции f ( x ) . 179Б.
МЕТОД НЬЮТОНА–РАФСОНААлгоритмШаг 1. Задать x 0 , ε1 > 0, ε 2 > 0 , M – предельное число итераций. Найти градиент ∇f (x ) и матрицу Гессе H (x ) .Шаг 2. Положить k = 0 .( )Шаг 3. Вычислить ∇f x k .( )Шаг 4. Проверить выполнение условия ∇f x k≤ ε1 :а) если неравенство выполнено, то расчет закончен и x ∗ = x k ;б) если нет, перейти к шагу 5.Шаг 5. Проверить выполнение условия k ≥ M :а) если неравенство выполнено, расчет окончен и x ∗ = x k ;б) если нет, перейти к шагу 6.( )Шаг 7. Найти обратную матрицу H ( x ) .Шаг 8.
Проверить выполнение условия H ( x ) > 0 :а) если условие выполняется, то найти d = − H ( x ) ∇f ( x ) ;б) если нет, то положить d = −∇f ( x ) .Шаг 6. Вычислить элементы матрицы H x k .−1k−1−1kkkkkkШаг 9. Определить x k +1 = x k + t k d k .()Шаг 10. Найти шаг t k∗ из условия ϕ(t k ) = f x k + t k d k → min .tkШаг 11.
Вычислить x k +1 = x k + t k∗ d k .Шаг 12. Проверить выполнение неравенствx k +1 − x k() ( )f x k +1 − f x k< ε2,< ε2 :а) если оба условия выполнены при текущем значении k и k = k − 1 , то расчетокончен и x ∗ = x k +1 ;б) в противном случае положить k = k + 1 и перейти к шагу 3.Пример 6. Найти локальный минимум функции 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⎛4 1⎞⎟⎟ .диент функции ∇f ( x ) = (4 x1 + x 2 ; x1 + 2 x 2 )T и матрицу Гессе H (x ) = ⎜⎜⎝1 2⎠2.
Положим k = 0 .180( )( )30 . Вычислим ∇f x 0 : ∇f x 0 = (3; 2,5) .T( )4 0 . Проверим выполнение условия ∇f x 0≤ ε1 :( )∇f x 0= 3,9 > 0,1 .5 0 . Проверим выполнение условия k ≥ M : k = 0 < 10 . Перейдем к шагу 6.( )( )⎛ 4 1⎞6 0 . Вычислим H x 0 : H x 0 = ⎜⎟.⎝ 1 2⎠⎛ 2⎜7 0 . Вычислим H −1 x 0 : H −1 x 0 = ⎜ 7⎜− 1⎜⎝ 7( )( )1⎞⎟7⎟.4 ⎟⎟7 ⎠−( )80 . Проверим выполнение условия H −1 x 0 > 0 .Так как Δ 1 =( )21> 0, Δ 2 = > 0 , то согласно критерию Сильвестра H −1 x 0 > 0 .770Поэтому найдем d = −H−1( x ) ∇f ( x ) : d00T⎛ 1⎞= ⎜ − ,− 1 ⎟ (см. шаг 90 примера 5).⎝ 2⎠0T0109 . Определим: x = x + t 0 d0T⎞⎛ 1⎛1 ⎞= ⎜⎜ , 1⎟⎟ + t 0 ⎜⎜ − , − 1 ⎟⎟⎠⎝ 2⎝2 ⎠T⎞⎛1 1= ⎜⎜ − t 0 ,1 − t 0 ⎟⎟ .⎠⎝2 2100 .
Определим t 0∗ из условия ϕ(t 0 ) = f ( x 0 + t 0 d 0 ) → min . Получимt0T⎛⎛ 1 1⎞⎜⎟⎜f ( x + t0 d ) = f ⎜ − t0 ,1 − t0 ⎟⎜ 2 2⎠⎝⎝00⎞⎟=⎟⎠2⎛1 1 ⎞⎛1 1 ⎞= 2 ⋅ ⎜⎜ − t0 ⎟⎟ + ⎜⎜ − t0 ⎟⎟ ⋅ (1 − t0 ) + (1 − t0 )2 = 2 ⋅ (1 − t0 )2 = ϕ(t0 ).⎝2 2 ⎠⎝2 2 ⎠dϕd 2ϕИз условия= 2 ⋅ 2 ⋅ (1 − t 0 ) ⋅ (−1) = 0 находим t 0∗ = 1 . При этом= 4 > 0 , т.е.dt 0d t 02найденная величина шага обеспечивает минимум функции ϕ(t 0 ) .01011 . Вычислим x = x +t0∗ d 0 :T⎞⎛1 1x = ⎜⎜ − ⋅ 1 , 1 − 1⎟⎟⎠⎝2 2112 0 . Проверим выполнение условийx1 − x 0x1 − x 0< ε2,( ) ( )= 1,12 > 0,15 ;= (0, 0 )T .( ) ( )f x1 − f x 0f x1 − f x 0= 2 > 0,15 .( )∇f x 1< ε2 :Положим k = 1 и перейдем к шагу 3.( )( )31 . Bычислим ∇f x 1 : ∇f x 1 = (0;0 )T .41 .
Проверим выполнение условия∇f x 1< ε1 :( )= 0 < 0,1 . Расчетокончен: x ∗ = x 1 .II. Проведем анализ точки x 1 . Точка x ∗ = (0;0 )T – точка локального и одновременно глобального минимума f ( x ) (см. пример 5). 181Занятие 5. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА УСЛОВНОГОЭКСТРЕМУМАА. МЕТОД ШТРАФОВПостановка задачиДаныдваждынепрерывнодифференцируемыецелеваяf ( x) = f ( x1,…, xn ) и функции ограничений g j ( x) = 0 , j = 1, … , m ;функцияg j ( x) ≤ 0 ,j = m + 1, … , p , определяющие множество допустимых решений Х.Требуется найти локальный минимум целевой функции на множестве Х , т.е. такую точку x ∗ ∈ X , чтоf ( x ∗ ) = min f ( x) ,x∈X⎧⎪где X = ⎨ x⎩⎪m < n ⎫⎪⎬.j = m + 1,… , p⎭⎪g j ( x) = 0,j = 1,… , m;g j ( x) ≤ 0,АлгоритмШаг 1. Задать начальную точку x 0 , начальное значение параметра штрафаr 0 > 0 , число C > 1 для увеличения параметра, малое число ε > 0 для остановки алгоритма.
Положить k = 0 .Шаг 2. Составить вспомогательную функцию()F x, r k = f ( x ) +rk2⎧⎪ m2⎨ ∑ [ g j ( x) ] +⎪⎩ j =1⎫+2⎪gx[()]⎬.∑ jj = m +1⎭⎪p(Шаг 3. Найти точку x ∗ ( r k ) безусловного минимума функции F x , r k)по хс помощью какого-либо метода (нулевого, первого или второго порядка):()()F x ∗ (r k ), r k = min F x, r k .x∈R nПри этом задать все требуемые выбранным методом параметры. В качестве начальной()точки взять x k . Вычислить P x ∗ (r k ), r k .Шаг 4. Проверить условие окончания:()а) если P x ∗ (r k ), r k ≤ ε , процесс поиска закончить:(x ∗ = x ∗ (r k ),()f ( x ∗ ) = f x ∗ (r k ) ;)б) если P x ∗ (r k ), r k > ε , положить: r k +1 = C r k , x k +1 = x ∗ ( r k ), k = k + 1 иперейти к шагу 2.182Пример 1.
Найти условный минимум в задачеf ( x) = x 2 − 4 x → min,g1 ( x) = x − 1 ≤ 0. 1. В поставленной задаче m = 0 (ограничения-равенства отсутствуют),p = 1 . Решим задачу аналитически при произвольном параметре штрафа r k , а затемполучим решение последовательности задач поиска безусловного минимума.2. Составим вспомогательную функцию:()F x, r k = x 2 − 4 x +rk[ max { 0, (x − 1) } ]2 .2(3. Найдем безусловный минимум функции F x , r k) пох с помощью необхо-димых и достаточных условий (см.
гл. 2 – лекция 1):()∂ F x, r k⎪⎧ 2 x − 4 = 0, x − 1 ≤ 0,=⎨∂x⎪⎩ 2 x − 4 + r k (x − 1) = 0, x − 1 > 0 .Отсюда x ∗ = 2 , но при этом не удовлетворяется условие x ∗ − 1 ≤ 0 , а также∗kx (r ) =4+rk2+rk.В табл. 1 приведены результаты расчетов при r k = 1, 2,10,100,1000, ∞ , а на рис. 1 данаграфическая иллюстрация процесса поиска решения.(Таблица 1krkx ∗ (r k )F x ∗ (r k ), r k0153−3,66123= 1,52−3,5210−3,1663100410005∞7= 1,1666652= 1,019651502= 1,001995011−3,019−3,002−3183)(f ( x ), F x , r k)x ∗ (10) x ∗ (2) x ∗ (1)Xx∗r1 = 221x3r0 = 1−1f (x )−2−3−4Рис. 1Так как((∂ 2 F x ∗ (r k ), r k)∂x2) = 2 + r k > 0 при rk≥ 0 , то достаточные условия ми-нимума F x , r k удовлетворяются. При r k → ∞ имеемx ∗ = lim4+ rkr → ∞ 2+rkkf ( x ∗ ) = −3 .= 1,Найдем решение этой задачи с применением необходимых и достаточных условий экстремума.
Функция Лагранжа имеет вид()L ( x , λ 0 , λ1 ) = λ 0 x 2 − 4 x + λ1 ( x − 1) .Необходимые условия минимума первого порядка:а)∂ L (x , λ 0 , λ 1 )∂x= λ 0 (2 x − 4 ) + λ1 = 0 ;б) x − 1 ≤ 0 ;в) λ1 ≥ 0 ;г) λ1 ( x − 1) = 0 .Решим систему для двух случаев.Первый случай: λ 0 = 0 , тогда из условия «а» получаем λ1 = 0 , что не удовлетворяет утверждению.184Второй случай: λ 0 ≠ 0 .
Поделив уравнения системы на λ 0 и заменивλ1на λ1 ,λ0получим 2 x − 4 + λ1 = 0 . Из условия «г» имеем λ1 = 0 или x = 1 . При λ1 = 0 из условия «а» следует, что x = 2 , но при этом не удовлетворяется условие «б». Приx ∗ = 1 имеем λ∗1 = 2 .Достаточные условия минимума первого порядка удовлетворяются, так как∗λ1 = 2 > 0 и число активных ограничений l = 1 = n . Пример 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
