Проблема линейной дополнительности

В теории математической оптимизации проблема линейной дополнительности (ЛКП) часто возникает в вычислительной механике и включает в себя известное квадратичное программирование как частный случай. Он был предложен Коттлом и Данцигом в 1968 году.

Формулировка

Учитывая действительную матрицу M и вектор q , проблема линейной дополнительности LCP( q , M ) ищет векторы z и w, которые удовлетворяют следующим ограничениям:

• $w,z\geqslant 0,$ (то есть каждый компонент этих двух векторов неотрицательен)
• $z^{T}w=0$ или эквивалентно $\sum \nolimits _{i}w_{i}z_{i}=0.$ Это условие дополнительности , поскольку оно означает, что для всех $i$, максимум один из $w_{i}$ и $z_{i}$ может быть положительным.
• $w=Mz+q$

Достаточным условием существования и единственности решения этой задачи является то, что симметрична положительно M определена . Если M таково, что LCP( q , M ) имеет решение для каждого q , то M является Q-матрицей . Если M таково, что LCP( q , M ) имеет единственное решение для каждого q , то M является P-матрицей . Обе эти характеристики достаточны и необходимы.

Вектор w является слабой переменной , и поэтому обычно отбрасывается после z обнаружения . Таким образом, проблему можно также сформулировать так:

• $Mz+q\geqslant 0$
• $z\geqslant 0$
• $z^{\mathrm {T} }(Mz+q)=0$ (условие дополнительности)

квадратичная минимизация:

Поиск решения задачи линейной дополнительности связан с минимизацией квадратичной функции

$f(z)=z^{T}(Mz+q)$

с учетом ограничений

${Mz}+q\geqslant 0$

$z\geqslant 0$

Эти ограничения гарантируют, что f всегда будет неотрицательным. Минимум f равен 0 в точке z тогда и только тогда, когда z решает проблему линейной дополнительности.

Если M положительно определен , любой алгоритм решения (строго) выпуклых QP может решить LCP. Специально разработанные алгоритмы поворота базисного обмена, такие как алгоритм Лемке и вариант симплексного алгоритма Данцига, использовались на протяжении десятилетий. Помимо полиномиальной временной сложности, методы внутренней точки также эффективны на практике.

Кроме того, задача квадратичного программирования формулируется как минимизация $f(x)=c^{T}x+{\tfrac {1}{2}}x^{T}Qx$ при условии $Ax\geqslant b$ а также $x\geqslant 0$ с Q симметричным

то же самое, что решение ЛКП с

$q={\begin{bmatrix}c\\-b\end{bmatrix}},\qquad M={\begin{bmatrix}Q&-A^{T}\\A&0\end{bmatrix}}$

Это связано с тем, что условия Каруша – Куна – Такера задачи QP можно записать как:

${\begin{cases}v=Qx-A^{T}{\lambda }+c\\s=Ax-b\\x,{\lambda },v,s\geqslant 0\\x^{T}v+{\lambda }^{T}s=0\end{cases}}$

где v - множители Лагранжа для ограничений неотрицательности, λ - множители для ограничений-неравенств и s - слабые переменные для ограничений-неравенств. Четвертое условие вытекает из дополнительности каждой группы переменных ( x , s ) с ее набором векторов KKT (оптимальных множителей Лагранжа), равным ( v , λ ) . В этом случае

$z={\begin{bmatrix}x\\\lambda \end{bmatrix}},\qquad w={\begin{bmatrix}v\\s\end{bmatrix}}$

Если ограничение неотрицательности на x ослаблено, размерность задачи LCP может быть уменьшена до количества неравенств, пока Q не является сингулярным (что гарантируется, если оно положительно определенное ). Множителей v больше нет, и первые условия ККТ можно переписать как:

$Qx=A^{T}{\lambda }-c$

или:

$x=Q^{-1}(A^{T}{\lambda }-c)$

предварительно умножив две части на А и вычитая b, получим:

$Ax-b=AQ^{-1}(A^{T}{\lambda }-c)-b\,$

Левая часть, согласно второму условию KKT, равна s . Замена и изменение порядка:

$s=(AQ^{-1}A^{T}){\lambda }+(-AQ^{-1}c-b)\,$

Звоню сейчас

${\begin{aligned}M&:=(AQ^{-1}A^{T})\\q&:=(-AQ^{-1}c-b)\end{aligned}}$

у нас есть LCP из-за отношения дополнительности между слабыми переменными s и их множителями Лагранжа λ . Решив ее, мы можем получить значение x из λ с помощью первого условия KKT.

Наконец, также можно обрабатывать дополнительные ограничения равенства:

$A_{eq}x=b_{eq}$

Это вводит вектор множителей Лагранжа µ той же размерности, что и $b_{eq}$.

Легко проверить, что M и Q для системы LCP $s=M{\lambda }+Q$ теперь выражаются как:

${\begin{aligned}M&:={\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\\0\end{bmatrix}}\\q&:=-{\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}c\\b_{eq}\end{bmatrix}}-b\end{aligned}}$

По λ мы теперь можем восстановить значения как x , так и множителя Лагранжа равенств µ :

${\begin{bmatrix}x\\\mu \end{bmatrix}}={\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\lambda -c\\-b_{eq}\end{bmatrix}}$

