선형 상보성 문제

수치해석 물리 게임 개발 마지막 수정: 2026-07-19 04:37:19

1. 개요[편집]

선형 상보성 문제 Linear Complementarity Problem
약칭	LCP
표기	LCP(q, M)
조건	w = Mz + q, w ≥ 0, z ≥ 0, wᵀz = 0
일반 복잡도	NP-난해 (일반 M)
대표 응용	강체 접촉, 이차계획법, 자유경계 문제

물체는 밀 수는 있어도 당길 수는 없다. 이 한 줄의 부등식이 물리 엔진을 선형대수 문제에서 조합 최적화 문제로 승격시켰다.

선형 상보성 문제(Linear Complementarity Problem, LCP)는 주어진 행렬 $M \in \mathbb{R}^{n \times n}$ 과 벡터 $q \in \mathbb{R}^n$ 에 대해, 다음을 동시에 만족하는 벡터 쌍 $(w, z)$ 를 찾는 문제이다.

w = Mz + q, \qquad w \ge 0, \quad z \ge 0, \quad w^{\mathsf T} z = 0

앞의 등식만 있으면 그냥 반복법으로 풀면 되는 선형계다. 핵심은 마지막 상보 조건 $w^{\mathsf T} z = 0$ 이다. 두 벡터가 모두 비음수이므로 이 내적이 0이라는 말은 성분별로 $w_i z_i = 0$ , 즉 각 지표마다 둘 중 최소 하나는 0이라는 뜻이다. 어느 쪽이 0인지는 미리 알 수 없고 풀면서 결정된다. 연속적인 선형 문제 안에 $2^n$ 개의 조합 선택이 숨어 있는 셈이고, 그래서 일반 $M$ 에 대한 LCP는 NP-난해다.

제약 해결기 문서가 “게임 물리는 결국 LCP를 근사해서 푼다”고 말할 때의 그 LCP가 이것이다.

2. 접촉이 왜 LCP인가[편집]

강체 접촉이 LCP가 되는 논리는 놀랄 만큼 직접적이다. 접촉점 $i$ 에서 법선 방향 상대 속도를 $v_i$ , 그 접촉에서 발생하는 법선 임펄스를 $\lambda_i$ 라 하면 물리적으로 요구되는 조건은 셋이다.

$v_i \ge 0$ — 파고들지 않는다(분리하거나, 최소한 붙어 있다).
$\lambda_i \ge 0$ — 접촉은 밀기만 한다. 당기는 접촉력은 없다.
$v_i \lambda_i = 0$ — 떨어지고 있으면 힘이 0이고, 힘이 있으면 떨어지지 않는다.

이 세 줄이 시뇨리니 조건(Signorini condition)이고, 형태가 정확히 상보성이다. 여기에 강체 동역학의 운동 방정식과 제약 자코비안 $J$ 를 대입하면 속도는 임펄스의 아핀 함수가 된다.

v = \underbrace{J M_{\text{body}}^{-1} J^{\mathsf T}}_{A} \lambda + b

행렬 $A$ 는 델라수스 연산자(Delassus operator) 또는 유효 질량 행렬이라 불리며, $M_{\text{body}}$ 가 양정치이므로 $A$ 는 대칭 준양정치다. 그러니 접촉 문제는 LCP $(b, A)$ 이고, $A$ 가 대칭 PSD라는 성질 덕분에 이 LCP는 다음 이차계획법과 동치가 된다.

\min_{\lambda \ge 0} \ \tfrac{1}{2}\lambda^{\mathsf T} A \lambda + b^{\mathsf T} \lambda

이 QP의 카루시-쿤-터커 조건을 쓰면 원래의 LCP가 그대로 나온다. 상보성이 곧 KKT의 상보 여유(complementary slackness)이고, $\lambda$ 는 라그랑주 승수법의 승수 그 자체다. 볼록 QP라 다항 시간에 풀리므로, 접촉 LCP는 “NP-난해한 일반 LCP”의 무서운 사례가 아니라 얌전한 부류에 속한다. 마찰이 끼기 전까지는.

