본문 바로가기
AI 수학/최적화

라그랑지 곱수법의 증명

by 세인트 워터멜론 2020. 10. 1.

라그랑지 곱수(Lagrange multiplier)법을 증명해 보자.

먼저 기하학적 직관을 이용해서 증명해 본다. 다음과 같이 변수가 \( \mathbf{x} \in R^2 \)이고 등식 제약조건이 한 개 있는 최적화 문제를 살펴보자.

 

\[ \begin{align} & p^* = \min_{x_1, x_2} f( x_1, x_2 ) \\ \\ subject \ to \ \ \ & h (x_1, x_2) = 0 \end{align} \]

 

등식 제약조건은 평면상의 곡선의 식을 나타낸다. 먼저 목적함수와 등식 제약조건 식을 \( x_1,x_2 \)을 축으로 하는 평면에 그려보자.

 

 

검은색 선은 \( f(x_1,x_2 )=c \)의 등고선을 나타낸다. 등고선이란 동일한 함수 값 \(c\)를 산출하는 변수 \( x_1,x_2 \) 값의 집합이다.

그림에서 \(c_1, c_2 \)는 서로 다른 등고선 값을 나타낸다. 빨간색 선은 등식 제약조건을 만족하는 곡선이다. 제약조건을 만족하면서 함수 \( f(x_1,x_2 ) \)의 최소값을 구하는 문제는 빨간색 곡선과 등고선의 교점 중에서 가장 작은 등고선 값 \(c\)를 구하는 문제와 동일하다. 그 교점이 \(P\)라고 할 때, 점 \(P\)에서는 두 곡선의 접선(tangent)이 동일할 것이다.

 

 

동일한 접선을 갖는 두 곡선의 기울기 벡터(그래디언트)는 동일한 방향을 가지므로, 등식 제약조건을 만족하면서 함수 \( f(x_1,x_2 ) \)의 최소값을 갖는 교점 \(P \)에서 다음 식을 만족해야 한다.

 

\[ \begin{align} & \triangledown f + \lambda \triangledown h = 0 \\ \\ & h (x_1, x_2) = 0 \end{align} \]

 

여기서 \( \lambda \)는 두 곡선의 기울기 벡터의 크기 비를 나타내는 어떤 실수 값이다.

다음으로 최적화 변수가 \( \mathbf{x} \in R^3 \)이고 등식 제약조건이 한 개 있는 최적화 문제를 살펴보자. 이번에는 해석적으로 접근해 본다.

 

\[ \begin{align} & \min_{x_1, x_2, x_3} f( x_1, x_2, x_3 ) \\ \\ subject \ to \ \ \ & h (x_1, x_2, x_3) = 0 \end{align} \]

 

등식 제약조건은 공간상의 곡면의 식을 나타낸다. 제약조건을 만족해야 하므로 함수의 최소값 또는 최대값은 곡면위에 있는 어떤 점일 것이다. 제약조건을 만족하는 곡면상의 한 점 \( P \)에서 함수의 최소값 또는 최대값을 갖는다고 하자. 그리고 \( \mathbf{r}(t)=[x_1 (t) \ x_2 (t) \ x_3 (t)]^T \)을 곡면상에 있는 임의의 곡선을 나타내는 벡터라고 하고, 변수 \( t=t_0 \)일 때 벡터 \( \mathbf{r}(t) \)이 점 \(P\)를 지난다고 가정하자.

그러면 함수 \( f(x_1,x_2,x_3 ) \)는 다음과 같이 \(t\)의 함수로 쓸 수 있다.

 

\[ w(t) = f(x_1 (t), x_2 (t), x_3 (t) ) \]

 

위 식을 \(t\)로 미분하면 다음과 같다.

 

\[ w'(t) = ( \triangledown f(x_1 (t), x_2 (t), x_3 (t) ) )^T \mathbf{r} ' (t) \]

 

함수 \( f \)는 \( t=t_0 \)에서 최소 또는 최대값을 가지므로,

 

\[ w'(t_0) = ( \triangledown f(x_1 (t_0), x_2 (t_0), x_3 (t_0) ) )^T \mathbf{r} ' (t_0) = 0 \]

 

