semopt5 (Практические занятия)

Занятие 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. Найти условный минимум в задачеf ( x) = x12 + x 22 → min,g1 ( x) = x1 + x 2 − 2 = 0.† 1. В поставленной задаче m = 1 , ограничения-неравенства отсутствуют.

Решим ее аналитически.2. Составим вспомогательную функцию:()F x, r k = x12 + x 22 +(rk(x1 + x 2 − 2)2 .23. Найдем безусловный минимум F x , r kдостаточных условий:()())по х с помощью необходимых и∂ F x, r k= 2 x1 + r k (x1 + x 2 − 2) = 0 ,∂ x1∂ F x, r k= 2 x 2 + r k (x1 + x 2 − 2 ) = 0 .∂ x2Вычитая из первого уравнения второе, получаем x1 = x 2 иx1∗ (r k ) = x 2∗ (r k ) =rk.1+ r kВ табл. 2 приведены результаты расчетов при r k = 1, 2, 10, 100, 1000, ∞ , а на рис.

2дана графическая иллюстрация процесса поиска решения.(Таблица 2krkx1∗ (r k ) = x 2∗ (r k )F x ∗ (r k ), r k011122103100410005∞122310111001011000100111,3331,811,981,9982185)x22Ax 2∗x ∗ (10)=1x∗x ∗ ( 2)x1(1 )2x1∗ = 1g1 ( x) = x1 + x 2 − 2 = 0Рис. 2(∗kТак как матрица Гессе H x (r ), rk)⎛2+ rk=⎜⎜ rk⎝(таточные условия безусловного минимума F x , r kимеемrklimrk →∞ 1+ r)rk ⎞⎟ > 0 при r k > 0 , то досk⎟2+r ⎠удовлетворяются. При r k → ∞= 1 = x1∗ = x 2∗ ; f ( x ∗ ) = 2 . „kПример 3.

Найти условный минимум в задачеf ( x) = x12 + x 22 → min,g1 ( x) = x1 − 1 = 0,g 2 ( x) = x1 + x 2 − 2 ≤ 0.† 1. В задаче m = 1, p = 2 . Решим ее аналитически.2. Составим вспомогательную функцию:()F x, r k = x12 + x 22 +rk2{[x1}− 1]2 + [ max { 0, (x1 + x 2 − 2 ) } ]2 .()3. Найдем безусловный минимум F x , r k по х с помощью необходимых и достаточных условий:()()⎧⎪ 2 x1 + r k (x1 − 1) + r k (x1 + x 2 − 2 ) , x1 + x 2 − 2 > 0,∂ F x, r k=0=⎨∂ x1⎪⎩ 2 x1 + r k (x1 − 1) , x1 + x 2 − 2 ≤ 0,⎧⎪ 2 x 2 + r k (x1 + x 2 − 2) , x1 + x 2 − 2 > 0,∂ F x, r k=0=⎨∂ x2⎪⎩ 2 x 2 , x1 + x 2 − 2 ≤ 0 .Рассмотрим два случая.1861. Пусть x1 + x 2 − 2 > 0 .

Вычитая из первого уравнения второе, получаемx 2 = x1 +rk(x1 − 1) .2После подстановки в первое уравнение имеемx1∗ (r k ) =( r k ) 2 + 6r k( r k ) 2 + 6r k + 4x 2∗ (r k ),=( r k ) 2 + 4r k( r k ) 2 + 6r k + 4Однако при всех r k > 0 имеем x1∗ (r k ) + x 2∗ ( r k ) − 2 =−2r k − 8( r k ) 2 + 6r k + 4воречит условию x1 + x 2 − 2 > 0 для рассматриваемого случая.2. Пусть x1 + x 2 − 2 ≤ 0 . Тогда x 2∗ = 0 , а x1∗ (r k ) =rk.< 0 , что проти-. В табл. 3 приведены2+rkрезультаты расчетов, а на рис. 3 дана графическая иллюстрация процесса поиска решения.⎛ 2 + r k 0⎞kТак как матрица Гессе H x ∗ (r k ), r k = ⎜⎟⎟ > 0 при всех r > 0 , то⎜ 02⎠⎝достаточные условия минимума F x , r k удовлетворяются.

