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

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

• 1 Формулировка
• 2 Выпуклая квадратичная минимизация: минимальные условия
• 3 См. Также
• 4 Примечания
• 5 Ссылки
• 6 Дополнительная литература
• 7 Внешние ссылки

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

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

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

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

• $M\; z\; +\; q\; ⩾\; 0\; \{\backslash \; displaystyle\; Mz\; +\; q\; \backslash \; geqslant\; 0\}$
• $z\; ⩾\; 0\; \{\backslash \; displaystyle\; z\; \backslash \; geqslant\; 0\}$
• $z\; T\; (\; M\; z\; +\; q)\; знак\; равно\; 0\; \{\backslash \; displaystyle\; z\; ^\; \{\backslash \; mathrm\; \{T\}\}\; (Mz\; +\; q)\; =\; 0\}$(условие дополнительности)

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

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

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

$M\; z\; +\; q\; ⩾\; 0\; \{\backslash \; displaystyle\; \{Mz\}\; +\; q\; \backslash \; geqslant\; 0\}$

$z\; ⩾\; 0\; \{\backslash \; displaystyle\; z\; \backslash \; geqslant\; 0\}$

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

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

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

аналогично решению LCP с

$q\; =\; [c\; -\; b],\; M\; =\; [Q\; -\; ATA\; 0]\; \{\backslash \; displaystyle\; q\; =\; \{\backslash \; begin\; \{bmatrix\}\; c\; \backslash \backslash \; -\; b\; \backslash \; end\; \{bmatrix\}\},\; \backslash \; qquad\; M\; =\; \{\backslash \; begin\; \{bmatrix\}\; Q\; -A\; ^\; \{T\}\; \backslash \backslash \; A\; 0\; \backslash \; end\; \{bmatrix\}\; \}\}$

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

$\{v\; =\; Q\; x\; -\; AT\; \lambda \; +\; cs\; =\; A\; x\; -\; bx,\; \lambda ,\; v,\; s\; ⩾\; 0\; Икс\; T\; v\; +\; \lambda \; T\; s\; знак\; равно\; 0\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{cases\}\; v\; =\; Qx-A\; ^\; \{T\}\; \{\backslash \; lambda\}\; +\; c\; \backslash \backslash \; s\; =\; Ax-b\; \backslash \backslash \; x,\; \{\backslash \; lambda\},\; v,\; s\; \backslash \; geqslant\; 0\; \backslash \backslash \; x\; ^\; \{T\}\; v\; +\; \{\backslash \; lambda\}\; ^\; \{T\}\; s\; =\; 0\; \backslash \; end\; \{cases\}\}\}$

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

$z\; =\; [x\; \lambda ],\; w\; =\; [vs]\; \{\backslash \; displaystyle\; z\; =\; \{\backslash \; begin\; \{bmatrix\}\; x\; \backslash \backslash \backslash \; lambda\; \backslash \; end\; \{bmatrix\}\},\; \backslash \; qquad\; w\; =\; \{\backslash \; begin\; \{\; bmatrix\}\; v\; \backslash \backslash \; s\; \backslash \; end\; \{bmatrix\}\}\}$

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

$Q\; x\; =\; AT\; \lambda \; -\; c\; \{\backslash \; displaystyle\; Qx\; =\; A\; ^\; \{T\}\; \{\backslash \; lambda\}\; -c\}$

или:

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

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

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

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

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

Звонок сейчас

$M:\; =\; (AQ\; -\; 1\; AT)\; q:\; =\; (-\; AQ\; -\; 1\; c\; -\; b)\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; M\; :\; =\; (AQ\; ^\; \{-\; 1\}\; A\; ^\; \{T\})\; \backslash \backslash \; q\; :\; =\; (-\; AQ\; ^\; \{-\; 1\}\; cb)\; \backslash \; end\; \{align\}\}\}$

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

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

$A\; eqx\; =\; beq\; \{\backslash \; displaystyle\; A\_\; \{eq\}\; x\; =\; b\_\; \{eq\}\}$

Это вводит вектор множителей Лагранжа μ, с тем же размером, что и $beq\; \{\backslash \; displaystyle\; b\_\; \{eq\}\}$.

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

$M:\; =\; [A\; 0]\; [QA\; eq\; T\; -\; A\; eq\; 0]\; -\; 1\; [AT\; 0]\; q:\; =\; -\; [A\; 0\; ]\; [QA\; eq\; T\; -\; A\; eq\; 0]\; -\; 1\; [cbeq]\; -\; b\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; M\; :\; =\; \{\backslash \; begin\; \{bmatrix\}\; A\; 0\; \backslash \; end\; \{bmatrix\}\}\; \{\backslash \; begin\; \{bmatrix\}\; QA\_\; \{\; eq\}\; ^\; \{T\}\; \backslash \backslash \; -\; A\_\; \{eq\}\; 0\; \backslash \; end\; \{bmatrix\}\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{bmatrix\}\; A\; ^\; \{T\}\; \backslash \backslash \; 0\; \backslash \; end\; \{bmatrix\}\}\; \backslash \backslash \; q\; :\; =\; -\; \{\backslash \; begin\; \{bmatrix\}\; A\; 0\; \backslash \; end\; \{bmatrix\}\}\; \{\backslash \; begin\; \{bmatrix\}\; Q\; A\_\; \{eq\}\; ^\; \{T\}\; \backslash \backslash \; -\; A\_\; \{eq\}\; 0\; \backslash \; end\; \{bmatrix\}\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{bmatrix\}\; c\; \backslash \backslash \; b\_\; \{eq\}\; \backslash \; end\; \{bmatrix\}\}\; -\; b\; \backslash \; end\; \{align\}\}\}$

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

