Линейная задача о дополнительности
Линейная задача о дополнительности (LCP) — задача математической теории оптимизации, часто возникающая в вычислительной механике и охватывающая хорошо известное квадратичное программирование как частный случай. Задача был предложен Коттлом и Данцигом в 1968 годуШаблон:SfnpШаблон:SfnpШаблон:Sfnp.
Формулировка
Даны действительные матрица M и вектор q. Задача линейной дополнительности (LCP) предусматривает определение по (q, M) векторов z и w, которые удовлетворяют следующим ограничениям:
- (то есть каждая компонента этих векторов неотрицательна)
- или, что эквивалентно, Это условие из Шаблон:Iw, так как из него следует тот факт, что для всех хотя бы одна из величин и может быть положительна.
Достаточным условием существования и единственности решения этой задачи является то, что матрица M должна быть симметричной положительно определённой. Если матрица M такова, что LCP (q, M) имеет решение для каждого q, то M является Q-матрицей. Если M таково, что LCP (q, M) имеет единственное решение для каждого q, то M является P-матрицей. Обе эти характеристики являются достаточными и необходимымиШаблон:Sfnp.
Вектор w является переменной рассогласованияШаблон:Sfnp и поэтому она обычно отбрасывается после нахождения z. Таким образом, задача также может быть сформулирована следующим образом:
- (условие дополнительности)