이번에는 Convex Quadratic Programming(CQP)에 대해서 다뤄보려고 한다. CQP란 2차 다항식의 목적함수에 선형 제약조건을 갖는 최적화 문제를 말한다. 먼저 어떻게 생긴 문제인지 살펴보도록 하자. 모든 등식은 부등식 두 개, 예를 들어 을 와 ,로 쪼갤 수 있으므로 부등식 제약조건만을 가진  CQP에 대해서 다루도록 하겠다. 꼭 두개로 쪼개지 않더라도 제약조건을 표현하는 행렬의 Nullspace를 이용해서 부등식에 껴 넣을 수 있다.

표준형은 다음과 같다.

여기서 는 의 행렬이고 , , 의 벡터들이다.

이렇게 표현해 놓으니까 뭔지 잘 와닿지 않을 것 같다. 좀더 쉬운 예를 들어보도록 하겠다. 다음과 같은 문제를 한번 보자.

이 문제를 한번 초딩처럼 모눈종이에 그려봐? ^^

퍼런 부분이 제약 조건 네개로 이루어진 영역이고 동그라미 들은 목적함수의 등고선(contour)이다. 감좀 잡았나?  이거 고등학교 3학년(?) 때 하던 선형 계획의 확장 판이다. ^^ 수능에 자주 등장하는 그 문제.

그럼 이 문제를 어떻게 풀 것인가? 어떻게 푸는지 파해쳐 주려고 쓰는 것 아닌가? 우선 원래 문제의 Lagrangian을 구한다. 다음과 같다.

해가 있는 곳은 다음과 같다.

1. Lagrangian의 Gradient가 이 되는 곳, (이면서)

2. 제약조건과 의 Complementarity가 성립되는 곳, 즉 for , , , and .

즉, 다음이 성립되는 곳에 해가 있다.

이를 KKT (Karush-Kuhn-Tucker) 조건이라 한다. 여기서 는 사실상 를 등호 조건으로 변경하기 위해 도입한 변수라 slack 변수라 부른다.

KKT condition의 Geometry 해석은 다음 그림과 같다.

(그림)

이 KKT 조건 문제를 해결하면 최적화 문제이 답을 찾게 되는데 원래 문제의 답만 찾는게 아니라 다음과 같은 Dual 문제의 답도 찾게 된다.