younghwanjoo1608

ㅎㅇ

1 minute read

"한 번으로 안 되면 두 번으로"


Second order optimality condition의 필요조건부터 시작하자.


Definition 1.3.1

$f: U \rightarrow \mathbb{R}$이 open set $U \subseteq \mathbb{R}^n$ 위에서 정의되었다고 하자. $f$가 $U$에서 두 번 미분 가능하고 $\textbf{x}^{\ast}$가 stationary point라고 하자.

(a) $\textbf{x}^{\ast}$가 $U$ 위에서 $f$의 local minimum point이면, $\nabla^2 f(\textbf{x}^{\ast}) \preceq 0$.

(b) $\textbf{x}^{\ast}$가 $U$ 위에서 $f$의 local maximum point이면, $\nabla^2 f(\textbf{x}^{\ast}) \succeq 0$.


Proof.


[(a)]

$\textbf{x}^{\ast}$가 $f$의 local minimum point이므로, ball $B(\textbf{x}^{\ast}, r) \subseteq U$가 존재해서 모든 $\textbf{x} \in B(\textbf{x}^{\ast}, r)$에 대해 $f(\textbf{x}) \geq f(\textbf{x}^{\ast})$가 성립한다.

$\textbf{d} \in \mathbb{R}^n$가 nonzero vector라고 하자. 임의의 $0 < \alpha < \frac{r}{ \Vert \textbf{d} \Vert }$에 대해, $\textbf{x}_{\alpha}^{\ast} \equiv \textbf{x}^{\ast} + \alpha \textbf{d} \in B(\textbf{x}^{\ast}, r)$이므로

\[f(\textbf{x}_{\alpha}^{\ast}) \geq f(\textbf{x}^{\ast})\]

를 만족한다.

반면 linear approximation을 생각하면, vector \(\textbf{z} _{\alpha} \in[\textbf{x}_{\alpha}^{\ast}, \textbf{x}^{\ast}]\)가 존재해서

\[f(\textbf{x}_{\alpha}^{\ast}) - f(\textbf{x}^{\ast}) = \nabla f(\textbf{x}^{\ast})^T(\textbf{x}_{\alpha}^{\ast} - \textbf{x}^{\ast}) + \frac{1}{2}(\textbf{x}_{\alpha}^{\ast} - \textbf{x}^{\ast})^T \nabla^2f(\textbf{z}_{\alpha})(\textbf{x}_{\alpha}^{\ast} - \textbf{x}^{\ast})\]

가 성립한다.


$\textbf{x}^{\ast}$가 $f$의 stationary point이고 $\textbf{x}_{\alpha}^{\ast}$의 정의에 의해

\[f(\textbf{x}_{\alpha}^{\ast}) - f(\textbf{x}^{\ast}) = \frac{\alpha^2}{2}\textbf{d}^T \nabla^2f(\textbf{z}_{\alpha})\textbf{d}\]

이제 첫 번째 식과 조합하면 임의의 $\alpha \in (0, \frac{r}{ \Vert \textbf{d} \Vert })$에 대해 부등식 $\textbf{d}^T \nabla^2f(\textbf{z}_{\alpha})\textbf{d} \geq 0$이 성립한다.


마지막으로 $\alpha \rightarrow 0^+$에서 $\textbf{z}_{\alpha} \rightarrow \textbf{x}^{\ast}$라는 사실과 Hessian의 continuity로부터 $\textbf{d}^T \nabla^2 f(\textbf{x}^{\ast})\textbf{d} \geq 0$를 얻는다. 위 부등식은 임의의 nonzero vector $\textbf{d} \in \mathbb{R}^n$에 대해 성립하므로 증명 끝.


[(b)]

Function $-f$에 대해 위 내용을 반복. $\square$


You may also enjoy