11. Duality in General Programs

$c \in R^{n}$ , $A \in R^{m \times n}$ , $b \in R^{m}$ , $G \in R^{r \times n}$ , $h \in R^{r}$ 일 때,

$\begin{aligned} min_{x} & c^{T} x \\ s . t . & A x = b \\ G x \leq h \end{aligned}$

$\begin{aligned} max_{u, b} & - b^{T} u - h^{T} v \\ s . t . & - A^{T} u - G^{T} v = c \\ v \geq 0 \end{aligned}$

모든 $u$ 와 $v \geq 0$ , 그리고 primal feasible $x$ 에 대해 다음이 성립된다.

$u^{T} (A x - b) + v^{T} (G x - h) \leq 0$

즉,

$(- A^{T} u - G^{T} v)^{T} x \geq - b^{T} u - h^{T} v$

위 관계에 의해, 만약, $c = - A^{T} u - G^{T} v$ 이면, primal 최적해에 대한 lower bound를 얻을 수 있다.

모든 $u$ 와 $v \geq 0$ , 그리고 primal feasible $x$ 에 대해,

$c^{T} x \geq c^{T} x + u^{T} (A x - b) + v^{T} (G x - h) := L (x, u, v)$

그래서, 만약 $C$ 가 primal feasible set이고, $f^{*}$ 가 primal 최적해라면,

$f^{*} \geq min_{x \in C} L (x, u, v) \geq min_{x} L (x, u, v) := g (u, v)$

다시말해, $g (u, v)$ 는 $f^{*}$ 에 대한 lower bound이다.

$g (u, v) = {\begin{cases} - b^{T} u - h^{T} v & if c = - A^{T} u - G^{T} v \\ - \infty & otherwise \end{cases}$

두번째 설명은 첫번째와 같은 dual을 가져오지만, completely general하고 (convex하지 않은 문제를 포함한) 임의의 모든 최적 문제에 적용된다.