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

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

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

,

.

Причому на компоненти векторів накладено обмеження на знаки. Позначимо множину точок, що задовольняють такі обмеження, через .

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

= . (8.12)

Точка називається сідловою точкою функції Лагранжа (8.12), якщо для всіх виконується співвідношення:

. (8.13)

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

Сідлова точка функції виду (8.12) за означенням задовольняє умову:

.

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

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

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

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

1) коли всі , то максимальне значення функції L (x_k) досягатиметься в точці, для якої (рис.8.5).

Рисунок 8.5

2) коли максимум функції L (x_k) досягатиметься в точці і розглядувана частинна похідна також дорівнюватиме нулю: (рис.8.6).

Рисунок 8.6

3) коли точка максимуму функції L (x_k) досягатиметься також у точці
, а частинна похідна (рис.8.7).

Рисунок 8.7

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

для

та

.

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

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

Рисунок 8.8 Рисунок 8.9

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

для тих індексів j, де . (8.14)

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

для тих індексів j, де . (8.15)

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

, – довільного знака. (8.16)

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

. (8.17)

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

для тих індексів і, де , (8.18)

для тих індексів і, де , (8.19)

для тих індексів і, де має довільний знак. (8.20)

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

. (8.21)

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

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

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

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

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

, (8.22)

, (8.23)

. (8.24)

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

Теорема 8.1. (Теорема Куна-Таккера). Вектор Х^* є оптимальним розв’язком задачі (8.22)-(8.24) тоді і тільки тоді, коли існує такий вектор , що при для всіх точка є сідловою точкою функції Лагранжа

,

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

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

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

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

. (8.25)

Якщо нерівність строга і виконується для , то функція називається строго опуклою.

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

. (8.26)

Якщо нерівність строга і виконується для , то функція називається строго угнутою.

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

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

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

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

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

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

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

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

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

, (8.27)

, ; (8.28)

, (8.29)

де , – угнуті функції.

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

Позначимо: , тоді , і маємо:

, (8.30)

; (8.31)

, (8.32)

де , – опуклі функції.

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

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

Як наслідок теорем 8.2 та 8.3 справджується таке твердження: точка локального максимуму (мінімуму) задачі опуклого програмування (8.27)-(8.29) є одночасно її глобальним максимумом (мінімумом).

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

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

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

(8.33)

де – множники Лагранжа.

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

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

(І) , ; (8.34)

(ІІ) , ; (8.35)

(ІІІ) , ; (8.36)

(IV) , . (8.37)

Для задачі мінімізації (8.30)-(8.32), де всі функції диференційовні і опуклі по Х, маємо умови, аналогічні вищенаведеним, але зі знаком «≥» в нерівностях (8.35) та (8.37).