younghwanjoo1608

ㅎㅇ

3 minute read

"어디가 정상이고 어디가 계곡인가"


우리는 전체 space 위에서 정의된 어떤 함수의 최솟값과 최댓값을 찾고자 한다.


Definition 1.1.1

$f:\mathcal{S} \rightarrow \mathbb{R}$이 set $\mathcal{S} \subseteq \mathbb{R}^n$ 위에서 정의되었다고 하자.

(a) 임의의 $\textbf{x} \in \mathcal{S}$에 대해 $f(\textbf{x}) \geq f(\textbf{x}^{\ast})$이 성립하면, $\textbf{x}^{\ast} \in \mathcal{S}$을 $\mathcal{S}$ 위에서 $f$의 global minimum point라고 한다.

(b) 임의의 $\textbf{x}^{\ast} \not= \textbf{x} \in \mathcal{S}$에 대해 $f(\textbf{x}) > f(\textbf{x}^{\ast})$이 성립하면, $\textbf{x}^{\ast} \in \mathcal{S}$을 $\mathcal{S}$ 위에서 $f$의 strict global minimum point라고 한다.

(c) 임의의 $\textbf{x} \in \mathcal{S}$에 대해 $f(\textbf{x}) \leq f(\textbf{x}^{\ast})$이 성립하면, $\textbf{x}^{\ast} \in \mathcal{S}$을 $\mathcal{S}$ 위에서 $f$의 global maximum point라고 한다.

(d) 임의의 $\textbf{x}^{\ast} \not= \textbf{x} \in \mathcal{S}$에 대해 $f(\textbf{x}) < f(\textbf{x}^{\ast})$이 성립하면, $\textbf{x}^{\ast} \in \mathcal{S}$을 $\mathcal{S}$ 위에서 $f$의 strict global maximum point라고 한다.


$f$의 최적화가 이루어지는 set $\mathcal{S}$를 feasible set이라고 하며, 임의의 점 $\textbf{x} \in \mathcal{S}$를 feasible solution이라고 한다. 편의상 global minimum point를 minimizer/global minimizer, global maximum point를 maximizer/global maximizer라고 하기도 한다.


Vector $\textbf{x}^{\ast} \in \mathcal{S}$가 global minimum 또는 global maximum이면, $\textbf{x}^{\ast}$를 $\mathcal{S}$ 위에서 $f$의 global optimum이라고 한다.


$\mathcal{S}$ 위에서 $f$의 maximal value는 $f$의 supremum으로써 정의된다.

\[\max\{f(\textbf{x}) : \textbf{x} \in \mathcal{S}\} = \sup\{f(\textbf{x}) : \textbf{x} \in \mathcal{S}\}\]

$\textbf{x}^{\ast} \in \mathcal{S}$가 $\mathcal{S}$ 위에서 $f$의 global maximum이면, $\mathcal{S}$ 위에서 $f$의 maximal value는 $f(\textbf{x}^{\ast})$가 된다.

마찬가지로 $f$의 minimal value는 $f$의 infimum으로써 정의.

\[\min\{f(\textbf{x}) : \textbf{x} \in \mathcal{S}\} = \inf\{f(\textbf{x}) : \textbf{x} \in \mathcal{S}\}\]

$\textbf{x}^{\ast} \in \mathcal{S}$가 $\mathcal{S}$ 위에서 $f$의 global minimum이면, $\mathcal{S}$ 위에서 $f$의 minimal value는 $f(\textbf{x}^{\ast})$가 된다.


$\mathcal{S}$ 위에서 $f$의 모든 global minimizer, global maximizer들의 set을 다음과 같이 쓴다.

\[\arg \min \{ f(\textbf{x}) : \textbf{x} \in \mathcal{S} \} \\ \arg \max \{ f(\textbf{x}) : \textbf{x} \in \mathcal{S} \}\]


Example 1.1.2

Unit ball $\mathcal{S} = B[0,1] = {(x,y)^T:x^2 + y^2 \leq 1}$ 위에서 정의된 2-dim. linear function $f(x,y) = x+y$를 생각하자.

Cauchy-Schwarz 부등식에 의하여, 임의의 $(x,y)^T \in \mathcal{S}$에 대해

\[x+y = \begin{pmatrix}x & y\end{pmatrix}\begin{pmatrix}1 \\ 1\end{pmatrix} \leq \sqrt{x^2 + y^2}\sqrt{1^2 + 1^2} \leq \sqrt{2}\]

따라서 $\mathcal{S}$ 위에서 $f$의 maximal value는 $\sqrt{2}$에 의해 위로 bounded된다. 또한 이 upper bound $\sqrt{2}$는 $(x , y) = (\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}} )$로부터 얻는다.

이 값을 갖는 점은 $(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}} )$뿐이므로, 이는 $\mathcal{S}$ 위에서 $f$의 strict global maximum point이며 $\sqrt{2}$는 maximal value이다.

같은 방법으로 strict global minimum point $(-\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}} )$와 minimal value $-\sqrt{2}$를 얻을 수 있다.


물론 global maximum과 minimum을 알 수 있다면 좋겠지만, 대부분의 결과는 우리가 관심 있는 한 point의 neighborhood에 관한 local maximum과 local minimum만을 얻을 수 있다.