При r k → ∞ имеем()(x1∗ = limrkrk → ∞ 2 + rk= 1,x 2∗ = 0,)f ( x ∗ ) = 1. „(Таблица 3krkx1∗ ( r k )x 2∗ ( r k )F x ∗ (r k ), r k010122103100410005∞131256505150050115934353626002601251000251001100000187)x2g1 ( x) = x1 − 1 = 021x ∗ (1)x ∗ ( 2)2x∗1x ∗ (10)x1x1 + x 2 − 2 = 0Рис. 3Б. МЕТОД БАРЬЕРНЫХ ФУНКЦИЙПостановка задачиДаны дважды непрерывно дифференцируемые целевая функцияf ( x) = f ( x1,…, xn ) и функции ограничений-неравенств g j ( x) ≤ 0 , j = 1, … , m , определяющие множество допустимых решений Х.Требуется найти локальный минимум целевой функции на множестве Х, т.е.такую точку x ∗ ∈ X , чтоf ( x ∗ ) = min f ( x) ,где X ={x}x∈Xg j ( x) ≤ 0, j = 1,… , m .АлгоритмШаг 1.

Задать начальную точку x 0 внутри области Х, начальное значение параметра штрафа r k ≥ 0 , число C > 1 для уменьшения параметра штрафа, малое числоε > 0 для остановки алгоритма. Положить k = 0 .Шаг 2. Составить вспомогательную функцию:(F x, rk) = f ( x) − rkm∑j =1m1kkили F x, r = f ( x) − r ∑ ln ⎡⎣ − g j ( x) ⎤⎦ .g j ( x)j =1()(Шаг 3. Найти точку x ∗ ( r k ) минимума функции F x , r k) с помощьюкакого-либо метода (нулевого, первого или второго порядка) поиска безусловного минимумас проверкой принадлежности текущей точки внутренности множества Х. При этом задать все требуемые выбранным методом параметры. В качестве начальной точки взятьx k .

Вычислить:188()m1j =1g j x ∗ (r k )P x ∗ (r k ), r k = − r k ∑()(m)()или P x ∗ (r k ), r k = − r k ∑ ln ⎡⎢ − g j x ∗ (r k ) ⎤⎥ .⎣⎦j =1Шаг 4. Проверить выполнение условия окончания:() ≤ ε , процесс поиска закончить:x ∗ = x ∗ (r k ) ,f ( x ∗ ) = f ( x ∗ (r k ) ) ;rP ( x ∗ ( r k ), r k ) > ε , положить r=; x k +1 = x ∗ (r k ) , k = k + 1Cа) если P x ∗ ( r k ), r kб) еслиkk +1иперейти к шагу 2.З а м е ч а н и я.1.

Обычно выбирается r 0 = 1,10,100 , a параметр C = 10;12;16 .2. При r k → +0 обеспечивается сходимость, однако с уменьшением r k функ-(ция F x , r k) становится все более «овражной». Поэтому полагать rkмалым числомсразу нецелесообразно.Пример 4. Найти условный минимум в задачеf ( x) = x → min,g1 ( x) = 2 − x ≤ 0.† 1. Найдем решение аналитически с применением обратной штрафной функ-ции.()2.

Составим вспомогательную функцию: F x, r k = x − r k(1.2−xP ( x,r k ))3. Найдем безусловный минимум F x , r k с помощью необходимых и достаточных условий:()∂ F x, r krk=1−= 0 . Так как внутри множества допустимых∂x(2 − x )2решений 2 − x < 0 , то x = 2 ± r k , а x ∗ (r k ) = 2 + r k (результаты приведены втабл.4). Достаточные условия минимума выполняются:(∂ 2 F x ∗ (r k ), r k∂ x2)=−rk∗⎡ 2 − x (r ) ⎤⎣⎦k3> 0.(krkx ∗ (r k )F x ∗ (r k ), r k0123410,10,010,001032,312,12,03242,632,22,0632189)(Таблица 4P x ∗ (r k ), r k10,320,10,033-).