[最佳化理論] 有限維空間 無拘束最佳化問題 的二階充分必要條件

回顧先前我們討論過的一階必要條件，以下我們介紹有限維空間 無拘束最佳化問題的 二階必要與充分條件，首先是二階必要條件：

====================
Theorem: Second-Order Necessary Condition, SONC:
令 $S \subset \mathbb{R}^n$ 且令 $f \in C^2(S)$。若 ${\bf x}^*$ 為 local minimum point of $f$ over $S$ 則 對 在點 ${\bf x}^*$的任意可行方向 ${\bf d} \in \mathbb{R}^n$，我們有
1. $\nabla f({\bf x}^*) \cdot {\bf d} \geq 0$
2. 若 $\nabla f({\bf x}^*) \cdot {\bf d} =0$ 則 ${\bf d}^T \nabla^2 f({\bf x}^*) {\bf d} \geq 0$
====================

Proof: 由於 ${\bf x}^*$ 為 local minimum point of $f$ over $S$ 對條件 1 自動成立。我們僅需證明條件2。令  ${\bf d} \in \mathbb{R}^n$ 為 在點 ${\bf x}^*$的任意可行方向，故存在 $\bar \alpha >0$ 使得
\[
{\bf x}(\alpha) := {\bf x}^* + \alpha {\bf d} \in S, \;\;\; \alpha \in [0, \bar \alpha]
\] 利用 Taylor Theorem 對 ${\bf x}^*$ 展開到二階項，我們可得
\begin{align*}
  f\left( {{\mathbf{x}}\left( \alpha  \right)} \right)
&= f\left( {{{\mathbf{x}}^*}} \right) + \nabla f\left( {{{\mathbf{x}}^*}} \right)\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right) \\
& \hspace{10mm}+ \frac{1}{2}{\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right)^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right)\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right) + o\left( {{{\left\| \alpha  \right\|}^2}} \right) \hfill \\
 &  = f\left( {{{\mathbf{x}}^*}} \right) + \alpha \nabla f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}} + \frac{1}{2}{\alpha ^2}{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}} + o\left( {{{\left\| \alpha  \right\|}^2}} \right) \hfill \\
\end{align*} 若 $\nabla f({\bf x}^*) \cdot {\bf d} =0$，則上式變成
\[\begin{gathered}
  f\left( {{\mathbf{x}}\left( \alpha  \right)} \right) = f\left( {{{\mathbf{x}}^*}} \right) + \alpha \underbrace {\nabla f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}}}_{ = 0} + \frac{1}{2}{\alpha ^2}{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}} + o\left( {{{\left\| \alpha  \right\|}^2}} \right) \hfill \\
   = f\left( {{{\mathbf{x}}^*}} \right) + \frac{1}{2}{\alpha ^2}{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}} + o\left( {{{\left\| \alpha  \right\|}^2}} \right) \hfill \\
\end{gathered} \]注意到若 ${{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}}<0$ 對在 ${\bf x}^*$任意足夠小的鄰域成立，則我們得到
\[f\left( {{\mathbf{x}}\left( \alpha  \right)} \right) \leqslant f\left( {{{\mathbf{x}}^*}} \right) \]此與 ${\bf x}^*$是 local minimum 矛盾，故
\[{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}}\geq 0\;\;\;\;\; \square\]

Comments:
讀者大概不難發現不論是一階 或者 二階 條件都是依賴 Taylor 定理展開式，依此來進行估計。


====================
Theorem: Second-Order Sufficient Condition, SOSC: 
令 $S \subset \mathbb{R}^n$ 且令 $f \in C^2(S)$。若 ${\bf x}^* \in S$ 為interior point 且$f$ 在該點有定義。若
1. $\nabla f({\bf x}^*) = {\bf 0}$
2. 對任意 ${\bf d} \in \mathbb{R}^n$，${\bf d}^T \nabla^2 f({\bf x}^*) {\bf d} >0$ (亦即 $\nabla^2 f({\bf x}^*)$ 為 positive definite)，則 ${\bf x}^*$ 為 strict local minimum of $f$。
====================

Proof: 要證明 ${\bf x}^*$ 為 strict local minimum of $f$，我們僅需證明
\[
f({\bf x}) > f({\bf x^*}),\;\;\; {\bf x} \in \mathcal{N}({\bf x}^*)
\]其中 $\mathcal{N}({\bf x}^*)$為以 ${\bf x}^*$為中心所成之鄰域。故令  ${\bf d} \in \mathbb{R}^n$ 為 在點 ${\bf x}^*$的任意可行方向，故存在 $\bar \alpha >0$ 使得
\[
{\bf x}(\alpha) := {\bf x}^* + \alpha {\bf d} \in \mathcal{N}({\bf x}^*), \;\;\; \alpha \in [0, \bar \alpha]
\] 利用 $\nabla f({\bf x}^*) = {\bf 0}$ 與 Taylor Theorem 對 ${\bf x}^*$ 展開到二階項，我們可得
\begin{align*}
  f\left( {{\mathbf{x}}\left( \alpha  \right)} \right)
&= f\left( {{{\mathbf{x}}^*}} \right) + \nabla f\left( {{{\mathbf{x}}^*}} \right)\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right) \\
& \hspace{10mm}+ \frac{1}{2}{\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right)^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right)\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right) + o\left( {{{\left\| \alpha  \right\|}^2}} \right) \hfill \\
 &  =f\left( {{{\mathbf{x}}^*}} \right) + \frac{1}{2}{\alpha ^2}\underbrace {{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}}}_{ > 0} + o\left( {{{\left\| \alpha  \right\|}^2}} \right)\\
\end{align*}
在 ${\bf x}^*$ 附近鄰域而言，我們可推知
\[\begin{gathered}
  f\left( {{\mathbf{x}}\left( \alpha  \right)} \right) - f\left( {{{\mathbf{x}}^*}} \right) = \frac{1}{2}{\alpha ^2}\underbrace {{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}}}_{ > 0} > 0 \hfill \\
\end{gathered} \]則 ${\bf x}^*$ 為 strict local minimum of $f$ 。$\square$