Duality Thorey

이 글은 Duality Problem에 대해 간단히 정리한 글입니다.

Duality Theroy

우리는 선형계획에서 optimum(최적값)을 찾기를 원합니다. 또, 만약 최적값을 찾게 되었다면 그에 대한 검증이 필요합니다.

어떤 최적값에 대한 검증에는 하한, 상한으로 검증하게 됩니다. 이 방법이 Dual, 쌍대 문제입니다.

예를 들어서, 밑과 같은 선형문제가 있다고 생각해봅시다.

이 문제에서 각 등식에 y1, y2와 같은 변수를 곱해서 목적식과 비슷하게 만들어주면 간단히 상한을 구할 수 있습니다.(해보시길..)

쌍대 문제로 바꾸게 되면 다음 그림처럼 바뀌게 됩니다.

왜 이런 그림이 나오는지는 다음 그림으로 설명되어질 수 있습니다.

상한을 구하는게 목적인 것을 생각해보면 제약식이 왜 저런 형태를 띄고 있는지를 알 수 있으며, 목적식 또한 그 의미를 알 수 있을 것입니다.

Primal(원문제) 가 최대식이라면 Dual 은 최소로 바뀌게 됩니다. 반대로 Primal이 최소식이라면 Dual은 최대로 바뀌게됩니다.

또한, 하한을 구하기위해 몇 번의 곱셈을 하다보면 Dual의 Dual은 Primal이라는 것을 알 수 있습니다.

즉, 위의 그림과 같이 쌍대문제로 전환하여 W를 구하게 되면 원문제 Z의 상한이 된다는 의미입니다.

Duality Problems : Primal <-> Dual

쌍대 문제에서는 3가지 속성이 존재합니다.

1. 약쌍대성

- > 만약 최대화 문제일 때, 쌍대문제를 통해 값을 도출하였다면 이 값은 원문제의 최적해에 대해 상한이 됩니다.

2. 강쌍대성

-> 쌍대 문제에서의 최소 상한값이 원 문제에서의 optimum값과 같다는 정의입니다.

3. 상보여유정리

상보여유정리는 쉽게 말씀드리자면 다음과 같습니다. 만약 쌍대변수의 값 (그림에서 y1, y2, y3, y4를 의미)이 0이 아닌 경우, 원 문제의 제약식은 등식을 만족해야 합니다.

-> 그림에서 y1, y2가 0이 아닌 양수임을 볼 수 있습니다. 이 의미는 원문제에서 1, 2번째 제약식이 등식을 만족한다는 뜻입니다.(직접 x1, x2의 값을 넣어보십시오). 또한 3, 4번째는 상대변수의 값이 0이 되므로 원문제에서 3, 4번째 제약식은 등식이 성립하지 않습니다.

감사합니다.

Reference

KMOOC