Фактически, большинство решателей QP работают по формулировке LCP, включая метод внутренней точки , поворот принципа принципа/дополнительности и методы активного множества . Проблемы LCP могут быть решены также с помощью алгоритма крест-накрест , и наоборот, для задач линейной дополнительности алгоритм крест-накрест завершается конечно, только если матрица является достаточной матрицей. Достаточной матрицей является обобщение как положительно определенной матрицы, так и P-матрицы , главные миноры которой положительны. Такие задачи LCP можно решить, если их сформулировать абстрактно с использованием теории ориентированного матроида .

См. также

• Теория дополнительности
• Физический движок. Физические движки импульсного/ограниченного типа для игр используют этот подход.
• Контактная динамика Контактная динамика при негладком подходе.
• Биматричные игры можно свести к LCP.

Ссылки

• Бьёрнер, Андерс ; Лас Верньяс, Мишель ; Штурмфельс, Бернд ; Уайт, Нил ; Циглер, Гюнтер (1999). «10 Линейное программирование». Ориентированные матроиды . Издательство Кембриджского университета. стр. 417–479. дои : 10.1017/CBO9780511586507 . ISBN  978-0-521-77750-6 . МР   1744046 .
• Коттл, RW; Данциг, Великобритания (1968). «Дополнительная теория математического программирования» . Линейная алгебра и ее приложения . 1 : 103–125. дои : 10.1016/0024-3795(68)90052-9 .
• Коттл, Ричард В.; Панг, Чон-Ши; Стоун, Ричард Э. (1992). Проблема линейной дополнительности . Информатика и научные вычисления. Бостон, Массачусетс: Academic Press, Inc., стр. xxiv+762 стр. ISBN.  978-0-12-192350-1 . МР   1150683 .
• Коттл, RW ; Панг, Ж.-С.; Венкатешваран, В. (март – апрель 1989 г.). «Достаточные матрицы и проблема линейной дополнительности». Линейная алгебра и ее приложения . 114–115: 231–249. дои : 10.1016/0024-3795(89)90463-1 . МР   0986877 .
• Чизмадия, Жолт; Иллес, Тибор (2006). «Новые алгоритмы типа крест-накрест для задач линейной дополнительности с достаточными матрицами» (PDF) . Методы оптимизации и программное обеспечение . 21 (2): 247–266. дои : 10.1080/10556780500095009 . S2CID   24418835 .
• Фукуда, Комей ; Намики, Макото (март 1994 г.). «Об экстремальном поведении метода наименьшего индекса Мерти». Математическое программирование . 64 (1): 365–370. дои : 10.1007/BF01582581 . МР   1286455 . S2CID   21476636 .
• Фукуда, Комей; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы поворота». Математическое программирование, серия Б. Материалы 16-го Международного симпозиума по математическому программированию, состоявшегося в Лозанне, 1997 г. 79 (1–3): 369–395. CiteSeerX   10.1.1.36.9373 . дои : 10.1007/BF02614325 . МР   1464775 . S2CID   2794181 . Препринт постскриптума .
• ден Хертог, Д.; Роос, К.; Терлаки, Т. (1 июля 1993 г.). «Проблема линейной дополнительности, достаточные матрицы и метод крест-накрест» (PDF) . Линейная алгебра и ее приложения . 187 : 1–14. дои : 10.1016/0024-3795(93)90124-7 .
• Мурти, Катта Г. (январь 1972 г.). «О числе решений проблемы дополнительности и связующих свойствах дополнительных конусов» (PDF) . Линейная алгебра и ее приложения . 5 (1): 65–108. дои : 10.1016/0024-3795(72)90019-5 . hdl : 2027.42/34188 .
• Мурти, КГ (1988). Линейная дополнительность, линейное и нелинейное программирование . Серия Сигма в прикладной математике. Том. 3. Берлин: Хелдерманн Верлаг. ISBN  978-3-88538-403-8 . МР   0949214 . Обновленная и бесплатная версия PDF на веб-сайте Катты Г. Мурти . Архивировано из оригинала 1 апреля 2010 г.
• Тейлор, Джошуа Адам (2015). Выпуклая оптимизация энергетических систем . Издательство Кембриджского университета. ISBN  9781107076877 .
• Терлаки, Тамаш; Чжан, Шу Чжун (1993). «Опорные правила линейного программирования: обзор последних теоретических разработок». Анналы исследования операций . Вырождение в задачах оптимизации. 46–47 (1): 203–233. CiteSeerX   10.1.1.36.7658 . дои : 10.1007/BF02096264 . ISSN   0254-5330 . МР   1260019 . S2CID   6058077 .
• Тодд, Майкл Дж. (1985). «Линейное и квадратичное программирование в ориентированных матроидах» . Журнал комбинаторной теории . Серия Б. 39 (2): 105–133. дои : 10.1016/0095-8956(85)90042-5 . МР   0811116 .

Дальнейшее чтение

• Р. Чандрасекаран. «Биматричные игры» (PDF) . стр. 5–7 . Проверено 18 декабря 2015 г.

Внешние ссылки

• LCPSollve — Простая процедура в GAUSS для решения линейной задачи дополнительности.
• Реализация Siconos / Numerics под лицензией GPL с открытым исходным кодом на языке C, алгоритм Лемке и другие методы решения LCP и MLCP.