Задача линейного дополнения (Linear Complementarity Problem)

Задача LCP - задача квадратичного программирования, пришла из области математической оптимизации. Применяется для решения задач о дополнительности, т.е. оптимизации вектора в соответствии с заданными условиями. Применяется в разных областях, в т.ч. в экономике и вычислительной механике.

Описание
Ссылки

Описание

LCP имеет одно решение тогда и только тогда, когда матрица A - симметричная ( A^T = A ) и положительно определенная ( при ненулевом x, x^T * (A * x)  > 0 ).

Существует два основных типа солверов для данной системы: прямые и итеративные.
Прямые пытаются найти точное решение, но они слишком чувствительны ( плохо относятся к большим, перегруженным системам ) и медленны. Разработаны они были первыми, и явные представители прямых солверов это Lemke и Dantzig.
Итеративные же солверы берут за основу некоторое начальное предположение ( initital guess ), и с каждой итерацией пытаются приблизится к истинному решению. При использовании данных методов возможно довольно легко менять соотношение скорость/точность. При попытке солвера уйти от правильного решения, его деятельность можно остановить, и далее не продолжать вычисления.
Применительно к динамике твердых тел ( в частности его использует E. Catto в Sequential Impulses ), часто используется модифицированный PGS.
Стоит отметить, что PGS решает систему подобного вида:
Ax = b
lo_i < x_i < hi_i
что не совсем соответствует определению LCP, однако, его можно доработать до нахождения двух неизвестных векторов, x и q.

Ссылки

Что такое Задача линейного дополнения (Linear Complementarity Problem)?

#constraint, #dynamics, #физика, #rigid body

12 июня 2009