(선형대수학) 부록 2-3. Example of Dual Problem
다시 16-1의 Optimization Problem으로 돌아와서 문제를 살펴보자!
이번에는 다른 예시를 하나 더 살펴보자.
(문제)
시험을 보기 위해서 인강을 보자!
A 인강을 한번 보는데 10000원을 내고, 성적이 10점 오른다.
B 인강을 한번 보는데 4000원을 내고 , 성적이 2점 오른다.
현재 시험을 보면 0점이라고 하자.
100점을 맞기 위해서 비용을 최소로 하고 싶을 떄, 비용은 얼마나 들까???
당연히 A 인강만 보는 것이 가장 싸게 먹히겠지만(즉, A만 10번 보고 10만원 지출!), 이를 최적화 문제로 살펴보자.
x: A 인강을 보는 횟수, y: B 인강을 보는 횟수
1. 조건:
2. Cost(시간(분)):
선형대수학 파트이니 저 조건과 Cost를 행렬표현으로 심플하게 써보도록 하자.
그런데, 저 부등호의 방향도 서로 다르니 문제가 되고, 어떻게 써야할지 감이 안잡힐 수도 있다.
=> 그러면, 그냥 변수를 추가해서 저 조건을 바꾸어보자!!!
=> 이렇게 추가된 변수를 Slack Variable이라고 한다.
이렇게 변수를 추가하면 Optimization 문제를 다음과 같이 바꿔버릴 수 있다.
(여기서 벡터의 부등식은 각 성분마다 x>=0, y>=0, w>=0으로 해석하면 된다.)
이를 조금 더 일반화 한다면(조건에 등식도 포함이 된다면) 다음처럼 쓸 수 있다.
(Primal Problem)
그런데, 상황에 따라서는 이렇게 직관적으로 문제를 정의하면 저 조건들의 영역이 깔끔하게 떨어지지 않을 수도 있다.
예를 들어서 우리 문제의 조건에 부등식이 4개가 더 붙었다고 하자. 그러면, Primal Problem에서 Slack Variables의 개수가 최대 4개 더 늘어날 수도 있는 것이다...
이렇게 차원이 늘어나게 되면, 저 문제를 풀 때, 계산시간도 늘어나고 영역을 고려할 때 꽤나 복잡해질 것이다.
Dual Problem은 이 복잡성을 줄여줄 수도 있다...(물론, 언제나 해결해주지는 않는다.)
Dual Problem을 이해하기 위해서 다시 우리의 문제로 돌아가보자.
(문제)
시험을 보기 위해서 인강을 보자!
A 인강을 한번 보는데 10000원을 내고, 성적이 10점 오른다.
B 인강을 한번 보는데 4000원을 내고 , 성적이 2점 오른다.
현재 시험을 보면 0점이라고 하자.
100점을 맞기 위해서 비용을 최소로 하고 싶을 떄, 각 인강을 몇 번씩 보면 될까??
=> 이 문제를 "신생 인강 업체" 입장에서 생각해보자.
신생 인강 업체 C에서 인강을 한번 보는데는 p원이 들고, 성적이 "1점" 오른다고 하자.
C 업체는 A, B와의 경쟁에서 이기기 위해서 가격 p를 결정해야 한다.
C 업체 입장에서는 수익이 최대가 되는 것을 원하므로, Cost Function은 p가 되고, 이를 "최대화"하고 싶다.
그런데, 한 학생이 C만 이용해서 100점을 맞기 위해서는 C 업체에 100p를 내야 한다. 그러므로 Cost Function을 다음과 같이 잡아도 된다.
1. Cost
또한, A,B 업체와의 경쟁에서 이겨야 하기 때문에 A,B보다 더 좋은 조건을 가져야 한다.
2-1. A와의 경쟁
A 인강의 경우 1점에 1000원으로 생각할 수 있으므로, p<=1000이어야 A 대신 C를 이용할 것이다.
2-2. B와의 경쟁
B 인강의 경우 1점에 2000원으로 생각할 수 있으므로, p<=2000이어야 B 대신 C를 이용할 것이다.
2-3. 기본 조건
p는 당연히 0보다 커야 한다.
정리해보면 C 업체 입장에서는 다음과 같은 최적화 문제를 푸는 것과 같다.
(사실 100p나 p나 같은 말이지만, "성적 단위 가격"으로 생각했다.)
=> 결국에 (학생이 "최소" 비용을 내고 인강을 보는 문제)와 (신생 C 업체가 "최대" 비용을 얻으려는 문제) 는 동일하다!!
=> 앞의 문제를 Primal Problem이라고 하면, 뒤의 문제는 Dual Problem이라고 한다.
즉, 항상 최소화 문제를 <-> 최대화 문제로 바꿀 수 있고 이러한 관계를 Duality라고 한다.
그럼 Dual Problem을 풀어보면... -> 조건에서 0<=p<=1000만 남으므로, 결국 Maximize 100p => Cost: 10만원!!
=> Primal Problem의 결과와 동일하다!!!
여기서 한가지 눈여겨보아야 할 것은 "문제의 복잡성"이다.
우리의 예시에서 Primal Problem은 Slack Variable이 등장하므로 변수 개수가 크게 늘어났다..... -> 복잡!
그러나, Dual Problem에서는 변수가 p 하나 뿐이다!!! -> 간단!!!
(NOTE1)
항상 Dual Problem이 간단한 것은 아니다!! -> Primal Problem이 오히려 간단할 수도!
=> 그냥 Primal Problem과 Dual Problem이 동일한 문제라고 생각하면 된다! => 어떻게 쓰냐에 따라서 쉬울수도, 어려울수도....
(NOTE2)
결국 MINIMIZE 문제는 MAXIMIZE하는 문제와 동일하다는 것을 알 수 있다... -> 사실 직관적으로 알아차릴 수도 있지만, "영역"이라는 문제가 끼어들어가기 때문에 Cost Function에 마이너스만 붙이는 식으로 생각하면 안된다!!
(NOTE3)
Primal Problem에서 x,y -> Dual Problem에서 p => 새로운 업체를 불러들였기 때문에, x,y와 p는 서로 "연관"되어 있지 않다. 즉, (x,y)와 p는 서로 "독립적인 차원"에서 정의되었다고 생각할 수 있다...
다음 시간에는 조금 더 이론적으로 Dual Problem에 대한 내용을 들어가보자