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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

для , та .

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

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

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

для тих індексів j де (5.44)

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

для тих індексів j де (5.45)

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

, – довільного знаку (5.46)

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

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

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

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

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

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

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

 

 

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

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

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

Теорема Куна-Таккера тісно пов’язана з необхідними та достатніми умовами існування сідлової точки.

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

(5.52)

(5.53)

(5.54)

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

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

,

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

Доведення. Необхідність. Нехай – оптимальний план задачі (5.52)-(5.53), тобто визначає точку глобального максимуму задачі. Отже для всіх інших планів задачі з множини допустимих розв’язків виконуватиметься співвідношення:

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

З умови (5.51) маємо , тоді

(5.55)

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

.

Функція – лінійна відносно , тобто остання нерівність виконується для будь-якого . Отже точка – точка глобального мінімуму по функції Лагранжа.

Для встановлення нерівності, що відповідає лівій частині умови (5.43), а саме скористаємося також рівнянням (5.51), просумувавши його по і: . За умовою теореми – угнуті функції і , тому виконується наступне рівняння:

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

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

У (5.43) підставимо вираз функції Лагранжа (5.42) для задачі (5.52)-(5.53):

+

(5.56)

при всіх значеннях .

Розглянемо праву частину подвійної нерівності (5.56).

Остання нерівність має виконуватися для всіх , крім того , тобто нерівність справедлива лише у випадку, коли

.

Тоді з лівої частини нерівності (5.56) маємо:

Так як , то приходимо до нерівності , яка справедлива для всіх значень .

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

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