극값 정리의 조건 완화 (1) 긴밀성(Compactness)

실해석학에서 극값 정리(Extreme Value Theorem) 또는 최대-최소 정리(Max-Min Theorem)이라고 불리는 정리는 아래와 같다.

정리 (극값 정리 또는 최대-최소 정리)

집합 $E \subseteq \R^n$를 긴밀집합(compact set)이라 하고 함수 $f : E \to \R$가 연속함수(continuous function)라 하자. 그러면 함수 $f$는 집합 $E$ 안에서 언제나 최댓값(maximum)과 최솟값(minimum)을 갖는다. 다시 말해, 임의의 $x \in E$에 대하여 $f(x^*) \leq f(x) \leq f(y^*) $를 만족하는 $x^*,\, y^* \in E$가 존재한다.

이 정리에서 중요한 사실은 주어진 집합 $E$의 긴밀성(compactness)과 주어진 함수 $f$의 연속성(connectedness)이다. 일단 이 두 조건이 만족 되면 반드시 최댓값과 최솟값의 존재성이 보장 되기 때문에, 적당한 알고리즘을 통해 이 극값들을 찾을 수 있을것이라 기대할 수 있다. 하지만 이 두 조건 모두 굉장히 강력한 조건들이라 위 정리를 실제로 적용하기가 쉽지 않은 경우가 많다. 그래서 이번 글에서는 이 두 강력한 조건들을 상대적으로 약한 조건으로 완화 하는 방법에 대해서 생각해 보고자 한다.

제약집합 $E$의 긴밀성(compactness)

먼저 집합 $E$의 긴밀성(compactness)을 완화하는 방법에 대해서 생각해 보자. 우선 주어진 함수 $f$의 sub-level set에 대한 정의가 필요하다.

정의 1.1 (Sub-Level Set)

함수 $f: \R^n \to \R$과 실수 $\alpha \in \R$에 대하여, $f$의 sub-level set을 아래와 같이 정의한다.

\[ S_\alpha = \set{x \in V}{f(X) \leq \alpha}. \]

정리 1.2

목적함수(objective function) $f : \R^n \to \R$가 연속이라 하자. 또한 제약집합(constraint set) $E$가 닫힌 집합(closed set)이라 하자. 만약 $E \cap S_\alpha$가 유계(bounded)가 되게 하는 실수 $\alpha \in \R$가 존재한다면, $\min_{x \in E} f(x)$는 최적해(optimal solution)을 갖는다.

증명. 우선 sub-level set을 아래와 같이 생각할 수 있다.

\[ S_\alpha = f^{-1}((-\infty,\, \alpha]). \]

이 때, $(-\infty,\, \alpha]$는 닫힌 집합이고 $f$가 연속이므로, sub-level set $S_\alpha$ 또한 닫힌 집합임을 알 수 있다. 또한 $E$가 닫힌 집합이라 가정하였으므로, $E \cap S_\alpha$도 닫힌 집합이다. 따라서 $E \cap S_\alpha$는 유계이고 닫힌 집합이므로 긴밀집합이다.

따라서, 극값 정리를 여기에 적용할 수 있다. 즉, $\min_{x \in E \cap S_\alpha} f(x)$는 $E \cap S_\alpha$ 안에서 최적해 $x^*$를 갖는다. 이제 $x^*$가 집합 $E$의 원소임을 보이면 증명이 완료 된다. 먼저 $x^*$가 최적해이므로, 임의의 $x \in E \cap S_\alpha$에 대하여,

\[ \alpha \geq f(x) \geq f(x^*). \]

또한 임의의 $x \in P \setminus S_\alpha$에 대하여, ($x$가 $S_\alpha$의 원소가 아니기 때문에) $f(x) > \alpha$를 얻고 결과적으로 $f(x) > \alpha \geq f(x^*)$를 얻는다. 이는 임의의 $x \in P$에 대하여 $f(x) \geq f(x^*)$임을 의미하므로, $x^*$는 $\min_{x \in P} f(x)$의 최적해임을 알 수 있다.

이제 주어진 함수 $f : \R^n \to \R$의 sub-level set이 유계임을 확인할 수 있는 또 다른 방법에 대해서 알아보자. 만약 $x$의 크기(노름)가 발산할때마다 $f(x)$의 값 또한 같이 발산하면 함수 $f$를 coercive하다고 한다. 좀 더 자세한 정의는 아래와 같다.

정의 1.3 (Coercivity)

함수 $f: \R^n \to \R$가 주어졌다고 하자. 만약 $\norm{x_n} \to \infty$를 만족하는 임의의 수열 $(x_n)$에 대하여 $f(x_n) \to \infty$가 성립하면, $f$를 coercive function이라 한다.

coercivity와 sub-level set 사이에는 아래와 같이 밀접한 관계가 존재한다.

정리 1.4

함수 $f: \R^n \to \R$가 coercive하다고 하자. 그러면 임의의 $\alpha \in \R$에 대하여 $f$의 sub-level set $S_\alpha$는 유계이다. (참고로 이 정리의 역 또한 성립한다: 함수 $f: \R^n \to \R$의 모든 sub-level set $S_\alpha$이 유계이면, $f$는 coercive하다.)

증명. (모순을 이끌어 내기 위하여) 어떤 $\alpha \in \R$가 존재하여 $S_\alpha$가 유계가 아니라 가정해보자. 그러면 $\norm{x_n} \to \infty$를 만족하는 수열 $(x_n)$이 $S_\alpha$에 존재한다. 이제 $f$가 coercive하므로, 반드시 $f(x_n) \to \infty$여야만 한다. 하지만 이는 임의의 $x \in S_\alpha$에 대하여 $f(x) \leq \alpha$라는 사실과 모순이다. 그러므로 $f$의 모든 sub-level set들은 유계이다.

따름정리 1.5

목적함수(objective function) $f : \R^n \to \R$가 연속이고 coercive하다고 하자. 또한 제약집합(constraint set) $E$가 닫힌 집합(closed set)이라 하자. 그러면, $\min_{x \in E} f(x)$는 최적해(optimal solution)을 갖는다.

증명. 정리 1.4와 정리 1.2에 의해 성립한다.