7.116 쌍대 문제와 강쌍대성 조건

1. 라그랑주 쌍대 함수

일반적인 최적화 문제 $\min f(\mathbf{x})$ subject to $g_i(\mathbf{x}) \leq 0$ , $h_j(\mathbf{x}) = 0$ 에 대해 라그랑지안을 $\mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\nu}) = f(\mathbf{x}) + \boldsymbol{\mu}^T\mathbf{g}(\mathbf{x}) + \boldsymbol{\nu}^T\mathbf{h}(\mathbf{x})$ 로 정의한다. 라그랑주 쌍대 함수(Lagrange dual function)는 라그랑지안을 원초 변수 $\mathbf{x}$ 에 대해 최소화한 것이다.

$d(\boldsymbol{\mu}, \boldsymbol{\nu}) = \inf_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\nu})$

쌍대 함수는 볼록 함수들의 점별 하한(pointwise infimum)이므로, 원초 문제의 볼록성과 무관하게 항상 오목(concave)이다.

2. 약쌍대성

쌍대 함수는 원초 최적값 $f^*$ 의 하한을 제공한다.

$d(\boldsymbol{\mu}, \boldsymbol{\nu}) \leq f^*, \quad \forall \boldsymbol{\mu} \geq \mathbf{0}, \boldsymbol{\nu}$

이를 약쌍대성(weak duality)이라 한다. 따라서 쌍대 문제 $\max_{\boldsymbol{\mu} \geq \mathbf{0}, \boldsymbol{\nu}} d(\boldsymbol{\mu}, \boldsymbol{\nu})$ 의 최적값 $d^*$ 는 $d^* \leq f^*$ 를 만족한다. $f^* - d^* \geq 0$ 을 쌍대 간극(duality gap)이라 한다.

3. 쌍대 문제

라그랑주 쌍대 문제(Lagrange dual problem)는 쌍대 함수를 최대화하는 문제이다.

$\max_{\boldsymbol{\mu}, \boldsymbol{\nu}} \quad d(\boldsymbol{\mu}, \boldsymbol{\nu}) \quad \text{s.t.} \quad \boldsymbol{\mu} \geq \mathbf{0}$

쌍대 함수가 오목이므로, 쌍대 문제는 원초 문제의 볼록성과 무관하게 항상 볼록 최적화 문제이다. 이는 쌍대성 이론의 중요한 구조적 성질이다.

4. 강쌍대성

강쌍대성(strong duality)은 쌍대 간극이 영인 경우, 즉 $d^* = f^*$ 인 경우를 의미한다. 강쌍대성이 성립하면, 쌍대 문제를 풀어 원초 문제의 최적값을 정확히 결정할 수 있으며, 쌍대 최적해가 원초 문제의 KKT 승수를 제공한다.

4.1 슬레이터 조건(Slater’s Condition)

볼록 문제에서 강쌍대성이 성립하기 위한 가장 널리 사용되는 충분 조건이다. 강 허용 가능한 점(strictly feasible point) $\tilde{\mathbf{x}}$ 가 존재하면 강쌍대성이 성립한다.

$\exists \tilde{\mathbf{x}} : g_i(\tilde{\mathbf{x}}) < 0, \; i = 1, \ldots, m, \quad \mathbf{A}\tilde{\mathbf{x}} = \mathbf{b}$

슬레이터 조건은 허용 영역의 내부가 비어 있지 않을 것을 요구하며, 실용적으로 거의 항상 만족된다. 아핀 부등식 제약 $\mathbf{a}_i^T\mathbf{x} \leq b_i$ 에 대해서는 엄격한 부등호가 아닌 $\leq$ 만 만족하면 된다.

5. 쌍대성의 활용

5.1 하한의 계산

비볼록 문제에서도 쌍대 문제는 볼록이므로 효율적으로 풀 수 있다. 쌍대 최적값 $d^*$ 는 원초 최적값의 하한을 제공하며, 이는 다음의 용도로 활용된다.

최적성 간극 평가: 허용 해 $\mathbf{x}$ 의 목적 함수값 $f(\mathbf{x})$ 와 쌍대 하한 $d^*$ 의 차이 $f(\mathbf{x}) - d^*$ 는 해의 비최적성의 상한이다.
분기 한정법의 하한: 비볼록 전역 최적화에서 탐색 공간을 분할하고, 각 부분 문제의 쌍대 하한으로 가지치기를 수행한다.

5.2 분해 기법

대규모 문제에서 쌍대 문제는 원초 문제보다 분해하기 용이한 구조를 가질 수 있다. 라그랑주 이완(Lagrangian relaxation)에 의해 결합 제약을 쌍대 변수로 처리하면, 원초 문제가 독립적인 하위 문제들로 분리된다.

6. 쌍대성과 감도 분석

쌍대 최적해 $(\boldsymbol{\mu}^*, \boldsymbol{\nu}^*)$ 는 제약 조건의 변화에 대한 최적값의 민감도를 나타낸다.

$\mu_i^* = -\frac{\partial f^*}{\partial u_i} \bigg\vert_{u_i=0}$

여기서 $u_i$ 는 $i$ 번째 부등식 제약의 우변 $g_i(\mathbf{x}) \leq u_i$ 의 완화량이다. 승수 $\mu_i^*$ 가 큰 제약을 완화하면 최적 비용이 크게 개선되며, 이 정보는 로봇 시스템 설계에서 어떤 물리적 한계(토크, 속도, 작업 공간 범위)의 개선이 가장 효과적인지 판단하는 데 활용된다.

7. 로봇 공학에서의 쌍대성 활용

접촉 역학의 쌍대 정식화: 접촉 문제의 원초-쌍대 쌍에서, 원초 변수가 접촉력이고 쌍대 변수가 접촉점 속도에 대응하는 경우가 많다. 최대 소산 원리(maximum dissipation principle)가 쌍대 문제의 형태로 표현된다.

분산 최적화: 다중 로봇 시스템에서 결합 제약(충돌 회피 등)을 쌍대 분해하여, 각 로봇이 독립적으로 자신의 하위 문제를 풀고 쌍대 변수를 교환하는 분산 알고리즘을 구성한다.

8. 참고 문헌

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Bertsekas, D. P. (2009). Convex Optimization Theory. Athena Scientific.
Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.
Luenberger, D. G., & Ye, Y. (2016). Linear and Nonlinear Programming (4th ed.). Springer.

version: 1.0