[ML]라그랑주 승수법(Lagrange Multiplier Method)

라그랑주 승수법(Lagrange Multiplier Method)

라그랑즈 승수법이란 제약식(Constraint)이 있는 Optimization 문제를 라그랑주 승수 항을 추가해, 제약이 없는 문제로 바꾸는 방법입니다

제약식, 라그랑주 승수에 대해서 생소하실텐데, 수식을 통해 라그랑주 승수법에 대한 설명을 시작하도록 하겠습니다

Primal Problem(원초문제)

우리가 해결해야할 문제입니다

\begin{aligned}
&\underset{x}{\min} \, c^T x\\
&subject\;to\; Ax = b\; , Gx \le h
\end{aligned}

원초 문제 $f = c^T x$를 최소화하는 과정에서 $Ax = b$, $Gx \le h$라는 제약식(Constraint)을 가지는 상황입니다.

라그랑주 승수법을 사용하기 위해(제약식이 없는 문제로 바꾸기 위해) 라그랑주 승수 벡터 $u$와 $v\ge0$를 도입하여 라그랑주 함수 $L(x, u, v)$을 만들어야합니다 ($v\ge0$인 이유는 부등식으로 표현된 식들은 0보다 큰 라그랑주 승수 벡터를 사용해야하기 때문입니다)

 

완성된 라그랑주 함수 $L$은 아래와 같습니다

$$L(x,u,v) = c^T x + u^T(Ax-b) + v^T(Gx - h) \le c^T x$$

$Ax-b = 0$, $v^T\ge0$, $Gx-h \le 0$이기 때문에 위의 식이 성립하게 됩니다

이제 라그랑주 함수를 최소화하는 $x$를 찾고, 그 결과를 사용하여 라그랑주 승수 벡터를 찾아야 합니다

 

Dual Function(듀얼 함수)

먼저 라그랑주 함수를 최소화하는 $x$를 찾아야합니다

$$f^* = c^T x^* \ge \underset{x}{\inf} L(x,u,v) = \underset{x}{\inf} \{c^T x + u^T(Ax-b) + v^T(Gx - h)\} = g(u,v) $$

여기서 듀얼 함수 $g(u,v)$는 라그랑주 함수를 $x$에 대해 최소화한 결과로 정의됩니다. 즉, 원초 문제의 최적값 $f^∗$는 항상 듀얼 함수 $g(u,v)$의 최적값보다 크거나 같음을 알 수 있습니다.

 

이제, x에 대한 편미분의 결과가 0인 지점에서 라그랑주 함수의 최소값을 찾습니다

 

편미분을 하여 식을 정리하면 아래와 같습니다

$$
\begin{aligned}
&\frac{\partial L}{\partial x} =c^T + u^T A + v^T G = 0\\
&c = -A^T u -G^T v\\
\end{aligned}
$$

여기서 구한 조건을 사용하여 듀얼 함수를 다음과 같이 정의할 수 있습니다:
$$
\begin{aligned}
g(u, v)  &= \underset{x}{\inf}\{c^T x + u^T(Ax-b) + v^T(Gx - h)\}\\
&= \underset{x}{\inf}\{( -A^T u -G^T v )^T x + u^T(Ax-b) + v^T(Gx - h)\}\\
&=\underset{x}{\inf}\{-u^T A x - v^T G x + u^T(Ax-b) + v^T (Gx-h) \}\\
&= -u^T b - v^T h \\
\end{aligned}
$$

Duality Gap

위에서 확인했듯이 라그랑주 함수 $L(x, u, v)$ 라그랑지 듀얼 함수 $g(u, v)$가 같은 값을 가질 때 라그랑주 함수가 최솟값을 갖게 되고 이를 만족하는 라그랑주 승수 벡터 $u, \; v\ge0$을 구할 수 있습니다

 

이 때 둘 사이에 gap이 존재하면($f^* \gt g(u,v)$) weak duality, 존재하지 않으면($f^* = g(u,v)$) strong duality 이라고 합니다

 

즉, 원초 문제의 최적값 $f^*$는 항상 듀얼 함수의 최적값보다 크거나 같습니다

$$f^* = \underset{x}{\min} L(x, u, v) \ge g(u, v)$$

따라서 듀얼함수 $g(u,v)$를 최대화하는 것이 원초 문제의 최적값에 가까워진다고 할 수 있습니다

---

Lagrange Dual Problem(라그랑주 듀얼 문제)