Definition 1.1.3

$f:\mathcal{S} \rightarrow \mathbb{R}$이 set $\mathcal{S} \subseteq \mathbb{R}^n$ 위에서 정의되었다고 하자.

(a) 임의의 $\textbf{x} \in \mathcal{S} \cap B(\textbf{x}^{\ast}, r)$에 대해 $f(\textbf{x}) \geq f(\textbf{x}^{\ast})$인 $r>0$이 존재하면, $\textbf{x}^{\ast} \in \mathcal{S}$을 $\mathcal{S}$ 위에서 $f$의 local minimum point라고 한다.

(b) 임의의 $\textbf{x}^{\ast} \not= \textbf{x} \in \mathcal{S}\cap B(\textbf{x}^{\ast}, r)$에 대해 $f(\textbf{x}) > f(\textbf{x}^{\ast})$인 $r>0$이 존재하면, $\textbf{x}^{\ast} \in \mathcal{S}$을 $\mathcal{S}$ 위에서 $f$의 strict global minimum point라고 한다.

(c) 임의의 $\textbf{x} \in \mathcal{S}\cap B(\textbf{x}^{\ast}, r)$에 대해 $f(\textbf{x}) \leq f(\textbf{x}^{\ast})$인 $r>0$이 존재하면, $\textbf{x}^{\ast} \in \mathcal{S}$을 $\mathcal{S}$ 위에서 $f$의 global maximum point라고 한다.

(d) 임의의 $\textbf{x}^{\ast} \not= \textbf{x} \in \mathcal{S}\cap B(\textbf{x}^{\ast}, r)$에 대해 $f(\textbf{x}) < f(\textbf{x}^{\ast})$인 $r>0$이 존재하면, $\textbf{x}^{\ast} \in \mathcal{S}$을 $\mathcal{S}$ 위에서 $f$의 strict global maximum point라고 한다.


물론 global maximum(minimum)은 local maximum(minimum)이기도 하다. Maximizer와 마찬가지로 local maximum(minimum) point를 local maximizer(minimizer)라고 표현한다.


그럼 local maximum(minimum)은 어떻게 찾지?


Theorem 1.1.4 [Fermat’s Theorem]

1-dim. function $f$가 구간 $(a,b)$에서 미분 가능하다고 하자.

만약 점 $x^{\ast} \in (a,b)$가 local maximum 또는 local minimum이면, $f’(x^{\ast})=0$이다.


위 Thm.을 multidimension으로 확장시키면, gradient가 $0$이 되는 곳이 local optimum point가 된다는 내용이 될 것이다. 이를 first order optimality condition이라고 한다. 일차 미분을 통해 얻어졌으니까.1


Theorem 1.1.5 [First Order Optimality Condition for Local Optima Points]

함수 $f : U \rightarrow \mathbb{R}$이 set $U \subseteq \mathbb{R}^n$에서 정의되었다고 하자.

$\textbf{x}^{\ast} \in \textrm{int}(U)$가 local optimum point이고 $\textbf{x}^{\ast}$에서 $f$의 모든 partial derivative가 존재한다고 하자. 그러면 $\nabla f(\textbf{x}^{\ast})=0$이다.


Proof.


$i \in {1,2, \cdots , n}이라 하자.

일차 함수 $g(t) = f(\textbf{x}^{\ast} + t \textbf{e}_i)$를 생각하자. $g$는 $t=0$에서 미분 가능하며 $g’(0)=\frac{\partial f}{\partial x_i}(\textbf{x}^{\ast})$이다. $\textbf{x}^{\ast}$는 $f$의 local optimum point이므로, $t=0$은 $g$의 local optimum point가 된다.

따라서 Thm. 1.1.4(Fermat’s Theorem)에 의해 $g’(0)=0$이고, 이는 $\frac{\partial f}{\partial x_i}(\textbf{x}^{\ast})=0$와 같다. 이는 모든 $i \in {1,2, \cdots , n}$에 대해 성립하므로 $\nabla f(\textbf{x}^{\ast})=0$를 얻는다. $\square$

위 Thm.을 보면 다변수 함수의 first order optimality condition을 체크하는데 일변수 함수의 first order optimality condition을 사용했음을 알 수 있다.


아쉽게도 Thm. 1.1.5의 역은 일반적으로 성립하지 않는다. Gradient가 0인 점이라도 local optimum point가 아닐 수 있다. 예를 들어, 함수 $f(x)=x^3$의 일차 미분은 $x=0$에서 $0$이 되지만, 점 $0$은 $f$의 local maximum도 local minimum도 아니다.


Definition 1.1.6

함수 $f : U \rightarrow \mathbb{R}$이 set $U \subseteq \mathbb{R}^n$에서 정의되었다고 하자.

점 $\textbf{x}^{\ast} \in \int(U)$에 대해 $\textbf{x}^{\ast}$의 어떤 neigborhood 위에서 $f$가 미분 가능하다고 하자. 만약 $\nabla f(\textbf{x}^{\ast})=0$이면 $\textbf{x}^{\ast}$를 stationary point라고 한다.


  1. 그 말은 *second* order optimality condition이 존재한다는 복선... ↩

You may also enjoy