KKT Condition (Karush-Kuhn-Tucker Condition)

개념

• 라그랑주 승수법은 등식 제약(equality constraint) $g(x) = 0$ 만 다룸
• 제약 조건이 부등식(inequality constraint) $g(x) \leq 0$ 형태이면, 기존의 $\nabla \mathcal{L} = 0$ 조건만으로는 부족하고 아래 조건들이 추가로 필요함:
  • $\mu \, g(x) = 0$ (상보성 조건, complementary slackness)
  • $\mu \geq 0$ (듀얼 실행가능 조건, dual feasibility)
• 이 조건들을 통틀어 KKT 조건이라고 함

Auxiliary Function

KKT 조건 정리

부등식 제약을 갖는 최적화 문제

에 대해, 최적점 $x^*$ 는 다음 조건들을 만족해야 함:

1. 정상성 조건 (Stationarity)

   $\nabla f(x^*) + \mu \nabla g(x^*) = 0$

2. 원 문제 실행가능 조건 (Primal Feasibility)

   $g(x^*) \leq 0$

3. 듀얼 실행가능 조건 (Dual Feasibility)

   $\mu \geq 0$

4. 상보성 조건 (Complementary Slackness)

   $\mu \, g(x^*) = 0$

각 조건의 의미

$\mu = 0$ 인 경우 — 제약이 "느슨함" (inactive)

• 상보성 조건에 의해 $\mu = 0$ 이면 $g(x^*) < 0$ 이어도 무방함
• 이는 곧 제약 조건 $g(x) \leq 0$ 이 최적점을 찾는 데 아무 영향을 주지 않는다는 뜻
• 즉, 제약이 없어도 어차피 $f$의 최적점이 실행가능 영역 내부에 존재하는 상황 → 그냥 $\nabla f(x^*) = 0$ 인 일반적인 최적화와 동일

$\mu > 0$ 인 경우 — 제약이 "활성화됨" (active)

• 상보성 조건에 의해 $\mu > 0$ 이면 반드시 $g(x^*) = 0$ 이어야 함
• 즉, 최적점이 실행가능 영역의 경계(boundary) 위, 정확히 $g(x) = 0$ 인 지점에 위치함
• 이 경우엔 등식 제약이 있을 때의 라그랑주 승수법과 동일하게, $\nabla f$ 와 $\nabla g$ 가 서로 평행(스칼라배 관계)이 되는 지점을 찾는 문제로 환원됨
• $\mu \geq 0$ 이라는 부호 조건은 $\nabla f$ 가 실행가능 영역을 벗어나는 방향(즉 $g$가 증가하는 방향)과 반대 방향을 향해야 한다는 것을 보장 — 그래야 경계에서 더 이상 $f$를 줄일 수 없는 최적점이 됨

기하학적 해석

• 등식 제약: 최적점은 반드시 곡선(경계) 위에 있어야 함
• 부등식 제약: 최적점은 경계 위에 있을 수도, 영역 내부에 있을 수도 있음
  • 내부에 있으면 ($\mu = 0$) → 제약이 없는 것과 동일한 상황
  • 경계 위에 있으면 ($\mu > 0$) → 등식 제약 문제로 환원되고, $\nabla f$ 와 $\nabla g$ 가 반대 방향이 아니라 같은 방향(부호 일치) 으로 정렬됨

Multiple Inequality Constraints (추가 예정)

• 부등식 제약이 여러 개인 경우, 각 제약마다 $\mu_i \geq 0,\ \mu_i g_i(x) = 0$ 조건이 붙고
  $\nabla f(x^*) + \sum_i \mu_i \nabla g_i(x^*) = 0$
  형태로 확장됨 (등식 제약의 $\lambda_i$ 와 함께 섞어 쓸 수도 있음)