Умови Куна-Такера для задач нелінійного програмування.

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

. (8.27)

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

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

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

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

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

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

. (8.29)

Множина Х опукла, тому точка при також належить цій множині. Враховуючи, що , нерів­ність (8.29) матиме вигляд:

;

.

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

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

Доведення. З рівності (8.12) для знаходимо:

;

;

.

Через те що існують частинні похідні першого порядку, функцію можна розкласти в ряд Тейлора:

,

де — градієнт функції f, обчислений у точці , . Тоді:

.

Переходимо до границі при , отримаємо:

. (8.30)

Ця умова виконується для будь-яких внутрішніх точок Х ₁ та Х ₂ і є необхідною і достатньою умовою опуклості f (X).

Якщо функція f (X) неперервна разом з частинними похідними першого порядку і угнута на множині Х, то аналогічно поперед­ньому результату маємо:

.

Припустимо, що Х ⁰ — довільна точка множини Х, тоді, взявши , , а також за умовою теореми , в нерівності (8.30) маємо:

.

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

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

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

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

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

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

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

, (8.22)

, (8.23)

. (8.24)

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

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

,

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

Доведення. Необхідність. Нехай Х^* — оптимальний план задачі (8.22)—(8.24), тобто є точкою глобального максимуму задачі. Отже, для всіх інших планів задачі Х з множини допустимих розв’язків виконуватиметься співвідношення:

.

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

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

. (8.25)

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

.

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

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

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

Достатність. Для доведення достатності умов теореми потрібно виходити з того, що , — сідлова точка функції (тобто для виконується нерівність (8.13)), і необхідно довести, що тоді Х ^* є оптимальним планом задачі опуклого програмування.

Підставимо у нерівність (8.13) вираз функції Лагранжа (8.12) для задачі (8.22)—(8.23):

(8.26)

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

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

.

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

.

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

.

Через те що , приходимо до нерівності , яка справджується для всіх значень .

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