Необхідні умови існування сідлової точки

Для розроблення методів розв’язування окремих типів задач нелінійного програмування важливе значення має поняття сідлової точки, а також визначення необхідних і достатніх умов існування сідлових точок функції Лагранжа Необхідні умови існування сідлової точки - student2.ru у (n+m)-вимірному просторі змінних Необхідні умови існування сідлової точки - student2.ru за довільних умов, які можуть накладатися на їх знаки (необхідні і достатні умови існування сідлової точки функції Лагранжа за відсутності обмежень на знаки змінних розглянуто в п.7.4).

Розглянемо нелінійну задачу:

Необхідні умови існування сідлової точки - student2.ru ,

Необхідні умови існування сідлової точки - student2.ru .

Причому на компоненти векторів Необхідні умови існування сідлової точки - student2.ru накладено обмеження на знаки. Позначимо множину точок, що задовольняють такі обмеження, через Необхідні умови існування сідлової точки - student2.ru .

Функція Лагранжа для цієї задачі має вигляд:

Необхідні умови існування сідлової точки - student2.ru = Необхідні умови існування сідлової точки - student2.ru . (7.12)

Точка Необхідні умови існування сідлової точки - student2.ru називається сідловою точкою функції Лагранжа (7.12), якщо для всіх Необхідні умови існування сідлової точки - student2.ru виконується співвідношення:

Необхідні умови існування сідлової точки - student2.ru . (7.13)

Для диференційовних функцій Необхідні умови існування сідлової точки - student2.ru та Необхідні умови існування сідлової точки - student2.ru знайдемо необхідні умови існування сідлової точки.

Сідлова точка Необхідні умови існування сідлової точки - student2.ru функції Необхідні умови існування сідлової точки - student2.ru виду (7.12) за означенням задовольняє умову:

Необхідні умови існування сідлової точки - student2.ru .

Нерівність виконується для всіх точок Х, тобто також і для тих, у яких лише одна координата відрізняється від Х*. Допустимо, що це хk, а всі інші збігаються з координатами сідлової точки Необхідні умови існування сідлової точки - student2.ru .

Оскільки права частина нерівності є фіксованою, а в лівій частині змінюється лише одна координата хk, то приходимо до функ­ції однієї змінної Необхідні умови існування сідлової точки - student2.ru , яку можна зобразити графічно на координатній площині.

Розглянемо спочатку випадок, коли Необхідні умови існування сідлової точки - student2.ru , тобто лише частину координатної площини, для якої Необхідні умови існування сідлової точки - student2.ru .

Можливі такі випадки:

1) коли всі Необхідні умови існування сідлової точки - student2.ru , то максимальне значення функції L(xk) досягатиметься в точці, для якої Необхідні умови існування сідлової точки - student2.ru (рис.7.5).

Необхідні умови існування сідлової точки - student2.ru

Рисунок 7.5

2) коли максимум функції L(xk) досягатиметься в точці Необхідні умови існування сідлової точки - student2.ru і розглядувана частинна похідна також дорівнюватиме нулю: Необхідні умови існування сідлової точки - student2.ru (рис.7.6).

Необхідні умови існування сідлової точки - student2.ru

Рисунок 7.6

3) коли точка максимуму функції L(xk) досягатиметься також у точці
Необхідні умови існування сідлової точки - student2.ru , а частинна похідна Необхідні умови існування сідлової точки - student2.ru (рис.7.7).

Необхідні умови існування сідлової точки - student2.ru

Рисунок 7.7

Узагальнюючи всі три ситуації, маємо:

Необхідні умови існування сідлової точки - student2.ru для Необхідні умови існування сідлової точки - student2.ru

та

Необхідні умови існування сідлової точки - student2.ru .

Розглядаючи другу частину нерівності (7.13):

Необхідні умови існування сідлової точки - student2.ru

аналогічними міркуваннями, що проілюстровані рис.7.8-7.9, встановлюються необхідні умови для похідних по Необхідні умови існування сідлової точки - student2.ru функції Лагранжа в сідловій точці.

Необхідні умови існування сідлової точки - student2.ru

Рисунок 7.8 Рисунок 7.9

Об’єднуючи всі три випадки для невід’ємних координат, маємо необхідні умови сідлової точки:

Необхідні умови існування сідлової точки - student2.ru для тих індексів j, де Необхідні умови існування сідлової точки - student2.ru . (7.14)

Зауважимо, що для Необхідні умови існування сідлової точки - student2.ru маємо ті самі випадки, які зображено на рис.7.5-7.9, причому графіки будуть симетрично відоб­ражені відносно осі Оy, тобто для недодатних координат необхідна умова має вигляд:

Необхідні умови існування сідлової точки - student2.ru для тих індексів j, де Необхідні умови існування сідлової точки - student2.ru . (7.15)

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

Необхідні умови існування сідлової точки - student2.ru , Необхідні умови існування сідлової точки - student2.ru – довільного знака. (7.16)

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

Необхідні умови існування сідлової точки - student2.ru . (7.17)

