[최적화] 등식 제약 최적화와 라그랑주 승수법 (Lagrange Multiplier Method)
등식 제약 최적화 (Equality Constrained Optimization)
등식 제약 조건을 만족하면서, 목적 함수 $f(x)$의 값을 최소화하는 변수 $x$를 찾는 최적화 문제이다.
\[\begin{aligned} \mathbf{x}^*=\min_{\mathbf{x}}f(\mathbf{x})~~~~\\ \text{subject to}~g(\mathbf{x})=c \end{aligned}\]$g(\mathbf{x})=c$라는 제약 조건 위에서만 $\mathbf{x}$를 찾아야 한다.
제약 조건에서의 최적해
아래와 같은 목적 함수 $f$와 제약 조건 $g$에 대해 생각해보자.
\[f(x,y)=6-\frac{3}{16}(x^2+y^2)~~,~~g(x,y)=\frac{\vphantom{\Big(}(x-2)^2}{0.25}+\frac{y^2}{4}-1\]$f$는 2차원 평면에서는 원 형태의 등고선 (파란색), 3차원 공간에서는 위로 볼록한 포물곡면 형태로 나타난다.
$g$는 2차원 평면에서는 타원 형태의 등고선 (초록색), 3차원 공간에서는 아래로 볼록한 타원포물면 형태 (빨간색)로 나타난다.
이때 빨간색 곡선 위에서 목적 함수가 최대가 될 때는 아래와 같다. 즉, 파란색 곡선이 초록색 곡선과 접할 때이다.
따라서 제약 조건을 만족하는 최적점에서는 목적 함수의 등고선과 제약 조건의 곡선이 서로 접할 때이며, 이 지점에서 두 함수의 그라디언트의 방향은 동일하다.
\[\nabla f(\mathbf{x}^*)=\lambda\nabla g(\mathbf{x}^*)\]
$\lambda$는 라그랑주 승수 (Lagrange Multiplier)로, 비례 상수이다. $\lambda>0$이면 두 그라디언트의 방향이 같다는 뜻이며, $\lambda<0$이면 두 그라디언트의 방향이 반대라는 뜻이다.
라그랑주 승수법 (Lagrange Multiplier Method)
비제약 최적화 문제에서는 단순히 $\nabla f(x)=0$을 만족하는 지점을 찾아 최적점을 찾을 수 있지만, 제약 조건이 있을 때는 그럴 수 없다.
이를 해결하기 위해 제약식을 목적 함수에 포함시킨 새로운 함수 $\mathcal{L}$을 정의하는데, 이를 라그랑주 함수 (Lagrangian) 라고 한다.
\[\mathcal{L}(x,y,\lambda)=f(x,y)-\lambda g(x,y)\]라그랑주 승수법은 다음 조건을 만족하는 점을 찾는 방법이다.
\[\nabla_{x,y,\lambda}\mathcal{L}(x,y,\lambda)=0\]즉, 모든 변수 $x,y,\lambda$에 대해 편미분이 0이 되는 지점을 찾는 방법이며, 이를 통해 제약 최적화 문제를 비제약 최적화 문제로 바꾸어 풀 수 있게 된다.
위 식을 전개하면 아래와 같다.
\[\begin{equation} \frac{\partial\mathcal{L}}{\partial x}=\nabla_x f(x,y)-\lambda\nabla_x g(x,y)=0 \end{equation}\] \[\begin{equation} \frac{\partial\mathcal{L}}{\partial y}=\nabla_y f(x,y)-\lambda\nabla_y g(x,y)=0 \end{equation}\] \[\begin{equation} \frac{\partial\mathcal{L}}{\partial\lambda}=-g(x,y)=0 \end{equation}\]$(1), (2)$번 식에 의해 아래 식이 성립한다.
\[\nabla f(x,y)=\lambda\nabla g(x,y)\]$(3)$번 식에 의해 아래의 식이 성립한다.
\[g(x,y)=0\]즉, $\nabla_{x,y,\lambda}\mathcal{L}(x,y,\lambda)=0$은 제약 조건을 만족하면서 목적 함수의 기울기 방향이 제약식의 기울기와 일치하는 점을 찾는 것과 같다.
Example 1
둘레의 길이가 $20$인 직사각형이 가질 수 있는 최대 넓이는 얼마이며, 그때의 가로와 세로 길이는 얼마인가?
1. 목적 함수와 제약 조건 식 세우기
가로를 $x$, 세로를 $y$라고 하자.
\[\begin{aligned} \max_{x,y}~xy~~~~~~~~~~~~~\\ \text{subject to}~x+y=10 \end{aligned}\]2. 라그랑주 함수 정의
\[\mathcal{L}(x,y,\lambda)=xy-\lambda(x+y-10)\]3. $\nabla\mathcal{L}=0$ 계산
\[\nabla_x\mathcal{L}=y-\lambda=0~\to~y=\lambda\] \[\nabla_y\mathcal{L}=x-\lambda=0~\to~x=\lambda\] \[\nabla_\lambda\mathcal{L}=-x-y+10~\to~x+y=10\]4. 연립 방정식 풀기
\[\begin{cases} x=\lambda\\y=\lambda\\x+y=10 \end{cases}~~~~\to~x=y=5\]따라서 최대 넓이는 $25$, 그때의 가로와 세로의 길이는 각각 $5, 5$이다.
제약 조건이 여러 개인 경우
제약 조건이 여러 개인 경우는 어떻게 풀어야할까? 먼저 제약 조건이 2개인 경우에 대해서
\[\begin{aligned} \mathbf{x}^*=\min_{\mathbf{x}}f(\mathbf{x})~~~~\\ \text{subject to}~g_1(\mathbf{x})=a\\ g_2(\mathbf{x})=b \end{aligned}\]제약 조건에서의 최적점은 두 제약식의 그라디언트의 선형 결합으로 표현할 수 있다.
\[\nabla f(\mathbf{x}^*)=\lambda_1\nabla g_1(\mathbf{x}^*)+\lambda_2\nabla g_2(\mathbf{x}^*)\]
이를 일반화하면 아래와 같다.
\[\nabla f(\mathbf{x}^*)=\sum_{k=1}^M\lambda_k\nabla g_k(\mathbf{x}^*)\]따라서, 제약 조건의 여러 개인 경우의 라그랑주 함수는 아래와 같이 정의된다.
\[\mathcal{L}(\mathbf{x}^*,\boldsymbol\lambda)=f(\mathbf{x})-\sum_{k=1}^M\lambda_k g_k(\mathbf{x})\] \[\nabla\mathcal{L}(\mathbf{x}^*,\boldsymbol\lambda)=\nabla f(\mathbf{x})-\sum_{k=1}^M\lambda_k \nabla g_k(\mathbf{x})\]