KKT 조건 (KKT Conditions)
쉽게 풀면
등식 제약만 있을 때 최적해를 찾는 방법이 라그랑주 승수법이라면, KKT(Karush-Kuhn-Tucker) 조건은 여기에 "이 값은 5 이하여야 한다" 같은 부등식 제약까지 추가된 상황으로 확장한 것입니다. 핵심 아이디어는 "제약이 실제로 딱 걸려서 작동 중인지(등호로 맞닿아 있는지), 아니면 여유가 있어서 사실상 없는 것과 마찬가지인지"를 구분하는 것입니다. 예를 들어 "예산은 100만원 이하"라는 제약이 있을 때, 실제로 100만원을 다 써야 최적이라면 그 제약이 "활성화"된 것이고, 80만원만 써도 최적이라면 그 제약은 "비활성화" 상태입니다. KKT 조건은 이런 활성/비활성 여부와 최적성 조건을 동시에 수식으로 표현한 것입니다.
왜 중요한가
현실의 최적화 문제는 대부분 "예산 이하", "용량 초과 금지"처럼 부등식 제약을 포함하기 때문에, KKT 조건은 이런 제약 최적화 문제를 실제로 풀고 그 해가 최적임을 증명하는 표준적인 도구로 쓰입니다. 서포트 벡터 머신 같은 머신러닝 모델의 학습 원리, 경제학의 자원 배분 문제, 제어공학의 최적 제어 설계 등 제약이 있는 의사결정 문제 전반에서 이론적 근거로 반복 등장합니다.
논문에서는 이렇게 쓰입니다
이 문장은 "이 문제가 볼록성을 가지고 있기 때문에, KKT 조건을 만족하는 점을 찾기만 하면 그것이 국소 최적해가 아니라 전체 문제에서 가장 좋은 해임을 보장할 수 있다"는 뜻입니다. 서포트 벡터 머신(SVM), 자원 배분, 제어 이론 논문에서 최적해의 성질을 증명할 때 핵심적으로 쓰입니다.
전력시스템 공학에서 최적화 문제의 라그랑주 승수가 자원의 한계가치(그림자 가격)로 해석되는 경우이다.
학습 기반 방법론의 결과를 전통적인 최적화 이론의 최적성 조건과 비교 검증한 예시이다.
조금 더 깊게 보면
KKT 조건은 정상성(목적함수와 제약의 기울기 관계), 원문제 실현가능성, 쌍대 실현가능성, 상보여유조건(complementary slackness)이라는 몇 가지 조건으로 구성됩니다. 이 중 상보여유조건이 바로 "제약이 활성화되었는지"를 수식으로 표현하는 부분으로, 활성화되지 않은 제약의 라그랑주 승수는 0이 되어야 한다는 뜻입니다. 또한 KKT 조건이 성립하려면 일반적으로 특정 제약자격조건(constraint qualification)이 만족되어야 하는데, 논문에서 이를 명시적으로 확인하지 않고 넘어가는 경우도 있어 엄밀한 해석에는 주의가 필요합니다.
주의할 점
KKT 조건은 일반적으로 최적해가 되기 위한 "필요조건"일 뿐이며, 문제가 볼록함수 형태가 아니라면 KKT 조건을 만족한다고 해서 반드시 전역 최적해라고 단정할 수 없습니다. 볼록 최적화 문제에서만 KKT 조건이 충분조건까지 겸하게 됩니다.