Розділ 6. Нелінійне програмування. Методи умовної оптимізації

6.1 Класична задача математичного програмування

Класична задача математичного програмування має такий вигляд:

F(x₁,…,x_n) extrem,

g_i(x₁,…,x_n)=b_i,i=1,m, m<n.

У загальному випадку можливі такі підкласи задачі математичного програмування:

а) (n = 1, m = 0);

б) (n > 1, m = 0); в) (n > 1, m 0) 

Щоб класичним методом можна було відшукати екстремальні точки, функції F(X) та g(Х) мають бути неперервними та диференційованими і мати неперервні похідні хоча б до другого порядку включно.

Стаціонарні точки функції у випадках а) і б) визначаються як розв’язок системи рівнянь , яка у загальному випадку може бути нелінійною. Серед стаціонарних точок можуть бути і точки перетину (сідлові точки) функції.

Щоб визначити тип стаціонарних точок для функції однієї змінної, треба перевірити достатні умови, якими визначаються вид екстремуму й сідлові точки. Так, для існування максимуму функції однієї змінної достатні умови мають вигляд

Якщо маємо функцію двох змінних, то достатні умови існування максимуму полягають у від’ємності матриці Гессе, тобто у, виконанні умов:

В інших випадках достатні умови мають досить складний ха­рактер.

Метод множників Лагранжа застосовується для знаходження умовно­го екстремуму, тобто екстремуму функції F(x₁,…,x_n) на множині точок, які є розв'язками системи рівнянь виду g_i(x₁,…,x_n) =b_i, ,m<n. Цю задачу замінимо простішою задачею знаходження відповідного екстремального значення так званої функції Лагранжа, яка має структуру

L(X,)= F(x₁,…,x_n)+,

де  =1, m - множники Лагранжа.

Необхідні умови існування екстремуму функції Лагранжа поля­гають у виконанні рівнянь

.

Розв'язання цієї системи щодо змінних X_j та _ дає можливість визначити позиції стаціонарної точки. Аналіз функції F(x) у визначеній точці дає змогу з’ясувати вид екстремуму функції F(x).

Приклад 6.1. Знайти F(x)=(x₁ -1)²+ x₂²  extrem

за умови g(x) =x₁² – x₂ +1= 0.

Розв’яжемо умову g(x) = 0 щодо х₂: x₂ = x₁² +1.

Замінивши х₂ у функції мети, дістанемо функцію однієї змінної

F(x₁) = x₁⁴ + 3x₁² - 2x₁ + 2.

Стаціонарна точка цієї функції задовольняє умову

,

яка має розв’язок x^*₁= 0,313.

Оскільки друга похідна у цій точці додатна, то функціяF(x₁) має мінімум. При цьому х*₂ =1,098, aF(x^*₁, x^*₂) = 1.678.

Приклад 6.2. Для розглянутої вище задачі функція Лагранжа має вигляд

L(X,) = (x₁-1)² + x₂² + (x₁² - x₂+1).

Дістанемо необхідні умови екстремуму

Розв’язок цієї системи рівнянь дає х₁^*= 0,313,х₂^*= 1,098,^*= 2,196.

Виконаємо аналіз функції у точці X^*= (0.313; 1,098) за допомогою матриці Гессе. Знайдемо

Оскільки тобтото матриця Гессе достатньо визначена, а тому функціяF(x) опукла і у точці X^* досягає мінімуму.

6.2 Задача опуклого квадратичного програмування.

Постановка задачі опуклого програмування (ЗОП). Знайти вектор x = (x₁,...,x_n), що мiнi­мi­зує (максимізує) функцію F(x) = F(x₁,...,x_n) i задовольняє систему обмежень

G_i(x₁,...,x_n)£0, i=1,..., m, x_j³0, j=1,...,n,

де функції F, G_i (i=1,...,m) — опуклі.

