jebae's dev blog

라그랑주 승수법 (Lagrange Multiplier Method)

제약조건이 있는 최적화 문제 풀기

2019년 02월 25일

라그랑주 승수법은 제약조건이 있는 최적화 문제를 풀기 위한 방법입니다. 예를 들어 다음과 같이 f(x,y)f(x,y)와 g(x,y)g(x, y)가 존재합니다.

g(x,y)=cg(x, y) = c라는 제약 조건을 만족하는 f(x,y)f(x, y)의 최댓값은 어떻게 구할 수 있을까요? 직관적으로 최댓값은 f(x,y)f(x,y)가 g(x,y)g(x, y)에 접할 때라는 것을 알 수 있습니다. 라그랑주 승수법은 두 함수 ff, gg의 Gradient 벡터를 이용해 최댓값을 찾습니다. 어떤 지점에서 Gradient 벡터는 접선 벡터에 수직인 벡터입니다. ff와 gg의 접점에서의 Gradient 벡터는 같은 방향이므로 다음과 같이 쓸 수 있습니다.

∇f=λ∇g(∂f∂x,∂f∂y)=λ(∂g∂x,∂g∂y)(∂f∂x,∂f∂y,∂f∂z)=λ(∂g∂x,∂g∂y,∂g∂z)\nabla f = \lambda \nabla g \\ \begin{pmatrix} \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} \end{pmatrix} = \lambda \begin{pmatrix} \frac{\partial g}{\partial x}, \frac{\partial g}{\partial y} \end{pmatrix} \\ \begin{pmatrix} \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}, \frac{\partial f}{\partial z} \end{pmatrix} = \lambda \begin{pmatrix} \frac{\partial g}{\partial x}, \frac{\partial g}{\partial y}, \frac{\partial g}{\partial z} \end{pmatrix}

이 때 상수 λ\lambda를 라그랑주 승수라 합니다. 라그랑주 승수법은 최적화를 위해 접점을 찾는 과정이라 할 수 있습니다. 다음은 라그랑주 승수법에서 정의하는 보조 함수입니다.

L(x,y,λ)=f(x,y)−λ(g(x,y)−c)L(x, y, \lambda) = f(x, y) - \lambda (g(x, y) - c)

위 식을 예시의 원과 직선, x2+y2=4x^2 + y^2 = 4, 2x+y=k2x + y = k 대해 적용하면 다음과 같이 쓸 수 있습니다.

L(x,y,λ)=2x+y−k−λ(x2+y2−4)L(x, y, \lambda) = 2x + y - k - \lambda (x^2 + y^2 - 4)

보조 함수의 관점에서 최적화 문제를 푸는 것은 ∇f−λ∇g\nabla f - \lambda \nabla g 의 Gradient 벡터가 영벡터임을 만족하는 편미분을 푸는 것과 같습니다. 예를 들면 다음과 같습니다.

∂L∂x=∂f∂x−λ∂g∂x=0\frac{\partial L}{\partial x} = \frac{\partial f}{\partial x} - \lambda \frac{\partial g}{\partial x} = 0 ∂L∂y=∂f∂y−λ∂g∂y=0\frac{\partial L}{\partial y} = \frac{\partial f}{\partial y} - \lambda \frac{\partial g}{\partial y} = 0

제약 조건이 여러개일 때 보조 함수를 일반화하면 다음과 같습니다.

L(x,y,λ1,...,λn)=f(x,y)−∑i=1Nλi(gi(x,y)−ci)L(x, y, \lambda_1, ..., \lambda_n) = f(x, y) - \sum^{N}_{i=1} \lambda_i (g_i(x, y) - c_i)





출처 및 참고

최적화 문제
# 라그랑주 승수법