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

В математике теория оптимизации, то задача линейной дополнительности (LCP) часто возникает в вычислительная механика и включает в себя хорошо известные квадратичное программирование как частный случай. Это было предложено Коттлом и Данциг в 1968 г.^[1][2][3]

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

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

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

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

Вектор ш это слабая переменная,^[5] и поэтому обычно выбрасывается после z находится. Таким образом, проблема также может быть сформулирована как:

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

Выпуклая квадратичная минимизация: условия минимума

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

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

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

${\displaystyle {Mz}+q\geqslant 0}$

${\displaystyle z\geqslant 0}$

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

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

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

то же самое, что и решение LCP с

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

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

${\displaystyle {\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 переменные запаса для ограничений неравенства. Четвертое условие вытекает из дополнительности каждой группы переменных. (Икс, s) с его набором векторов KKT (оптимальные множители Лагранжа) (v, λ). В таком случае,

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

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

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

или же:

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

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

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

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

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

Звоню сейчас

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

у нас есть LCP из-за отношения дополнительности между переменными резервов s и их множители Лагранжа λ. Как только мы ее решим, мы можем получить значение Икс из λ через первое условие ККТ.

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

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

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

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

${\displaystyle {\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}}}$

Из λ теперь мы можем восстановить значения обоих Икс и множитель равенств Лагранжа μ:

${\displaystyle {\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, включая метод внутренней точки, вращение принципа / дополнительности и активный набор методы.^[1][2] Проблемы LCP могут быть решены также перекрестный алгоритм,^[6][7][8][9] и наоборот, для задач линейной дополнительности алгоритм крест-накрест заканчивается, только если матрица является достаточной матрицей.^[8][9] А достаточная матрица является обобщением как положительно определенная матрица и из P-матрица, чей основные несовершеннолетние каждый положительный.^[8][9][10]Такие LCP могут быть решены, если они сформулированы абстрактно с использованием ориентированный матроид теория.^[11][12][13]

Смотрите также

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

Примечания

1. Мерти (1988)
2. Коттл, Панг и камень (1992)
3. Р. В. Коттл и Г. Б. Данциг. Дополнительная стержневая теория математического программирования. Линейная алгебра и ее приложения, 1:103-125, 1968.
4. Мурти, Катта Г. (январь 1972 г.). «О числе решений проблемы дополнительности и остовных свойствах дополнительных конусов» (PDF). Линейная алгебра и ее приложения. 5 (1): 65–108. Дои:10.1016/0024-3795(72)90019-5. HDL:2027.42/34188.
5. Тейлор, Джошуа Адам (2015), Выпуклая оптимизация энергосистем, Cambridge University Press, стр. 172, ISBN  9781107076877.
6. Фукуда и Намики (1994)
7. Фукуда и Терлаки (1997)
8. den Hertog, D .; Roos, C .; Терлаки, Т. (1 июля 1993 г.). «Проблема линейной дополнительности, достаточные матрицы и метод крест-накрест» (PDF). Линейная алгебра и ее приложения. 187: 1–14. Дои:10.1016/0024-3795(93)90124-7.
9. Csizmadia, Zsolt; Иллеш, Тибор (2006). «Новые алгоритмы типа крест-накрест для задач линейной дополнительности с достаточными матрицами» (PDF). Методы оптимизации и программное обеспечение. 21 (2): 247–266. Дои:10.1080/10556780500095009. S2CID  24418835.
10. Коттл, Р. В.; Pang, J.-S .; Венкатешваран, В. (март – апрель 1989 г.). «Достаточные матрицы и проблема линейной дополнительности». Линейная алгебра и ее приложения. 114–115: 231–249. Дои:10.1016/0024-3795(89)90463-1. МИСТЕР  0986877.
11. Тодд (1985)
12. Терлаки и Чжан (1993) Ошибка harvtxt: несколько целей (2 ×): CITEREFTerlakyZhang1993 (помощь): Терлаки, Тамаш; Чжан, Шу Чжун (1993). «Правила поворота для линейного программирования: обзор последних теоретических разработок». Анналы исследований операций. Вырождение в задачах оптимизации. 46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658. Дои:10.1007 / BF02096264. ISSN  0254-5330. МИСТЕР  1260019. S2CID  6058077.
13. Бьёрнер, Андерс; Лас Вергнас, Мишель; Штурмфельс, Бернд; Белый, Нил; Циглер, Гюнтер (1999). «10 Линейное программирование». Ориентированные матроиды. Издательство Кембриджского университета. С. 417–479. Дои:10.1017 / CBO9780511586507. ISBN  978-0-521-77750-6. МИСТЕР  1744046.

Рекомендации

• Коттл, Ричард В .; Пан, Чон-Ши; Стоун, Ричард Э. (1992). Проблема линейной дополнительности. Компьютерные науки и научные вычисления. Бостон, Массачусетс: Academic Press, Inc., стр. Xxiv + 762 стр. ISBN  978-0-12-192350-1. МИСТЕР  1150683.
• Коттл, Р. В.; Pang, J.-S .; Венкатешваран, В. (март – апрель 1989 г.). «Достаточные матрицы и проблема линейной дополнительности». Линейная алгебра и ее приложения. 114–115: 231–249. Дои:10.1016/0024-3795(89)90463-1. МИСТЕР  0986877.
• Csizmadia, Zsolt; Иллеш, Тибор (2006). «Новые алгоритмы типа крест-накрест для задач линейной дополнительности с достаточными матрицами» (PDF). Методы оптимизации и программное обеспечение. 21 (2): 247–266. Дои:10.1080/10556780500095009. S2CID  24418835.
• Фукуда, Комей; Намики, Макото (март 1994). «Об экстремальном поведении метода наименьшего индекса Мурти». Математическое программирование. 64 (1): 365–370. Дои:10.1007 / BF01582581. МИСТЕР  1286455. S2CID  21476636.
• den Hertog, D .; Roos, C .; Терлаки, Т. (1 июля 1993 г.). «Проблема линейной дополнительности, достаточные матрицы и метод крест-накрест» (PDF). Линейная алгебра и ее приложения. 187: 1–14. Дои:10.1016/0024-3795(93)90124-7.
• Мурти, К. Г. (1988). Линейная дополнительность, линейное и нелинейное программирование. Сигма-серия в прикладной математике. 3. Берлин: Heldermann Verlag. с. xlviii + 629 с. ISBN  978-3-88538-403-8. МИСТЕР  0949214. Обновленная и бесплатная версия PDF на веб-сайте Катты Г. Мурти. Архивировано из оригинал на 2010-04-01.
• Фукуда, Комей; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы разворота». Математическое программирование, серия B. Материалы 16-го Международного симпозиума по математическому программированию, состоявшегося в Лозанне, 1997 г. 79 (1–3): 369–395. CiteSeerX  10.1.1.36.9373. Дои:10.1007 / BF02614325. МИСТЕР  1464775. S2CID  2794181. Постскриптум препринт.
• Тодд, Майкл Дж. (1985). «Линейное и квадратичное программирование в ориентированных матроидах». Журнал комбинаторной теории. Серия Б. 39 (2): 105–133. Дои:10.1016/0095-8956(85)90042-5. МИСТЕР  0811116.
• Р. Чандрасекаран. «Биматричные игры» (PDF). стр. 5–7. Получено 18 декабря 2015.

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

• Р. В. Коттл и Г. Б. Данциг. Дополнительная стержневая теория математического программирования. Линейная алгебра и ее приложения, 1:103-125, 1968.
• Терлаки, Тамаш; Чжан, Шу Чжун (1993). «Правила поворота для линейного программирования: обзор последних теоретических разработок». Анналы исследований операций. Вырождение в задачах оптимизации. 46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658. Дои:10.1007 / BF02096264. ISSN  0254-5330. МИСТЕР  1260019. S2CID  6058077.

внешняя ссылка

• LCPSolve - Простая процедура в GAUSS для решения задачи линейной дополнительности
• Siconos / Цифровая реализация GPL с открытым исходным кодом на языке C алгоритма Лемке и другие методы для решения LCP и MLCP