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

Означення 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) , причому якщо , то , .

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

Приклад 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

Отже, сідлова точка .

, .

Тоді оптимальний розв’язок: , .