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

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

Lagrangian multiplier in Optimization Theory

설명

비선형목적 함수를 가지는 비선형 최적화 문제에서 제약조건에 라그랑주 승수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 $$ 에서 사실상 원래의 제약조건을 만족시킬수밖에 없게 되지만, 이에 따라 제약조건이 없거나 약해야하는 최적화기법을 사용할 수 있게 된 것이다.

예시

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

샤넌 엔트로피일양분포에서 극대화되는 것을 라그랑주 승수법을 통해 확인해보자. $\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 }} $$ 이다. 다시 말해, 일양분포엔트로피를 최대화한다.

서포트 벡터 머신

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


  1. Luenberger. (2021). Linear and Nonlinear Programming (5th Edition): p370~371. ↩︎

댓글