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

Квадратичне програмування (Шаблон:Lang-en, QP) — особливий тип оптимізаційної задачі. Це задача оптимізації (зведення до мінімуму або максимуму) квадратичної функції декількох змінних при лінійних обмеженнях на ці змінні. Квадратичне програмування є одним з видів нелінійного програмування.

«Програмування» в цьому контексті стосується формальної процедури розв'язання математичної задачі. Таке використання сягає 1940-х років і не пов'язане конкретно з поняттям «комп'ютерне програмування», яке поширилося пізніше. Щоб уникнути плутанини, інколи використовують термін «оптимізація» — наприклад, «квадратична оптимізація».

Формулювання задачі квадратичного програмування

Задачу квадратичного програмування можна сформулювати так:

Нехай x належить простору ${ℝ}^n$. Матриця n×n Q симетрична, і c — будь-який n×1 вектор.

Мінімізувати (відносно x)

$f(𝐱)=\frac{1}{2}{𝐱}^{T}Q𝐱+{𝐜}^T𝐱.$

З урахуванням одного або декількох обмежень у такій формі:

$A𝐱\le 𝐛$ (обмеження-нерівність)

$E𝐱=𝐝$ (обмеження-рівність)

де ${𝐱}^T$ вказує на транспонування вектора $𝐱$. Позначення $Ax\le b$ означає, що кожен елемент вектора Ax менший або дорівнює відповідному елементу вектора $𝐛$.

Якщо матриця $Q$ є невід'ємноозначеною, то $f()$ є опуклою функцією: у цьому разі задача квадратичного програмування має глобальний мінімум, якщо існує деякий допустимий вектор x (вектор, що задовольняє обмеження) і якщо $f()$ обмежена знизу в допустимій області. Якщо матриця Q є додатноозначеною і задача має допустимий розв'язок, то глобальний мінімум є унікальним.

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

Пов'язана з цим задача Шаблон:Нп може бути поставлена додаванням квадратичних обмежень на змінні.

Див. також

• Квадратична функція

Джерела

• Шаблон:Cite book
• Шаблон:Cite book A6: MP2, pg.245.
• Шаблон:Cite web
• Шаблон:Cite book (Доступна для завантаження на сторінці професора Katta G. Murty Шаблон:Webarchive.) Шаблон:MR

Посилання

• Сторінка про квадратичне програмування (QP) Шаблон:Webarchive Шаблон:Ref-en
• Путівник NEOS квадратичним програмуванням Шаблон:Ref-en