1. Weak Duality Theorem

• Primal Problem의 Bound를 Dual Problem을 풀면 계산할 수 있다는 정리이다.

(1) Primal Problem이 최소화 문제인 경우

• minimization primal problem의 모든 feasible solution과 maximization dual problem의 모든 feasible solution에 대하여, primal problem의 objective value가 dual problem의 objective value보다 항상 더 크거나 같다
• 따라서, Primal Problem과 Dual Problem 사이에 다음 관계가 성립한다.

$$ \max_{u}d(\boldsymbol u)=\max_{\boldsymbol u} \min_{\boldsymbol x} L(\boldsymbol x, \boldsymbol u) \leq \min_{x} \max_{u} L(\boldsymbol x, \boldsymbol u) = \min_{x}f(\boldsymbol x) $$

• 등호 및 부등호가 성립하는 이유는 다음과 같다.

  $$ L(\boldsymbol x, \boldsymbol u) = f(\boldsymbol x) + \sum_{i=1}^{I}u_ig_i(\boldsymbol x)\\\max_{u}L(\boldsymbol x, \boldsymbol u) = f(\boldsymbol x) \quad (\longleftarrow g_i(\boldsymbol x) \leq 0, \quad L(\boldsymbol x, \boldsymbol u) \leq f(\boldsymbol x)) \\ d(\boldsymbol u) =\min_{x^} L(\boldsymbol x, \boldsymbol u) \leq \min_{x \in C} L(\boldsymbol x, \boldsymbol u) \leq f^= \min_{x^*} f(\boldsymbol x) \leq \min_{x \in C} f(\boldsymbol x) $$

(2) Primal Problem이 최대화 문제인 경우

• maximization primal problem의 모든 feasible solution과 minimization dual problem의 모든 feasible solution에 대하여, primal problem의 objective value가 dual problem의 objective value보다 항상 더 작거나 같다

• 따라서, Primal Problem과 Dual Problem 사이에 다음 관계가 성립한다.

  $$ \min_{u}d(\boldsymbol u) = \min_{u}\max_{x}L(\boldsymbol x, \boldsymbol u) \geq \max_{x}\min_{u}L(\boldsymbol x, \boldsymbol u) = \max_{x}f(\boldsymbol x) $$

• 등호 및 부등호가 성립하는 이유는 다음과 같다.

  $$ L(\boldsymbol x, \boldsymbol u) =f(\boldsymbol x)-u^{T}g_{i}(\boldsymbol x) \\ \min_{u} L(\boldsymbol x, \boldsymbol u) = f(\boldsymbol x) \quad (\longleftarrow g_i(\boldsymbol x) \leq 0, \quad f(\boldsymbol x) \leq L(\boldsymbol x, \boldsymbol u)) \\ d(\boldsymbol u) =\max_{x^} L(\boldsymbol x, \boldsymbol u) \geq \max_{x \in C} L(\boldsymbol x, \boldsymbol u) \geq f^= \max_{x^*} f(\boldsymbol x) \geq \min_{x \in C} f(\boldsymbol x) $$

2. Strong Duality Theorem

• Primal Problem의 optimal solution이 존재하면 Dual Problem에도 optimal solution이 존재하며, 두 문제의 objective value는 서로 같다. 즉, $d^* = f^*$인 경우에 Strong Duality가 성립한다.

3. Slater Condition

• Convex Optimization 같은 경우에는, Primal Problem이 Slater Condition을 만족하면 Strong Duality가 보장된다.
• Slater Condition은 Primal Problem이 Convex & Strictly Feasible Solution이 하나 이상 존재하는 것을 말한다.

$$ \forall i,j, \quad \exist \boldsymbol x \in R^n \quad s.t. \quad h_i(\boldsymbol x) < 0, \quad g_j(\boldsymbol x) = 0
$$

4. Complementary Slackness Theorem