Розглядаючи другу частину нерівності (7.13), за допомогою аналогічних міркувань встановлюємо необхідні умови для похідних по Необхідні умови існування сідлової точки - student2.ru функції Лагранжа в сідловій точці:

Необхідні умови існування сідлової точки - student2.ru для тих індексів і, де Необхідні умови існування сідлової точки - student2.ru , (7.18)

Необхідні умови існування сідлової точки - student2.ru для тих індексів і, де Необхідні умови існування сідлової точки - student2.ru , (7.19)

Необхідні умови існування сідлової точки - student2.ru для тих індексів і, де Необхідні умови існування сідлової точки - student2.ru має довільний знак. (7.20)

Отже, справджується рівняння:

Необхідні умови існування сідлової точки - student2.ru . (7.21)

Сукупність співвідношень (7.14)-(7.21) становить необхідні умови, які має задовольняти сідлова точка Необхідні умови існування сідлової точки - student2.ru функції Лагранжа для точок, що належать множині Необхідні умови існування сідлової точки - student2.ru . При цьому Необхідні умови існування сідлової точки - student2.ru повинна мати частинні похідні по всіх компонентах векторів Необхідні умови існування сідлової точки - student2.ru .

Теорема Куна-Таккера

Розглянутий метод множників Лагранжа уможливлює знаходження лише локальних сідлових точок функції Лагранжа.

Теорема Куна-Таккера дає змогу встановити типи задач, для яких на множині допустимих розв’язків існує лише один глобальний екстремум зумовленого типу. Вона тісно пов’язана з необхідними та достатніми умовами існування сідлової точки.

Розглянемо задачу нелінійного програмування, яку, не зменшуючи загальності, подамо у вигляді:

Необхідні умови існування сідлової точки - student2.ru , (7.22)

Необхідні умови існування сідлової точки - student2.ru , (7.23)

Необхідні умови існування сідлової точки - student2.ru . (7.24)

(Очевидно, що знак нерівності можна змінити на протилежний множенням лівої і правої частин обмеження на (– 1)).

Теорема 7.1. (Теорема Куна-Таккера). Вектор Х* є оптимальним розв’язком задачі (7.22)-(7.24) тоді і тільки тоді, коли існує такий вектор Необхідні умови існування сідлової точки - student2.ru , що при Необхідні умови існування сідлової точки - student2.ru для всіх Необхідні умови існування сідлової точки - student2.ru точка Необхідні умови існування сідлової точки - student2.ru є сідловою точкою функції Лагранжа

Необхідні умови існування сідлової точки - student2.ru ,

і функція мети Необхідні умови існування сідлової точки - student2.ru для всіх Необхідні умови існування сідлової точки - student2.ru угнута, а функції Необхідні умови існування сідлової точки - student2.ru – опуклі.

Умови теореми Куна — Таккера виконуються лише для задач, що містять опуклі функції.

Опуклі й вогнуті функції

Наведемо основні означення та теореми. Нехай задано n-вимірний лінійний простір Rn. Функція Необхідні умови існування сідлової точки - student2.ru , що задана на опуклій множині Необхідні умови існування сідлової точки - student2.ru , називається опуклою, якщо для будь-яких двох точок Необхідні умови існування сідлової точки - student2.ru та Необхідні умови існування сідлової точки - student2.ru з множини X і будь-яких значень Необхідні умови існування сідлової точки - student2.ru виконується співвідношення:

Необхідні умови існування сідлової точки - student2.ru . (7.25)

Якщо нерівність строга і виконується для Необхідні умови існування сідлової точки - student2.ru , то функція Необхідні умови існування сідлової точки - student2.ru називається строго опуклою.

Функція Необхідні умови існування сідлової точки - student2.ru , яка задана на опуклій множині Необхідні умови існування сідлової точки - student2.ru , називається вогнутою, якщо для будь-яких двох точок Необхідні умови існування сідлової точки - student2.ru та Необхідні умови існування сідлової точки - student2.ru з множини X і будь-якого Необхідні умови існування сідлової точки - student2.ru справджується співвідношення:

Необхідні умови існування сідлової точки - student2.ru . (7.26)

Якщо нерівність строга і виконується для Необхідні умови існування сідлової точки - student2.ru , то функція Необхідні умови існування сідлової точки - student2.ru називається строго угнутою.

Слід зазначити, що опуклість та угнутість функції визначаються лише відносно опуклих множин у Необхідні умови існування сідлової точки - student2.ru , оскільки за наведеними означеннями разом з двома будь-якими точками Необхідні умови існування сідлової точки - student2.ru та Необхідні умови існування сідлової точки - student2.ru множині X належать також точки їх лінійної комбінації: Необхідні умови існування сідлової точки - student2.ru для всіх значень Необхідні умови існування сідлової точки - student2.ru , що можливо лише у разі, коли множина X є опуклою.

Теорема 7.2. Нехай Необхідні умови існування сідлової точки - student2.ru – опукла функція, що задана на замкненій опуклій множині X, тоді будь-який локальний мінімум Необхідні умови існування сідлової точки - student2.ru на цій множині є і глобальним.

