라그랑지 곱수법의 증명

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

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

 

$$\begin{array}{rl}& p^{\ast }=\underset{x_1,x_2}{min}f(x_1,x_2)\\ \\ subjectto& h(x_1,x_2)=0\end{array}$$

 

등식 제약조건은 평면상의 곡선의 식을 나타낸다. 먼저 목적함수와 등식 제약조건 식을 $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{array}{rl}& ▽f+\lambda ▽h=0\\ \\ & h(x_1,x_2)=0\end{array}$$

 

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

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

 

$$\begin{array}{rl}& \underset{x_1,x_2,x_3}{min}f(x_1,x_2,x_3)\\ \\ subjectto& h(x_1,x_2,x_3)=0\end{array}$$

 

등식 제약조건은 공간상의 곡면의 식을 나타낸다. 제약조건을 만족해야 하므로 함수의 최소값 또는 최대값은 곡면위에 있는 어떤 점일 것이다. 제약조건을 만족하는 곡면상의 한 점 $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^{\prime }(t)=(▽f(x_1(t),x_2(t),x_3(t)){)}^T{\mathbf{r}}^{\prime }(t)$$

 

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

 

$$w^{\prime }(t_0)=(▽f(x_1(t_0),x_2(t_0),x_3(t_0)){)}^T{\mathbf{r}}^{\prime }(t_0)=0$$

 

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

 

$$\begin{array}{rl}& ▽f+\lambda ▽h=0\\ \\ & h(x_1,x_2,x_3)=0\end{array}$$

 

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

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

 

$$\begin{array}{rl}& \underset{x_1,x_2,x_3}{min}f(x_1,x_2,x_3)\\ \\ subjectto& h_1(x_1,x_2,x_3)=0\\ \\ & h_2(x_1,x_2,x_3)=0\end{array}$$

 

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

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

 

$$\begin{array}{rl}& 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{array}$$

 

위 식을 $t$로 미분하면 다음과 같다.

 

$$\begin{array}{rl}& (▽h_1(x_1(t),x_2(t),x_3(t)){)}^T{\mathbf{r}}^{\prime }(t)=0\\ \\ & (▽h_2(x_1(t),x_2(t),x_3(t)){)}^T{\mathbf{r}}^{\prime }(t)=0\end{array}$$

 

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

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

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

 

$$w^{\prime }(t_0)=(▽f(x_1(t_0),x_2(t_0),x_3(t_0)){)}^T{\mathbf{r}}^{\prime }(t_0)=0$$

 

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

 

$$\begin{array}{rl}& ▽f+{\lambda }_1▽h_1+{\lambda }_2▽h_2=0\\ \\ & h_1(x_1,x_2,x_3)=0\\ \\ & h_2(x_1,x_2,x_3)=0\end{array}$$

 

여기서 ${\lambda }_1,{\lambda }_2$는 어떤 실수다.

 

 

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

 

$$\begin{array}{rl}& ▽f(\mathbf{x})+{\lambda }_1▽h_1(\mathbf{x})+{\lambda }_2▽h_2(\mathbf{x})+\cdots +{\lambda }_p▽h_p(\mathbf{x})=0\\ \\ & h_1(\mathbf{x})=0,h_2(\mathbf{x})=0,\cdots ,h_p(\mathbf{x})=0\end{array}$$

 

이제 라그랑지안 $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$의 그래디언트를 $▽L=0$으로 놓으면,

 

$$▽L=\left[\begin{array}{c}▽f(\mathbf{x})+{\lambda }_1▽h_1(\mathbf{x})+{\lambda }_2▽h_2(\mathbf{x})+\cdots +{\lambda }_p▽h_p(\mathbf{x})\\ h_1(\mathbf{x})\\ h_2(\mathbf{x})\\ ⋮\\ h_p(\mathbf{x})\end{array}\right]=0$$

 

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

 

$$p^{\ast }=\underset{\mathbf{x},{\lambda }_1,{\lambda }_2,...,{\lambda }_p}{min}f(\mathbf{x},{\lambda }_1,{\lambda }_2,...,{\lambda }_p)$$

 

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