Тема 2.2. Квадратичне програмування

Квадратичне програмування є частковим випадком нелінійного програмування. У задачі квадратичного програмування обмеження

(2.2.1)

є лінійними функціями, а цільова функція Z є сумою лінійної та квадратичної функцій:

. (2.2.2)

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

, (2.2.3)

де

, , . (2.2.4)

При цьому припускається, що – симетрична матриця . У матричній формі задача квадратичного програмування матиме вигляд:

(2.2.5)

при

. (2.2.6)

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

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

Питання про те, чи буде квадратична форма угнутою чи опуклою, залежить від того, чи є вона від’ємно визначеною, від’ємно напіввизначеною, додатньо визначеною, додатньо напіввизначеною чи взагалі невизначеною.

Квадратична форма називається від’ємно визначеною, якщо для всіх крім .

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

Квадратична форма називається додатньо визначеною (додатньо напіввизначеною), якщо квадратична форма від’ємно визначена (від’ємно напіввизначена).

Квадратична форма називається невизначеною, якщо вона додатна для одних значень і від’ємна для інших.

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

(2.2.7)

і при цьому всі _j > 0, то вона додатньо визначена, а при _j < 0 – від’ємно визначена. Якщо ж серед значень _j є і від’ємні й додатні, то квадратична форма невизначена.

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

Теорема. Якщо для канонічної форми

(2.2.8)

усі визначники D₁, D₂, … D_n відмінні від нуля, то цю форму можна трикутним перетворення привести до вигляду

, (2.2.9)

де

, (2.2.10)

D₁ = d₁₁, , … , . (2.2.11)

Отже, знаки коефіцієнтів _і визначаються знаками визначників D_і. Розглянемо можливі випадки, які можуть зустрітись у конкретних задачах.

Випадок 1. Якщо всі визначники D_і­ додатні, то й усі коефіцієнти _і додатні, отже, квадратична форма додатньо визначена.

Випадок 2. Якщо у ряду D₁, D₂, … D_n знаки чисел чергуються, то всі коефіцієнти _і від’ємні, і у цьому випадку форма є від’ємно визначеною.

Випадок 3. Якщо ранг матриці D дорівнює r < n, то вона буде додатньо напіввизначеною, якщо перші r її визначників додатні, а решта дорівнюють нулю.

Випадок 4. Якщо ранг матриці D дорівнює r < n, в ряду D₁, D₂, … D_r знаки чергуються, і D_r+1 = D_r+2 =… D_n = 0, то квадратична форма від’ємно напіввизначена.

Випадок 5. Якщо у ряду чисел D₁, D₂, … D_n немає чергування знаків, причому зустрічаються від’ємні D_і­ , то відповідна квадратична форма є невизначеною.

Двоїстість у квадратичному програмуванні. У розділі «Лінійне програмування» вже розглядався принцип двоїстості, який має місце і для задач квадратичного програмування.

Якщо вихідна задача формулюється так:

знайти при обмеженнях ,

то двоїста задача матиме вигляд:

знайти при обмеженнях .

Для двоїстих квадратичних задач справедливим є ряд тверджень.

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

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

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

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

Якщо матриця строго визначена, то справедливе й обернене твердження.

Якщо в основній задачі матриця є, наприклад, матрицею витрат ресурсів на виробництво продукції, то, аналогічно до двоїстої задачі лінійного програмування, змінні _і визначають неявні ціни і-того виду ресурсів.

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

Розв’язування починають з довільної допустимої точки . Для переходу в результаті ітерацій від точки до точки в точці визначають такий напрям , щоб при достатньо малому  > 0 промінь належав області допустимих значень . Потім знаходять величину параметра як , де – значення параметра, при якому промінь перетинає область допустимих значень, – таке допустиме значення параметра , при якому функція досягає максимуму на промені . Якщо значення безмежне, то цільова функція необмежена. В протилежному випадку визначають наступну точку ітераційного процесу:

. (2.2.12)

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

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

Метод проектованих градієнтів Розена. Метод Розена застосовують для розв’язування задач квадратичного програмування з визначеною (напіввизначеною) квадратичною формою. Якщо точка – гранична, то градієнт проектують на границю допустимої області і рух здійснюють за напрямком його проекції. У цьому випадку траєкторія руху весь час залишається на межі допустимої області, не покидаючи її. Наприклад, у випадку тривимірного простору допустима область є многогранником, і її межа складається з утворень з розмірністю 2 (грань), 1 (ребро) і 0 (вершина). Якщо точки належить грані, але не належить ребру, то градієнт проектують на грань; якщо ж належить ребру – то на ребро. Для внутрішньої точки метод Розена аналогічний до звичайного градієнтного методу.

Метод допустимих напрямків Зойтендейка. У цьому методі, як і в інших градієнтних методах, початковою є довільна точка . Перехід з точки в точку здійснюють за таким напрямком , щоб при  > 0 промінь належав області допустимих розв’язків. Для цього необхідним є дотримання умови

, (2.2.13)

де для всіх і в точці виконується співвідношення

. (2.2.14)

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

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

Градієнтний метод Лагранжа. Цей метод придатний при застосуванні методу градієнтів до функції Лагранжа в задачі математичного програмування.

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

. (2.2.15)

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