따라서 원초 문제의 최적값에 도달하기 위해 라그랑주 함수를 최소화하는 문제에서 라그랑주 듀얼 함수의 최대화 문제로 바꾸어 해결할 수 있습니다

 

$$
\begin{aligned}
&\underset{u, v}{\max} -u^T b - v^T h\\
&subject \; to \; -A^T u -G^T v = c ,\; v\ge0 
\end{aligned}
$$

 

이 듀얼 문제는 원초 문제의 제약 조건을 만족하면서 듀얼 변수를 사용해 최적화 문제를 푸는 방법입니다. 

• Weak Duality
  • $f^* \ge g(u,v)$가 성립합니다
  • 즉, 원초 문제의 최적값이 듀얼 문제의 최적값보다 항상 크거나 같음을 의미합니다
• Strong Duality 
  • $f^* = \underset{u, v}{max} g(u,v)$가 성립합니다
  • 즉, 원초 문제의 최적값이 듀얼 문제의 최적값과 같음을 의미합니다
  • Strong Duality가 성립하는 조건 중 하나는 Slater's Condition입니다

Slater's Condition

Slater's Condition이란 Strong Duality를 만족하기 위한 충분조건입니다

$$
\begin{aligned}
&\underset{x}{\min} f(x)\\
&subject\; to\; \begin{cases}
    h_i(x) \le 0,&\;  i = 1, \cdots , m\\
    l_j(x) = 0, &\; j=1, \cdots, r
\end{cases}
\end{aligned}
$$

• 조건 1 : 원초 문제가 Convex
  • $h_1,\; \cdots , \; h_m$이 convex(아래로 볼록), $l_1,\; \cdots , \; l_r$이 affine
• 조건 2 : $x\in \mathbb{R}^n$에 대해 최소 한개 이상의 strictly feasible 한 $x$를 가져야 한다
  • $h_1(x) \lt 0,\; \cdots , \; h_m \lt 0$,  $l_1(x) = 0,\; \cdots , \; l_r(x) = 0$

조건 1, 조건 2를 만족하면 원초 문제와 듀얼 문제가 Strong Duality를 만족한다

 

Slates' Condition을 만족하면 원초 문제와 듀얼 문제 사이에 Strong Duality가 성립하게 되고, 이는 원초 문제의 최적값($f^*$과 듀얼 문제의 최적값($g^*$)이 같아짐을 의미합니다
결론적으로 듀얼 문제의 최적해가 존재함을 보장하게 되므로 듀얼 변수(라그랑주 승수 벡터 $u, v$)를 통해 원초 문제의 제약 조건을 직접적으로 다룰 수 있게 한다

 

※ Strictly Feasible Point

제약조건을 엄격하게 만족하는 해

특히, 최적화 문제에서 제약조건을 만족하는 해를 의미한다

여기서, 등호를 제외한 제약조건을 만족시키는 해를 Strictly Feasible 이라한다(등호를 포함하면 Feasible)

---

KKT Condition(Karush-Kuhn-Tucker Condition)

Strong Duality의 문제(Slater's Condition 만족)에서는 아래의 명제를 만족합니다

$$
x^*\;and\; u^*,\;v^* are\;primal\;and\;dual\;solutions\\
\Leftrightarrow x^*\;and\;u^*\; v^*\;satisfy\;the\;KKT\;Condition
$$

• Stationarity 조건 
  • 최적점에서 원초 문제의 Gradient와 라그랑주 함수의 그래디언트의 합이 0이 되어야 한다는 것을 의미한다 
  • $\nabla L(x^*, u^*, v^*) = \nabla f(x^*) + \sum \limits_{i=1}^{m} {u_i}^* \nabla h_i(x^*) + \sum \limits_{j=1}^{r} {v_j}^* \nabla l_j(x^*) = 0$
• Complementary slackness 조건
  • 라그랑주 승수와 해당 제약 조건 간의 관계를 나타낸다
  • 각 제약조건 $h_i(x)$에 대해 라그랑주 승수 $u_i$가 0이거나, 해당 제약이 등식 제약이면 $u_i \gt 0$이어야 한다
  • 부등식 제약 $l_j(x)$에 대해 라그랑주 승수 $v_j$가 0이거나, 해당 부등식이 활성화 부등식이면 $v_j \gt 0$이어야 한다
  • ${u_i}^* \,\cdot\,h_i(x^*) = 0, \; for\;all\;i, \quad {v_j}^* \cdot l_j(x^*) = 0, \; for\;all\;j$