Проблема линейной дополнительности
В теории математической оптимизации проблема линейной дополнительности (ЛКП) часто возникает в вычислительной механике и включает в себя известное квадратичное программирование как частный случай. Он был предложен Коттлом и Данцигом в 1968 году. [1] [2] [3]
Формулировка [ править ]
Учитывая действительную матрицу M и вектор q , проблема линейной дополнительности LCP( q , M ) ищет векторы z и w, которые удовлетворяют следующим ограничениям:
- (то есть каждый компонент этих двух векторов неотрицательен)
- или эквивалентно Это условие дополнительности , поскольку оно означает, что для всех , максимум один из и может быть положительным.
Достаточным условием существования и единственности решения этой задачи является то, что симметрична положительно M определена . Если M таково, что LCP( q , M ) имеет решение для каждого q , то M является Q-матрицей . Если M таково, что LCP( q , M ) имеет единственное решение для каждого q , то M является P-матрицей . Обе эти характеристики достаточны и необходимы. [4]
Вектор w является слабой переменной , [5] и поэтому обычно отбрасывается после z обнаружения . Таким образом, проблему можно также сформулировать так:
- (условие дополнительности)
квадратичная минимизация: минимальные условия Выпуклая
Поиск решения задачи линейной дополнительности связан с минимизацией квадратичной функции
с учетом ограничений
Эти ограничения гарантируют, что f всегда будет неотрицательным. Минимум f равен 0 в точке z тогда и только тогда, когда z решает проблему линейной дополнительности.
Если M положительно определен , любой алгоритм решения (строго) выпуклых QP может решить LCP. Специально разработанные алгоритмы поворота базисного обмена, такие как алгоритм Лемке и вариант симплексного алгоритма Данцига, использовались на протяжении десятилетий. Помимо полиномиальной временной сложности, методы внутренней точки также эффективны на практике.
Кроме того, задача квадратичного программирования формулируется как минимизация при условии а также с Q симметричным
то же самое, что решение ЛКП с
Это связано с тем, что условия Каруша – Куна – Такера задачи QP можно записать как:
где v - множители Лагранжа для ограничений неотрицательности, λ - множители для ограничений-неравенств и s - слабые переменные для ограничений-неравенств. Четвертое условие вытекает из дополнительности каждой группы переменных ( x , s ) с ее набором векторов KKT (оптимальных множителей Лагранжа), равным ( v , λ ) . В этом случае
Если ограничение неотрицательности на x ослаблено, размерность задачи LCP может быть уменьшена до количества неравенств, пока Q не является сингулярным (что гарантируется, если оно положительно определенное ). Множителей v больше нет, и первые условия ККТ можно переписать как:
или:
предварительно умножив две части на А и вычитая b, получим:
Левая часть, согласно второму условию KKT, равна s . Замена и изменение порядка:
Звоню сейчас
у нас есть LCP из-за отношения дополнительности между слабыми переменными s и их множителями Лагранжа λ . Решив ее, мы можем получить значение x из λ с помощью первого условия KKT.
Наконец, также можно обрабатывать дополнительные ограничения равенства:
Это вводит вектор множителей Лагранжа µ той же размерности, что и .
Легко проверить, что M и Q для системы LCP теперь выражаются как:
По λ мы теперь можем восстановить значения как x , так и множителя Лагранжа равенств µ :
Фактически, большинство решателей QP работают по формулировке LCP, включая метод внутренней точки , поворот принципа принципа/дополнительности и методы активного множества . [1] [2] Проблемы LCP могут быть решены также с помощью алгоритма крест-накрест , [6] [7] [8] [9] и наоборот, для задач линейной дополнительности алгоритм крест-накрест завершается конечно, только если матрица является достаточной матрицей. [8] [9] Достаточной матрицей является обобщение как положительно определенной матрицы, так и P-матрицы , главные миноры которой положительны. [8] [9] [10] Такие задачи LCP можно решить, если их сформулировать абстрактно с использованием теории ориентированного матроида . [11] [12] [13]
См. также [ править ]
- Теория дополнительности
- Физический движок. Физические движки импульсного/ограниченного типа для игр используют этот подход.
- Контактная динамика Контактная динамика при негладком подходе.
- Биматричные игры можно свести к LCP.
Примечания [ править ]
- ↑ Перейти обратно: Перейти обратно: а б Мурти (1988) .
- ↑ Перейти обратно: Перейти обратно: а б Коттл, Панг и Стоун (1992) .
- ^ Коттл и Данциг (1968) .
- ^ Мурти (1972) .
- ^ Тейлор (2015) , с. 172 .
- ^ Фукуда и Намики (1994) .
- ^ Фукуда и Терлаки (1997) .
- ↑ Перейти обратно: Перейти обратно: а б с ден Хертог, Роос и Терлаки (1993) .
- ↑ Перейти обратно: Перейти обратно: а б с Чизмадиа и Иллес (2006) .
- ^ Коттл, Панг и Венкатешваран (1989) .
- ^ Тодд (1985) .
- ^ Терлаки и Чжан (1993) .
- ^ Бьорнер и др. (1999) .
Ссылки [ править ]
- Бьёрнер, Андерс ; Лас Верньяс, Мишель ; Штурмфельс, Бернд ; Уайт, Нил ; Циглер, Гюнтер (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.