7.101 부등식 제약 조건과 KKT 조건

1. 부등식 제약 최적화 문제

부등식 제약을 포함하는 일반적인 비선형 계획 문제(nonlinear programming problem)는 다음과 같이 정식화된다.

$\min_{\mathbf{x} \in \mathbb{R}^n} \quad f(\mathbf{x})$

$\text{subject to} \quad g_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m$

$h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, p$

부등식 제약은 등식 제약과 본질적으로 다른 구조를 갖는다. 최적점에서 부등식 제약이 등호로 성립하는 경우(활성 제약)와 엄격한 부등호로 성립하는 경우(비활성 제약)를 구별해야 하며, 이 구별이 최적 조건의 구조를 결정한다.

2. 활성 제약과 비활성 제약

점 $\mathbf{x}$ 에서의 활성 집합(active set)은 등호로 성립하는 부등식 제약의 인덱스 집합이다.

$\mathcal{A}(\mathbf{x}) = \{i : g_i(\mathbf{x}) = 0\}$

비활성 제약( $g_i(\mathbf{x}) < 0$ )은 최적점 근방에서 자유롭게 움직일 수 있는 여유(slack)를 가지므로, 최적 조건에 영향을 미치지 않는다. 활성 제약만이 최적 조건에 관여하며, 이는 등식 제약과 유사하게 취급된다.

3. KKT 조건의 유도

3.1 라그랑지안

라그랑주 승수 $\mu_i \geq 0$ (부등식 제약), $\nu_j$ (등식 제약)를 도입하여 라그랑지안을 구성한다.

$\mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\nu}) = f(\mathbf{x}) + \sum_{i=1}^{m} \mu_i g_i(\mathbf{x}) + \sum_{j=1}^{p} \nu_j h_j(\mathbf{x})$

3.2 KKT 필요 조건

$\mathbf{x}^*$ 가 국소 최소점이고 적절한 제약 자격이 성립하면, $\boldsymbol{\mu}^* \in \mathbb{R}^m$ , $\boldsymbol{\nu}^* \in \mathbb{R}^p$ 가 존재하여 다음의 카루시-쿤-터커(Karush-Kuhn-Tucker) 조건이 성립한다.

(1) 정류 조건(Stationarity):

$\nabla f(\mathbf{x}^*) + \sum_{i=1}^{m} \mu_i^* \nabla g_i(\mathbf{x}^*) + \sum_{j=1}^{p} \nu_j^* \nabla h_j(\mathbf{x}^*) = \mathbf{0}$

(2) 원초 허용 가능성(Primal Feasibility):

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

$h_j(\mathbf{x}^*) = 0, \quad j = 1, \ldots, p$

(3) 쌍대 허용 가능성(Dual Feasibility):

$\mu_i^* \geq 0, \quad i = 1, \ldots, m$

(4) 상보성 조건(Complementary Slackness):

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

4. 상보성 조건의 의미

상보성 조건은 KKT 조건의 가장 특징적인 요소이다. 각 부등식 제약 $i$ 에 대해 다음의 두 경우 중 하나가 반드시 성립한다.

$g_i(\mathbf{x}^*) < 0$ (비활성): 이 경우 $\mu_i^* = 0$ 이어야 한다. 비활성 제약은 최적해에 영향을 미치지 않으므로 대응 승수가 영이다.
$\mu_i^* > 0$ (양의 승수): 이 경우 $g_i(\mathbf{x}^*) = 0$ 이어야 한다. 양의 승수를 갖는 제약은 반드시 활성이다.

두 조건이 동시에 등호로 성립하는 경우( $g_i(\mathbf{x}^*) = 0$ 이고 $\mu_i^* = 0$ )를 퇴화(degenerate) 또는 약 상보성이라 하며, 이 경우 활성 집합의 식별이 어려워 수치적 해법의 수렴에 영향을 미칠 수 있다.

5. 쌍대 허용 가능성의 기하학적 의미

$\mu_i^* \geq 0$ 조건은 기하학적으로 다음을 의미한다. 최적점에서 $-\nabla f(\mathbf{x}^*)$ 가 활성 제약의 그래디언트들이 이루는 원추(cone)의 내부에 놓여야 한다. 부등식 제약에서는 허용 영역이 제약 경계의 한쪽에만 있으므로, 그래디언트의 방향(부호)이 중요하며 이것이 $\mu_i^* \geq 0$ 으로 반영된다.

6. 제약 자격 조건

KKT 조건이 필요 조건으로서 유효하려면 제약 자격(constraint qualification)이 만족되어야 한다.

LICQ(선형 독립 제약 자격): 활성 제약의 그래디언트 $\{\nabla g_i(\mathbf{x}^*) : i \in \mathcal{A}(\mathbf{x}^*)\} \cup \{\nabla h_j(\mathbf{x}^*) : j = 1, \ldots, p\}$ 가 선형 독립이다.

MFCQ(망가사리안-프로모비츠 제약 자격): 등식 제약의 그래디언트가 선형 독립이고, 모든 활성 부등식 제약에 대해 음의 방향 도함수를 갖는 방향 $\mathbf{d}$ 가 존재한다.

슬레이터 조건(Slater’s Condition): 볼록 문제에서, 모든 부등식 제약을 엄격하게 만족하는 점(내부 허용 점)이 존재한다. 이는 볼록 최적화에서 가장 약한 조건이며, 실용적으로 거의 항상 만족된다.

7. 볼록 문제에서의 충분성

목적 함수가 볼록, 부등식 제약 함수가 볼록, 등식 제약 함수가 아핀이고 슬레이터 조건이 성립하면, KKT 조건은 전역 최적의 필요 충분 조건이 된다. 이는 볼록 최적화의 핵심 정리이며, KKT 점을 찾으면 곧 전역 최적해를 확보할 수 있음을 의미한다.

8. 로봇 공학에서의 부등식 제약

로봇 시스템에서 발생하는 대표적인 부등식 제약은 다음과 같다.

관절 한계: $q_{i,\min} \leq q_i \leq q_{i,\max}$

관절 속도 한계: $\lvert \dot{q}_i \rvert \leq \dot{q}_{i,\max}$

토크 한계: $\lvert \tau_i \rvert \leq \tau_{i,\max}$

장애물 회피: $d(\mathbf{q}) \geq d_{safe}$ , 여기서 $d$ 는 로봇과 장애물 사이의 최소 거리

마찰 원추 제약: $\lVert \mathbf{f}_t \rVert \leq \mu f_n$ , 여기서 $\mathbf{f}_t$ 는 접선 방향 힘, $f_n$ 은 법선 방향 힘, $\mu$ 는 마찰 계수

이러한 제약들은 로봇의 물리적 한계와 안전 요구를 반영하며, KKT 조건에 기반한 수치적 최적화 알고리즘(SQP, 내점법 등)에 의해 처리된다.

9. 참고 문헌

Karush, W. (1939). “Minima of Functions of Several Variables with Inequalities as Side Constraints.” M.Sc. Dissertation, University of Chicago.
Kuhn, H. W., & Tucker, A. W. (1951). “Nonlinear Programming.” Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, 481–492.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.

version: 1.0