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

Квадратичное программирование (англ. quadratic programming, QP) — это процесс решения задачи оптимизации специального типа, а именно — задачи оптимизации (минимизации или максимизации) квадратичной функции нескольких переменных при линейных ограничениях на эти переменные. Квадратичное программирование является частным случаем нелинейного программирования.

Задача квадратичного программирования с n переменными и m ограничениями можно сформулировать следующим образом^[1].

Дано:

• вещественный n-мерный вектор c,
• n × n-мерная вещественная симметричная матрица Q,
• m × n-мерная вещественная матрица A
• вещественный m-мерный вектор b,

Целью задачи квадратичного программирования является поиск n-мерного вектора x, который

минимизирует	${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }$
при условиях	${\displaystyle A\mathbf {x} \leq \mathbf {b} ,}$

где x^T обозначает транспонированный вектор. Обозначение Ax ≤ b означает, что любой элемент вектора Ax не превосходит соответствующего элемента вектора b.

Связанная задача программирования, квадратичная задача с квадратичными ограничениями^[англ.] имеет квадратичные ограничения на переменные.

Для общих значений используются различные методы, среди них

• Метод внутренней точки
• Метод активного набора^{[англ.] [2]}
• Метод обобщённого лагранжиана^{[англ.] [3]}
• метод сопряжённых градиентов
• Метод проекции градиента
• Модификация симплекс-метода^[2][4]

В случае, когда Q является положительно определённой, задача является частным случаем более общей задачи выпуклой оптимизации.

Задача квадратичного программирования несколько проще, если Q является положительно определённой и все ограничения являются равенствами (нет неравенств), поскольку в этом случае можно свести задачу к решению системы линейных уравнений. Если использовать множители Лагранжа и искать экстремум лагранжиана, можно легко показать, что решение задачи

минимизировать	${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }$
при условиях	${\displaystyle B\mathbf {x} =\mathbf {d} }$

определяется системой линейных уравнений

${\displaystyle {\begin{bmatrix}Q&B^{T}\\B&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix}-\mathbf {c} \\\mathbf {d} \end{bmatrix}}}$

где ${\displaystyle \lambda }$ — множество множителей Лагранжа, которые появляются вместе с решением ${\displaystyle \mathbf {x} }$.

Самый лёгкий способ решить эту систему — решить её прямыми методами (например, с помощью LU-разложения, очень удобного для небольших задач). Для больших задач возникают некоторые необычные трудности, наиболее заметные, когда задача не положительно определена (даже если ${\displaystyle Q}$ положительно определена), что делает потенциально очень трудно найти хороший математический подход и существует много подходов, зависящих от задачи^[].

Если число ограничений не равно числу переменных, можно попробовать относительно простую атаку, заменив переменные таким образом, что ограничения будут выполняться безусловно. Например, допустим, что ${\displaystyle \mathbf {d} =0}$ (переход к ненулевым значениям достаточно прост). Рассмотрим ограничения

${\displaystyle B\mathbf {x} =0}$

Введём новый вектор ${\displaystyle \mathbf {y} }$, определённый равенством

${\displaystyle Z\mathbf {y} =\mathbf {x} }$

где ${\displaystyle \mathbf {y} }$ имеет размерность ${\displaystyle \mathbf {x} }$ минус число ограничений. Тогда

${\displaystyle BZ\mathbf {y} =0}$

и если матрица ${\displaystyle Z}$ выбрана так, что ${\displaystyle BZ=0}$, равенства в ограничениях будут выполняться всегда. Поиск матрицы ${\displaystyle Z}$ подразумевает нахождение ядра матрицы ${\displaystyle B}$, что более или менее просто, в зависимости от структуры матрицы ${\displaystyle B}$. Подставляя новый вектор в исходные условия, получаем квадратичную задачу без ограничений:

${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{T}Q\mathbf {x} +\mathbf {c} ^{T}\mathbf {x} \quad \Rightarrow \quad {\tfrac {1}{2}}\mathbf {y} ^{T}Z^{T}QZ\mathbf {y} +(Z^{T}\mathbf {c} )^{T}\mathbf {y} }$

и решение можно будет найти, решив уравнение

${\displaystyle Z^{T}QZ\mathbf {y} =-Z^{T}\mathbf {c} }$

При некоторых ограничениях на ${\displaystyle Q}$ сокращённая матрица ${\displaystyle Z^{T}QZ}$ будет положительно определена. Можно написать вариант метода сопряжённых градиентов, при котором нет необходимости явного вычисления матрицы ${\displaystyle Z}$^[5].

Двойственная задача Лагранжа для квадратичного программирования является также задачей квадратичного программирования. Чтобы это понять, остановимся на случае ${\displaystyle c=0}$ с положительно определённой матрицей Q. Выпишем множители Лагранжа функции

${\displaystyle L(x,\lambda )={\tfrac {1}{2}}x^{T}Qx+\lambda ^{T}(Ax-b).}$

Если определим (лагранжеву) двойственную функцию ${\displaystyle g(\lambda )}$ как ${\displaystyle g(\lambda )=\inf _{x}L(x,\lambda )}$, мы ищем нижнюю границу ${\displaystyle L}$, используя ${\displaystyle \nabla _{x}L(x,\lambda )=0}$ и положительную определённость мaтрицы Q:

${\displaystyle x^{*}=-Q^{-1}A^{T}\lambda .}$

Следовательно, двойственна функция равна

${\displaystyle g(\lambda )=-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b,}$

и двойственной задачей Лагранжа для исходной задачи будет

минимизировать	${\displaystyle -{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b}$
при условиях	${\displaystyle \lambda \geqslant 0}$.

Кроме теории двойственности Лагранжа, существуют другие двойственные пары задач (например, двойственность Вулфа^[англ.]).

Для положительно определённой матрицы Q метод эллипсоидов решает задачу за полиномиальное время^[6]. Если, с другой стороны, Q не является положительно определённой, то задача становится NP-трудной^[7]. Фактически, даже если Q имеет единственное отрицательное собственное значение, задача NP-трудна^[8].

• Метод опорных векторов
• Последовательное квадратичное программирование
• Линейное программирование

• A page about QP Архивная копия от 7 июня 2011 на Wayback Machine
• NEOS Optimization Guide: Quadratic Programming Архивная копия от 18 июня 2017 на Wayback Machine
• Solve an example Quadratic Programming (QP) problem Архивная копия от 10 мая 2015 на Wayback Machine