보통 어떤 수학적 구조의 쌍대(duality)란 그 구조를 뒤집어서 구성한 것
최적화 문제는 두 가지 관점에서 문제를 표현할 수 있는데 원초문제(primal-problem), 쌍대문제(dual-problem) 이다.
아래와 같이 함수 $f(x,y)$ 를 minimize 하는 primal-problem 문제가 있을 때
이미 condition function 에 $p, q$ 가 각각 1일 때 feasible set 을 만족하면서 minimize 된 lower bound(하한값)가 2 인 것을 알 수 있다.
수식적으로 아래와 같이 설명할 수 있다.
condition function 에 각각 상수 $a,b,c$ 를 곱하여 표현
음수일경우 부등호가 바뀜으로 $a, b, c \ge 0$ 이다.
어차피 $bx$ 와 $cy$ 는 0보다 큰값임으로 선형결합한다고 해도 $2a$ 보다 작아질 수 없다.
그리고 아래와 같이 $p,q$ 를 재정의하면 $\min f(x,y)$ 도 재정의할 수 있다.
\[(a+b) x + (a+c) y \ge 2a\] \[p=a+b \\ q=a+c \\ f(x,y) = px + qy \ge 2a \\ \min f(x,y) = 2a\]위와 같이 얻은 lower bound 결과를 최대화하는 것으로 새로운 최적화 문제, dual-problem 을 정의할 수 있다
이때 lower bound 를 만족하게 하는 조건들이 이 문제에서의 condition function 된다.
primal-problem 의 $x,y$ 를 minimize 하는 문제와
dual-problem 의 $\min(f(x,y))$ 의 $2a$ 를 maximize 하는 문제가 동일하다.
위의 상황에서 $a$ 가 가장 크려면 $b=0, c=0$ 인 상황이 가장 클 것이니 $a=p=q$ 라 할 수 있다.