Optimaization/ Karush-Kuhn-Tucker, KKT 카루시-쿤-터커 조건

목차

 

개요

이번 포스트에서는 부등식 제약조건이 주어졌을때 만족해야하는 Karush-Kuhn-Tucker, KKT 카루시-쿤-터커 조건에 대해서 알아본다.

 

본 포스팅은 하단의 글을 통해 개념을 숙지하고 와야지 쉽게 이해가 가능하다.

라그랑지언 승수법을 확장한 개념이기에 해당 포스팅과 등식, 부등식 제약 조건에 대해서 쓴 포스팅 두가지를 읽고 오는것을 추천한다.

Optimaization/ Lagrange multiplier 라그랑지안 승수법

 

Concept/ Unconstrained, constrained optimization 비구속/ 구속 제약 최적화

 

 

---

개념과 조건

 

부등식 제약 조건이 있는 최적화 문제를 해결하는 데 사용되는 방법

 

개요에서도 말했다싶이 KKT 조건은 라그랑지안 승수 방법을 부등식 제약 조건에 적용,확장한 것으로 볼 수 있다. KKT 조건은 솔루션이 최적점이라면 만족해야 하는 일련의 조건들의 나열이다.

 

 

• KKT1

모든 변수는 feasible한 도메인 내에 있어야 한다.

 

 

• KKT2 (Primal feasibility)

등식 제약 조건: gi(x) = 0 (i = 1, ..., m)

부등식 제약 조건: hj(x) <= 0 (j = 1, ..., n)

 

 

• KKT3 (Dual Feasibility)

모든 라그랑주 승수는 음수가 아니어야 한다.

μj >= 0 (j = 1, ..., n)

 

 

• KKT4 (Complementary Slackness ;라그랑주 승수-제약 조건 상호작용 조건)

각 라그랑주 승수와 불등식 제약 조건의 곱이 0이어야 한다. 이 조건을 통해 활성화 된 제약 조건에 대해서만 라그랑주 승수가 영향을 미친다.

 

μj * hj(x) = 0 (j = 1, ..., n)

 

 

• KKT5 (Stationarity Condition; 그래디언트 조건)

목적함수와 라그랑주 승수를 고려한 그래디언트의 합이 0이어야 한다.

∇f(x) + ∑(λi * ∇gi(x)) + ∑(μj * ∇hj(x)) = 0

 

 

---

 

예시

 

목적함수: minimize f(x, y) = x^2 + y^2
제약 조건: x + y <= 2

 

위 문제에서 KKT 조건을 적용하면

 

• KKT1

모든 변수는 feasible한 도메인 내에 있어야 한다.

x, y는 실수 공간에 있으므로 이 조건은 만족

 

• KKT2 (Primal feasibility)

등식 제약 조건: gi(x) = 0 (i = 1, ..., m)

부등식 제약 조건: hj(x) <= 0 (j = 1, ..., n)

 x + y <= 2

 

• KKT3 (Dual Feasibility)

모든 라그랑주 승수는 음수가 아니어야 한다.

μj >= 0 (j = 1, ..., n)

일단 0보다 크거나 작다고 가정한다 μ >= 0

 

• KKT4 (Complementary Slackness ;라그랑주 승수-제약 조건 상호작용 조건)

각 라그랑주 승수와 불등식 제약 조건의 곱이 0이어야 한다. 이 조건을 통해 활성화 된 제약 조건에 대해서만 라그랑주 승수가 영향을 미친다.

μ(x + y - 2) = 0

 

• KKT5 (Stationarity Condition; 그래디언트 조건)

목적함수와 라그랑주 승수를 고려한 그래디언트의 합이 0이어야 한다.

∇f(x) + ∑(λi * ∇gi(x)) + ∑(μj * ∇hj(x)) = 0

∇f(x, y) = (2x, 2y)
∇h(x, y) = (1, 1)
(2x, 2y) + μ(1, 1) = (0, 0)

 

최종 도출

x + y <= 2
μ >= 0
μ(x + y - 2) = 0
2x + μ = 0
2y + μ = 0

μ > 0 인 경우 (제약 조건이 활성화되어 있음)
이 경우, x + y = 2

2x + μ = 0,  2y + μ = 0을 x,y로 전개하면

x = -(μ / 2)
y = -(μ / 2)

x + y = 2에서 μ 값을 구할 수 있다:

-(μ / 2) - (μ / 2) = 2
μ = -4
μ 값이 음수이므로, 이 경우는 KKT 조건을 만족하지 않는다.

μ = 0 인 경우 (제약 조건이 비활성화되어 있음)
이 경우, 2x + μ = 0 , 2y + μ = 0에서

x = 0
y = 0

x + y <= 2 제약 조건을 만족하므로, 이 경우는 KKT 조건을 만족

부등식 제약 조건이 비활성화된 경우, μ = 0이므로 

2x = 0
2y = 0

이 경우 x = 0, y = 0이 최적해가 되고 이때 모든 KKT 조건이 만족하므로 최적해가 올바르게 찾아졌다고 볼 수 있다.

 

결론적으로 이 예제에서 최소화되는 f(x, y)의 값은 0이며, 최적점은 (0, 0)이다.
 

 

 

마무리

따라서 이렇게 KKT를 이용해서 부등식 제약 조건을 갖는 문제에서 간단한 식들로 최적해를 구해내는 방식을 알아보았다.

 

라그랑지언 승수법과 별개의 문제가 아니라 라그랑지언 승수법을 적용하면서 부등식 제약조건의 추가로 인해서 KKT 조건또한 추가적으로 확인한다는 방식으로 이해해보자