线性互补问题

Linear Complementarity ProblemLCP进阶

求两组非负变量「一个为正另一个就为零」的数学问题，经典接触力求解就归结为它。

线性互补问题由 Cottle 和 Dantzig 在 1968 年提出：给定矩阵 M 和向量 q，找非负向量 z 和 w，使 w = Mz + q，并且 z 与 w 对应分量中至少有一个为零（互补条件）。放到仿真里，它正好描述接触：两个物体之间要么有间隙、接触力为零，要么贴在一起、接触力为正，两者不会同时为正，物理引擎每一步都要解出满足这类条件的接触力。ODE 的接触与摩擦模型就基于 Dantzig 的 LCP 求解器，游戏引擎常用投影高斯-赛德尔等迭代法近似求解。MuJoCo 则指出带摩擦的 LCP 属 NP 难问题，改用放松互补条件的凸软接触模型。