WikiSort.ru - Не сортированное

Ограничения – равенства

Задача квадратичного программирования несколько проще, если 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}$ положительно определена), что делает потенциально очень трудно найти хороший математический подход и существует много подходов, зависящих от задачи^{[источник не указан 694 дня]}.

Если число ограничений не равно числу переменных, можно попробовать относительно простую атаку, заменив переменные таким образом, что ограничения будут выполняться безусловно. Например, допустим, что ${\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}$ подразумевает нахождение ядра^[en] матрицы ${\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].