Metodi_optimizatsiyi

До останньої системи додаємо умову нормування, яка обмежує довжину вектора r s

Серед всіх можливих напрямків знаходимо напрямок r s , який мінімізує

похідну по напрямку r s від функції f (x ) в точці x s . Він є оптимальним розв’язком задачі мінімізації

з обмеженнями (11.11) i (11.12).

Розв'язавши задачу (11.11) –(11.13), перевіряємо умову:

•якщо оптимальне значення функції (11.13) невід'ємне, то кінець обчислень, оскільки підхожих напрямків в точці x s не існує; x s — стаціонарна точка функції f (x ) в області D;

•якщо оптимальне значення функції (11.13) від'ємне, то виконуємо дії пунктів 4,

5, 6, замінивши антиградієнт − f (x s ) вектором знайденого можливого i

підхожого напрямку r s.

Пpиклад 11.2. Розв'язати задачу комбінованим методом f (x1,x2) = (x1 − 6 )2 + (x2 − 4 )2 → min,

вибираючи x 0 = (2,4).

Розв’язування. Обчислимо градієнт f (x1,x2)

f (x1,x2) = (2 x1 − 12 , 2 x2 − 8 ) .

201

1-а iтеpацiя.

f (x 0 ) = (− 8 , 0) ≠ 0 .

Визначаємо активні обмеження в точці x 0 :

2 + 4 = 6 < 8,

2 + 3 × 4 = 14 < 18,

2 > 0,

4 > 0 .

Активних обмежень немає. Точка x 0 є внутрішньою точкою допустимої області задачі, тому напрямок антиградієнта − f (x 0 ) є можливим. Будуємо

(0,1/4 ] . Скоpистаємось необхідними умовами екстpемуму функції однієї змінної:

= −((2(2+8ρ)−12,0),(−8,0)) = 8(16ρ−8)=0,

звідки маємо ρ= 1/2 .

202

Оскiльки ця точка лежить праворуч від допустимого інтервалу, а функція g(ρ) опукла донизу, то мінімальне значення функції g(ρ) досягається на правому кінці допустимого інтервалу для ρ. Отже, ρ0 = 1/4.

Обчислюємо x 1 = x 0 −ρ0 f (x 0 ) = (2 , 4 ) −(1/4 ) (−8,0) = (4 , 4 ).

2-а iтеpацiя.

f (x 1 ) = (− 4 , 0) ≠ 0 .

Визначаємо активні обмеження в точці x 1: 4 + 4 = 8, (Активне обмеження)

4 + 3 × 4 = 16 < 18,

4 > 0,

4 > 0.

Пеpевipяємо, чи є антиградієнт − f (x 1) можливим напрямком. Будуємо промінь x(ρ), що виходить з точки x 1 в напрямі антиградієнта − f (x 1):

x(ρ) = x 1 −ρ f (x 1 ) = (4,4 ) −ρ(−4,0) = (4 +4ρ, 4 ), ρ> 0.

Пiдставляємо точку x 1 в активне обмеження: 4 +4ρ+ 4 ≤8 , звідки ρ≤0 .

Водночас повинно бути ρ> 0 . Тому − f (x 1) не є можливим напрямком. Визначимо можливий напрямок. Hехай r 1 = ( r11, r21) — вектор невідомого

можливого напрямку. Будуємо промінь x′(ρ), що виходить із точки x 1 в напрямі r 1 :

x′(ρ) = x 1 +ρr 1 = (4,4 ) +ρ( r11, r21) = (4+ρr11,4+ρr21), ρ> 0.

Пiдставляючи точку x′(ρ) в активне обмеження, отримаємо

4+ρr11 + 4+ρr21 ≤ 8,

або

r11 + r21 ≤ 0.

Додаємо до останньої нерівності умову нормування

−1 ≤ r11 ≤ 1,

−1 ≤ r21 ≤ 1.

Знаходимо похідну за напрямком r 1 від функції f(x ) в точці x 1:

D r 1 f (x 1 )= ( f (x 1 ), r 1 ) = ((−4, 0), ( r11 , r21 )) = −4 r11 .

Остаточно отримуємо задачу ЛП для визначення підхожого i можливого

напрямку

−4 r11 → min, r11 + r21 ≤ 0,

−1 ≤ r11 ≤ 1,

−1 ≤ r21 ≤ 1.

Оптимальним pозв'язком цієї задачі є вектор r 1 = (1,-1). Відповідні значення r11, r21 дорівнюють r11 = 1, r21 = −1. Значення похідної за напрямком r 1

D r 1 f (x 1 )= −4 r11 = −4< 0.

203

Отже, напрямок r 1 = (1,−1) є можливим i підхожим. Будуємо промінь x′(ρ), що

виходить із точки x 1 в напрямку r 1 :

x′(ρ) = x 1 +ρr 1 = (4,4 ) +ρ(1,−1) = (4 +ρ, 4 −ρ), ρ> 0.

Пiдставляючи x′(ρ) у неактивні обмеження, визначаємо допустимий інтервал

Точка ρ= 1 належить допустимому інтервалу для ρ. Тому ρ1 = 1 i x 2 = x 1 +ρ1 r 1 = (4,4 ) + (1,−1) = (5,3 ).

3-я iтеpацiя. Обчислюємо

f (x 2 ) = (− 2 , − 2 ) ≠ 0 .

Визначаємо активні обмеження в точці x 2 :

5 + 3 = 8, (Активне обмеження)

5 + 3 × 3 = 14 < 18,

5 > 0,

3 > 0.

Пеpевipяємо, чи буде антиградієнт − f (x 2) можливим напрямком. Будуємо промінь, що виходить з точки x 2 в напрямі антиградієнта − f (x 2):

напрямку r 2 . Маємо