Теорема 7.3. Нехай Необхідні умови існування сідлової точки - student2.ru – опукла функція, що визначена на опуклій множині Х, і крім того, вона неперервна разом з частинними похідними першого порядку в усіх внутрішніх точках Х. Нехай Необхідні умови існування сідлової точки - student2.ru – точка, в якій Необхідні умови існування сідлової точки - student2.ru . Тоді в точці Необхідні умови існування сідлової точки - student2.ru досягається локальний мінімум, що збігається з глобальним.

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

Для угнутих функцій отримані результати формулюють так. Нехай f(X) – угнута функція, що задана на замкненій опуклій множині Необхідні умови існування сідлової точки - student2.ru . Тоді будь-який локальний максимум f(X) на множині Х є глобальним. Якщо глобальний максимум досягається в двох різних точках множини, то він досягається і на нескінченній множині точок, що лежать на відрізку, який сполучає ці точки. Для строго угнутої функції існує єдина точка, в якій вона досягає глобального максимуму.

Градієнт угнутої функції f(X) у точках максимуму дорівнює нулю, якщо f(X) – диференційовна функція. Глобальний мінімум угнутої функції, якщо він скінченний на замкненій обмеженій зверху множині, має досягатися в одній чи кількох її крайніх точках за умови скінченності функції f(X) у кожній точці цієї множини.

Опукле програмування

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

Загальний вигляд задачі опуклого програмування такий:

Необхідні умови існування сідлової точки - student2.ru , (7.27)

Необхідні умови існування сідлової точки - student2.ru , Необхідні умови існування сідлової точки - student2.ru ; (7.28)

Необхідні умови існування сідлової точки - student2.ru , (7.29)

де Необхідні умови існування сідлової точки - student2.ru , Необхідні умови існування сідлової точки - student2.ru – угнуті функції.

Аналогічний вигляд має задача для опуклих функцій.

Позначимо: Необхідні умови існування сідлової точки - student2.ru , тоді Необхідні умови існування сідлової точки - student2.ru , і маємо:

Необхідні умови існування сідлової точки - student2.ru , (7.30)

Необхідні умови існування сідлової точки - student2.ru Необхідні умови існування сідлової точки - student2.ru ; (7.31)

Необхідні умови існування сідлової точки - student2.ru , (7.32)

де Необхідні умови існування сідлової точки - student2.ru , Необхідні умови існування сідлової точки - student2.ru – опуклі функції.

Оскільки ці задачі еквівалентні, то нижче розглянемо задачу (7.27)-(7.29).

Множина допустимих планів задачі, що визначається системою (7.28), є опуклою.

Як наслідок теорем 7.2 та 7.3 справджується таке твердження: точка локального максимуму (мінімуму) задачі опуклого програмування (7.27)-(7.29) є одночасно її глобальним максимумом (мінімумом).

Отже, якщо визначено точку локального екстремуму задачі опуклого програмування, то це означає, що знайдено точку глобального максимуму (мінімуму).

У разі обмежень-нерівностей задачу опуклого програмування розв’язують, застосовуючи метод множників Лагранжа.

Функція Лагранжа для задачі (7.27)-(7.29) має вид:

Необхідні умови існування сідлової точки - student2.ru (7.33)

де Необхідні умови існування сідлової точки - student2.ru – множники Лагранжа.

Використовуючи теорему Куна-Таккера, маємо необхідні та достатні умови існування оптимального плану задачі опуклого програмування.

Теорема 7.4. Якщо задано задачу нелінійного програмування виду (7.27)-(7.29), де функції Необхідні умови існування сідлової точки - student2.ru Необхідні умови існування сідлової точки - student2.ru диференційовні і вгнуті по Х, то для того, щоб вектор Необхідні умови існування сідлової точки - student2.ru був розв’язком цієї задачі, необхідно і достатньо, щоб існував такий вектор Необхідні умови існування сідлової точки - student2.ru , що пара ( Необхідні умови існування сідлової точки - student2.ru , Необхідні умови існування сідлової точки - student2.ru ) була б сідловою точкою функції Лагранжа, тобто щоб виконувалися умови:

(І) Необхідні умови існування сідлової точки - student2.ru , Необхідні умови існування сідлової точки - student2.ru ; (7.34)

(ІІ) Необхідні умови існування сідлової точки - student2.ru , Необхідні умови існування сідлової точки - student2.ru ; (7.35)

(ІІІ) Необхідні умови існування сідлової точки - student2.ru , Необхідні умови існування сідлової точки - student2.ru ; (7.36)

(IV) Необхідні умови існування сідлової точки - student2.ru , Необхідні умови існування сідлової точки - student2.ru . (7.37)

Для задачі мінімізації (7.30)-(7.32), де всі функції Необхідні умови існування сідлової точки - student2.ru Необхідні умови існування сідлової точки - student2.ru диференційовні і опуклі по Х, маємо умови, аналогічні вищенаведеним, але зі знаком «≥» в нерівностях (7.35) та (7.37).

Наши рекомендации