쌍대 이론 (Duality Theory) 나만의 언어로 정리

SVM 서벡머를 저번에 정리했는데 쌍대문제와 아주 비슷해보였다.
제약조건이 존재하고, 이를 반대로 이용해서 Max margin 문제를 벡터를 가변으로, margin을 2/||w|| 로 고정해서 푸는 형태가 비슷해보였다.

쌍대이론 나의 언어로 정리

• Primal Problem(원본문제)에 대응하는 Dual Problem always exist. 이는 Constraints가 많을 때 유용함. Primal Problem에 제약조건이 많을 때 Dual Problem으로 변환해서 해를 구하면 제약조건 g(x)들이 변수로 바뀌며 풀기 쉬워짐.
• Primal Problem에서 Dual Problem Conversion by Langurange Multiplier. 제약조건이 원의 영역으로 전재하고, 목적함수가 선으로 존재한다 가정하면 목적함수 x, y의 조합으로 나온 값을 K라고 하면 K의 최댓값은 선과 원이 접할 때 선의 y절편이 최대가 됨.
• 이 때, 접하는 지점을 Gradient Vectors(구배벡터)로 찾을 수 있음.
• 구배벡터는 해당 지점에서 모든 변수에 대해 편미분한, 즉 Gradient를 모은 Vector.
• 목적함수와 제약함수의 구배벡터가 평행하면 최적의 지점을 찾을 수 있음. 즉, 좌변에 함수 L, 우변에 f(x)와 g(x)가 같이 있는 Dual Problem이 된다.

심화

• 하지만 Dual Problem으로 찾은 값이 최적값의 하한인지, 정말 최적값인지는 모름!
• 왜냐하면 Lagrange Condition은 필요조건이지 충분조건이 아니기 때문이다.
• 이는 강한 쌍대성과 약한 쌍대성으로 연결된다. 강한 쌍대성은 Dual Problem과 Primal Problem의 해가 일치할 때이고, 약한 상대성은 Dual의 해가 Primal해의 하한선이라는 보편적인 관계이다. 둘을 구분하기 위해서는 이계도 함수로 볼록성을 보는 것처럼 local optimum/ Global Optimum을 판별하는 작업이 필요합니다.