Jump to content

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

В теории математической оптимизации проблема линейной дополнительности (ЛКП) часто возникает в вычислительной механике и включает в себя известное квадратичное программирование как частный случай. Он был предложен Коттлом и Данцигом в 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]

См. также [ править ]

Примечания [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

  • LCPSollve — Простая процедура в GAUSS для решения линейной задачи дополнительности.
  • Реализация Siconos / Numerics под лицензией GPL с открытым исходным кодом на языке C, алгоритм Лемке и другие методы решения LCP и MLCP.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 23b9a2c34d384649a3efd94e5857eb00__1712317140
URL1:https://arc.ask3.ru/arc/aa/23/00/23b9a2c34d384649a3efd94e5857eb00.html
Заголовок, (Title) документа по адресу, URL1:
Linear complementarity problem - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)