[기계학습] 최적화 문제 - 라그랑주 프리멀 함수, 라그랑주 듀얼 함수

 최적화라 함은 최대값 또는 최소값을 구하는 것을 말한다.

즉, 극값을 구해야하므로 미분을 수행해야한다.

그런데 어떻게 해야하나?

 

$\min f(x)$ -> 목적함수(objective function)

subject to $\left \{ \begin{matrix} g_i(x) \le 0, & i=1, ... ,m \\ h_i(x) = 0, & i=1, ... , p \end{matrix} \right.$  -> 제약식

 

라그랑주 승수법: 제약식이 있는 최적화 문제를 푸는 방법

다변수 함수 2개 이상에서 서로 맞닿는 부분(접점)을 구하기 위한 방법인데, 이를 제약식과 목적함수에 대입하여, 극값을 구하기 위해 사용한다.

 

라그랑주 프리멀 함수:

$L_p(x,\lambda ,v) = f(x) + \sum_{i=1}^m\lambda_{i}g(x) + \sum_{i=1}^pv_{i}h(x)$

라그랑주 승수법을 이용해서 극값을 구하는 함수를 만든 것이다.

 

라그랑주 듀얼 함수:

$L_D(\lambda,v) = \inf L(x,\lambda,v) = \inf \left( f(x) + \sum_{i=1}^m\lambda_{i}g(x) + \sum_{i=1}^pv_{i}h(x) \right)$

의미: $\lambda \ge 0$에 대해 프리멀 함수 최적값 $p^*$의 하한 (lower bound)를 나타냄

 

$p^*=$ 라그랑주 프리멀 함수의 최적값

$d^*=$ 라그랑주 듀얼 함수의 최적값

 

$L_D(\lambda,v) \le p^*$

 

$d^* \le p^* \to$ 프리멀 문제의 최적값 = 듀얼 함수의 최대화 (weak duality)

$d^* = p^* \to$ 프리멀 문제의 최적값 = 듀얼 함수의 최적값 (strong duality)

 

간략정리

최적값을 구하기 위해 프리멀 함수의 람다값이 오차를 최소화하는 값을 갖도록 조정 후 그 람다값을 구하기 위함

추후 릿지 회귀에서 이용