Таким чином, для задачі опуклого програмування цільова функція опукла, а обмеження визначають опуклу допустиму множину.

Постановка задачі опуклого квадратичного програмування. Знайти вектор x, що мiнiмiзує цільову функцію F(x) = x D x^Т + c x^Т i задовольняє систему обмежень:

A x^Т £ b^Т, x ³ 0,

де c=(c₁,...,c_n), x=(x₁,...,x_n), D=||d_kl||, k,l=1,...n, A=||a_ij||, i=1,...,m, j=1,...,n, b=(b₁,...,b_m), матриця D симетрична та невід'ємно визначена.

Таким чином, для задачі опуклого квадратичного програмування (ЗОКП) цільова функція - опукло-квадратична, а обмеження - лінійні i визначають опуклу допустиму множину.

Зауважимо, що для випадку n=2, m=1 ЗОКП має вигляд:

d₁₁ x₁² + d₂₂ x₂² + 2 d₁₂ x₁ x₂ + c₁ x₁ + c₂ x₂ ® min,

a₁₁ x₁ + a₁₂ x₂ £ a₁₀, x_j ³ 0, j=1,2,

до того ж D=||d_kl||, k,l=1,2, d₁₂ = d₂₁.

Основні твердження і теореми

Означення 6.1. Множина W називається опуклою, якщо для довільних точок x,yÎW, та tÎ[0,1] виконується tx+(1–t)yÎW.

Означення 6.2. Функцiя H(x), xÎWÌEⁿ, де W — опукла множина, зветься опуклою, якщо для довільних точок x,yÎW та tÎ[0,1] виконується нерівність H(tx+(1–t)y)£tH(x)+(1–t)H(y).

Теорема 6.1. Множина {x:H(x)£0}, де H(x) опукла, є опуклою.

Теорема 6.2. Перетин опуклих множин є опуклою множиною.

Теорема 6.3. Квадратична функція F(x)=xDx^Т+cx^Т опукла, якщо матриця D - невід'ємно визначена.

Теорема 6.4. Матриця D - невід'ємно визначена, якщо всі її діагональні мінори невід'ємні:

det(D(k))³0, D(k)=||d_ij||, i,j=1,...k.

Теорема Куна-Таккера-1. Нехай допустима область

D={xÎEⁿ:G_i(x)£0,i=1,...,m,x³0}

задачі опуклого програмування задовольняє умову Слейтера: існує xÎD таке, що для всіх i=1,...,m G_i(x)<0, тобто множина D має внутрішні точки. Тоді для того, щоб вектор x* був оптимальним розв'язком задачі опуклого програмування, необхідно i достатньо, щоб існував вектор u*³0 такий, що пара (x*,u*) є сiдловою точкою функції Лагранжа:

L(x,u)= F(x)+(u₁ G₁(x) +...+ u_m G_m(x)),

x=(x₁,...,x_n)³0, u=(u₁,...,u_m)³0.

Кажуть, що точка (x*,u*) є сiдловою точкою функції L(x,u), якщо для всіх x³0, u³0 мають місце нерівності

L(x*,u) £ L(x*,u*) £ L(x,u*).

Теорема Куна-Таккера-2. Для неперервно диференцiйовних функцій F(x), G_i(x), i=1,...,m, теорема Куна-Таккера може бути переформульована таким чином. Вектор x* є оптимальним розв'язком задачі опуклого програмування тоді i лише тоді, коли існує вектор u*³0 такий, що для пари (x*,u*) виконуються умови:

Ñ_xL(x*,u*)³0, Ñ_xL(x*,u*)(x*)^Т=0, j=1,...,n,

Ñ_uL(x*,u*)£0, Ñ_uL(x*,u*)(u*)^Т=0, i=1,...,m.

Для задачі опуклого квадратичного програмування останні співвідношення набувають вигляду

c+2xD+uA ³0;

(c+2xD+uA)x^Т=0;

xA^Т–£0;

