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

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

В матричной форме задача квадратичного программирования может быть записана следующим образом:

где - вектор неизвестных разметрности , состоящий из элементов ; - матрица коэффициентов размерности ; - вектор коэффициентов размерности ; - матрица ркзметрности ; - вектор-столбец размерности

Задача квадратичного программирования является  частным случаем задачи нелинейного программирования, в которой ограничения

являются линейными, а функция   представляет собой сумму линейной и квадратичной функции (квадратичной формы)

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

Функция   представляет собой сумму линейной функции (которая является и выпуклой, и вогнутой) и квадратичной формы. Если последняя является вогнутой (выпуклой), то задачи отыскания максимума (минимума) целевой функции могут быть успешно решены. Вопрос о том, будет ли квадратичная форма вогнутой или выпуклой, зависит от того, является ли она отрицательно-определенной, отрицательно-полуопределенной, положительно-определенной, положительно-полуопределенной или вообще неопределенной.

Реальные задачи технико-экономического содержания, математическими моделями которых являются задачи Квадратичного программирования, немногочисленны. Однако задачи Квадратичного программирования возникают как вспомогательные при решении различных задач математического программирования. Так, в одном из вариантов метода возможных направлений для численного решения задач нелинейного программирования проблему выбора направления спуска на каждой итерации сводят к решению задачи Квадратичного программирования. Задачи безусловной минимизации квадратичных функций, а также задачи Квадратичного программирования с ограничениями простейшего вида (напр., когда ограничениями являются условия неотрицательности переменных) возникают в результате применения метода регуляризации для решения неустойчивых (некорректных) задач линейного программирования и штрафных функций метода для решения задач линейного программирования.