극값 정리의 조건 완화 - 2. 연속성(Continuity)

      Comments Off on 극값 정리의 조건 완화 - 2. 연속성(Continuity)

저번 글에서는 극값 정리의 조건 중 제약집합(constraint set)의 옹골성(compactness)를 완화하는 방법에 대해서 살펴보았다. 이번 글에서는 극값 정리의 조건 중 목적함수(objective function)의 연속성(continuity)를 완화하는 방법에 대해서 살펴보고자 한다.

 

목적함수 $f$의 연속성(continuity)

먼저 연속성보다 약한 조건인 반연속성(semi-continuity)를 정의하자.

 

정의 2.1. Lower Semi-continuity

함수 $f: \R^n \to \R$에 대하여, $f$가 아래의 두 동치인 조건 (1) 또는 (2) 중 하나를 만족하면

  1. $x^*$로 수렴하는 임의의 수열 $(x_n)$에 대하여
    \[ f(x^*) \leq \liminf_n f(x_n) \]
  2. 임의의 $\varepsilon > 0$에 대하여, $x^*$의 개근방(open neighborhood) $U$가 존재하여
    \[ f(x) \geq f(x^*) - \varepsilon, \quad \forall\, x \in U \]

$f$는 점 $x^* \in \R^n$에서 하반연속(lower semi-continuous)이라 한다.

만약 함수 $f$가 $\R^n$의 모든 점에서 하반연속이면 $f$는 $\R^n$ 위에서 하반연속이라 한다.

 

이제 함수 $f$가 $\R^n$ 위에서 하반연속이기 위한 동치 조건들에 대해 살펴보자.

 

정리 2.2.

함수 $f : \R^n \to \R$에 대하여, 다음은 모두 동치이다.

  1. $f$는 $\R^n$ 위에서 하반연속이다.
  2. $f$의 epigraph \[ \operatorname{epi}(f) = \set{(x,\,t) \in \R^n \times \R}{f(x) \leq t} \]는 $\R^n \times \R$에서 닫힌 집합이다.
  3. 임의의 $\alpha \in \R$에 대하여, $f$의 sub-level set \[ S_\alpha = \set{x \in \R^n}{f(x) \leq \alpha} \]은 $\R^n$에서 닫힌 집합이다.

 

증명.

$(1) \Rightarrow (2)$ $f$가 $\R^n$ 위에서 하반연속이라 하자. $\operatorname{epi}(f)$에서의 수열 $((x_n,\, t_n))$이 $(x^*,\, t^*)$으로 수렴한다고 가정하자. 즉, $(x_n,\,t_n) \to (x^*,\,t^*) \in E \times \R$라고 가정해보자. 이제 $(x^*,\,t^*) \in \operatorname{epi}(f)$임을 증명해야 한다.

먼저, $x_n \to x^*$, $t_n \to t^*$이고 또한 임의의 $n$에 대하여 $f(x_n) \leq t^n$임을 알 수 있다. 따라서 $f$의 점 $x^*$에서의 하반연속성에 의해,

\[ f(x^*) \leq \liminf_n f(x_n) \leq \liminf_n t_n = \lim_{n \to \infty} t_n = t^*. \]

임을 알 수 있다. 그러므로 $f(x^*) \leq t^*$이고 따라서 $(x^*,\,t^*) \in \operatorname{epi}(f)$를 얻는다.

 

$(2) \Rightarrow (3)$ $\alpha \in \R$가 $S_\alpha \neq \emptyset$를 만족한다고 가정해보자. ($S_\alpha = \emptyset$인 경우, 닫힌 집합임이 자명하다.) 이제 $S_\alpha$에서의 수열 $(x_n)$이 $x^* \in \R^n$으로 수렴한다고 가정해보자. 임의의 $n$에 대하여 $x_n \in S_\alpha$이므로, $f(x_n) \leq \alpha$이고 $(x_n,\, \alpha) \in \operatorname{epi}(f)$임을 알 수 있다. 이제 $n \to \infty$의 극한을 취하고 $\operatorname{epi}(f)$가 닫혀있다는 사실을 이용하면, $(x^*,\, \alpha) \in \operatorname{epi}(f)$를 얻는다. 이는 $f(x^*) \leq \alpha$임을 의미하므로 $x^* \in S_\alpha$를 얻는다. 따라서 $S_\alpha$는 닫힌 집합이다.

 

