KKT condition

KKT condition 이란?

목적함수를 최적화하는데

부등식 제약조건을 만족시켜야 하는 경우

반드시 성립해야 하는 몇 가지 조건들이 존재하는데..

그 조건들을 kkt 조건이라 한다

 

이 조건들이 왜 필요한가?

 

svm(support vector machine)에서 목적함수를 최적화하는 과정에

부등식 제약조건이 발생한다.

그때의 최적화 문제를 풀기 위한 수학적 방법

 

f(x)를 최적화하는데

 

다음과 같은 제약조건이 있다고 하자

즉 부등식 제약조건과 방정식 제약조건이 같이 있는 상황

 

이렇게 제약조건이 주어진 함수는 최적화 함수를 아래와 같이 표현하고

 

원래의 f(x)를 최적화하는 문제를

L(x,µ,λ) 함수가 최적이 되는 파라미터 x,µ,λ 를 찾는 문제로 바꿔서 풀 수 있다..

즉 목적은 L(x,µ,λ) 함수를 최적화하는 것

 

---

 

그래서 kkt 조건에는 뭐가 있나

 

1. 최적화 함수의 대상함수인 L(x,µ,λ) 를 미분해서 그때의 최적의 파라미터를 넣으면 0이 나와야 한다.

즉 최적의 point에서는 미분 값이 0이어야 한다는 단순 라그랑주 계산

 

2. x는 기존의 제약조건을 만족시키는 값이어야 한다는 것 너무 당연하다.

 

3. 다음과 같은 조건이 있는데 이건 dual form을 이해해야..

 

 

---

 

dual form 이란?

 

 

어떠한 최적화 문제도 primal problem이 있으면 그에 대한 dual form이 존재한다.

원래의 문제가 최대화 문제라면 그에 대응되는 최소화 문제가 존재한다는 뜻

 

앞서 정의한 함수에서  x변수만을 고려해 함수의 최소를 구한다고 해보자.

x만 고려한 최소화

 

그러면 아래와 같은 부등식을 만족할 것이다.

다른 제약조건을 고려하지 않고 x만 조절하여 최소화하였으니

그 값은 찾아야 할 실제 최솟값 보다 더 작을 것이다.

 

이제 x에 대해 최소화 한 함수의 변수는 µ,λ 만 존재하므로

아래와 같이 표현할 수 있으며 이 함수를 dual form이라 한다.

µ,λ 변수를 조절하여 이 함수를 최대화하는 것이 primal 함수를 최소화하는 것.

 

이제 나머지 kkt 조건 유도

 

최적의 파라미터 𝑥 ∗ , 𝜇 ∗ , 𝜆 ∗를 찾았다고 가정해 보자.

앞서 본 부등식에 최적의 파리미터를 대입하면

 

위의 부등식은 등호가 성립할 것이다. (최적의 파라미터이므로)

이때 우측 함수를 원래의 표현방식으로 돌리면 아래와 같고

 

등호가 성립하므로 다음을 만족한다.

 

처음의 부등식 제약조건은 아래와 같았다.

 

이때 아래 식의 최댓값이 0인걸 방금 전 확인, 즉 𝜇 >= 0 를 만족해야 한다.

(어떤 함수의 최댓값이 0이라면 가질 수 있는 범위는 음수여야 하고 여기서는 원래 제약조건이 음수이므로 앞에 곱해진 𝜇는 양수여야 한다)

 

 

그래서 나머지 kkt 조건도 만족해야 한다.