6장. 라그랑주 승수와 KKT 조건

현실의 최적화에는 조건이 붙습니다. 예산은 정해져 있고, 확률은 합이 1이어야 하며, 다리의 응력은 한계를 넘으면 안 됩니다. 다변수 미적분 6장에서 등식 제약을 라그랑주 승수로 풀었습니다. 이 장에서는 “이하”처럼 부등식 제약이 붙는 경우까지 넓힌 KKT 조건을 다룹니다. SVM, 최대 엔트로피 분포, 강화학습의 제약 최적화(TRPO)를 읽으려면 이 조건이 필요합니다.

6.1 등식 제약 복습

정리 6.1 (라그랑주 승수). $\min f(\mathbf x)$ s.t. $h_j(\mathbf x) = 0$ ($j = 1, \dots, p$)의 국소 최솟값 $\mathbf x^*$에서 $\nabla h_j(\mathbf x^*)$들이 일차독립이면, 수 $\nu_1, \dots, \nu_p$가 있어

(s.t.는 such that, “다음 조건 아래에서”라는 뜻입니다.) 함수 $\mathcal L(\mathbf x, \boldsymbol\nu) = f(\mathbf x) + \sum_j\nu_jh_j(\mathbf x)$를 라그랑주 함수(Lagrangian)라 합니다. 위 조건은 $\nabla_{\mathbf x}\mathcal L = \mathbf 0$입니다.

기하학적 뜻: 최적점에서 $f$의 그래디언트는 제약 곡면에 수직입니다. 그렇지 않으면 곡면을 따라 움직여 $f$를 더 줄일 수 있습니다.

예제 6.2 (최대 엔트로피). 확률 $p_1, \dots, p_n$에 대해 엔트로피 $-\sum p_i\ln p_i$를 $\sum p_i = 1$ 아래에서 최대로 합니다. $\mathcal L = \sum p_i\ln p_i + \nu(\sum p_i - 1)$을 $p_i$로 미분하면 $\ln p_i + 1 + \nu = 0$이므로 모든 $p_i$가 같고, $p_i = 1/n$. 균등분포가 엔트로피를 최대로 합니다(확률과 통계 11장).

6.2 부등식 제약과 KKT 조건

이제 문제는

$\mathcal L(\mathbf x, \boldsymbol\lambda, \boldsymbol\nu) = f + \sum_i\lambda_ig_i + \sum_j\nu_jh_j$로 둡니다.

정리 6.3 (KKT 조건). 적당한 정칙 조건 아래에서 $\mathbf x^*$가 국소 최솟값이면 $\boldsymbol\lambda^*, \boldsymbol\nu^*$가 있어 다음 네 조건이 성립합니다.

1. 정상성(stationarity): $\nabla f(\mathbf x^*) + \sum_i\lambda_i^*\nabla g_i(\mathbf x^*) + \sum_j\nu_j^*\nabla h_j(\mathbf x^*) = \mathbf 0$.
2. 원문제 실행 가능성(primal feasibility): $g_i(\mathbf x^*) \le 0$, $h_j(\mathbf x^*) = 0$.
3. 쌍대 실행 가능성(dual feasibility): $\lambda_i^* \ge 0$.
4. 상보 여유성(complementary slackness): $\lambda_i^*g_i(\mathbf x^*) = 0$.

이름은 이 조건을 발견한 카루시, 쿤, 터커(Karush–Kuhn–Tucker)의 머리글자입니다. 문제가 볼록이면($f, g_i$ 볼록, $h_j$ 일차) KKT 조건은 충분조건이기도 합니다.

6.3 상보 여유성의 뜻

조건 4는 각 제약마다 둘 중 하나라는 뜻입니다.

• $g_i(\mathbf x^*) < 0$: 제약이 최적점에서 “여유가 있음”(비활성, inactive). 그러면 $\lambda_i^* = 0$이고, 그 제약은 없는 것과 같습니다.
• $\lambda_i^* > 0$: 그러면 $g_i(\mathbf x^*) = 0$, 곧 제약의 경계에 붙어 있습니다(활성, active).

