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