Constrained Optimization and Lagrange Multipliers

7.1장에서는 $f : \mathbb{R}^D\rightarrow\mathbb{R}$ 함수의 minimum을 찾기 위한 문제를 고려했습니다.

\[\min_{\boldsymbol{x}} f(\boldsymbol{x}) \tag{7.16}\]

7.2장에서 다룰 문제는 추가적인 제약 사항이 존재합니다. 즉, real-valued functions $g_i : \mathbb{R}^D\rightarrow\mathbb{R}\text{ for } i=1,\dotsc,m$ 에 대해서, 아래와 같은 constrained optimization problem(제약이 있는 최적화 문제)에 대해 다룹니다.

\[\begin{align*} \min_{\boldsymbol{x}} \quad&f(\boldsymbol{x}) \tag{7.17} \\ \text{subject to} \quad &g_i(\boldsymbol{x}) \leq 0 \quad \text{for all} \quad i = 1,\dotsc,m \end{align*}\]

예를 들면, 아래의 Figure 7.4와 같습니다.

일반적으로 함수 $f$ 와 $g_i$ 는 non-convex일 수 있으며, 다음 장에서 convex인 경우에 대해서 다루도록 하겠습니다.

실용적이지는 않지만, constrained problem인 (7.17) 식을 unconstrained problem으로 변환하는 한 가지 명백한 방법은 아래의 indicator function을 사용하는 것 입니다.

\[J(\boldsymbol{x}) = f(\boldsymbol{x}) + \sum_{i=1}^m \boldsymbol{1}(g_i(\boldsymbol{x})) \tag{7.18}\]

여기서 $\boldsymbol{1}(z)$ 함수는 infinite step function 입니다.

\[\boldsymbol{1}(z) = \left\lbrace\begin{align*}0\quad&\text{if }z \leq 0 \\ \infty \quad&\text{otherwise}\end{align*}\right. \tag{7.19}\]

이는 제약 조건이 충족되지 않으면 infinite penalty를 주기 때문에 기존의 식과 동일한 해를 제공합니다. 하지만, (7.19)의 infinite step function도 최적화하기 어렵습니다만, Lagrange multipliers(라그랑주 승수) 를 도입하면 해결할 수 있습니다. 라그랑주 승수의 아이디어는 step function을 linear function으로 대체하는 것입니다 (라그랑주 승수에 대한 참고 내용: link).

각각의 부등식 제약 조건에 대응하는 라그랑주 승수 $\lambda_i \geq 0$ 를 도입하여 풀어야하는 문제 (7.17) 식에 Lagrangian 을 다음과 같이 연관시킵니다.

\[\begin{align*} \mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda}) &= f(\boldsymbol{x}) + \sum_{i=1}^m\lambda_i g_i(\boldsymbol{x}) \tag{7.20a} \\ &= f(\boldsymbol{x}) + \boldsymbol{\lambda}^\top\boldsymbol{g}(\boldsymbol{x}) \tag{7.20b} \end{align*}\]

여기서 (7.20b) 식에서 모든 제약 $g_i(\boldsymbol{x})$ 를 벡터 $\boldsymbol{g}(\boldsymbol{x})$ 로 연결했고, 모든 라그랑주 승수는 벡터 $\boldsymbol{\lambda}\in\mathbb{R}^m$ 으로 연결했습니다.

여기서 이제 Lagrangian duality 라는 개념을 도입합니다. 일반적으로 최적화에서 duality(쌍대)는 변수 $\boldsymbol{x}$(called the primal variables)의 한 집합에 대한 최적화 문제를 다른 변수 $\boldsymbol{\lambda}$(called the dual variables) 집합에 대한 또 다른 최적화 문제로 변환하는 것입니다. Duality에 대한 두 가지 다른 접근 방법을 소개할텐데, 7.2장에서는 Lagrangian duality에 대해서 살펴보고, 7.3.3장에서 Legendre-Fenchel duality에 대해 살펴보도록 하겠습니다.

Definition 7.1. 식 (7.17)의 문제

\[\begin{align*} \min_{\boldsymbol{x}}\quad&f(\boldsymbol{x}) \tag{7.21} \\ \text{subject to} \quad &g_i(\boldsymbol{x}) \leq 0 \quad \text{for all} \quad i = 1,\dotsc,m \end{align*}\]

