Задачі опуклого програмування

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

Означення 2. Функція називається строго опуклою, якщо в умові знак замінено на і .

Означення 3. Функція називається вгнутою на опуклій множині , якщо для довільних і і довільного , , виконується:

Формули (1), (2) дають одночасно методи дослідження функції на опуклість. Але часто так досліджувати складно. У ряді випадків дослідження на опуклість спрощується.

Нехай (x _{1 ,…,} x_n) має неперервні частинні похідні другого порядку. Розглянемо матрицю

де .

Матриця називається матрицею Гессе функції (x_1,…,x_n).

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

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

Приклад 15.1 Вивчити поведінку функції

в околі точки .

Розв’язання.

, ,

, .

– від не залежить.

, .

Отже, строго вгнута для всіх , .

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

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

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

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

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

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

Розглянемо задачу опуклого програмування з обмеженнями-нерівностями виду

;

, ,

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

Нехай задача (1)-(3) задовольняє умову регулярності Слейтера: існує хоч одна точка , в якій

, .

Метод множників Лагранжа можна поширити і на задачі (1)-(3), де обмеження задані нерівностями.

Означення4. Функцією Лагранжа задачі (1)-(3) називають

Означення 5. Точка називається сідловою точкою Лагранжа , якщо для всіх

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

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

Якщо функції , диференційовані, то можна довести, що необхідними і додатними умовами того, що – сідлова, є такі:

, , , ;

, , , .

Зауваження. Ці умови називаються локальними умовами Куна-Таккера (умовами ортогональності пари двоїстих задач лінійного програмування). По аналогії і у нелінійному програмуванні говорять про двоїсті задачі, причому одна з них ,

друга: ,

де – множина допустимих розв’язків, визначена системою (2),(3).

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

;

, .

Зведемо всі обмеження до одного типу:

Складемо функцію Лагранжа

Знайдемо її частинні похідні:

, ;

, .

У цьому випадку умови теореми Куна-Таккера формулюються так. Нехай , - диференційовані функції. Для того, щоб вектор був оптимальним розв’язком задачі, необхідно, щоб існував вектор такий, що виконуються умови:

1) , , ;

2) , ;

3) , причому якщо , то , .

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