📂최적화이론

최적화이론의 라그랑주 승수법

설명

비선형인 목적 함수를 가지는 비선형 최적화 문제에서 제약조건에 라그랑주 승수^{lagrangian Multiplier}라는 것을 곱해서 목적 함수에 반영시키는 풀이법을 라그랑주 승수법이라 한다.

$$\begin{matrix} \text{Maximize} & f(x) \\ \text{subject to} & g(x) = 0 \end{matrix}$$

가령 미분가능한 스칼라함수 $f,g : \mathbb{R}^{p} \to \mathbb{R}$ 에 대한 최적화 문제가 위와 같이 주어져 있다고 하면, 우리의 목표는 가용해의 집합^{feasible solution} $F = \left\{ x \in \mathbb{R}^{n} : g(x) = 0 \right\}$ 에서 $f \left( x^{\ast} \right)$ 가 최대가 되게끔하는 $x^{\ast} \in F$ 를 찾는 것이다. 라그랑주 승수법은 이에 대한 해법 중 하나로써, 라그랑주 승수 $-\lambda$ 를 $g(x)$ 에 곱해서 $f$ 에 더한 라그랑주 함수 $$L \left( x, \lambda \right) := f(x) - \lambda g(x)$$ 를 목적 함수로 삼는 다음의 최적화 문제로 바꾸는 것이다. $$\begin{matrix} \text{Maximize} & L \left( x, \lambda \right) \end{matrix}$$

이렇게 얻은 새 최적화 문제는 제약조건이 없어졌고, 이는 마법이 아니라 수학이다. $L$ 을 최적화하는 과정에서 $L$ 의 $\lambda$ 에 대한 변화량이 $0$ 이 되는 지점, 그러니까 $${{ \partial L } \over { \partial \lambda }} = 0 \implies -g(x) = 0$$ 에서 사실상 원래의 제약조건을 만족시킬수밖에 없게 되지만, 이에 따라 제약조건이 없거나 약해야하는 최적화기법을 사용할 수 있게 된 것이다.

예시

엔트로피를 최대화하는 분포는 균등분포다 ¹

샤넌 엔트로피는 일양분포에서 극대화되는 것을 라그랑주 승수법을 통해 확인해보자. $\left( p_{1} , \cdots , p_{n} \right)$ 에 대해 확률변수 $X$ 의 확률분포가 다음과 같다고 하자. $$P\left( X = k \right) = p_{k}$$

그러면 엔트로피를 가장 크게 하는 $\left( p_{1} , \cdots , p_{n} \right)$ 를 구하는 최적화 문제는 다음과 같이 쓸 수 있다.

$$\begin{matrix} \text{Maximize} & - \sum_{k=1}^{n} p_{k} \log p_{k} \\ \text{subject to} & \sum_{k=1}^{n} p_{k} - 1 = 0 \\ & p_{k} \ge 0 \end{matrix} \\ k = 1, \cdots, n$$

제약조건인 $\displaystyle \sum_{k=1}^{n} p_{k} = 1$ 은 모든 확률의 합이 $1$ 이어야하기 때문이다. 원래의 목적 함수 $f \left( p_{1} , \cdots , p_{n} \right) = - \sum_{k=1}^{n} p_{k} \log p_{k}$ 는 이 제약조건에 따라 무한정 커질 수가 없게 된다. 이 문제에 대한 라그랑주 함수는 다음과 같다. $$L \left( p_{1} , \cdots , p_{n} , \lambda \right) = - \sum_{k=1}^{n} p_{k} \log p_{k} - \lambda \left( \sum_{k=1}^{n} p_{k} - 1 \right)$$ 그러면 $L$ 을 $k = 1, \cdots , n$ 에 대해 $p_{k}$ 로 편미분 했을 때 $${{ \partial L } \over { \partial p_{k} }} = - \log p_{k} + 1 - \lambda \implies \lambda = 1 - \log p_{k}$$ 이다. 이는 $$\begin{align*} & \lambda \\ =& 1 - \log p_{1} \\ & \vdots \\ =& 1 - \log p_{n} \end{align*}$$ 을 함의하므로 $$p_{1} = \cdots = p_{n}$$ 이어야 한다. 한편 $\lambda$ 에 대한 편미분에서 $${{ \partial L } \over { \partial \lambda }} = 0 \implies \sum_{k=1}^{n} p_{k} = 1$$ 이므로, 원래 문제였던 엔트로피를 극대화하는 확률분포는 정확히 $$p_{1} = \cdots = p_{n} = {{ 1 } \over { n }}$$ 이다. 다시 말해, 일양분포는 엔트로피를 최대화한다.

■

서포트 벡터 머신

머신러닝에서는 서포트벡터머신이 초평면을 찾는 기법으로써 라그랑주 승수법이 등장할 수 있다. 다음 단락을 참고하라:

• 서포트벡터머신/커널 트릭