라그랑주 승수법(Lagrange multiplier)

원점과 점 (x, y)를 마주 보는 두 꼭짓점⁠(vertex)⁠으로 하는 직사각형을 생각합시다. x와 y가 양수이면 넓이⁠(area)⁠는 $f(x, y) = xy$입니다. 점이 직선 $x + 2y = 6$ 위에 있어야 한다면 넓이는 얼마까지 커질까요? 이 경우는 $y = (6 - x)/2$를 대입해 $f = x(6 - x)/2$의 꼭대기를 찾으면 됩니다. 답은 x = 3, y = 1.5, 넓이 4.5입니다(최적화⁠, optimization⁠). 그러나 제약이 복잡하면 한 변수를 다른 변수로 풀어 쓰기조차 어렵습니다. 라그랑주 승수법은 대입 없이 그림 하나로 답의 조건을 줍니다.

회색 곡선은 f의 등고선(xy가 일정한 쌍곡선⁠(hyperbola)⁠)이고, 분홍 선이 제약입니다. 노란 점 P를 제약을 따라 끌어 보세요. 보라 곡선은 P를 지나는 등고선입니다. 넓이가 가장 큰 곳에서 보라 등고선은 제약에 딱 스칩니다. 스치지 않고 가로지른다면, 제약을 따라 한쪽으로 가면 더 높은 등고선으로 넘어갈 수 있을 테니까요. 제약: , 수준 c = (분홍 손잡이를 끌어 바꿉니다). 가장 넓은 곳으로

두 곡선이 스친다는 것은 그 점에서 두 곡선에 수직인 방향이 같다는 뜻이고, 등고선에 수직인 방향은 기울기 벡터가 가리킵니다. 그러니 최적점에서는 어떤 수 λ가 있어서 $\nabla f = \lambda\nabla g$입니다. 지금 P에서 f = , $\nabla f =$ , $\nabla g =$ 이고, 두 벡터⁠(vector)⁠가 이루는 직선 사이의 각은 입니다. P를 끌어 이 각이 0°가 되는 곳을 찾아보세요.

그래서 미지수 λ를 하나 더 들여 $\nabla f = \lambda\nabla g$와 $g = c$를 함께 풉니다. 직선의 예에서 $\nabla f = (y, x)$, $\nabla g = (1, 2)$이니 y = λ, x = 2λ이고, 제약 $x + 2y = 4\lambda = 6$에서 λ = 1.5, 최적점은 (3, 1.5)입니다. 같은 것을 $\mathcal L(x, y, \lambda) = f - \lambda\,(g - c)$의 편미분⁠(partial derivative)⁠을 모두 0으로 두는 것으로 쓰기도 합니다. λ로 미분⁠(differentiation)⁠한 식이 제약 자체입니다.

까닭. 제약 위에서 P를 조금 움직이는 방향 $\vec t$는 g를 바꾸지 않으니 $\nabla g\cdot\vec t = 0$, 곧 $\vec t$는 ∇g에 수직입니다. P가 최적이라면 그 방향으로 움직여도 f가 1차로는 변하지 않아야 하므로 $\nabla f\cdot\vec t = 0$입니다. 평면에서 0이 아닌 ∇g에 수직인 방향은 한 직선뿐이니, 그 직선에 함께 수직인 ∇f는 ∇g와 평행합니다. 변수가 n개, 제약이 m개여도, 제약들의 기울기⁠(slope)⁠ $\nabla g_1, \ldots, \nabla g_m$이 일차독립이면 같은 논리로 $\nabla f = \lambda_1\nabla g_1 + \cdots + \lambda_m\nabla g_m$이 나옵니다.

주의할 점. 이 조건은 필요조건⁠(necessary condition)⁠일 뿐입니다. '원' 제약 $x^2 + y^2 = r^2$에서 xy는 $(r/\sqrt2,\ r/\sqrt2)$와 그 반대편 점에서 가장 크고, $(r/\sqrt2,\ -r/\sqrt2)$와 그 반대편 점에서 가장 작은데, 네 점 모두 조건을 만족합니다(최대인 곳은 λ = 1/2, 최소인 곳은 λ = −1/2). 조건을 만족하는 후보를 모두 구해 값을 비교해야 합니다. 또 최적점에서 $\nabla g \ne 0$이어야 합니다. 곡선 $y^2 = x^3$ 위에서 x를 가장 작게 하면 답은 뾰족한 점 (0, 0)이지만, 거기서 $\nabla g = (-3x^2, 2y) = (0, 0)$이라 $\nabla f = (1, 0) = \lambda\nabla g$인 λ가 없습니다. 정리의 정확한 내용은 이렇습니다. f와 g가 연속적으로 미분 가능하고, 제약 위에서 f가 극대나 극소가 되는 점에서 $\nabla g \ne 0$이면, 그 점에서 $\nabla f = \lambda\nabla g$인 λ가 있습니다.

λ는 무엇을 말하나. 분홍 손잡이로 c를 바꿔 보세요. 최댓값 $f^*$가 c에 따라 변하는데, 그 변화율이 λ입니다.

