11-5 Duality gap

Primal 문제가 \(x\)에서 \(f(x)\)의 값를 갖고, dual 문제는 \(u,v\)에서 \(g(u,v)\)의 값을 갖는다고 할 때, 두 값의 차이 \(f(x) - g(u,v)\)를 duality gap이라 한다.

한편, 위 feasible한 값들은 다음의 관계를 항상 만족하므로

\[\begin{equation} f(x) - f^* \leq f(x) - g(u,v), \end{equation}\]

duality gap이 \(0\)이 되면, \(x\)는 primal 문제의 최적 해가 되고, \(u,v\)는 dual 문제의 최적 해가 된다.

또한, Duality gap이 \(f(x)-g(u,v) \leq \epsilon\) 이면, \(f(x) -f^* \leq \epsilon\) 인 것을 의미하므로,

iterative 방식으로 문제를 푸는 알고리즘에서, duality gap을 stopping 판별 조건으로 사용 할 수도 있게 된다.