Duality Gap과 최적성 인증

모르는 최솟값을 위아래에서 감싸기

최적화 알고리즘은 점을 출력해도 정확한 최솟값을 모를 수 있다. 쌍대성은 따로 검산할 수 있는 하한을 준다. x가 원문제 가능점이고 λ가 쌍대 가능점이면 d(λ)≤p*≤f(x)다. 따라서 계산 가능한 f(x)−d(λ)가 모르는 목적 오차 f(x)−p*의 상한이 된다.

이 인증 간극과 최적값 사이의 쌍대 간극 p*−d*는 다르다. 강쌍대성이 성립하는 문제에서도 현재 점과 승수가 좋지 않으면 인증 간극이 크다. 실습에서는 정확한 최적해도 구할 수 있는 작은 이차 문제를 사용해 두 개념을 비교한다.

잔차로 분해하는 항등식

f(x)=(x−a)²/2, 제약 x≤b를 생각하자. 쌍대함수는 d(λ)=λ(a−b)−λ²/2이고 가능 승수는 λ≥0이다. 완전제곱으로 정리하면

첫 항은 정상성 잔차 제곱의 절반, 둘째 항은 승수와 slack의 곱이다. 가능 쌍에서는 두 항 모두 비음수다. 점들을 많이 그리지 않고도 이 문제족의 약쌍대성을 증명한다.

항등식 자체는 가능영역 밖에서도 맞지만 각 항의 비음수성은 그렇지 않다. 화면은 대수적 간극과 두 가능성 표시를 분리하고, 어느 하나라도 실패하면 인증 간극을 제공하지 않는다. λ<0 구간의 곡선은 공식의 대수적 연장이지 유효한 하한의 모음이 아니다.

실제 인증과 실패 예제

a=2,b=1이면 최적 쌍은 x=1,λ=1이고 목적값과 쌍대값은 모두 0.5다. x=0,λ=0에서는 인증 간극이 2이고 실제 목적 오차는 1.5다. 인증이 유효해도 느슨할 수 있음을 확인한다.

a=0,b=1,x=0,λ=−1에서는 대수적 간극이 −0.5다. 승수가 불가능하므로 약쌍대성의 반례가 아니다. a=2,b=1,x=2,λ=1도 −0.5를 주지만 이번에는 x가 불가능하다. 유효한 쌍대 하한이 있다고 불가능한 x의 목적값까지 상한이 되는 것은 아니다.

목적 오차에서 위치 오차로

이 목적함수의 강볼록 상수는 1이다. 제약 최적점 x*의 일차 변분부등식과 강볼록성을 결합하면 가능점에 대해

따라서 거리도 √(2gap) 이하라고 인증할 수 있다. 앞의 x=0,λ=0 예에서는 거리 상한 2, 실제 거리 1이다. 강볼록 상수가 μ라면 √(2gap/μ)로 바뀐다. 강볼록성이 없으면 작은 목적 오차만으로 특정 최적점과의 거리가 작다고 말할 수 없다. 평평한 최적해 집합을 떠올리자.

직접 풀기와 수치 해석

a=2,b=1,x=1을 고정하고 λ를 0에서 2까지 바꾸자. 원문제 점은 계속 최적인데 맞는 승수를 선택할 때만 간극이 사라진다. 이를 정상성 잔차의 제곱으로 설명하면 원문제 풀이 실패와 쌍대 승수의 부정확성을 구별할 수 있다.

화면은 f−d를 직접 뺀 값과 잔차 분해로 계산한 값도 나란히 보여준다. 수렴 근처에서 거의 같은 두 목적값을 빼면 상대정확도를 잃을 수 있다. 이 문제족의 가능 쌍에서는 비음수 항을 더하는 분해가 상쇄를 줄인다. 그러나 가능성 위반을 고치거나 음수를 몰래 0으로 바꿔도 된다는 뜻은 아니다. 다른 문제에서는 해당 구조에 맞는 안정적인 인증 계산을 따로 설계해야 한다.

더 읽기: Boyd와 Vandenberghe, Convex Optimization.