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

Квадратичное программирование [quadratic program­ming] — раздел выпуклого программирования, совокупность методов решения экстремальных задач, в которых целевая функция (критерий) представляет собой многочлен второй степени (см. Квадратичная форма), а ограничения — линейны. В матричной форме может быть записана следующим образом:

 

x’ Dx + (c’,x)  → max

 

при условиях Ax = b, x ≥ 0.

Здесь x — n-мерный вектор-столбец, x’ и с’ n-мер­ные вектор-строки , bm-мерный вектор-столбец, Aматрица размерностью m ´ n, Dквадратная матрица (если она равна нулю, то получаем задачу линейного программирования).  Соответственно строится и двойственная задача К.п..

Задачи К.п. формулируются, например, тогда, когда оптимум зависит от объема продукции и цен, в свою очередь зависящих от объема. Наиболее эффективно они решаются в тех случаях, когда их удается свести к задачам линейного программирования. Но разработаны и специальные методы их решения.