📂최적화이론

다변수함수의 극값에 대한 2계 필요/충분 조건

정리¹

함수 $f : \mathbb{R}^{n} \to \mathbb{R}$가 주어졌다고 하자. $\nabla f$, $\nabla^{2}f$를 각각 $f$의 그래디언트와 헤시안이라고 하자.

• 2계 필요 조건^{second-order necessary conditions}

  만약 $x^{\ast}$가 지역 최적해^{local optimizer}이고, $x^{\ast}$의 근방에서 $\nabla^{2}f$가 존재하고 연속이면,

  $$ \nabla f(x^{\ast}) = 0 $$

  이고 $\nabla^{2} f(x^{\ast})$는 양의 준정부호이다.

  여기서 $0$은 숫자 영^zero이 아니라, 영벡터임에 주의하라.

• 2계 충분 조건^{second-order sufficient conditions}

  $x^{\ast}$의 근방에서 $\nabla^{2}f$가 연속이고, $\nabla f (x^{\ast}) = 0$, 그리고 $\nabla f(x^{\ast})$가 양의 정부호라고 하자. 그러면 $x^{\ast}$는 엄격한 지역 최적해이다.

설명

필요조건은 $x^{\ast}$가 극값일 때 $f$가 가지는 성질에 대해 얘기한다. 충분조건은 $f$가 어떤 성질을 가질 때 $x^{\ast}$가 극값인지에 대해서 얘기한다.

증명

2계필요조건

1계필요조건에 의해 $\nabla f(x^{\ast})$가 성립하는 것은 사실이다.

나머지 내용은 귀류법으로 증명한다. $\nabla^{2} f(x^{\ast})$가 양의 준정부호가 아니라고 가정하자. 그리고 $p^{t} \nabla^{2}f(x^{\ast}) p \lt 0$을 만족하는 어떤 벡터 $p$를 선택하자. 이때 $p^{t}$는 전치행렬이다. 그러면 $\nabla^{2}f$가 $x^{\ast}$ 근방에서 연속이므로, 어떤 $s \gt 0$에 대해서 다음이 성립한다.

$$ \begin{equation} p^{t} \nabla^{2}f(x^{\ast} + \xi p) p \lt 0,\quad \forall \xi \in [0, s] \end{equation} $$

또한 다변수함수의 테일러전개공식에 의해,

$$ \begin{equation} f(x^{\ast} + \xi p) = f (x^{\ast}) + \xi p^{t} \nabla f(x^{\ast}) + \dfrac{1}{2}\xi^{2} p^{t} \nabla^{2} f(x^{\ast} + \bar{\xi} p)p,\quad \text{for some } \bar{\xi} \in (0, \xi) \end{equation} $$

그러면, $\nabla f(x^{\ast}) = 0$이므로, $(1)$과 $(2)$에 의해 다음을 얻는다.

$$ f(x^{\ast} + \xi p) \lt f (x^{\ast}), \qquad \forall \xi \in [0, s] $$

이는 $x^{\ast}$가 로컬 미니마이저라는 사실에 모순된다. 따라서 가정이 틀렸으며, $\nabla^{2} f (x^{\ast})$는 양의 준정부호 행렬이다.

■

2계충분조건

$x^{\ast}$에서 헤시안 $\nabla^{2}f$가 연속이고 양의 정부호이므로, 모든 $x \in B$에 대해서 $\nabla^{2}f (x)$가 양의 정부호가 되도록하는 오븐 볼 $B_{r} = \left\{ x : \left\| x - x^{\ast} \right\| \lt r \right\}$을 선택할 수 있다.

$$ p^{t}\nabla^{2} f(x) p \gt 0,\quad \forall p \in \mathbb{R}^{n} $$

이제 $0$이 아니고 $\left\| p \right\| \lt r$인 어떤 벡터 $p$에 대해서, 다변수함수의 테일러전개공식에 의해, 다음을 얻는다.

$$ \begin{align*} f(x^{\ast} + p) &= f(x^{\ast}) + p^{t}\nabla f(x^{\ast}) + \dfrac{1}{2}p^{t} \nabla^{2} f(x + \xi p) p,\quad \xi \in (0, 1) \\ &= f(x^{\ast}) + \dfrac{1}{2}p^{t} \nabla^{2} f(x + \xi p) p \end{align*} $$

여기서 $x^{\ast} + \xi p \in B$이므로,

$$ f(x^{\ast} + p) \gt f(x^{\ast}) $$

따라서 $x^{\ast}$는 로컬 미니마이저이다.

■

같이보기

• 1계 필요조건