본문 바로가기
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에서 데이터를 무작위로 추출해야 하는 이유  (0) 2021.01.04
함수의 최소화 또는 최대화의 조건  (0) 2020.10.20
라그랑지 곱수법의 증명  (0) 2020.10.01
라그랑지 곱수법  (0) 2020.10.01
경사하강법  (0) 2020.09.30
최적화 문제의 분류  (0) 2020.09.30

댓글0