$\lambda_i \ge 0$인 이유도 직관적입니다. 제약 $g_i \le 0$은 $f$가 줄어드는 쪽으로 가는 것을 막는 벽입니다. 정상성 조건 $-\nabla f = \lambda_i\nabla g_i$는 “내려가고 싶은 방향이 벽 바깥을 향한다”는 뜻이고, 그러려면 $\lambda_i \ge 0$이어야 합니다.

승수의 의미(민감도). $\lambda_i^*$는 제약을 조금 풀었을 때($g_i \le \varepsilon$) 최솟값이 줄어드는 비율입니다: $\frac{d f^*}{d\varepsilon} = -\lambda_i^*$. 경제학에서는 자원의 잠재 가격(shadow price)이라 부릅니다.

6.4 풀이 절차

KKT 문제는 보통 “어떤 제약이 활성인가”를 경우로 나누어 풉니다.

예제 6.4. $\min (x - 3)^2 + (y - 2)^2$ s.t. $x + y \le 2$.

• 경우 1 (비활성, $\lambda = 0$): 제약 없는 최솟값 $(3, 2)$는 $x + y = 5 > 2$라 실행 불가능합니다. 탈락.
• 경우 2 (활성, $x + y = 2$): 정상성 $2(x - 3) + \lambda = 0$, $2(y - 2) + \lambda = 0$에서 $x - 3 = y - 2$, 곧 $x = y + 1$. $x + y = 2$와 함께 $x = 1.5$, $y = 0.5$, $\lambda = 3 \ge 0$. 모든 조건 만족.

최적해 $(1.5, 0.5)$, 최솟값 $1.5^2 + 1.5^2 = 4.5$입니다. 점 $(3, 2)$에서 직선 $x + y = 2$에 내린 수선의 발이고, $\lambda = 3$은 제약을 1만큼 풀면 최솟값이 약 3 줄어든다는 뜻입니다.

6.5 알고리즘

• 사영 경사하강법(projected gradient descent): 경사하강법으로 한 걸음 간 뒤, 실행 가능 집합에서 가장 가까운 점으로 되돌립니다. $\mathbf x_{k+1} = \Pi_C(\mathbf x_k - \eta\nabla f(\mathbf x_k))$. 상자 제약 $[a, b]$이면 사영은 값을 잘라내기(clip)만 하면 됩니다.
• 벌점법(penalty method): 제약 위반에 벌점을 줍니다. $\min f(\mathbf x) + \frac\mu2\sum_i\max(0, g_i(\mathbf x))^2$. $\mu$를 키울수록 원래 문제에 가까워집니다.
• 장벽법(barrier method): 경계에 다가가면 무한대가 되는 항 $-\frac1t\sum\ln(-g_i)$을 더해 안쪽에서 접근합니다. 내부점 방법의 기초입니다.

6.6 이 장의 요약

• 라그랑주 함수 $\mathcal L = f + \sum\lambda_ig_i + \sum\nu_jh_j$.
• KKT: 정상성, 원문제·쌍대 실행 가능성, 상보 여유성. 볼록이면 필요충분.
• 상보 여유성: 비활성 제약의 승수는 0. 승수 = 잠재 가격.
• 알고리즘: 사영 경사하강법, 벌점법, 장벽법.

쓰이는 곳. SVM의 서포트 벡터(승수가 0이 아닌 데이터 점, 7장), 최대 엔트로피 원리와 지수족 분포, 강화학습의 TRPO(KL 제약)와 제약 RL, 공정성 제약이 붙은 학습, 경제학의 효용 최대화, 공학의 구조 최적화, 통계역학의 볼츠만 분포 유도(에너지 평균 제약 아래 엔트로피 최대)가 KKT 조건을 씁니다.

문제

1
2
5

0

1
6

0.6