$(3) \Rightarrow (1)$ $f$가 어떤 $x_0 \in E$에서 하반연속이지 않다고 가정해보자. 그러면 $\varepsilon_0>0$와 $x_0$로 수렴하는 수열 $(x_n)$이 존재하여

\[ f(x_n) < f(x_0) - \varepsilon_0, \quad \forall\, n \in \N. \]

이제 $\alpha = f(x_0) - \varepsilon_0$를 택하자. 그러면 임의의 $n$에 대하여 $f(x_n) < \alpha$임을 알 수 있다. 가정에 의해 $S_\alpha$는 닫혀 있고 $x_n \to x_0$이므로, $x_0 \in S_\alpha$를 얻는다. 하지만 이는

\[ f(x_0) \leq \alpha = f(x_0) - \varepsilon_0 \quad \Rightarrow \quad \varepsilon_0 \leq 0 \]

이 되어 모순이 생긴다. 따라서 $f$는 $\R^n$의 모든점에서 하반연속이다..

 

이제 극값 정리를 좀더 약화된 조건으로 증명해 보자.

 

정리 2.3.

함수 $f : \R^n \to \R$이 하반연속이고 제약집합 $P \subseteq \R^n$는 옹골집합이라 하자. 그러면 $\min_{x \in P} f(x)$는 최적해(optimal solution)를 갖는다.

 

증명. 먼저 $\inf_{\alpha \in I} f(x)$이 유계임을 보이자. (모순을 이끌어 내기 위하여) 이 하한(infimum)이 $-\infty$라 가정해 보자. 그러면 $f(x_n) \to -\infty$인 수열 $(x_n) \in P$를 택할 수 있다. 하지만 $P$가 옹골집합이므로, 수렴하는 부분수열 $(x_{n_k})$가 존재한다. 따라서 $x_{n_k} \to x^* \in P$이고 동시에 $f(x_{n_k}) \to -\infty$를 얻는다. 이제 $f$는 $x^*$에서 하반연속이므로,

\[ f(x^*) \leq \liminf_k f(x_{n_k}) = -\infty, \]

이는 모순이다. 따라서 하한이 실수값임을 알 수 있다.

 

다음으로 $x^* \in P$가 존재하여 $f(x^*) = f(P) = \inf_{x \in P} f(x)$임을 보이자. $\inf f(P)$이 실수값이므로, $f(x_n) \to \inf f(P)$를 만족하는 수열 $(x_n) \in P$를 택할 수 있다. 이제 집합 $P$가 옹골성을 이용하면, 수렴하는 부분수열 $(x_{n_k})$이 존재하여 $x_{n_k} \to x^* \in P$이고 $f(x_{n_k}) \to \inf f(P)$를 만족한다. 따라서

\[ f(x^*) \leq \liminf_k f(x_{n_k}) = \lim_{k \to \infty} f(x_{n_k}) = \inf f(P). \]

하지만 $x^* \in P$이므로, $\inf f(P) \leq f(x^*)$여야만 한다. 따라서 $f(x^*) = \inf f(P)$임을 알 수 있고 $x^*$가 최적해임을 알 수 있다..

 

참고. 만약 목적함수 $f$가 $\R^n$에서 coercive하거나 집합 $S_\alpha \cap P$이 유계이면 (단, $P$는 닫힌 집합이다), $f$는 $P$에서 언제나 minimizer를 가짐을 보일 수 있다.