가 된다. 여기서 \( \mathbf{r}' (t_0 ) \)는 곡면 위에 있는 점 \(P\)를 지나는 임의의 곡선의 접선을 나타내므로 그래디언트 \( \triangledown f \)는 점 \(P\)에서 곡면에 접한 평면과 직각이 되는 것을 알 수 있다. 이는 또한 점 \(P\)에서 \( \triangledown f\)의 방향이 \( \triangledown h \)와 평행하다는 것을 의미하므로 다음과 같이 쓸 수 있다.

 

\[ \begin{align} & \triangledown f + \lambda \triangledown h = 0 \\ \\ & h (x_1, x_2, x_3) = 0 \end{align} \]

 

여기서 \( \lambda \)는 어떤 실수다.

등식 제약조건이 두 개 있는 경우의 최적화 문제는 어떨지 살펴보자.

 

\[ \begin{align} & \min_{x_1, x_2, x_3} f( x_1, x_2, x_3 ) \\ \\ subject \ to \ \ \ & h_1 (x_1, x_2, x_3) = 0 \\ \\ & h_2 (x_1, x_2, x_3) = 0 \end{align} \]

 

두 개의 제약조건을 만족해야 하므로 함수의 최소값 또는 최대값은 두 곡면이 만나는 곡선상에 있을 것이다.

두 개의 제약조건을 만족하는 곡선상의 어떤 점 \(P\)에서 함수의 최소값 또는 최대값을 갖는다고 하자. 그리고 \( \mathbf{r}(t)=[x_1 (t) \ x_2 (t) \ x_3 (t)]^T \)을 곡선을 나타내는 벡터라고 하고 변수 \( t=t_0 \)일 때 벡터 \( \mathbf{r}(t) \)이 점 \(P\)를 지난다고 가정하자. 그러면 제약조건은 다음과 같이 표현할 수 있다.

 

\[ \begin{align} & h_1 ( x_1 (t), x_2 (t), x_3 (t) )=0 \\ \\ & h_2 (x_1 (t), x_2 (t), x_3 (t) ) = 0 \end{align} \]

 

위 식을 \( t \)로 미분하면 다음과 같다.

 

\[ \begin{align} & ( \triangledown h_1 ( x_1 (t), x_2 (t), x_3 (t) ) ) ^T \mathbf{r} ' (t) =0 \\ \\ & ( \triangledown h_2 ( x_1 (t), x_2 (t), x_3 (t) ) ) ^T \mathbf{r} ' (t) =0 \end{align} \]

 

\( t=t_0 \)를 대입하면 \( \mathbf{r}' (t_0 ) \)는 점 \(P\)에서 곡선의 접선을 나타내므로 그래디언트 \( \triangledown h_1 \)과 \( \triangledown h_2 \)는 점 \(P\)에서 접선과 직각이 되는 것을 알 수 있다.

따라서 그래디언트 \( \triangledown h_1 \)과 \( \triangledown h_2 \)가 만드는 평면에 접선 벡터 \( \mathbf{r}' (t_0 ) \)이 수직이 됨을 알 수 있다.

함수 \( f \)는 \( t=t_0 \)에서 최소 또는 최대값을 가지므로,

 

\[ w'(t_0) = ( \triangledown f(x_1 (t_0), x_2 (t_0), x_3 (t_0) ) )^T \mathbf{r} ' (t_0) = 0 \]

 

이 된다. 따라서 그래디언트 \( \triangledown f \)도 점 \(P\)에서 \( \mathbf{r}' (t_0 ) \)와 직각이므로 \( \triangledown f \)도 그래디언트 \( \triangledown h_1 \)과 \( \triangledown h_2 \)가 만드는 평면에 있다는 것을 알 수 있다. 따라서 점 \( P \)에서 다음 식이 성립한다.

 

\[ \begin{align} & \triangledown f + \lambda _1 \triangledown h_1 + \lambda_2 \triangledown h_2 = 0 \\ \\ & h_1 (x_1, x_2, x_3) = 0 \\ \\ & h_2 (x_1, x_2, x_3) = 0 \end{align} \]

 

여기서 \( \lambda_1 , \lambda_2 \)는 어떤 실수다.

 

 

이와 같은 방법으로 다변수 목적함수 \( f( \mathbf{x}) \)와 \(p\)개의 등식 제약함수 \( h_j (\mathbf{x}) \)에 대해서도 함수의 최소 또는 최대값을 갖는 극점 \(P\)에서는 다음 식을 만족해야 하는 것을 보일 수 있다.

 

\[ \begin{align} & \triangledown f (\mathbf{x}) + \lambda_1 \triangledown h_1( \mathbf{x}) + \lambda_2 \triangledown h_2 (\mathbf{x} )+ \cdots + \lambda_p \triangledown h_p (\mathbf{x}) = 0 \\ \\ & h_1( \mathbf{x}) =0, \ \ h_2 (\mathbf{x} ) = 0, \ \ \cdots , \ \ h_p (\mathbf{x}) = 0 \end{align} \]

 

이제 라그랑지안 \( L \)을 다음과 같이 도입하고,

 

\[ L ({\mathbf{x}, \lambda_1 , \lambda_2 , ... , \lambda_p} ) = f( \mathbf{x})+ \lambda_1 h_1 ( \mathbf{x}) + \lambda_2 h_2 ( \mathbf{x}) + \cdots + \lambda_p h_p ( \mathbf{x}) \]

 

\( L \)의 그래디언트를 \( \triangledown L=0 \)으로 놓으면,

 

\[ \triangledown L = \begin{bmatrix} \triangledown f( \mathbf{x})+ \lambda_1 \triangledown h_1 ( \mathbf{x}) + \lambda_2 \triangledown h_2 ( \mathbf{x}) + \cdots + \lambda_p \triangledown h_p ( \mathbf{x}) \\ h_1 ( \mathbf{x}) \\ h_2 ( \mathbf{x}) \\ \vdots \\ h_p ( \mathbf{x}) \end{bmatrix} = 0 \]

 

위 식이 다음과 같은 제약조건이 없는 최적화 문제를 푸는데 사용되는 수식과 동일한 것임을 알 수 있다.

 

\[ p^* = \min_{\mathbf{x}, \lambda_1 , \lambda_2 , ... , \lambda_p} f( \mathbf{x}, \lambda_1 , \lambda_2 , ... , \lambda_p ) \]

 

이로써 라그랑지 곱수법을 증명하였다.

 

 

'AI 수학 > 최적화' 카테고리의 다른 글

SGD에서 데이터를 무작위로 추출해야 하는 이유  (1) 2021.01.04
함수의 최소화 또는 최대화의 조건  (0) 2020.10.20
라그랑지 곱수법  (0) 2020.10.01
경사하강법  (0) 2020.09.30
최적화 문제의 분류  (0) 2020.09.30

댓글