3. 마찰이 부수는 것[편집]

쿨롱 마찰은 접선 마찰력의 크기가 $\|\lambda_t\| \le \mu \lambda_n$ 을 만족해야 한다는 조건이다. 이것은 원뿔(friction cone)이고, 원뿔은 다면체가 아니므로 문제가 비선형 상보성 문제(NCP)가 된다. 게다가 마찰의 상한이 법선 임펄스라는 다른 미지수에 의존한다.

실무의 표준 우회로는 마찰 원뿔을 각뿔로 근사하는 것이다. 접선 평면에 4방향 또는 8방향 기저를 잡아 원뿔을 다면체로 바꾸면 다시 LCP가 되고, 여기에 조인트 같은 등식 제약(부호 제한 없는 변수)을 섞으면 혼합 LCP(MLCP)가 된다.¹ 스튜어트와 트링클(1996), 아니테스쿠와 포트라(1997)의 시간 이산화 정식화가 이 계보의 고전이다.

다만 각뿔 근사는 마찰이 방향에 따라 세기가 달라지는 이방성을 만들고(대각선 방향으로 미끄러지는 상자), 원뿔을 촘촘히 쪼갤수록 문제 크기가 커진다. 게임 엔진은 아예 정식성을 포기하고 박스 마찰(boxed LCP)을 쓴다 — 접선 임펄스를 직전 반복의 법선 임펄스로 계산한 $\pm\mu\lambda_n$ 구간에 매 반복 클램프하는 것이다. 수렴 보장은 없지만 싸고, 대개 그럴듯해 보인다.

한 가지 불편한 진실도 있다. 강체 + 쿨롱 마찰 조합은 해가 존재하지 않거나 여러 개 존재할 수 있다. 마찰이 큰 경우 물체를 미는 데 필요한 힘이 자기 자신을 증폭시켜 모순에 빠지는 팽르베 역설(Painlevé paradox)이 대표 사례이며, 이때 LCP는 실행 가능해(feasible)가 없다. 물리 엔진이 가끔 물체를 우주로 쏘아 올리는 데는 이런 뿌리 깊은 이유가 있다.²

4. 해법[편집]

방법	성격	특징
렘키(Lemke) 알고리즘	피벗, 직접법	유한 종료 보장(copositive-plus 등 조건 하), 최악에는 지수 시간
댄치그(Dantzig) 알고리즘	피벗, 직접법	정확한 해. Baraff(1994)가 강체 접촉에 도입
주 피벗법(Murty)	피벗	활성 집합을 직접 갱신
PGS / PSOR	반복법	게임 엔진 표준. 싸고 무조건 돌아감, 수렴은 느림
내점법	반복법	대규모 볼록 문제에 강함, 실시간엔 무거움

피벗 계열은 가우스 소거법의 피벗팅처럼 기저를 바꿔가며 상보 조건을 만족하는 조합을 탐색한다. 정확하지만 접촉 개수가 수백 개로 늘면 실시간 예산을 넘긴다.

그래서 물리 엔진은 투영 가우스-자이델(PGS)로 간다. 가우스-자이델 반복을 한 성분 갱신할 때마다 유효 구간으로 잘라내는(projection) 방식이고, 제약 해결기 문서의 순차 임펄스가 바로 이것을 속도 수준에서 임펄스로 구현한 형태다. 반복을 4~10회에서 끊으므로 해는 정확하지 않고, 그 오차가 쌓인 결과가 상자 더미의 미세한 떨림과 물러짐이다. 웜 스타팅(직전 프레임 $\lambda$ 를 초기값으로 재사용)이 실질적으로 반복 횟수를 몇 배 벌어주는 이유도, PGS의 수렴이 초기값에 크게 좌우되기 때문이다.

행렬 $A$ 는 접촉이 국소적이라 대단히 희소하다. 실제 구현은 $A$ 를 명시적으로 만들지 않고 $J$ 와 $M_{\text{body}}^{-1}$ 만 들고 다니며 곱셈을 그때그때 수행한다. 접촉 100개짜리 $100 \times 100$ 밀집 행렬을 매 프레임 조립하는 것보다 훨씬 싸다.

