Глава II. Опукле програмування. Опукле програмування опукле програмування необхідні і достатні умови

Якщо в задачі математичного програмування потрібно знайти екстремум функції, наприклад:

на безлічі допустимих рішень, заданих обмеженнями

1) цільова функція є дифференцируемой і увігнутою, тобто для неї виконується умова:

При будь-яких,

2) а ліві частини всіх обмежень - диференційовними і опуклими функціями, тобто для них виконуються умови:

При будь-яких,

Тоді задача (4.7) - (4.8) називається завданням опуклого програмування.

Будь-яка лінійна функція одночасно задовольняє умовам і опуклості, і угнутості; тобто її можна вважати як опуклою, так і увігнутої. Це дозволяє вважати лінійні задачі окремим випадком задач опуклого програмування.

Якщо для завдань математичного програмування в загальному випадку поки відсутня струнка теорія існування і стійкості рішення, то для задач опуклого програмування така теорія є.

Введемо три визначення:

1). Функцією Лагранжа завдання опуклого програмування (4.7) - (4.8) називається функція:

,

, (4.9)

2). Кажуть, що завдання опуклого програмування (4.7) - (4.8) задовольняє умові регулярності, Якщо існує хоча б одна внутрішня точка допустимих рішень, що визначається строгими нерівностями, отриманими з (4.8) (тобто ).

3). точка називається седловой точкою функції, якщо для всіх виконано:

Якщо цільова функція (прибрати)

В теорії нелінійного програмування центральне місце займає теорема Куна-Таккера, узагальнююча класичний метод множників Лагранжа на випадок, коли обмеження нелінійної задачі поряд з обмеженнями у вигляді рівностей містять також і обмеження у вигляді нерівностей.

Теорема Куна-Таккера. Якщо завдання опуклого програмування (4.7) - (4.8) задовольняє умові регулярності, то точка є оптимальним вирішенням цього завдання тоді і тільки тоді, коли існує така точка з невід'ємними координатами, що є сідловою функції Лагранжа даного завдання.

умови Каруша - куна - Таккера в диференціальної формі:

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

,

,

,

приклад.Теорема Куна-Таккера обґрунтовує зведення задачі опуклого програмування до задачі пошуку сідлової точки функції Лагранжа. Щоб таке зведення мало практичний сенс, необхідно, щоб вийшла задача була в чомусь простіше вихідної. Це відбувається не завжди, тому розроблений ряд прямих методів пошуку рішення нелінійної задачі (4.5), (4.6). Розглянемо деякі з них.

Опуклого програмування, розділ математичного програмування, в якому досліджується задача максимізації увігнутою цільової функції f (х) векторного аргументу х \u003d (x 1, ..., х n), що задовольняє обмеженням gi (х) ≥ 0, х Є Х, i \u003d 1, ..., m, де gi - увігнуті функції, Х - опукле безліч. Точка х, що задовольняє цим обмеженням, називається допустимою. Основним результатом теорії опуклого програмування є теорема про седловой точці: для того щоб допустима точка х * завдання опуклого програмування була оптимальною, необхідно (при досить широких умовах) і досить існування вектора у * \u003d (у * 1, ..., ym *) з невід'ємними компонентами у * такого, що точка (х *, у *) є седловой для функції Лагранжа

завдання опуклого програмування, тобто для будь-яких х Є Х і у з невід'ємними компонентами виконуються нерівності

На теорему про седловой точці спирається ряд методів опуклого програмування, в яких або мінімізується функція φ (y 1, ..., у m) \u003d max x Є XL (x, у) при у i ≥ 0, i \u003d 1, .. ., m, або безпосередньо відшукується сідлова точка, причому замість функції Лагранжа іноді використовуються деякі її модифікації. Інший підхід до вирішення завдання опуклого програмування пов'язаний з пошуком можливих напрямків руху допустимої точки х, які не виводять з безлічі допустимих точок і при русі вздовж яких цільова функція зростає. Цей підхід реалізується за допомогою послідовності ітерацій. На кожній ітерації обчислюється можливий напрямок, що виходить з чергової точки, після чого проводиться зрушення в цьому напрямку на певну відстань до наступної точки. Існують методи вирішення завдань опуклого програмування, спеціально пристосовані до того випадку, коли цільова функція нелінійна, а обмеження лінійні. Як правило, методи опуклого програмування вимагають для точного визначення оптимальної точки нескінченного числа ітерацій. Винятком є \u200b\u200bзавдання квадратичного програмування (цільова функція - сума увігнутою квадратичної і лінійної функцій, обмеження лінійні) і лінійного програмування (цільова функція і обмеження лінійні), для яких в основному використовуються кінцеві методи. Багато обчислювальні методи опуклого програмування реалізовані у вигляді програм для ЕОМ; існують також пакети програм, що охоплюють завдання лінійного програмування і опуклого програмування. Дивись також Дослідження операцій.

