쌍대성이론 (Duality Theory)
쉽게 풀면
어떤 최적화 문제를 "얼마나 이익을 최대화할 수 있는가"로 볼 수도 있지만, 같은 문제를 뒤집어 "자원 하나를 추가로 얻으면 이익이 얼마나 늘어나는가"라는 관점에서도 볼 수 있습니다. 쌍대성이론은 이 두 관점이 사실은 같은 문제를 다른 방식으로 표현한 것이며, 서로 긴밀하게 연결되어 있다는 것을 설명합니다. 원래 문제를 주문제, 뒤집은 문제를 쌍대문제라고 부릅니다. 이 둘을 함께 보면 원래 문제만으로는 알기 어려운 정보를 얻을 수 있습니다. 쌍대성이론은 하나의 최적화 문제(원문제)에 대응하는 또 다른 최적화 문제(쌍대문제)를 만들어, 두 문제의 해가 어떤 관계를 갖는지를 밝히는 이론입니다.
왜 중요한가
쌍대성이론은 자원의 한계가치(그림자가격)를 계산할 수 있게 해주어, 어떤 자원을 늘리는 것이 가장 이익이 되는지 같은 경영 의사결정에 직접적인 통찰을 제공합니다. 또한 최적해 검증이나 알고리즘 설계에서도 이론적 기반으로 폭넓게 활용됩니다. 쌍대문제의 해는 원문제 제약조건 하나하나의 경제적 가치, 즉 잠재가격을 알려주기 때문에 자원의 한계가치를 해석하는 실무적 도구로 널리 활용됩니다.
논문에서는 이렇게 쓰입니다
제약을 하나 완화했을 때 목적함수가 얼마나 개선되는지를 쌍대이론을 통해 계산했다는 의미입니다.
일정 조건 아래에서 주문제와 쌍대문제의 최적값이 동일하다는 성질을 활용해 결과를 검증했다는 뜻입니다.
조금 더 깊게 보면
쌍대성에는 주문제의 목적값이 쌍대문제의 목적값보다 항상 작거나 같다는 약쌍대성(weak duality)과, 특정 조건 하에서 두 값이 정확히 일치하는 강쌍대성이 있습니다. 선형계획법에서는 일반적으로 강쌍대성이 성립하는 것으로 알려져 있으며, 이는 최적해를 검증하는 유용한 도구로 쓰입니다. 약쌍대성 정리는 쌍대문제의 목적함수 값이 원문제의 목적함수 값의 한계를 이룬다는 것을 보장하며, 강쌍대성 정리는 최적해에서는 두 값이 정확히 일치함을 보여 최적성 검증 수단으로 활용됩니다.
주의할 점
비선형계획법이나 정수계획법에서는 강쌍대성이 항상 성립하지는 않으며, 이 경우 주문제와 쌍대문제의 최적값 사이에 차이(duality gap)가 존재할 수 있습니다.