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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

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

Методи розв'язування[ред.ред. код]

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

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

Джерела[ред.ред. код]

Посилання[ред.ред. код]