조건식이 있는 최적화 문제에서 정류점을 찾기위해 라그랑주 승수법을 이용합니다. 라그랑주 승수법에 대해 다룬 여러 글들을 보면 정류점에서 조건식과 목적함수의 기울기가 나란해야 함을 언급합니다. 조건식이 하나만 있을 경우 이와 같은 설명은 직관적입니다. 하지만 조건식이 여러개 있을 경우 쉽게 이해가 되지 않습니다. 목적함수의 기울기가 꼭 조건식의 기울기의 선형조합을 이루어야 될까요? 그리고 조건식이 부등식일 때 라그랑지 승수의 범위는 어떻게 정해지는지 의문이 들었기에 직접 증명해 보았습니다.

$$ \begin{array}{l} \tag{ 1 } \min_x & f(x) \\ s.t. & g_i(x) \ge 0 \quad i = 1,...m \end{array} $$

위와 같은 최소화 문제를 생각해 봅시다. 우리는 주로 극소점을 찾는대신 정류점을 찾습니다. 점 $x$에서 활성화된 조건식이 없다면 간단히 $\nabla f$를 통해 정류점인지 판단할 수 있습니다. 활성화된 조건식이 있다면 경사하강법을 통해 구할 수 있습니다. 경사하강법은 임의의 점에서 시작해 정류점을 향해 이동합니다. 위치 $x$에서 이동방향을 $v_x$라고 합시다. 이동방향이 0이면 점 $x$는 정류점 입니다. 따라서 $x$에서 이동방향이 0이기 위한 조건은 $x$가 정류점일 조건입니다. 그러므로 $v_x$를 어떻게 구하는지 먼저 알아봅시다. 자세한 내용은 제약이 있는 경사하강법에 설명되어 있으며 여기선 간단히 설명합니다.

1. 제약이 있는 경사하강법에서 이동 방향

우선 기호를 정의합니다. 활성화된 조건식의 기울기의 단위벡터의 집합을 $A$라고 하고 $N$과 $M$을 다음과 같이 정의합니다. $N$의 컬럼스페이스는 $span(A)$, $M$의 컬럼스페이스는 $A^\bot$입니다. 또한 $M$의 모든 컬럼은 직교이고 정규화되어있습니다.

$$ \begin{array}{l} \tag{ 2 } A & = & \{ \: \frac{\nabla g_i}{\| \nabla g_i \|} \: | \: g_i(x) = 0 \: \} \newline N & = & \begin{bmatrix} A_0 | A_1 | A_2 … \end{bmatrix} \newline M & = & ( M \text{’s columns is orthonomal basis of } A^\bot ) \end{array} $$

0과 크기가 1인 모든 벡터의 집합 $V$를 $M$과 $N$을 이용해 정의합니다. $u$와 $\lambda$는 벡터로 $M$과 $N$의 컬럼을 선형조합합니다. $V$의 원소 중 조건식에 의해 제약되지 않은 방향의 집합 $\bar{V}$를 $M$과 $N$을 이용해 정의합니다.

$$ \begin{array}{l} \tag{ 3 } V & = & \{\,0\,\} \cup \{\, N\lambda + M u \,\mid\, \|\lambda\|^2 + \|u\|^2 = 1 \,\} \\ \bar{V} & = & \{\, v \in V \,\mid\, \forall{i} \quad (N^T v)_i \ge 0 \,\} \end{array} $$

$v_x$는 이동 가능한 방향 중 이동시 $f$의 변화량이 가장 큰 방향입니다. 따라서 $v_x$는 다음과 같습니다.

$$ \begin{array}{l} \tag{ 4 } v_x = \underset{v \in \bar{V}} {\arg\min} \nabla f^T v\\ \end{array} $$

2. 이동 방향이 0임과 동치명제

다시 본론으로 돌아갑시다. 아시다시피 $x$가 정류점임은 $v_x$가 0임과 동치입니다. 그리고 (4)에 의해 0을 제외한 $\bar{V}$의 모든 원소는 $\nabla f$와의 내적이 양수임과 동치입니다. 이를 이용해 정류점에서 $\nabla f$가 향할 수 있는 방향을 알아봅니다.