지금 $f^* =$ , $\lambda =$ 입니다. 직선의 예에서는 $f^* = c^2/8$이라 $df^*/dc = c/4$이고, c = 6이면 1.5로 위의 λ와 같습니다. 까닭은 한 줄입니다. 최적점 $\vec x^*(c)$가 c에 따라 매끄럽게 움직인다면 $df^*/dc = \nabla f\cdot d\vec x^*/dc = \lambda\,\nabla g\cdot d\vec x^*/dc = \lambda\, d\,g(\vec x^*(c))/dc = \lambda$입니다. 마지막 등호는 $g(\vec x^*(c)) = c$이기 때문입니다. 곧 c를 조금 늘리면 최적값은 그 λ배쯤 변합니다. 제약을 한 단위 늦춰 줄 때 목표가 대략 얼마나 좋아지는지를 재는 수라서, 경제학에서는 λ를 잠재 가격(그림자 가격⁠, shadow price⁠)이라 부릅니다. 예산이 제약이면 λ는 '돈 한 단위의 값'입니다. 선형 계획법⁠(linear programming)⁠의 쌍대 변수가 바로 이 뜻입니다.

부등식 제약. 제약이 $g \le c$이면 두 경우가 있습니다. 최적점이 경계에 닿지 않으면 제약이 없는 것과 같아 λ = 0이고, 경계에 닿으면 (최대화에서) λ ≥ 0입니다. 경계 바깥으로 나가야 f가 커지는 경우만 제약이 발목을 잡기 때문입니다. $\nabla f = \lambda\nabla g$, $g \le c$, $\lambda \ge 0$에 '둘 중 하나'라는 조건 $\lambda\,(g - c) = 0$(상보 여유성⁠, complementary slackness⁠)을 묶은 것이 카루시–쿤–터커(KKT) 조건입니다. 1939년 윌리엄 카루시의 석사 논문과 1951년 해럴드 쿤과 앨버트 터커의 논문에서 나왔습니다. 일반적으로 KKT 조건⁠(KKT conditions)⁠은 (∇g ≠ 0 같은 조건 아래의) 필요조건이지만, 볼록 최적화에서는 가벼운 가정 아래에서 필요충분조건이 되고, λ들을 변수로 하는 쌍대 문제⁠(dual problem)⁠가 원래 문제와 같은 값을 줍니다(쌍대성⁠(duality)⁠). 서포트 벡터 머신⁠(support vector machine)⁠에서 λ가 0이 아닌 데이터 점, 곧 여백의 경계에 닿거나 그 안으로 들어온 점이 '서포트 벡터⁠(support vector)⁠'라는 이름의 뜻입니다.

곳곳에 숨은 승수. 데이터의 공분산 행렬⁠(covariance matrix)⁠을 Σ라 할 때, 길이 1인 방향 u 가운데 그 방향의 분산⁠(variance)⁠ $\vec u^{\mathsf T}\Sigma\vec u$를 가장 크게 하는 주성분 분석⁠(principal component analysis)⁠에 이 방법을 쓰면 $2\Sigma\vec u = \lambda\cdot 2\vec u$, 곧 $\Sigma\vec u = \lambda\vec u$라는 고유벡터⁠(eigenvector)⁠ 방정식이 나오고, 승수 λ가 그 방향의 분산입니다. 합이 1이고 평균⁠(mean)⁠이 정해진 분포 가운데 엔트로피⁠(entropy)⁠가 가장 큰 것을 찾으면 승수 두 개로 $p_i \propto e^{\lambda x_i}$라는 지수 모양이 나오는데(최대 엔트로피 원리⁠, principle of maximum entropy⁠), 이것이 소프트맥스⁠(softmax)⁠의 모양입니다. 인간 피드백 강화 학습⁠(reinforcement learning)⁠에서 보상 r을 키우되 원래 모형 $\pi_{\text{ref}}$와의 KL 발산⁠(KL divergence)⁠에 벌점 β를 매기는 문제의 답도 같은 계산으로 $\pi(y) \propto \pi_{\text{ref}}(y)\,e^{r(y)/\beta}$입니다. 곡선 전체를 고르는 변분법⁠(calculus of variations)⁠에서도, 둘레가 정해진 곡선으로 넓이를 가장 크게 하는 등주 문제⁠(isoperimetric problem)⁠는 승수 하나로 풀리고 답은 원입니다. 역학에서는 $\lambda\nabla g$가 제약을 지키게 하는 힘, 이를테면 구슬을 철사 위에 붙잡아 두는 힘입니다.

이어지는 곳. 라그랑주는 1788년 『해석 역학』에서 제약이 있는 운동을 다루며 이 방법을 썼습니다. 곡선 전체를 고르는 문제에서는 같은 사람의 이름이 붙은 오일러–라그랑주 방정식⁠(Euler–Lagrange equation)⁠이 '1차 변화가 0'이라는 같은 생각을 함수⁠(function)⁠에 적용합니다. 조건 없이 기울기가 0인 곳을 찾는 기본형은 최적화에, 제약을 벌점으로 바꿔 손실에 더하는 방법은 정규화에 있습니다. 라소⁠(lasso)⁠ 같은 정규화는 '계수의 크기가 t 이하'라는 제약 문제와, 승수를 벌점의 세기로 삼은 벌점 문제가 서로 같은 답을 내는 짝입니다. '조금 움직여도 더 나아지지 않는다'는 한 가지 조건으로 여러 분야의 최적을 찾는 모습은 가장 좋은 것 고르기에 모아 두었습니다.