구현체로는 ODE의 dSolveLCP(댄치그 계열), Bullet의 MLCP 솔버 모듈(댄치그·렘키·PGS 선택 가능), 상용 PhysX의 반복 솔버, 그리고 학술·로보틱스 쪽의 PATH 솔버와 Siconos가 널리 쓰인다. 위치 수준에서 접근하는 위치 기반 동역학 계열은 LCP를 명시적으로 세우지 않지만, 제약을 순차 투영한다는 점에서 PGS와 정신적 친척이다.

5. 물리 밖의 LCP[편집]

접촉만의 이야기가 아니다. LCP는 변분부등식과 자유경계 문제의 이산화에서 반복적으로 등장한다.

장애물 문제(obstacle problem) — 팽팽한 막을 장애물 위에 씌울 때 “닿았거나(접촉력 발생) 떠 있거나(힘 0)“가 그대로 상보 조건이다. 유한요소 이산화하면 LCP.
미국식 옵션 가격결정 — 조기 행사 경계가 미지인 블랙-숄즈 부등식이 이산화 후 LCP가 된다. 금융공학에서 LCP를 만나는 표준 경로.
저널 베어링의 캐비테이션 — 레이놀즈 방정식에서 압력이 증기압 아래로 못 내려간다는 제약(Elrod–Adams 모델)이 상보성이다.
접촉 해석 — 유한요소 구조해석의 접촉 역시 이론적 뼈대는 같은 시뇨리니 조건이다. 다만 여기서는 실시간 제약이 없어 페널티법이나 증강 라그랑주법을 쓰는 경우가 더 많다.

6. 여담[편집]

논문에서는 “LCP를 푼다”고 쓰지만 게임 엔진에서 실제로 벌어지는 일은 “LCP를 8번 반복하다 만다”이다. 그 8이라는 숫자를 정하는 것이 물리 프로그래머의 주된 업무다.
접촉 개수는 장면 복잡도가 아니라 적층 높이에 민감하다. 상자 20개를 바닥에 흩어 놓으면 멀쩡하지만 20층으로 쌓으면 젤리가 된다. 정보가 위에서 아래로 한 반복에 한 층씩만 전파되기 때문이다.³
마찰 원뿔을 4각뿔로 근사한 엔진에서 경사면에 상자를 놓으면 대각선으로 슬금슬금 미끄러진다. 물리 버그처럼 보이지만 정확히는 이산화 아티팩트다.

7. 관련 문서[편집]

MLCP는 등식 제약에 해당하는 행에는 부호 제한이 없는 자유 변수를 두고, 부등식 행에만 상보 조건을 거는 형태다. 조인트로 연결된 관절 사슬(등식)과 바닥 접촉(부등식)이 한 장면에 공존하는 게임에서는 순수 LCP보다 이쪽이 실제 정식화에 가깝다. ↩
팽르베가 1895년에 제시한 예는 마찰이 큰 경사면 위를 미끄러지는 막대다. 강체 가정과 쿨롱 마찰이 동시에 성립하는 해가 존재하지 않는 구성이 만들어진다. 해결책은 셋 중 하나 — 강체 가정을 버리거나(약간의 탄성 허용), 마찰 계수를 낮추거나, 충격적 운동(impulsive motion)을 허용하는 확장 정식화를 쓰는 것이다. 게임 엔진은 대개 첫 번째와 두 번째를 몰래 쓴다. ↩
가우스-자이델의 정보 전파 속도가 반복당 이웃 하나이기 때문이다. 그래서 접촉 그래프를 위상 정렬해 아래층부터 갱신하거나, 계층적으로 성긴 문제를 먼저 푸는 다중격자법식 접근을 시도한 연구들이 있다. 다만 게임에서는 그냥 “상자 그만 쌓게 만들기”가 가장 많이 채택된 해법이다. ↩