$$ \begin{array}{l} \tag{ 5 } \nabla f = N \lambda^f + M u^f \end{array} $$

$x$를 정류점이라 가정합시다. $x$에서 $\nabla f$를 $M$과 $N$의 컬럼의 선형조합으로 표현합시다(5). $u^f$와 $\lambda^f$는 벡터로 $M$과 $N$의 컬럼을 선형조합합니다. $u^f$가 0이 아니면 $u^f$의 단위벡터를 이용해 $\nabla f$와 내적시 음수가 되는 $\bar{V}$의 원소를 만들 수 있습니다. $\lambda^f_i$가 음수라면 $i$번째 원소만 1인 단위벡터와 $\nabla f$의 내적이 음수가 됩니다. 자세한 사항은 (6)을 참고하시면 됩니다.

$$ \begin{array}{l} \tag{ 6 } \text{if } u^f \neq 0 & \rightarrow & \nabla f^T (-M (\hat{u^f})) < 0 \\ \text{if } \lambda^f_i < 0 & \rightarrow & \nabla f^T v < 0 & (v_j = 1 \text{ if } j=i \text{ else } 0) \end{array} $$

따라서 $u^f$는 0이고 $\lambda$의 모든 원소는 0 이상입니다.

$$ \begin{array}{l} \tag{ 7 } \nabla f \in \{\, N\lambda \,\mid\, \forall{\lambda_i} \ge 0 \,\} \\ \end{array} $$

즉, $x$가 정류점이면 (7)을 만족합니다.

$$ \begin{array}{l} \tag{ 8 } \nabla f^T v = (N \lambda^f)^T v = \lambda^{fT} (N^T v) \ge 0 \end{array} $$

역으로 $\nabla f$가 (7)을 만족하면 $\bar{V}$의 임의의 원소 $v$와의 내적은 언제나 양수입니다(8). $v_x$는 0이되고 $x$는 정류점 입니다. 따라서 $x$가 정류점임은 (7)과 동치입니다. $N$의 컬럼은 활성화된 조건식의 기울기의 단위벡터이므로 (7)은 우리가 아는 라그랑주 승수법(9)과 같습니다.

$$ \begin{array}{l} \tag{ 9 } \exists{\lambda_i \ge 0} \quad \nabla f = \sum{} \lambda_i \nabla g_i \\ \end{array} $$

3. 정리

라그랑주 승수의 범위는 조건식에 의해 막힌 방향입니다. 기울기가 증가하는 방향이 조건식에 의해 완전히 막혔을 때 그 위치는 정류점이 됩니다. 최소화 문제의 경우 $-\nabla f$ 방향은 조건식에 의해 막힌 방향(조건식이 0보다 클 때 기울기의 반대)입니다. (10)을 예시로 봅시다. 점 $x$에서 활성화된 조건식이 있으면 $x$가 정류점임은 (11)과 동치입니다.

$$ \begin{array}{l} \tag{ 10 } \min_x & f(x) \\ s.t. & g_i(x) \ge 0 & i = 1,...m \\ & h_j(x) \le 0 & j = 1,...n \\ & l_k(x) = 0 & k = 1,...r \end{array} $$ $$ \begin{array}{l} \tag{ 11 } \exists{\:a_i \ge 0,\: b_i \le 0,\: c_i} \quad f = \sum{} a_i g_i + \sum{} b_i h_i + \sum{} c_i l_i\\ \end{array} $$

(12)에서 점 $x$에서 활성화된 조건식이 있으면 $x$가 정류점임은 (13)과 동치입니다.

$$ \begin{array}{l} \tag{ 12 } \max_x & f(x) \\ s.t. & g_i(x) \ge 0 & i = 1,...m \\ & h_j(x) \le 0 & j = 1,...n \\ & l_k(x) = 0 & k = 1,...r \end{array} $$ $$ \begin{array}{l} \tag{ 13 } \exists{\:a_i \le 0,\: b_i \ge 0,\: c_i} \quad f = \sum{} a_i g_i + \sum{} b_i h_i + \sum{} c_i l_i\\ \end{array} $$