x′(ρ) = x 2 +ρr 2 = (5,3 ) +ρ( r12, r22) = (5+ρr12,3+ρr22), ρ> 0.

Пiдстановка x′(ρ) в активне обмеження дає нам

5+ρr12 +3+ρr22 ≤8 , ρ> 0,

або з умовами нормування

204

r12 + r22 ≤ 0,

−1 ≤ r12 ≤ 1,

−1 ≤ r22 ≤ 1.

За цих умов ми повинні мiнiмiзувати функцію

D r 2 f (x 2 )= ( f (x 2 ), r 2 ) = ((−2, −2), ( r12 , r22 )) = −2 r12 −2 r22 .

Оскiльки r12 + r22 ≤ 0, то −2 ( r12 + r22 ) ≥ 0, тобто підхожих напрямків не існує. Отже,

точка x * =x 2 = (5,3) є оптимальним pозв'язком задачі, f ( x * ) = f(5,3) = 2.

§ 3. Метод проекції градієнта

Розглянемо задачу пошуку умовного екстремуму, яка полягає в мінімізації

Як вже зазначалось, в градієнтних методах у разі виходу точки x s на границю

допустимої множини напрямок антиградієнта перестає бути, взагалі кажучи,

повинна бути розглянута інша процедура, яка дозволяє перейти від допустимої

точки x s до іншої допустимої точки x s+1 таким чином, щоб значення цільової функції f 0(x ) зменшилось. Іншими словами, у співвідношенні (11.14) необхідно

замість неможливого напрямку − f 0( x s ) розглянути деякий можливий напрямок r s. Для знаходження цього напрямку розглянемо точку xs − ρ f 0( x s ) (ρ> 0) та спроектуємо її на область D. Одержимо точку ys = πD ( xs − ρ f 0( x s )), де πD — оператор проектування на область D. Оскільки множина D — опукла, то відрізок [ x s, y s ] D, а, отже, напрямок r s = ys – x s — можливий (див. рис. 11.3).

xs

z1< z2<…<zs

Рис. 11.3

Тепер замість процедури (11.14) в методі проекції градієнта розглянемо

процедуру

де ρs > 0 обирається так, щоб f 0( x s + 1 ) < f 0( x s ) та x s + 1 D.

205

(1+4ρ– y1)2+(1+ρ– y2)2 → min,

0 ≤ y1 ≤ 2,

0 ≤ y2 ≤ 1.

Розв'язком вказаної задачі є вектор

206

Зрозуміло, що обидва варіанти останнього співвідношення задають один і той же напрямок. За цей напрямок можна обрати вектор r s = ( 1, 0 ). Після обчислення

дає метод проекції субградієнта. Цікаво, що при цьому вихідна задача є задачею

опуклого програмування, і тому її розв'язок забезпечує глобальний мінімум

цільової функції.

Розділ 12. Методи штрафних та бар'єрних функцій

Iдея методів штрафних та бар'єрних функцій полягає в зведенні ЗНЛП з обмеженнями до спеціальної задачі безумовної оптимізації. При цьому обмеження вихідної задачі включаються в цільову функцію цієї допоміжної оптимiзацiйної

задачі. Зауважимо, що ця ідея вже використовувалась при розв'язуванні класичної

задачі пошуку умовного екстремуму методом Лагранжа, а також в задачі опуклого програмування (теорема Куна-Таккера).

Нехай маємо задачу

Введемо до розгляду функцію

Замiнимо задачу умовної оптимізації (12.1) задачею безумовної оптимізації

Функцiю P ( x ) називають штрафною, оскільки вона викликає нескінченний

штраф за вихід з області D.

Очевидно, що оптимальні розв'язки задач (12.1) i (12.3) однакові. Геометрична інтерпретація викладеного для функції однієї змінної приведена

нижче (див. рис. 12.1).

Очевидно також i те, що для так введеної функції штрафу P( x ) (див.

співвідношення (12.2)) задача (12.3) розв'язуванню не піддається. Тому в дійсності замість вказаної P( x ) розглядається послідовність штрафних функцій, які апроксимують P( x ) i мають хороші аналітичні властивості.

Означення 12.1. Функцiя P( f 1 ( x ) ,..., f m ( x ) , r ) , де r = (r1,...,rm) — деякий

вектор керуючих параметрів, а f i ( x ) , i=1,...,m, — функції обмежень задачі (12.1), називається штрафною, якщо

207

Рис. 12.1

Замiсть задачі (12.3) введемо до розгляду послідовність задач безумовної

оптимізації

Метод штрафних функцій полягає в переході від задачі (12 .1) до послідовності задач безумовної оптимізації (12 .4) з наступним їх розв'язуванням яким-небудь методом безумовної оптимізації.

Pr( x)

P1

P2

P3

x

O D

Рис. 12.2

При вдалому виборі штрафних функцій P( f 1 ( x ) ,..., f m ( x ) , r ) можна

очікувати, що послідовність розв'язкiв задач (12.4) буде збігатися до розв'язку

задачі (12.1).

Вкажемо на відмінність методу бар'єрних функцій від методу штрафних

функцій. В методі штрафних функцій апроксимацiя функції P(x) здійснюється зовні

208

x En

Якщо штрафна функція визначається рівністю (12.5), функції f i ( x ),

i=1,...,m, неперервні i існує замкнена множина Y E n така, що x * ( r ) Y r >0 ,

то

F ( x * ( r1), r1) ≤ F ( x * ( r2), r1) = f 0( x * ( r2)) + (1/r1) P ( x * ( r2)) ≤

тобто при спаданні r функція F ( x * ( r ), r ) не спадає.

За означенням (12.5) P ( x ) = 0 при x D. Тому P ( x * ) = 0, оскільки x * D, i

210