Задачі опуклого програмування
Означення 1. Функція 
, яка задана на опуклій множині 
, називається опуклою, якщо для довільних двох точок 
і 
і довільного 
, 
, правильна нерівність
. 
Означення 2. Функція називається строго опуклою, якщо в умові знак 
замінено на 
і 
.
Означення 3. Функція називається вгнутою на опуклій множині , якщо для довільних і і довільного , , виконується:
Формули (1), (2) дають одночасно методи дослідження функції на опуклість. Але часто так досліджувати складно. У ряді випадків дослідження на опуклість спрощується.
Нехай 
(x1,…,xn) має неперервні частинні похідні другого порядку. Розглянемо матрицю
,
де 
.
Матриця 
називається матрицею Гессе функції (x1,…,xn).
Теорема. Нехай – опукла множина і 
. Для того, щоб функція була строго опукла в деякому околі точки необхідно і досить, щоб в цьому околі були додатні всі головні мінори її матриці . Якщо всі непарні головні мінори від’ємні, а парні – додатні, то функція строго вгнута в околі точки .
Якщо наведені умови опуклості виконуються для всіх 
, то функція є строго опуклою скрізь на .
Приклад 15.1 Вивчити поведінку функції
в околі точки 
.
Розв’язання.
, 
, 
,
, 
.
– від не залежить.
, 
.
Отже, строго вгнута для всіх 
, 
.
Основною властивістю опуклих функцій є те, що їх локальний екстремум є одночасно і глобальним. Сформулюємо точно ці результати.
1. Якщо 
– опукла (вгнута) функція, задана на замкненій опуклій множині , то всякий локальний мінімум (максимум) функції на області є глобальним.
2. Якщо глобальний мінімум (максимум) досягається у двох різних точках, то він досягається у кожній точці відрізка, що з’єднує дані точки.
3. Якщо – строго опукла (вгнута) функція, то її глобальний мінімум (максимум) на опуклій множині досягається в єдиній точці.
4. Нехай – опукла (вгнута) на опуклій множині , – має неперервні похідні першого порядку всередині . Нехай – стаціонарна точка . Тоді досягає в точці глобального мінімуму (максимуму).
Ці результати дають змогу розв’язувати задачі нелінійного програмування у випадку коли – опукла (вгнута), множина допустимих розв’язків опукла. Якщо при цьому має неперервні частинні похідні першого порядку в , то для знаходження мінімуму (максимуму) досить знайти стаціонарну точку функції .
Розглянемо задачу опуклого програмування з обмеженнями-нерівностями виду
;
;
, 
, 
де функції , 
– опуклі вгору.
Нехай задача (1)-(3) задовольняє умову регулярності Слейтера: існує хоч одна точка 
, в якій
, 
.
Метод множників Лагранжа можна поширити і на задачі (1)-(3), де обмеження задані нерівностями.
Означення4. Функцією Лагранжа задачі (1)-(3) називають
Означення 5. Точка 
називається сідловою точкою Лагранжа 
, якщо для всіх
Теорема Куна-Таккера. Нехай задача (1)-(3) задовольняє умову регулярності Слейтера, функції , є опуклими вгору. Вектор є оптимальним розв’язком задачі - тоді і тільки тоді, коли існує такий вектор 
, що 
є сідловою точкою функції Лагранжа .
Отже, задача опуклого програмування (1)-(3) зводиться до задачі знаходження сідлових точок функції Лагранжа: треба знайти точки, в яких функція Лагранжа досягає максимуму по 
і мінімуму по 
. Ця задача називається задачею максимінімізації і може бути записана так:
.
Якщо функції , диференційовані, то можна довести, що необхідними і додатними умовами того, що 
– сідлова, є такі:
, 
, 
, ; 
, 
, 
, . 
Зауваження. Ці умови називаються локальними умовами Куна-Таккера (умовами ортогональності пари двоїстих задач лінійного програмування). По аналогії і у нелінійному програмуванні говорять про двоїсті задачі, причому одна з них 
,
друга: 
,
де – множина допустимих розв’язків, визначена системою (2),(3).
Використовуючи ці результати, можна розглянути задачі нелінійного програмування у найзагальнішому вигляді:
;
, .
Зведемо всі обмеження до одного типу:
Складемо функцію Лагранжа
Знайдемо її частинні похідні:
, ;
, 
;
, 
.
У цьому випадку умови теореми Куна-Таккера формулюються так. Нехай , - диференційовані функції. Для того, щоб вектор був оптимальним розв’язком задачі, необхідно, щоб існував вектор такий, що виконуються умови:
1) 
, , 
;
2) 
, 
;
3) 
, причому якщо 
, то 
, 
.
Якщо точка 
задовольняє ці умови, функція є опуклою вверх, 
– опуклі вверх, 
– опуклі вниз, то є сідловою точкою функції Лагранжа , а 
є оптимальним розв’язком задачі нелінійного програмування.
Приклад 15.1 Розв’язати задачу опуклого програмування
Розглянемо функцію
.
Запишемо функцію Лагранжа
Запишемо умови Куна- Таккера
Розв’яжемо задачу методом штучного базису:
| i | Б | СБ | В | -М | ||||||||||
| Ах1 | Ах2 | Аλ1 | Аλ2 | Аλ3 | Аv1 | Аv2 | Аw1 | Аw2 | Аw3 | Аy1 | ||||
| Аv1 | -8 | -1 | -2 | -1 | ||||||||||
| Аy1 | -М | -1 | ||||||||||||
| Аw1 | ||||||||||||||
| Аw2 | ||||||||||||||
| Аw3 | ||||||||||||||
| m+2 | -2 | -8 | -1 | -1 | -2 | -1 | ||||||||
| Аv1 | -8 | -1 | -2 | -1 | ||||||||||
| Ах2 | 
| 
|
|
| 
|
| ||||||||
| Аw1 | 
|
|
| 
|
| |||||||||
| Аw2 | 
|
|
| 
|
| |||||||||
| Аw3 | 
|
|
|
|
| |||||||||
| m+1 |
.
Перевіримо умови Куна-Таккера:
0·8=0 
·0=0 0· =0 0· =0 0· =0
Отже, сідлова точка 
.
, 
.
Тоді оптимальний розв’язок: , 
.