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

令 $f: \mathbb{R}^n \to \mathbb{R}$ 且 $S \subset \mathbb{R}^n$ 為 feasible set，現在我們考慮以下的 有限維度 (無拘束)最佳化問題
\[\begin{gathered}
  \min f\left( {\mathbf{x}} \right) \hfill \\
  s.t.{\mathbf{x}} \in S \subseteq {R^n} \hfill \\
\end{gathered} \]
我們想知道上述最佳化問題是否有解？ 若有解則是哪一種解 e.g., 局部最佳解(local optimum)或者 全域最佳解(global optimum)？)，以及上述的解是否能夠透過某種方法來將其描述。

對於上述有限維度最佳解的存在性問題一般可由 Weierstrass Extremum Theorem處理，在此不做贅述。以下我們討論 最佳解 存在的必要條件：更近一步地說是 最佳化理論中的求取 "局部最佳解" 的一階必要條件，在給出結果之前我們首先定義 可行方向 (Feasible Direction)如下：

======================
Definition: Feasible Direction
給定 ${\bf x} \in S \subset \mathbb{R}^n$，我們說向量 ${\bf d} \in \mathbb{R}^n$ 為 在 ${\bf x}$ 處的可行方向 (feasible direction) 若下列條件成立：存在常數 $ \bar \theta >0$ 使得對任意 $\theta \in [0, \bar\theta]$而言，
\[
{\bf x} + \theta {\bf d} \in S
\]======================

有了以上的可行方向的想法，其局部最佳解的一階必要條件有如下陳述：

======================
Theorem: (First Order Necessary Condition, FONC): 令 $S \subset \mathbb{R}^n$ 且 $f \in C^1$ on $S$ ( $f$為一階可導且導數連續)。若 ${\bf x}^*$ 為 局部極小解 (local minimum point) of $f$ over $S$ 則 對任意在 ${\bf x}^*$點上的可行方向 ${\bf d} \in \mathbb{R}^n$，我們有
\[
\nabla f({\bf x}^*) \cdot {\bf d} \geq 0
\]======================

Proof: 用反證法：假設存在 對 ${\bf x}^*$點上的可行方向 ${\bf d} \in \mathbb{R}^n$ 使得
\[
\nabla f({\bf x}^*) \cdot {\bf d} <0
\]我們要證明矛盾。由 ${\bf d}$為可行方向之定義可知： 存在 $\bar \theta>0$ 使得 對任意 $\theta \in [0, \bar\theta]$而言，
\[
{\bf x}(\theta) = {\bf x}^* + \theta {\bf d} \in S
\]現在利用 Taylor 定理對 ${\bf x}^*$ 展開 且利用已知假設 $\nabla f({\bf x}^*) \cdot {\bf d} <0$ 可得
\begin{align*}
  f({\bf x}(\theta )) &= f({{\bf x}^*}) + \nabla f({{\bf x}^*})({\bf x}(\theta ) - {{\bf x}^*}) + o(||{\theta}||) \hfill \\
   &= f({{\bf x}^*}) + \nabla f({ {\bf x}^*})\theta {\bf d} + o(||{\theta}||) \hfill \\
  &= f({{\mathbf{x}}^*}) + \theta \underbrace {\nabla f({{\mathbf{x}}^*}) \cdot {\mathbf{d}}}_{ < 0} + o(||\theta ||)\\
   &< f({{\bf x}^*}) \hfill \\
\end{align*} 上述最後一條不等式當 $\theta$ 足夠小的時候成立。此與我們假設 $ f({ {\bf x}^*})$最小 矛盾。$\square$


Comments:
1. 上述一階必要條件說明了若我們已經處在局部最佳解的位置 ${\bf x}^*$ 則 沿著任何其他可行方向移動都會增加 目標函數值，亦即 \[
\nabla f({\bf x}^*) \cdot {\bf d} \geq  0
\]
2. 關於上述使用的 Taylor Theorem 與 little-oh 符號可以參考下方補充說明或者BLOG其餘相關文章。
3. 上述 一階必要條件 使用到了 Taylor Theorem 的一階項，一般而言可視為對 ${\bf x}^*$ 的 一階近似估計。


若為無拘束情況，則我們有以下的衍生結果：

=======================
Corollary: 令 $S \subset \mathbb{R}^n$ 且 $f \in C^1$ on $S$。若 ${\bf x}^*$ 為 local minimum point of $f$ over $S$ 且若 ${\bf x}^*$ 為 $S$ 的 interior point 則
\[
\nabla f({\bf x}^*) = {\bf 0}
\]=======================

Proof Sketch: 設 ${\bf x}^*$ 為 local minimum point of $f$ over $S$ 則由 FONC可知 對任意 ${\bf d} \in \mathbb{R}^n$ 為在 ${\bf x}^*$點上的可行方向，我們有
\[
\nabla f({\bf x}^*) \cdot {\bf d} \geq 0
\]但因為 若 ${\bf x}^*$ 為 $S$ 的 interior point 故在該點${\bf x}^*$ 之可行方向 ${\bf d}$ 可在足夠小的區域選為任意方向來移動， 若 ${\bf d} \neq {\bf 0}$ 則 為了使 $\nabla f({\bf x}^*) \cdot {\bf d} = 0$ 成立，我們必定要求
\[
\nabla f({\bf x}^*)  = {\bf 0} \;\;\;\; \square
\]

Comments:
1. 上述 FONC 無拘束情況的 FONC 將原本最佳問題轉成求解有 $n$ 未知數的 $n$ 個系統方程問題。

2. 上述結果只保證 局部最佳解 的必要條件，如果想要得到充分條件，通常需要 $f$ 的二階導數的資訊也就是 需要 Hessian matrix，一般稱作 Second-Order Sufficient Condition我們在以後的文章會在提及。

3. 局部最佳解落在集合 $S$ 上，若此集合為 convex 集合且 $f$ 為凸函數，則局部最佳解 為 全域最佳解，相關結果可翻閱本 BLOG關於最佳化與凸分析的文章。

4. 上述最佳化問題可以與 變分不等式問題 (Variational Inequality Problem)等價，以下給出此結果：

=======================
Corollary 2: Relationship Between Optimization and Variational Inequality
令 $S \subset \mathbb{R}^n$ 為 convex 且 $f : \mathbb{R}^n \to \mathbb{R}$ 且 $f \in C^1(S)$。若 ${\bf x}^*$ 為 local minimum point of $f$ over $S$，則 ${\bf x}^*$ 為下列變分不等式問題的解：求 ${\bf x} \in S$ 使得 對任意 ${\bf x}' \in S$ 而言，
\[
\langle {\bf x}' - {\bf x}, \nabla f({\bf x}) \rangle \geq 0
\]=======================
Proof:
取 ${\bf d} := {\bf x}' - {\bf x}$ 即可。



補充定理
==================
Taylor Theorem with Little-oh Notation:
假設 $X \subset \mathbb{R}^n$ 為 open，且 ${\bf x} \in X$ 與 $f: X \to \mathbb{R}$ 為 $C^1$。則
\[
f({\bf x}+{\bf h}) = f({\bf x}) + Df({\bf x}) {\bf h} + o(||{\bf h}||),\;\;\; ||h|| \to 0
\]==================