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

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

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

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

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

Нехай 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$ дорівнює нулю, то задача стає задачею лінійного програмування.

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

Методи розв'язування

Розв'язувачі, мови сценаріїв і програмування

Див. також

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

Примітки

↑ Wright, Stephen J. (2015), Continuous Optimization (Nonlinear and Linear Programming), у Nicholas J. Higham та ін. (ред.), The Princeton Companion to Applied Mathematics, Princeton University Press, с. 281—293
↑ Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (вид. 2nd). Berlin, New York: Springer-Verlag. с. 449. ISBN 978-0-387-30303-1..

Джерела

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 978-0-12-192350-1. MR 1150683.
Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A6: MP2, pg.245.
Gould, Nicholas I. M.; Toint, Philippe L. (2000). A Quadratic Programming Bibliography (PDF). RAL Numerical Analysis Group Internal Report 2000-1.
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. Архів оригіналу за 1 квітня 2010. Процитовано 10 червня 2011. (Доступна для завантаження на сторінці професора Katta G. Murty [Архівовано 6 Червня 2011 у Wayback Machine.].) MR 949214

Посилання

Сторінка про квадратичне програмування (QP) [Архівовано 7 Червня 2011 у Wayback Machine.] (англ.)
Путівник NEOS квадратичним програмуванням (англ.)

[PrincetonCompanion-1] Wright, Stephen J. (2015), Continuous Optimization (Nonlinear and Linear Programming), у Nicholas J. Higham та ін. (ред.), The Princeton Companion to Applied Mathematics, Princeton University Press, с. 281—293

[2] Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (вид. 2nd). Berlin, New York: Springer-Verlag. с. 449. ISBN 978-0-387-30303-1..

[1]

[2]