1. Lagrangian

• 임의의 최적화 문제는 형태가 다음과 같다.

$$ \min \quad f(\boldsymbol x) \\ s.t \quad h_i(\boldsymbol x) \leq 0, \quad g_j(\boldsymbol x) = 0 $$

• 제약 조건에 일정한 상수를 곱해서 목적 함수에 더하는 방식으로 제약을 완화하여, 최적화 문제의 Lagrangian $L(\boldsymbol x, \boldsymbol u, \boldsymbol v) = f(\boldsymbol x) + \sum_{i}^{I}u_ih_i(\boldsymbol x) + \sum_{j}^{J}v_jg_j(\boldsymbol x)$ 을 구할 수 있다.

2. Properties of Lagrangian

• $f(\boldsymbol x) + \sum_{i}u_ih_i(\boldsymbol x) + \sum_{j}v_jg_h(\boldsymbol x) \leq f(\boldsymbol x)$이므로, 모든 feasibile solution에 대해서 $L(\boldsymbol x, \boldsymbol u, \boldsymbol v) \leq f(\boldsymbol x)$이다.
• 즉, Lagrangian은 모든 feasibile solution에 대해서 Lower Bound가 된다.

3. Dual Function & Dual Problem

• 집합 C를 Primal Problem의 feasible solution set이라고 하면, 다음이 성립한다. 사실 임의의 feasible solution set에 대해서 Lagrangian이 목적 함수보다 작으므로, f* 이후의 min f(x)는 불필요하다.

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

• 여기서 g(u, v)를 Lagrangian Dual Function이라고 하며, optimal value보다 낮으므로 g(u, v)는 최적화 문제의 하한을 알려준다.

  

• 따라서, 임의의 dual varaible에 대해서 g(u, v)를 최대화하는 dual problem 문제를 풀면, primal problem의 가장 좋은 하한을 구할 수 있다.

$$ \max_{\boldsymbol u, \boldsymbol v} \min_{x} L(\boldsymbol x, \boldsymbol u, \boldsymbol v) \\ s.t \quad \boldsymbol u \geq \boldsymbol 0 $$