Lagrange Multiplier and KKT Condition(Kuhn-Tucker)

 

Lagrange Multiplier (라그랑주 승수)와 KKT Condition (Kuhn-Tucker 조건)

Lagrange Multiplier와 KKT Condition은 최적화 문제를 풀 때, 특히 제약 조건이 있는 최적화 문제에서 중요한 수학적 도구들이다. 이들은 주어진 제약 조건 하에서 최적화 문제를 해결하는 데 사용된다.

 

1. Lagrange Multiplier (라그랑주 승수)

라그랑주 승수는 제약 조건을 가진 최적화 문제를 해결할 때 사용되는 기법이다.

🧑‍🏫 기본 개념

최적화 문제를 해결할 때, 목표 함수 f(x)와 제약 조건 g(x)=0이 있을 때, 라그랑주 승수는 목표 함수와 제약 조건을 결합하여 새로운 라그랑주 함수(Lagrangian function)를 만든다. 이를 통해 최적화 문제를 제약이 없는 형태로 바꿀 수 있다.

📏 수학적 정의

1. 목표 함수: f(x)
2. 제약 조건: g(x) = 0

라그랑주 함수 L는 다음과 같이 정의된다:

여기서 λ는 라그랑주 승수(Lagrange Multiplier)이다. 이 승수는 제약 조건이 목표 함수에 미치는 영향을 나타낸다.

 

✅ 라그랑주 승수 문제 풀이 단계

1. 라그랑주 함수 L(x,λ)를 미분하여 최적화 조건을 찾는다.
2. 제약 조건 g(x) = 0을 만족하는 해를 구한다.

이를 통해 주어진 제약 조건 하에서 최적화 해를 구할 수 있다.

 

📐 2. KKT Condition (Kuhn-Tucker 조건)

KKT 조건은 라그랑주 승수법을 제약 조건이 부등식인 경우에 적용한 확장이다. 즉, 등식 제약뿐만 아니라 부등식 제약도 고려하는 최적화 문제에 대한 조건이다.

KKT 조건은 비선형 최적화 문제에서 최적성 조건을 제공한다. 부등식 제약이 있을 경우, KKT 조건은 최적해를 찾기 위해 필요한 충족해야 하는 조건들을 명시한다.

📏 KKT 조건의 주요 요소

1. 목표 함수: f(x)
2. 등식 제약 조건: h_i(x)=0,  i=1,2,...,m
3. 부등식 제약 조건: g_j(x) ≤ 0,  j=1,2,...,p

✅ KKT 조건

1. 라그랑주 함수 작성 (Lagrangian)

 

여기서 λi​와 μj는 각각 등식 제약과 부등식 제약에 대한 라그랑주 승수이다.

 

2. 1차 조건 (Stationarity Condition)

 

라그랑주 함수의 각 변수에 대해 미분한 후, 이를 0으로 설정하여 최적화 조건을 구한다.

 

3. Primal feasibility (주어진 제약 조건 만족)

 

• 등식 제약: h_i(x) = 0
• 부등식 제약: g_j(x) ≤ 0

4. Dual feasibility (라그랑주 승수 조건)

부등식 제약에 대한 라그랑주 승수는 항상 양수이어야 한다.

 

5. Complementary Slackness (상호 보완성 조건)

부등식 제약을 만족할 때, 그 제약의 라그랑주 승수와 제약 함수의 곱은 0이어야 한다.