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

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

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

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

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

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

$f(\mathbf{x}) = \tfrac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x}.$

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

$A\mathbf{x} \leq \mathbf b$ (обмеження-нерівність)

$E\mathbf{x} = \mathbf d$ (обмеження-рівність)

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

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

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

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

Див. також

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

Джерела

• Cottle Richard W., Pang Jong-Shi, Stone Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc. с. xxiv+762 pp. ISBN 0-12-192350-9.  MR1150683
• Garey Michael R., Johnson David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  A6: MP2, pg.245.
• Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics 3. Berlin: Heldermann Verlag. с. xlviii+629 pp. ISBN 3-88538-403-5.  (Доступна для звантаження на сторінці професора Katta G. Murty.) MR949214

Посилання

• Сторінка про квадратичне програмування (QP) (англ.)
• Путівник NEOS квадратичним програмуванням (англ.)