은 primal problem 이며, primal variables $x$에 대응합니다.

이와 관련된 Lagrangian dual problem 은 다음과 같이 주어집니다.

\[\begin{align*} \max_{\boldsymbol{\lambda}\in\mathbb{R}^m}\quad&\mathfrak{D}(\boldsymbol{\lambda}) \tag{7.22} \\ \text{subject to}\quad&\boldsymbol{\lambda} \geq \boldsymbol{0} \end{align*}\]

여기서 $\boldsymbol{\lambda}$ 는 dual variables이고, $\mathfrak{D}(\boldsymbol{\lambda}) = \min_{\boldsymbol{x}\in\mathbb{R}^d}\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda})$ 입니다.

식 (7.18)의 $J(\boldsymbol{x})$ 와 식 (7.20b)의 Lagrangian 간의 차이는 indicator function을 linear function으로 제약을 완화한 것 입니다. 그러므로, $\lambda\geq 0$ 일 때, Lagrangian $\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda})$ 는 $J(\boldsymbol{x})$ 의 lower bound가 됩니다. 따라서, $\boldsymbol{\lambda}$ 에 대한 $\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda})$ 최댓값(maximum)은

\[J(\boldsymbol{x}) = \max_{\boldsymbol{\lambda}\geq 0}\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda}) \tag{7.25}\]

가 됩니다. 원래의 문제가 $J(\boldsymbol{x})$ 를 최소화하는 것이기 때문에 결국 다음의 식을 구하는 것이 됩니다.

\[\min_{\boldsymbol{x}\in\mathbb{R}^d}\max_{\boldsymbol{\lambda}\geq0}\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda}) \tag{7.26}\]

(7.23)의 minimax inequality에 의해서, (7.26)의 minimum과 maximum의 순서를 바꾸면 더 작은 값이 됩니다. 즉, 다음과 같습니다.

\[\min_{\boldsymbol{x}\in\mathbb{R}^d}\max_{\boldsymbol{\lambda}\geq0}\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda}) \geq \max_{\boldsymbol{\lambda}\geq0}\min_{\boldsymbol{x}\in\mathbb{R}^d}\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda}) \tag{7.27}\]

이 또한 weak duality 로 알려져 있습니다. 우항의 안쪽 항이 dual objective function $\mathfrak{D}(\boldsymbol{\lambda}) = \min_{\boldsymbol{x}\in\mathbb{R}^d}\mathfrak{L}(\boldsymbol{x},\boldsymbol{y})$ 라는 것의 주목합니다.

제약이 존재하는 original optimzation problem과는 반대로, $\min_{\boldsymbol{x}\in\mathbb{R}^d}\mathfrak{L}(\boldsymbol{x},\boldsymbol{y})$ 는 주어진 $\boldsymbol{\lambda}$ 값에 대한 제약이 없는 최적화 문제(unconstrained optimization problem)입니다. 만약 $\min_{\boldsymbol{x}\in\mathbb{R}^d}\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda})$ 를 푸는 것이 쉽다면, 전체 문제를 푸는 것 또한 쉽습니다. 식 (7.20b)를 살펴보면, $\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda})$ 는 $\boldsymbol{\lambda}$ 에 대한 affine 이라는 것을 알 수 있습니다. 그러므로 $\min_{\boldsymbol{x}\in\mathbb{R}^d}\mathfrak{L}(\boldsymbol{x},\boldsymbol{\lambda})$ 는 $\boldsymbol{\lambda}$ 의 affine function의 pointwise minimum입니다. 그러므로, 비록 $f(\cdot), g(\cdot)$ 이 nonconvex일 지라도 $\mathfrak{D}(\boldsymbol{\lambda})$ 는 concave 입니다. Outer problem인 $\boldsymbol{\lambda}$ 에 대한 maximization 은 concave function의 maximum 이고, 효율적으로 계산될 수 있습니다.

$f(\cdot)$ 과 $g(\cdot)$ 이 미분가능하다고 가정한다면, 우리는 $\boldsymbol{x}$ 에 대해 Lagrangian을 미분하고 0과 같다고 설정하여 Lagrange dual problem을 찾을 수 있고, 최적값을 찾을 수 있습니다. 7.3.1장과 7.3.2장에서는 $f(\cdot)$ 과 $g(\cdot)$ 이 convex일 때의 구체적인 예제를 살펴봅니다.