11 Duality in General Programs

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

\[\begin{alignat}{1} \min_{x} & \quad c^T x \\\\ s.t. & \quad Ax = b \\\\ & \quad Gx \leq h \end{alignat}\]

\[\begin{alignat}{1} \max_{u,b} & \quad -b^T u - h^T v \\\\ s.t. & \quad - A^T u - G^T v = c \\\\ & \quad v \geq 0 \end{alignat}\]

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

\[\begin{equation} u^T (Ax-b) + v^T(Gx-h) \leq 0 \end{equation}\]

즉,

\[\begin{equation} (-A^Tu - G^Tv)^T x \geq -b^Tu - h^T v \end{equation}\]

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

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

\[\begin{equation} c^T x \geq c^T x + u^T (Ax-b) + v^T (Gx -h) := L(x,u,v) \end{equation}\]

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

\[\begin{equation} f^* \geq \min_{x \in C} L(x,u,v) \geq \min_x L(x,u,v) := g(u,v) \end{equation}\]

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

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

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

Next Post