라그랑주 승수(Lagrange multiplier)

라그랑주 승수(Lagrange multiplier)는 최적화 문제를 해결하기 위한 방법으로, 주어진 제약 조건 하에서 목적 함수를 극대화하거나 극소화하는 데 사용됩니다.

주요 개념을 간단히 설명하면:

1. 목적 함수: $f(x, y, \dots)$와 같은, 극대화 또는 극소화하려는 함수입니다.
2. 제약 조건: $g(x, y, \dots) = 0$ 형태로 주어진 조건입니다.

기본 원리

라그랑주 승수 방법에서는 제약 조건을 만족하는 동시에 목적 함수를 최적화하기 위해, 다음의 라그랑주 함수 $\mathcal{L}$를 정의합니다:

$\mathcal{L}(x, y, \lambda) = f(x, y) + \lambda \cdot g(x, y)$

여기서:

• $\lambda$는 라그랑주 승수로, 제약 조건 $g(x, y) = 0$과 목적 함수 $f(x, y)$ 간의 관계를 나타냅니다.

해결 방법

1. 라그랑주 방정식 세우기

   $\mathcal{L}(x, y, \lambda) = f(x, y) + \lambda \cdot g(x, y)$
   

2. 편미분

   $\nabla \mathcal{L} = 0$
   각 변수에 대해 $\mathcal{L}$의 편미분을 계산하고 이를 0으로 설정합니다.

3. 연립 방정식 풀기
   위 식들로부터 $x$, $y$, $\lambda$ 값을 구합니다.

   ($\nabla$ 델, 또는 나블라 기호 : 벡터 미분 연산자로, 스칼라 함수에 적용하면 그라디언트(gradient)를 나타냅니다.)

예제

최적화 문제: $f(x, y) = x^2 + y^2$를 $x + y = 1$이라는 제약 조건 아래 최소화하세요.

1. 라그랑주 함수 정의:

   $\mathcal{L}(x, y, \lambda) = x^2 + y^2 + \lambda(x + y - 1)$

2. 편미분 및 방정식 세우기:

   $\frac{\partial \mathcal{L}}{\partial x} = 2x + \lambda = 0$

   $\frac{\partial \mathcal{L}}{\partial y} = 2y + \lambda = 0$

   $\frac{\partial \mathcal{L}}{\partial \lambda} = x + y - 1 = 0$

3. 연립 방정식 풀기:

   $2x + \lambda = 0 \quad \text{(1)}$

   $2y + \lambda = 0 \quad \text{(2)}$

   $x + y - 1 = 0 \quad \text{(3)}$

   $(1)$과 $(2)$를 이용해 $x = y$를 얻고, 이를 $(3)$에 대입하면 $x = y = 0.5$를 얻습니다.
   최적화된 값은 $f(0.5, 0.5) = 0.5$입니다.

---

라그랑주 듀얼 형식(Lagrange duality)

라그랑주 듀얼 형식(Lagrange duality)은 제약이 있는 최적화 문제를 푸는 데 중요한 개념으로, 원래의 최적화 문제(이를 프라이멀 문제라고 합니다)를 듀얼 문제로 변환하여 푸는 방법입니다. 이 접근법은 복잡한 제약 조건이 있는 문제를 보다 간단히 분석하거나 해결하는 데 유용합니다.

프라이멀 문제(Primal Problem)

제약 조건이 있는 최적화 문제는 다음과 같이 정의됩니다:

$\text{minimize } f(x) \quad \text{subject to } \begin{cases} g_i(x) \leq 0, & \text{for } i = 1, \dots, m \\ h_j(x) = 0, & \text{for } j = 1, \dots, p \end{cases}$

여기서:

• $f(x)$ : 목적 함수 (최소화하려는 함수)
• $g_i(x)$ : 불평등 제약 조건
• $h_j(x)$ : 평등 제약 조건

