7.103 상보성 조건의 의미와 해석

1. 상보성 조건의 정의

KKT 조건에서 상보성 조건(complementary slackness condition)은 각 부등식 제약에 대해 다음을 요구한다.

$\mu_i g_i(\mathbf{x}) = 0, \quad i = 1, \ldots, m$

$\mu_i \geq 0$ 과 $g_i(\mathbf{x}) \leq 0$ 이 동시에 성립하므로, 두 양 중 적어도 하나는 반드시 영이어야 한다. 이를 상보성 쌍(complementary pair)이라 하며, 두 양이 동시에 양수가 될 수 없다는 의미에서 “상보적“이다.

2. 논리적 분기 구조

상보성 조건은 각 제약에 대해 다음의 이원적 분기(dichotomy)를 산출한다.

경우 1: $g_i(\mathbf{x}^*) < 0$ 이면 반드시 $\mu_i^* = 0$ 이다. 비능동 제약에 대응하는 승수는 영이며, 이 제약은 최적해의 결정에 관여하지 않는다.

경우 2: $\mu_i^* > 0$ 이면 반드시 $g_i(\mathbf{x}^*) = 0$ 이다. 양의 승수를 갖는 제약은 능동이며, 이 제약이 최적해를 적극적으로 구속한다.

경우 3: $g_i(\mathbf{x}^*) = 0$ 이고 $\mu_i^* = 0$ 이다. 이 경우 제약은 능동이지만 승수가 영인 퇴화 상태이다.

3. 경제학적 해석

경제학에서 상보성 조건은 자원 배분의 최적성을 나타내는 자연스러운 조건이다.

제약 $g_i(\mathbf{x}) \leq 0$ 을 자원의 사용량이 용량을 초과하지 않는 조건으로 해석하면, 승수 $\mu_i$ 는 해당 자원의 그림자 가격(shadow price)이다. 상보성 조건은 다음을 의미한다.

여유 자원( $g_i < 0$ )에는 가격이 없다( $\mu_i = 0$ ): 자원이 남아 있으면 추가 자원의 한계 가치가 영이다.
가격이 있는 자원( $\mu_i > 0$ )은 완전히 소진된다( $g_i = 0$ ): 한계 가치가 양수인 자원은 최적 배분에서 남김없이 사용된다.

4. 역학적 해석

로봇 접촉 역학에서 상보성 조건은 물리적 접촉 법칙과 직접 대응한다.

비관입 조건: 두 물체 사이의 간격(gap) $\phi \geq 0$ .

법선 접촉력: 법선 방향 접촉력 $f_n \geq 0$ .

상보성: $f_n \cdot \phi = 0$ .

이는 다음의 물리적 사실을 표현한다.

물체가 떨어져 있으면( $\phi > 0$ ) 접촉력이 없다( $f_n = 0$ ).
접촉력이 존재하면( $f_n > 0$ ) 물체는 접촉해야 한다( $\phi = 0$ ).

마찬가지로 쿨롱 마찰에서 접선 속도와 마찰력 사이에도 상보성 구조가 나타난다. 미끄러짐이 발생하면 마찰력이 한계에 도달하고, 마찰력이 한계 미만이면 미끄러짐이 없다.

5. 상보성 문제(Complementarity Problem)

상보성 조건은 보다 일반적인 상보성 문제(complementarity problem)의 틀로 추상화된다.

선형 상보성 문제(LCP): $\mathbf{w} = \mathbf{M}\mathbf{z} + \mathbf{q}$ 에서 $\mathbf{w} \geq \mathbf{0}$ , $\mathbf{z} \geq \mathbf{0}$ , $\mathbf{w}^T\mathbf{z} = 0$ 을 만족하는 $(\mathbf{w}, \mathbf{z})$ 를 구하는 문제이다.

비선형 상보성 문제(NCP): $\mathbf{F}(\mathbf{z}) \geq \mathbf{0}$ , $\mathbf{z} \geq \mathbf{0}$ , $\mathbf{F}(\mathbf{z})^T\mathbf{z} = 0$ 을 만족하는 $\mathbf{z}$ 를 구하는 문제이다.

로봇 접촉 시뮬레이션에서 접촉력의 계산은 LCP 또는 NCP로 정식화되며, 이에 대한 전용 해법(Lemke 알고리즘, PATH 해법기 등)이 개발되어 있다.

6. 수치적 처리

상보성 조건의 불연속적 논리 구조는 수치적 해법에서 어려움을 야기한다. 이를 처리하기 위한 주요 접근법은 다음과 같다.

6.1 피셔-버마이스터 함수

상보성 조건 $\mu \geq 0$ , $g \leq 0$ , $\mu g = 0$ 을 단일 등식으로 재정식화한다.

$\phi_{FB}(\mu, -g) = \sqrt{\mu^2 + g^2} - \mu + g = 0$

피셔-버마이스터(Fischer-Burmeister) 함수는 $\phi_{FB}(a, b) = 0$ 이 $a \geq 0$ , $b \geq 0$ , $ab = 0$ 과 동치인 성질을 갖는다. 이를 통해 상보성을 포함하는 KKT 시스템을 매끄러운(또는 반매끄러운) 방정식계로 변환하여 뉴턴형 방법을 적용할 수 있다.

6.2 내점법의 섭동

내점법(interior point method)에서는 상보성 조건을 다음의 섭동 조건으로 이완한다.

$\mu_i g_i(\mathbf{x}) = -\tau, \quad \tau > 0$

장벽 매개변수 $\tau$ 를 점진적으로 영으로 감소시키면서, 섭동된 KKT 시스템을 반복적으로 풀어 원래의 상보성 조건에 수렴한다.

6.3 정규화된 상보성

로봇 접촉 시뮬레이션에서 정규화된 접촉 모델(regularized contact model)은 상보성의 불연속성을 매끄러운 함수로 근사한다.

$f_n = \max(0, k \cdot \phi)^+ \quad \text{또는} \quad f_n = k \cdot \text{softplus}(-\phi/\epsilon)$

이러한 정규화는 미분 가능한 시뮬레이터의 구현에 필수적이다.

7. 강 상보성과 약 상보성

강 상보성(strong complementarity): 모든 능동 제약에 대해 $\mu_i^* > 0$ 이 성립한다. 이 경우 능동 집합이 명확히 식별되며, 내점법과 SQP의 국소 수렴 속도가 향상된다.

약 상보성(weak complementarity): 일부 능동 제약에 대해 $\mu_i^* = 0$ 이 성립하는 퇴화 상태이다. 이 경우 수치적 해법의 수렴 속도가 저하될 수 있으며, 능동 집합의 진동이 발생할 수 있다.

8. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Cottle, R. W., Pang, J.-S., & Stone, R. E. (2009). The Linear Complementarity Problem. SIAM.
Stewart, D. E. (2011). Dynamics with Inequalities: Impacts and Hard Constraints. SIAM.
Facchinei, F., & Pang, J.-S. (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer.

version: 1.0