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

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

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

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

정의 2.1 (Lower Semi-continuity)

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

1. $x^{\ast }$로 수렴하는 임의의 수열 $(x_n)$에 대하여
   $$f(x^{\ast })\le \underset{n}{lim inf}f(x_n).$$
2. 임의의 $\epsilon >0$에 대하여, $x^{\ast }$의 개근방(open neighborhood) $U$가 존재하여
   $$f(x)\ge f(x^{\ast })-\epsilon ,\mathrm{\forall }x\in U.$$

$f$는 점 $x^{\ast }\in {\mathbb{R}}^n$에서 lower semi-continuous하다고 한다.

만약 함수 $f$가 ${\mathbb{R}}^n$의 모든 점에서 lower semi-continuous이면 $f$는 ${\mathbb{R}}^n$ 위에서 lower semi-continuous하다고 한다.

이제 함수 $f$가 ${\mathbb{R}}^n$ 위에서 lower semi-continuous이기 위한 동치 조건들에 대해 살펴보자.

정리 2.2

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

1. $f$는 ${\mathbb{R}}^n$ 위에서 lower semi-continuous이다.
2. $f$의 epigraph
   $$\mathrm{epi}(f)=\left\{(x,t)\in {\mathbb{R}}^n\times \mathbb{R}\right|f(x)\le t\}$$는 ${\mathbb{R}}^n\times \mathbb{R}$에서 닫힌 집합이다.
3. 임의의 $\alpha \in \mathbb{R}$에 대하여, $f$의 sub-level set
   $$S_{\alpha }=\left\{x\in {\mathbb{R}}^n\right|f(x)\le \alpha \}$$은 ${\mathbb{R}}^n$에서 닫힌 집합이다.

증명.

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

먼저, $x_n\to x^{\ast }$, $t_n\to t^{\ast }$이고 또한 임의의 $n$에 대하여 $f(x_n)\le t^n$임을 알 수 있다. 따라서 $f$의 점 $x^{\ast }$에서의 lower semi-continuity에 의해,
$$f(x^{\ast })\le \underset{n}{lim inf}f(x_n)\le \underset{n}{lim inf}{t}_n=\underset{n\to \mathrm{\infty }}{lim}{t}_n=t^{\ast }.$$

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

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

$(3)\Rightarrow (1)$ $f$가 어떤 $x_0\in E$에서 lower semi-continuous하지 않다고 가정해보자. 그러면 ${\epsilon }_0>0$와 $x_0$로 수렴하는 수열 $(x_n)$이 존재하여

$$f(x_n)<f(x_0)-{\epsilon }_0,\mathrm{\forall }n\in \mathbb{N}.$$

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

$$f(x_0)\le \alpha =f(x_0)-{\epsilon }_0\Rightarrow {\epsilon }_0\le 0$$

이 되어 모순이 생긴다. 따라서 $f$는 ${\mathbb{R}}^n$의 모든점에서 lower semi-continuous하다.

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

정리 2.3

함수 $f:{\mathbb{R}}^n\to \mathbb{R}$이 lower semi-continuous하고 제약집합 $P\subseteq {\mathbb{R}}^n$는 compact하다고 하자. 그러면 $\underset{x\in P}{min}f(x)$는 최적해(optimal solution)를 갖는다.

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

$$f(x^{\ast })\le \underset{k}{lim inf}f(x_{n_k})=-\mathrm{\infty },$$

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

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

$$f(x^{\ast })\le \underset{k}{lim inf}f(x_{n_k})=\underset{k\to \mathrm{\infty }}{lim}f(x_{n_k})=inff(P).$$

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

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