※ $\text{subject to }$ : 주어진 문제에서 특정 조건(제약 조건)을 만족해야 한다

---

라그랑주 함수

라그랑주 승수를 이용해 제약 조건을 포함한 라그랑주 함수를 정의합니다:

$\mathcal{L}(x, \lambda, \nu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \nu_j h_j(x)$

여기서:

• $g_i(x) \leq 0$ : 불평등 제약 조건
• $h_j(x) = 0$ : 평등 제약 조건
• $\lambda_i$ : 불평등 제약 조건의 라그랑주 승수
• $\lambda_i > 0$ : 불평등 제약 조건 활성화 ( $g_i(x) = 0$ )
• $\nu_j$: 평등 제약 조건의 라그랑주 승수

---

불평등 제약 조건 (Inequality Constraints)

정의

불평등 제약 조건은 함수의 값이 특정 한계(임계값) 이하로 제한되는 조건을 의미합니다.
일반적으로 다음과 같은 형태로 나타납니다:

$g_i(x) \leq 0 \quad$

• $g_i(x)$: 제약 조건을 정의하는 함수
• $x$: 최적화 변수 벡터

Complementary slackness (상보성 느슨 조건)

불평등 제약 조건 $g_i(x) \leq 0$에 대한 라그랑주 승수 $\lambda_i$는 다음을 만족합니다:

$\lambda_i \geq 0 \quad \text{and} \quad \lambda_i g_i(x) = 0$

즉:

• $\lambda_i > 0$인 경우, 제약 조건 $g_i(x) = 0$이 활성화되어 최적화에 영향을 미칩니다.
• $\lambda_i = 0$인 경우, 해당 제약 조건은 비활성 상태입니다.

예제

1. $-x^2 + 4x \leq 0$: 함수의 값이 0 이하로 제한됨.
2. $x \geq 0$: 변수 $x$가 0 이상이어야 함(비음수 조건).

---

평등 제약 조건 (Equality Constraints)

정의

평등 제약 조건은 함수의 값이 특정 값과 정확히 같아야 하는 조건을 의미합니다. 일반적으로 다음과 같은 형태로 나타납니다:

$h_j(x) = 0$

• $h_j(x)$: 평등 제약 조건을 정의하는 함수
• $x$: 최적화 변수 벡터

Dual feasibility (대칭성 허용 가능성)

라그랑주 승수 $\nu^*$는 음수일 수 없으며, $\lambda_i^* \geq 0$여야 합니다.

예제

1. $x + y - 1 = 0$ : $x + y$의 합이 1이어야 함.
2. $x^2 - y = 0$ : $x^2$이 $y$와 같아야 함.

---

KKT 조건

KKT 조건은 불평등 제약 조건과 평등 제약 조건을 모두 포함하는 최적화 문제에서 중요한 역할을 하며, 이를 만족하는 $x^*$와 $\lambda^*, \nu^*$가 최적해를 제공할 수 있습니다.

1. Stationarity (정지 조건)

라그랑주 함수에 대한 $x$의 그라디언트가 0이어야 합니다. 즉, 목적 함수와 제약 조건들이 균형을 이루는 지점이어야 합니다.

$\nabla_x \mathcal{L}(x^*, \lambda^*, \nu^*) = \nabla f(x^*) + \sum_{i=1}^m \lambda_i^* \nabla g_i(x^*) + \sum_{j=1}^p \nu_j^* \nabla h_j(x^*) = 0$

여기서 $\lambda_i^*$는 불평등 제약 조건에 대한 라그랑주 승수이고, $\nu_j^*$는 평등 제약 조건에 대한 라그랑주 승수입니다.

2. Primal feasibility (원문제 허용 가능성)

최적해 $x^*$는 원문제의 제약 조건을 만족해야 합니다:

$g_i(x^*) \leq 0 \quad \text{for all } i$

$h_j(x^*) = 0 \quad \text{for all } j$

즉, 불평등 제약 조건은 반드시 만족하고, 평등 제약 조건도 만족해야 합니다.

3. Dual feasibility (대칭성 허용 가능성)

라그랑주 승수 $\lambda_i^*$는 음수일 수 없으며, $\lambda_i^* \geq 0$여야 합니다.
$\lambda_i^* \geq 0 \quad \text{for all } i$

4. Complementary slackness (상보성 느슨 조건)

각 불평등 제약 조건과 그에 대응하는 라그랑주 승수 사이의 상보성 조건입니다:

$\lambda_i^* g_i(x^*) = 0 \quad \text{for all } i$

이 조건은 다음을 의미합니다:

• $g_i(x^*) < 0$일 경우 $\lambda_i^* = 0$ (해당 제약이 "활성화되지 않음")
• $g_i(x^*) = 0$일 경우 $\lambda_i^* \geq 0$ (해당 제약이 "활성화됨")

즉, 불평등 제약 조건이 활성화되었을 때만 라그랑주 승수가 양의 값을 가질 수 있으며, 비활성화되었을 때는 라그랑주 승수가 0이 됩니다.

불평등 제약 조건과 평등 제약 조건에 대한 KKT 조건 해석

• 불평등 제약 조건 $g_i(x) \leq 0$에 대해서는, KKT 조건에서 Complementary slackness가 매우 중요합니다. $g_i(x) < 0$이면 해당 라그랑주 승수 $\lambda_i^* = 0$이어야 하고, $g_i(x) = 0$이면 해당 라그랑주 승수 $\lambda_i^* \geq 0$이어야 합니다.
• 평등 제약 조건 $h_j(x) = 0$에 대해서는, 라그랑주 승수 $\nu_j^*$가 평등 제약을 유지해야 하므로, Dual feasibility 조건에서 음이 아닌 값을 가져야 합니다.

---

듀얼 함수

라그랑주 함수로부터 듀얼 함수를 정의합니다.

$q(\lambda, \nu) = \inf_x \mathcal{L}(x, \lambda, \nu)$

• 듀얼 함수 $q(\lambda, \nu)$는 주어진 $\lambda, \nu$에 대해 항상 $f(x)$보다 작거나 같습니다. 즉,

  $q(\lambda, \nu) \leq f(x) \quad \text{for all feasible } x$

  주어진 제약 조건을 모두 만족하는 $x$를 의미

• $\inf_x$는 "$x$에 대해 infimum (최솟값)을 구한다."는 의미입니다. 즉, 함수 $\mathcal{L}(x, \lambda, \nu)$에 대해 $x$를 변화시켜가며 가장 작은 값을 찾는 과정입니다.

• $\mathcal{L}$이 $x$에 대해 연속적이고, $x$의 범위가 제한적이라면 실제 최솟값이 존재할 수도 있습니다.
  

---

듀얼 문제

듀얼 문제는 듀얼 함수 $q(\lambda, \nu)$를 최대화하는 문제로 정의됩니다:

$\text{maximize } q(\lambda, \nu) \quad \text{subject to } \lambda \geq 0$

---

프라이멀-듀얼 관계

약한 이중성(Weak Duality)

항상 다음 관계가 성립합니다:

$q(\lambda, \nu) \leq f(x^*)$

즉, 듀얼 문제의 최적값은 항상 프라이멀 문제의 최적값보다 작거나 같습니다.

강한 이중성(Strong Duality)

어떤 조건(예: 슬레이터 조건)이 만족되면, 다음이 성립합니다:

$q(\lambda^*, \nu^*) = f(x^*)$

즉, 듀얼 문제와 프라이멀 문제의 최적값이 동일해집니다.

---

예제

문제

$\text{minimize } f(x) = x^2 \quad \text{subject to } x \geq 1$

프라이멀 문제

최적해 : $x^* = 1, \quad f(x^*) = 1$

라그랑주 함수

$\mathcal{L}(x, \lambda) = x^2 + \lambda (1 - x)$

듀얼 함수

$q(\lambda) = \inf_x \mathcal{L}(x, \lambda) = \inf_x \left( x^2 + \lambda (1 - x) \right)$

최소화 조건을 풀면:

$x = \frac{\lambda}{2}$

---

최소화 과정

1. 함수의 미분

먼저, $\mathcal{L}(x, \lambda)$를 $x$에 대해 미분하여 최소화 조건을 구합니다.

$\frac{d}{dx} \mathcal{L}(x, \lambda) = \frac{d}{dx} \left( x^2 + \lambda (1 - x) \right)$

미분 결과는:

$\frac{d}{dx} \left( x^2 \right) = 2x, \quad \frac{d}{dx} \left( \lambda (1 - x) \right) = -\lambda$

따라서:

$\frac{d}{dx} \mathcal{L}(x, \lambda) = 2x - \lambda$

2. 최소화 조건

이제 최소화를 위해 미분한 결과를 0으로 두고, $x$에 대한 해를 구합니다.

$2x - \lambda = 0$

이 식을 풀면:

$2x = \lambda \quad \Rightarrow \quad x = \frac{\lambda}{2}$

따라서 최소화 조건을 만족하는 $x$는 $x = \frac{\lambda}{2}$입니다.

---

$\mathcal{L}(x, \lambda) = x^2 + \lambda (1 - x)$

여기에 $x = \frac{\lambda}{2}$를 대입하면:

$\mathcal{L}\left( \frac{\lambda}{2}, \lambda \right) = \left( \frac{\lambda}{2} \right)^2 + \lambda \left( 1 - \frac{\lambda}{2} \right)$

이를 전개하면:
$= \frac{\lambda^2}{4} + \lambda \left( 1 - \frac{\lambda}{2} \right)$

$= \frac{\lambda^2}{4} + \lambda - \frac{\lambda^2}{2}$

$= \lambda - \frac{\lambda^2}{4}$

듀얼 함수 $q(\lambda)$ 계산

$q(\lambda) = \lambda - \frac{\lambda^2}{4}$

듀얼 함수의 최적화

이제 듀얼 함수 $q(\lambda) = \lambda - \frac{\lambda^2}{4}$를 최적화합니다.

이를 극대화하려면 $\frac{d}{d\lambda} q(\lambda) = 0$이 되는 $\lambda$를 찾습니다.

미분

$\frac{d}{d\lambda} q(\lambda) = 1 - \frac{\lambda}{2}$

이를 0으로 설정하면:

$1 - \frac{\lambda}{2} = 0$

$\lambda = 2$

4. 듀얼 최적화 값

따라서, $\lambda = 2$에서 듀얼 함수가 최적화됩니다. 이때 듀얼 함수 값은:

$q(2) = 2 - \frac{2^2}{4} = 2 - 1 = 1$

결론

따라서, 듀얼 함수에서 최적화된 값은 $q(2) = 1$이며, 이 값은 프라이멀 문제에서 최적값 $f(x^*) = 1$과 일치합니다.

---

라그랑주 듀얼 형식의 의미

라그랑주 듀얼 형식은 다음과 같은 이점을 제공합니다:

1. 문제 단순화: 프라이멀 문제가 복잡한 형태라면, 듀얼 문제는 더 간단한 형태로 나타날 수 있습니다.
2. 최적화 효율성: 듀얼 문제를 풀어 프라이멀 문제의 해를 구할 수 있습니다.
3. 제약 조건의 해석: 라그랑주 승수 $\lambda, \nu$는 제약 조건의 민감도를 나타내어, 제약 조건이 목적 함수에 미치는 영향을 분석할 수 있습니다.
4. 강한 이중성을 통한 검증: 듀얼 문제의 최적값을 통해 프라이멀 문제 해의 최적성을 검증할 수 있습니다.