Топ питань
Часова шкала
Чат
Перспективи
Квадратичне програмування
З Вікіпедії, вільної енциклопедії
Remove ads
Квадратичне програмування (англ. Quadratic programming, QP) — особливий тип оптимізаційної задачі. Це задача оптимізації (зведення до мінімуму або максимуму) квадратичної функції декількох змінних при лінійних обмеженнях на ці змінні. Квадратичне програмування є одним з видів нелінійного програмування.
«Програмування» в цьому контексті стосується формальної процедури розв'язання математичної задачі. Таке використання сягає 1940-х років і не пов'язане конкретно з поняттям «комп'ютерне програмування», яке поширилося пізніше. Щоб уникнути плутанини, інколи використовують термін «оптимізація» — наприклад, «квадратична оптимізація»[1].
Remove ads
Формулювання задачі квадратичного програмування
Узагальнити
Перспектива
Задачу квадратичного програмування можна сформулювати так[2]:
Нехай x належить простору . Матриця n×n Q симетрична, і c — будь-який n×1 вектор.
Мінімізувати (відносно x)
З урахуванням одного або декількох обмежень у такій формі:
де вказує на транспонування вектора . Позначення означає, що кожен елемент вектора Ax менший або дорівнює відповідному елементу вектора .
Якщо матриця є невід'ємноозначеною, то є опуклою функцією: у цьому разі задача квадратичного програмування має глобальний мінімум, якщо існує деякий допустимий вектор x (вектор, що задовольняє обмеження) і якщо обмежена знизу в допустимій області. Якщо матриця Q є додатноозначеною і задача має допустимий розв'язок, то глобальний мінімум є унікальним.
Якщо дорівнює нулю, то задача стає задачею лінійного програмування.
Пов'язана з цим задача квадратичного програмування з квадратичними обмеженнями[en] може бути поставлена додаванням квадратичних обмежень на змінні.
Remove ads
Методи розв'язування
![]() | Цей розділ потребує доповнення. (червень 2011) |
Розв'язувачі, мови сценаріїв і програмування
![]() | Цей розділ потребує доповнення. (червень 2011) |
Див. також
Примітки
Джерела
Посилання
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads