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

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

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

Див. також

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

Примітки

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. 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.) MR 949214

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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..