$[x\; \mu ]\; =\; [QA\; eq\; T\; -\; A\; eq\; 0]\; -\; 1\; [AT\; \lambda \; -\; c\; -\; beq]\; \{\backslash \; displaysty\; le\; \{\backslash \; begin\; \{bmatrix\}\; x\; \backslash \backslash \backslash \; mu\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; Q\; A\_\; \{eq\}\; ^\; \{T\}\; \backslash \backslash \; -\; A\_\; \{eq\}\; 0\; \backslash \; end\; \{bmatrix\}\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{bmatrix\}\; A\; ^\; \{T\}\; \backslash \; lambda\; -c\; \backslash \backslash \; -\; b\_\; \{eq\}\; \backslash \; end\; \{bmatrix\}\}\}$

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

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

• Cottle, Ричард В.; Пан, Чон-Ши; Стоун, Ричард Э. (1992). Проблема линейной дополнительности. Компьютерные науки и научные вычисления. Бостон, Массачусетс: Academic Press, Inc., стр. Xxiv + 762 с. ISBN 978-0-12-192350-1. MR 1150683. CS1 maint: ref = harv (link )
• Cottle, RW ; Pang, J.-S.; Venkateswaran, V. (март – апрель 1989 г.). «Достаточные матрицы и проблема линейной дополнительности». Линейная алгебра и ее Приложения. 114–115: 231–249. doi : 10.1016 / 0024-3795 (89) 90463-1. MR 0986877. CS1 maint: ref = harv ( ссылка )
• Csizmadia, Zsolt; Illés, Tibor (2006). «Новые перекрестные алгоритмы для задач линейной дополнительности с достаточным количеством матриц» (PDF). Методы и программное обеспечение оптимизации. 21 (2): 247–266. doi : 10.1080 / 10556780500095009. Цитата имеет пустой неизвестный параметр: | 1 =( )
• ; Намики, Макото (март 1994 г.). «Об экстремальном поведении метода наименьшего индекса Мурти». Математическое программирование. 64 (1): 365–370. doi : 10.1007 / BF01582581. MR 1286455. CS1 maint: ref = harv (ссылка )
• den Hertog, D.; Roos, С.; Терлаки, Т. (1 июля 1993 г.). «Проблема линейной дополнительности, достаточные матрицы и метод крест-накрест» (PDF). Линейная алгебра и ее приложения. 187 : 1–14. doi : 10.1016 / 0024-3795 (93) 90124-7. CS1 maint: ref = harv (ссылка )
• Murty, KG (1988). Линейная дополнительность, линейное и нелинейное программирование. Сигма-серия в прикладной математике. 3 . Berlin: Heldermann Verlag. Pp. Xlviii + 629 pp. ISBN 978-3-88538-403-8. MR 0949214. Обновленная и бесплатная версия PDF на веб-сайте Катты Г. Мурти. Архивировано с оригинала на 2010-04- 01. CS1 maint: ref = harv (link )
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (ред.). «Перекрестные методы: A свежий взгляд на поворотные алгоритмы ». Математическое программирование, серия B. Доклады 16-го Международного симпозиума по математическому программированию, состоявшегося в Лозанне, 1997. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi : 10.1007 / BF02614325. MR 1464775. Препринт PostScript. Cite имеет пустые неизвестные параметры: | 1 =и | 2 =() CS1 maint: r ef = harv (ссылка )
• (1985). «Линейное и квадратичное программирование в ориентированных матроидах». Журнал комбинаторной теории. Серия Б. 39 (2): 105–133. doi : 10.1016 / 0095-8956 (85) 90042-5. MR 0811116. CS1 maint: ref = harv (ссылка )
• Р. Чандрасекаран. «Биматричные игры» (PDF). Стр. 5–7. Проверено 18 декабря 2015 г.

• RW Cottle и GB Dantzig. Дополнительная теория вращения математическое программирование. Линейная алгебра и ее приложения, 1: 103-125, 1968.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on the недавние теоретические разработки". Annals of Operations Исследования. Вырождение в задачах оптимизации. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. doi : 10.1007 / BF02096264. ISSN 0254-5330. MR 1260019. Cite имеет пустой неизвестный параметр: | 1 =() CS1 maint: ref = harv (ссылка )

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