(xA^Т–b)u^Т=0;

x ³ 0, u ³ 0.

Допомiжна ЗЛП для ЗОКП. Якщо ввести вектори y=(y₁,...,y_n)³0 та v=(v₁,...,v_m)³0, то вищенаведені співвідношення матимуть вигляд:

c+2xD+uA–y=0;

xA^Т–b+v=0;

y x^Т = 0;

v u^Т = 0;

x ³ 0, u ³ 0, y ³ 0, v ³ 0.

Зауважимо, що для випадку n=2, m=1 матимемо

2 d₁₁ x₁ + 2 d₁₂ x₂ + a₁₁ u – y₁ = – c₁ ,

2 d₁₂ x₁ + 2 d₂₂ x₂ + a₁₂ u – y₂ = – c₂ ,

a₁₁ x₁ + a₁₂ x₂ + v = a₁₀ ,

x₁ y₁ = 0, x₂ y₂ = y₂, u v = 0,

x₁, x₂, u, y₁, y₂, v ³ 0.

Наведена вище система складається з n+m лінійних рівнянь щодо 2(m+n) невідомих x_j, y_j (j=1,...,n), u_i, v_i (i=1,...,m). Крiм того повинні виконуватись такі умови: якщо x_j > 0, то y_j = 0, якщо y_j > 0, то x_j = 0, якщо u_i > 0, то v_i = 0, якщо v_i > 0, то u_i = 0.

Отже, шуканим розв'язком системи може бути довільний невід'ємний базисний її розв'язок, але такий, що змінні x_j та y_j (а також u_i та v_i) з однаковими індексами не можуть бути водночас базисними. Для відшукання такого розв'язку можна застосувати будь-який із відомих методів ЛП, зокрема, метод штучного базису. З цією метою запишемо досліджувану систему у вигляді

2xD+uA–y = –c;

xA^Т+v =b.

Не обмежуючи загальності, будемо вважати, що праві частини цієї системи невід'ємні: –c³0, b³0 (оскільки, в іншому випадку відповідні рівняння, їх праву i ліву частину, досить помножити на –1). Згiдно методу штучного базису у кожне рівняння отриманої системи, яке не містить базисної змінної, вводимо штучну змінну. Оскiльки змінні v_i (i=1,...,m) можна вважати базисними, то штучні змінні z=(z₁,...,z_n)³0 вводимо тільки в перше рівняння вищенаведеної системи i розглядаємо допоміжну КЗЛП

Zi^Т®min,

2xD+uA–y+z = – c;

xA^Т+v=b;

x ³ 0, u ³ 0, y ³ 0, v ³ 0, z ³ 0,

де i=(1,1,...,1) — n-вимірний одиничний вектор.

Квадратичний симплекс-метод. Описана вище задача розв'язується симплекс-методом. Якщо знайдений допустимий розв’язок цієї задачі задовольняє умови доповнюючої нежорсткостi, то він визначає оптимальний розв'язок вихідної ЗОКП. Iнакше треба перейти до нового розв’язку. При цьому до базисних включається нова змінна з нульовою оцінкою.

Симплекс-метод з умовами для розв'язування допоміжної КЗЛП, побудованої на основі вихідної задачі опуклого квадратичного програмування , i називають квадратичним симплекс-методом (алгоритм звичайного симплекс-методу. Якщо в оптимальному розв'язку допоміжної КЗЛП всі штучні змінні z_j (j=1,...,n) приймають нульові значення, то, відкидаючи їх, отримаємо розв’язок, частина якого відповідає змінним початкової задачі опуклого квадратичного програмування, i буде її оптимальним розв'язком. Якщо ж в оптимальному розв'язку допоміжної КЗЛП значення хоча б однієї із штучних змінних відмінне від нуля, то система не має розв'язкiв, а, отже, множина сiдлових точок функції Лагранжа початкової задачі опуклого квадратичного програмування порожня.