2020-2학기 이화여대 김정태 교수님 강의 내용을 바탕으로 본 글을 작성하였습니다.
Overview
- Lagrange multiplier (제약식이 방정식인 경우, 제약식이 없는 최적화기법으로 변경)
- Karush-Kuhn-Tucker (KKT) multiplier (제약식이 부등식인 경우, 제약식이 없는 최적화기법으로 변경)
이번에는 Machine Learning에서 자주 등장하는 최적화 기법인 대표적인 "Lagrange multiplier" 및 "Karush-Kuhn-Tucker (KKT) multiplier" 를 알아보고자 한다.
Largrange multiplier
Consider the problem of finding the maximum of a function $f(\mathbf{x})$ subject to a constraint
$$g(\mathbf{x}) = 0 \tag{1}\label{1}$$
어떤 목적 함수 $f(\mathbf{x})$를 최대화할때 주어진 제약식이 $g(\mathbf{x}) = 0$이라고 하자.
Note that $\nabla g(\mathbf{x})$ is normal to the contour of $g(\mathbf{x}) = 0$. On the contour, we seek $x^{*}$ such that $f(\mathbf{x})$ is maximized. On that point $\nabla f$ is also orthogonal to the contour since, otherwise we could increase the value of $f(\mathbf{x})$ by moving a short distance along the contour. Thus $\nabla f$ and $\nabla g$ are parallel (or anti parallel), so there exists a parameter $\lambda$ such that
$$\nabla f + \lambda \nabla g = 0 \tag{2}\label{2}$$
where $\lambda \neq 0$ is known as Lagrange multiplier. Therefore, we can convert a constrained optimization problem into unconstrained one by introducing the following Lagrangian function.
$$L(\mathbf{x}, \lambda) = f(\mathbf{x}) + \lambda g(\mathbf{x}) \tag{3}\label{3}$$
식 (3)과 같이 목적함수와 제약식을 우변으로 정리한 형태의 꼴을 Lagrangian function이라고 한다.
▶ Example
Maximize $f(\mathbf{x}_1, \mathbf{x}_2) = 1 − \mathbf{x}_1^2 − \mathbf{x}_2^2$ subject to the constraint $g(\mathbf{x}_1, \mathbf{x}_2) = \mathbf{x}_1 + \mathbf{x}_2 − 1 = 0$.
The Lagrangian function is
$$L(\mathbf{x}, \lambda) = 1 − \mathbf{x}_1^2 − \mathbf{x}_2^2 + \lambda (\mathbf{x}_1 + \mathbf{x}_2 − 1) \tag{4}\label{4}$$
The conditions for the Lagrangian to be stationary
$$
\begin{array}{r}
-2 x_{1}+\lambda=0 \tag{5}\label{5}\\
-2 x_{2}+\lambda=0 \\
x_{1}+x_{2}-1=0
\end{array}
$$
조건인 식 (2)을 만족해야하기 때문에 $f(\mathbf{x})$에 대한 1차 미분 및 $\lambda$에 대한 1차 미분을 통해 위의 방정식을 얻을 수 있다.
식 (5)의 연립방정식을 통해 $\lambda, \mathbf{x}_1, \mathbf{x}_2$를 구할 수 있을 것이다. (직접 풀어보기)
지금까지 제약식이 방정식인 경우에 대한 최적화 문제를 제약식이 없는 최적화 문제로 변경하여 푸는 기법인 "Largrange multiplier"를 다뤘다. 이어서 제약식이 부등식인 경우 풀기 위한 기법을 알아보자.
Karush-Kuhn-Tucker (KKT) multiplier
Consider the problem of finding the maximum of a function $f(\mathbf{x})$ subject to a constraint
$$g(\mathbf{x}) \geq 0 \tag{6}\label{6}$$
There exit two kind of solution. First case is that the stationary point lies in the region $g(\mathbf{x}) \gt 0$ in which case the constraint is inactive. The other case is that the stationary point lies on the boundary $g(\mathbf{x}) = 0$. First case, the solution is the same as the one from unconstrained optimization. Second case, the solution can be obtained using Lagrange multiplier. For this case, the sign of the Lagrange multiplier is crucial because $f(\mathbf{x})$ will be a maximum if the gradient is oriented away from region $g(\mathbf{x}) \gt 0$. We therefore have $\nabla f(\mathbf{x}) = −\lambda \nabla g(\mathbf{x})$. Either case
Reference
- Pattern Recognition and Machine Learning
- Meaning of Lagrange multiplier (Khan Academy | 3blue1brown)
- PRML Example Code (git) : github.com/ctgk/PRML
댓글