10 Duality in Linear Programs

이번 장에서부터는 최적화 이론에서 큰 비중을 차지하는 duality에 대해서 살펴본다. 최적화 관점에서 duality를 간단히 말하자면, 하나의 최적화 문제를 primal problem과 dual problem 두 가지 시각으로 볼 수 있다는 개념이다.

이 장에서는 특히 linear program에 대한 duality를 알아본다. 일반적인 convex 문제에 바로 적용하기보다는 linear program에 적용함으로써 primal problem에서 dual problem을 유도하고, 이 둘의 관계가 어떻게 이루어지는지, 또한 특정한 조건 하에 어떤 성질을 가지는지 정리해보고자 한다.