Квадратичне програмування (, QP) — особливий тип оптимізаційної задачі. Це задача оптимізації (зведення до мінімуму або максимуму) квадратичної функції декількох змінних при лінійних обмеженнях на ці змінні. Квадратичне програмування є одним з видів нелінійного програмування.
«Програмування» в цьому контексті стосується формальної процедури розв'язання математичної задачі. Таке використання сягає 1940-х років і не пов'язане конкретно з поняттям «комп'ютерне програмування», яке поширилося пізніше. Щоб уникнути плутанини, інколи використовують термін «оптимізація» — наприклад, «квадратична оптимізація».
Формулювання задачі квадратичного програмування Задачу квадратичного програмування можна сформулювати так.:
Нехай x належить простору . Матриця n×n Q симетрична, і c — будь-який n×1 вектор.
Мінімізувати (відносно x)
З урахуванням одного або декількох обмежень у такій формі: (обмеження-нерівність) (обмеження-рівність)
де вказує на транспонування вектора . Позначення означає, що кожен елемент вектора Ax менший або дорівнює відповідному елементу вектора .
Якщо матриця є невід'ємноозначеною, то є опуклою функцією: у цьому разі задача квадратичного програмування має глобальний мінімум, якщо існує деякий допустимий вектор x (вектор, що задовольняє обмеження) і якщо обмежена знизу в допустимій області. Якщо матриця Q є додатноозначеною і задача має допустимий розв'язок, то глобальний мінімум є унікальним.
Якщо дорівнює нулю, то задача стає задачею лінійного програмування.
Пов'язана з цим задача може бути поставлена додаванням квадратичних обмежень на змінні.
Методи розв'язування
Розв'язувачі, мови сценаріїв і програмування
Див. також Квадратична функція
Примітки
Джерела
A6: MP2, pg.245.
(Доступна для завантаження на сторінці професора Katta G. Murty .)
Посилання Сторінка про квадратичне програмування (QP) Путівник NEOS квадратичним програмуванням