이 단원 목차
계획과 별도로 검사할 수 있는 하한
출발·도착 주변 질량을 고정한 비음수 coupling은 선형계획의 가능집합이다. 쌍대는 출발 potential uᵢ와 도착 potential vⱼ를 둔다.
Potential은 음수여도 된다. 총질량이 같을 때 u에 상수를 더하고 v에서 빼도 부등식과 목적값은 같다. 실습은 u₀=0인 gauge를 사용한다.
주변 질량으로 약쌍대성 유도
계획과 potential이 모두 가능하면
각 항이 질량과 비음수 slack의 곱이다. 최적 쌍의 양의 흐름은 tight edge만 사용한다. 반대로 질량 0인 간선이 반드시 양의 slack을 갖는 것은 아니다. 사용하지 않는 tight edge도 가능하다.
인증 gap은 실제 최솟값을 몰라도 현재 원문제 오차를 위에서 잡는다. 여기서는 정확한 최적값도 계산하여 인증과 실제 오차를 비교한다.
완전한 원·쌍대 쌍 손계산
출발 (0,1), 도착 (0,L)의 제곱 비용은 [[0,L²],[1,(L−1)²]]다. a≤b이면 u=(0,1),v=(0,L²−2L), a>b이면 u=(0,1−2L),v=(0,L²)가 최적 선택이다. 단조 계획의 양의 간선이 tight하다.
a=0.4,b=0.6,L=2에서는 계획 [[0.4,0],[0.2,0.4]], potential u=(0,1),v=(0,0)다. 쌍대값 0.6이 비용과 같고, 사용하지 않는 0→L 간선 slack은 4다.
Potential을 바꾸기 전에 가능성 검사
δ는 v₁에 더하는 값이다. 음수 δ는 부등식을 보존하지만 쌍대값을 |δ|(1−b) 낮춘다. δ=−1이면 하한 0.2, gap 0.4다. 계획이 이미 최적이어도 승수가 부정확하면 gap이 남는다.
양수 δ는 tight 부등식을 어긴다. δ=1이면 대수적 primal-minus-dual은 −0.4다. 쌍대 불가능성이 원인이므로 약쌍대성의 반례가 아니다. 화면은 부호 있는 값을 남기되 인증 상한은 제공하지 않는다.
직접 풀기와 수치 해석
δ=0에서 계획 혼합을 최적 끝점에서 멀리 옮기자. 가중 slack 합과 비용 증가가 같은지 확인한다. 이어 v₁을 낮추어 원문제 오차와 쌍대 하한의 느슨함을 구별하자.
구현은 거의 같은 목적값의 차감 대신 상보성 항을 직접 계산하고 원래 차감도 함께 표시한다. 큰 해결기에서도 주변 잔차와 모든 potential 부등식을 검사해야 한다. 불가능 계획의 낮은 비용을 원문제 상한으로 사용하면 안 된다.
더 읽기: Peyré와 Cuturi의 최적수송 교재.
설명할 수 있나요?
실험 설정과 무관한 기준 예제를 묻습니다. 답을 고르고 설명을 확인해보세요.
선택한 답과 학습 표시는 이 브라우저에 저장됩니다. 다시 풀거나 표시를 해제할 수 있습니다.