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

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

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

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

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

[ред. | ред. код]

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

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

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

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

(обмеження-нерівність)
(обмеження-рівність)

де вказує на транспонування вектора . Позначення означає, що кожен елемент вектора Ax менший або дорівнює відповідному елементу вектора .

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

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

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

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

[ред. | ред. код]

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

[ред. | ред. код]

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  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..

Джерела

[ред. | ред. код]

Посилання

[ред. | ред. код]