Літ .: Гольштейн Е. Г. Опукле програмування. Елементи теорії. М., 1970; Зангвілл У. І. Нелінійне програмування. Єдиний підхід. М., 1973.

Нехай дана система нерівностей виду

(4.3) і функція

Z \u003d f (x 1, x 2, ..., x n), (4.4)

причому всі функції є опуклими на деякому опуклому безлічі M, а функція Z або опукла на безлічі М, або увігнута.

Завдання опуклого програмування полягає в знаходженні такого рішення системи обмежень (4.3), при якому цільова функція Z досягає мінімального значення, або увігнута функція Z досягає максимального значення. (Умови невід'ємності змінних можна вважати включеними в систему (4.3)).

З огляду на властивості 3 0 будь-яка задача лінійного програмування є окремим випадком завдання опуклого програмування. У загальному випадку завдання опуклого програмування є задачами нелінійного програмування. Виділення завдань опуклого програмування в спеціальний клас пояснюється екстремальними властивостями опуклих функцій: всякий локальний мінімум опуклої функції (локальний максимум увігнутої функції) є одночасно і глобальним; крім того, з огляду на властивості 2 0 опукла (увігнута) функція, задана на замкнутому обмеженому безлічі, досягає на цій множині глобального максимуму і глобального мінімуму. Звідси випливає, що якщо цільова функція Z є строго опуклою (строго ввігнутої) і якщо область рішень системи обмежень не порожня і обмежена, то завдання опуклого програмування завжди має єдине рішення.

Функція F (X) \u003d F (x 1, x 2, ..., x n) називається сепарабельном, Якщо її можна представити у вигляді суми функцій, кожна з яких залежить тільки від однієї змінної, тобто якщо

(Не виключено, що F i (x i) \u003d 0 при деяких i).

Нехай в задачі опуклого програмування задані система обмежень (4.3) і цільова функція (4.4), при цьому і функція мети Z, і всі обмеження, є сепарабельном. Тоді задача має вигляд:

Знайти мінімум опуклою (максимум - увігнутою) функції

при обмеженнях

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

Малюнок 12. Рішення задачі лінійного програмування методом кусочно-лінійної апроксимації

Для побудови наближеної завдання розглянемо кусочно-лінійну апроксимацію функції однієї змінної h (х), заданої на відрізку. Розіб'ємо цей відрізок на r частин точками x 0

Рівняння ділянки ламаної між точками (x k; h k) і (x k + 1; h k + 1) має вигляд (рівняння прямої по двох точках). Якщо кожне з відносин в цій рівності позначити через, то отримаємо:

Відзначимо, що для кожного існує єдине значення, яке задовольняє умовам (4.7). Позначивши можна переписати (4.7) у вигляді:

[Рівняння (4.8) називаються параметричними рівняннями відрізка.

Якщо h (x) \u003d 0, то другий з цих рівнянь звертається в тотожність 0 \u003d 0, а перше набирає вигляду (4.1) - рівняння відрізка, що лежить на осі абсцис].

Таким чином, для будь-якого рівняння ламаної можна записати у вигляді:

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

Повертаючись до задачі опуклого програмування з сепарабельном функціями, відзначимо, що перш за все (в залежності від системи обмежень) потрібно визначити інтервал зміни кожної змінної x j. Потім кожен цей інтервал розбивається на частини точками x jk і з використанням формул (4.9) будується кусочно-лінійна апроксимація для функцій f j і. Після цього можна для вихідної завдання (4.6) записати наближену задачу:

Знайти максимум функції

при обмеженнях (4.10)

Оскільки наближена завдання (4.10) є задачею лінійного програмування, яка зазвичай вирішується симплексним методом, умови невід'ємності змінних записуються окремо від інших обмежень.

Відмінність отриманої завдання (4.10) від звичайної задачі лінійного програмування полягає в тому, що для кожного x j є не більше двох сусідніх ненульових і, отже, не можна брати в якості основних змінних два з однаковим j і несоседних k. Зауважимо також, що для умов невід'ємності змінних доданків f j (x j) і (якщо такі виявляться) кусочно-лінійну апроксимацію проводити, звичайно, не потрібно.

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

функція називається опуклою

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

Іноді опуклу функцію називають опуклою вниз на відміну від увігнутої функції, яку іноді називають опуклою вгору. Сенс цих назв ясний з геометричного зображення типової опуклою (рис. 3.3) і увігнутою (рис. 3.4) функції.

Мал. 3.3. опукла функція

Мал. 3.4. увігнута функція

Підкреслимо, що визначення опуклої й увігнутої функцій мають сенс тільки для опуклого безлічі X, Так як тільки в цьому випадку точка обов'язково належить Х.

Завданням опуклого програмування називається окремий випадок загальної задачі математичного програмування (3.7), (3.8), коли цільова функція і функції обмежень є увігнутими на опуклому безлічі R.

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

завданням опуклого програмування називається також завдання мінімізації опуклої функції при обмеженнях:

, ,

де - опуклі функції; R - опукле безліч. Це просто інша форма завдання.

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

Лемма 1

Безліч допустимих планів задачівипуклого програмування

є опуклим. Будь-який локальний максимум увігнутої функції на Х є глобальним.

Якби функції обмежень були опуклі, то для визначається безлічі Х (3.14) опуклість вже б не йшла. В цьому випадку можна довести опуклість безлічі:

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

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

функція називається строго увігнутою на опуклому безлічі, якщо для будь-яких точок , І довільного числа виконується нерівність:

Лемма 2

Сума опуклих (увігнутих) функцій опукла (увігнута). Твір опуклою (увігнутою) функції на позитивне число опукло (увігнуто). Сума опуклою (увігнутою) і строго опуклою (строго ввігнутої) функцій строго опукла (строго увігнута).

теорема 1

Якщо функція строго увігнута (строго опукла) на опуклому безлічі Х, То у неї може бути тільки одна точка максимуму (мінімуму).

Доведення

Припустимо гидке, тобто що існує дві точки ,, Є точками максимуму строго ввігнутої функції на Х. Позначивши, маємо . Тоді для будь-якого справедливо:

тобто прийшли до протиріччя. Аналогічно доводиться для мінімуму строго опуклою функції.

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

.

Позначимо матрицю друге приватних похідних через.

Лемма 3

Для того щоб квадратична функція була опуклою (увігнутою) на всьому просторі, необхідно і достатньо, щоб матриця D була позитивно (негативно) визначена. якщо D позитивно (негативно) визначена, тобто

то строго опукла (строго увігнута).

Завдання максимізації (мінімізації) квадратичної функції при лінійних обмеженнях, де D - негативно (позитивно) визначена матриця, причому D T= D, називається завданням квадратичного програмування .

З леми випливає, що розглянута в розділі 2 завдання лінійного програмування, як і завдання квадратичного програмування, являє собою окремий випадок завдання опуклого програмування.

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

теорема 2

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

Розглянемо функцію Лагранжа для завдання опуклого програмування:

(3.15)

певну на прямому творі, де. Ця функція в силу угнутості, є увігнутою по і лінійної, а отже, опуклою по.

Однак не можна стверджувати на підставі теореми 1, що вона має седловую точку, так як безліч R не обов'язково є замкнутим і обмеженим, а Y свідомо необмежено. Проте, можна очікувати, що при деяких умовах сідлова точка все ж буде існувати.

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

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

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

Те, що умова Слейтера є істотним, показує наступний приклад.

приклад 1

Дана задача лінійного програмування:

Тут, очевидно, що x = 0 є рішення задачі, але у функції Лагранжа сідловий точки немає, так як зовнішня грань в мінімаксної задачі не досягається:

Розбиття обмежень в задачі опуклого програмування на і , Як уже говорилося, є умовним. Тому зазвичай під R розуміється безліч простого виду, це або весь простір E n, Або ненегативний ортант, або паралелепіпед. Складність же завдання опуклого програмування визначається системою обмежень:

.

Так як сідлова точка функції Лагранжа шукається на творі множин, де Y також є безліччю простого виду (невід'ємним ортантом), то сенс теореми Куна-Таккера полягає у зведенні задачі пошуку екстремуму функції зі складними обмеженнями на змінні до задачі пошуку екстремуму нової функції з простими обмеженнями.

якщо безліч R співпадає з E n, То умови екстремуму, як відомо, мають вигляд:

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

теорема 3

Для того щоб безперервно диференціюється увігнута функція мала в точці максимум на E n, Необхідно і достатньо, щоб градієнт функції в точці дорівнював нулю, тобто .

Згадаймо, що градієнт функції дорівнює:

.

Таким чином, для знаходження сідлової точки функції Лагранжа на творі, а отже, і для знаходження рішення задачі лінійного програмування при R= E n треба вирішити систему рівнянь (3.16). Але в цій системі n рівнянь, а невідомих n+ m, Так як крім nмірного вектора нам невідомий і m-мірний вектор множників Лагранжа. Однак для сідлової точки функції Лагранжа виконується дуже важлива властивість:

. (3.17)

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

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

Лекція 11.опукле програмування

Визначення 1. З адачі опуклого програмування називається задача нелінійного програмування, де всі функції є опуклими.

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

(1)

, (2)

. (3)

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

Для завдання (1) - (3) визначимо безліч

де
.

Лемма . Для завдання опуклого програмування (1) - (3) безліч опукло.

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

З отриманих нерівностей і випливає опуклість безлічі .

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

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

Необхідність. нехай - рішення задачі (1) - (3). покладемо
. Очевидно, що
, так як
,
і
.

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

Отже,
. Згідно лемі безліч опукло. Отже, виконуються всі вимоги теореми 8.2. Тому існує ненульовий

вектор
опорний в точці до безлічі :

Переконаємося далі, що всі координати вектора непозитивні. Припустимо гидке. Нехай існує координата
. Зафіксуємо у вектора всі компоненти, крім -ої. Тоді, враховуючи, що твір
може приймати як завгодно великі значення (в силу необмеженість зверху координати ), Отримуємо протиріччя з нерівністю (4).

Легко побачити, що при будь-якому
вектори
включаються в безліч . Тоді з (4) маємо:

Покажемо, що
. Нехай це не так. тоді
. отже,
. За умовою Слейтера існує вектор
такий, що
. Тому
. Отримане протиріччя і означає, що
.

позначимо
. Покажемо, що побудований вектор являє собою шуканий вектор множників Лагранжа. Очевидно, що
і з (5) отримуємо

Звідси при
слід

. (7)

З іншого боку, так як
(оскільки
) і
, Отримуємо нерівність

. Звідси і з (7) випливає, що в точці
виконується умова доповнює нежорсткості:

. (8)

З (6) і (8) маємо

або, що те ж саме,

Далі, нехай
. тоді
. Звідси і з (8) отримуємо нерівність

Нерівності (9), (10) і означають, що
- сідлова точка функції Лагранжа завдання випук-

лого програмування. Що й треба було.

Перш, ніж познайомитися з ще одним варіантом теореми Куна-Таккера, наведемо наступну теорему, яка представляє собою критерій умовного мінімуму в термінах конусів опорних векторів.

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

. (11)

Доказ випливає безпосередньо з теореми 6.5 і визначення конуса
опорних векторів в точці до безлічі
.

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

, (12)

.

Доведення. Покажемо, що умови (12) і (13) еквівалентні включенню (11). нехай точка
така, що
. тоді
і
.

нехай тепер
. Тоді з теорем 2 і 10.5 випливає, що необхідною і достатньою умовою екстремуму є існування таких множників
,
, для яких
. покладемо
для всіх
і отримаємо з останнього рівності умови (12) і (13). Що й треба було.

На закінчення параграфа наведемо формулювання двох теорем Куна-Таккера для задачі ви-

пукли програмування з лінійними обмеженнями.

Теорема 4. Нехай в задачі опуклого програмування (1) - (3) система обмежень (2) має вигляд

, B - вектор розмірності
. Тоді для того, щоб ненегативний вектор був рішенням завдання, необхідно і достатньо, щоб

існував ненегативний вектор такий, що
- сідлова точка функції Лагранжа даного завдання.

Відзначимо, що в цьому випадку функція Лагранжа має вигляд.

теорема 5. Нехай в задачі опуклого програмування (1), (2) цільова функція неперервно диференційовна, система обмежень (2) має вигляд
, Де A - матриця розмірності
, B - вектор розмірності
. Тоді для того, щоб вектор
був рішенням завдання, необхідно і достатньо, щоб існував ненегативний вектор такий, що виконуються умови
,
.

Зауважимо, що в теоремах 4 і 5 не потрібно виконання умови Слейтера, тому вони не є окремими випадками теорем 1 і 3 і вимагають самостійного докази.