ПРОГРАММИРОВАНИЕ КВАДРАТИЧНОЕ

— раздел программирования математического, рассматривающий специальный класс задач, в которых минимизируемая функция квадратична, а ограничения линейны. В общем виде задача П. к. может быть сформулирована так: пусть С — симметричная матрица размера , А — матрица размера , х - -мерный вектор, b — -мерный вектор, с — -мерный вектор; требуется минимизировать ф-цию при ограничениях Здесь скалярное произведение векторов х и у, а неравенство х у означает, что каждая компонента вектора х меньше или равна соответствующей компоненте вектора у.

В задаче П. к. обычно предполагается, что матрица С полуположительно определена, т. е. для всех х. В этом случае ф-ция является выпуклой. Если точка решение задачи П. к., то выполняются следующие необходимые и достаточные условия: существует такой -мерный вектор что Здесь Л — матрица, транспонированная к А.

В случае, когда матрица С строго положительно определена, т. е. для всех , для задачи П. к. может быть сформулирована двойственная задача: максимизировать

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

Для численного решения задачи П. к. применимы все методы, пригодные для решения общей задачи программирования выпуклого. Существует ряд методов, дающих возможность решать задачу П. за конечное число шагов. Лит.: Зойтендейк Г. Методы возможных направлений. Пер. с англ. М., 1963 [библиогр. с. 171 — 174]; Кюнци Г. П., Крелле В. Нелинейное программирование. Пер. с нем. М.. 1965 [библиогр. с. 286—293]. В. Я. Пшеничный.