优化基础系列 - 2. 无约束优化问题：一阶必要条件
0. 问题描述
这一讲关注以下问题：
无约束优化问题： \[ \begin{align} \label{eq:pblm-1} \min_{x \in \mathbb{R}^n} f(x) \end{align} \]
接下来讨论这个问题最优解需要满足的必要条件。
1. 无约束优化问题的必要条件
1.1 一阶必要条件
定理 1 （一阶必要条件）
考虑可微函数 \(f:\mathbb{R}^n\to\mathbb{R}\)。
- 如果 \(x^*\) 是 (f) 的局部极小点，即存在 \(\delta>0\) 使得 \[ \begin{align} |x-x^\ast|<\delta \ \Rightarrow\ f(x)\ge f(x^\ast), \end{align} \]
- 则 \(x^*\) 满足 \[ \begin{align} \label{eq:sln-1} \nabla f(x^*) = 0 \end{align} \]
下面分两步证明：
先证明 \(x\in\mathbb{R}\) 情形
再推广到 \(x\in\mathbb{R}^n\) 情形。
1.1.1 一维情形 \(x\in\mathbb{R}\)
已知
\(f:\mathbb{R}\to\mathbb{R}\) 在 \(x^*\) 可微
且 \(x^*\) 是局部极小点。
求证：
- \(f'(x^*)=0\)。
证明：
局部极小点的定义：存在 \(\delta>0\)，当 \(|x-x^\ast|<\delta\) 时，有 \[ f(x)\ge f(x^*). \]
对 右侧 取极限：
对所有足够小的 \(h>0\) \(x^\ast+h\) 仍在 \((x^\ast-\delta,x^\ast+\delta)\) 内，所以 \[ f(x^\ast+h)\ge f(x^\ast). \] 于是 \[ \frac{f(x^\ast+h)-f(x^\ast)}{h}\ge 0,\quad h>0. \] 令 \(h\downarrow 0\)，得到右导数 \[ \lim_{h\downarrow 0}\frac{f(x^\ast+h)-f(x^\ast)}{h}\ \ge\ 0. \]
对 左侧 取极限： 对所有足够小的 \(h<0\)，同样有 \[ f(x^\ast+h)\ge f(x^\ast), \] 但此时 \(h<0\)，所以 \[ \frac{f(x^\ast+h)-f(x^\ast)}{h}\le 0,\quad h<0, \] 令 \(h\uparrow 0\)，得到左导数 \[ \lim_{h\uparrow 0}\frac{f(x^\ast+h)-f(x^\ast)}{h}\ \le\ 0. \]
由于 \(f(\cdot)\) 在 \(x^*\) 可微，左右导数相等，都等于 \(f'(x^*)\)。于是 \[ 0\le f'(x^\ast)\le 0 \quad\Rightarrow\quad f'(x^\ast)=0. \]
一维情形得证。
1.1.2 多维情形 \(x\in\mathbb{R}^n\)
现在设 \(f:\mathbb{R}^n\to\mathbb{R}\) 在 \(x^*\) 可微，且 \(x^*\) 是局部极小点。
思路：
沿任意方向 \(d\) 看一条“截面函数” \[ \varphi_d(t)=f(x^\ast+t d). \]
由于 \(x^*\) 是局部极小点，在 \(t=0\) 处，这个一维函数也有局部极小值，于是一维结果告诉我们 \(\varphi_d'(0)=0\)。
另一方面，由链式法则 \[ \varphi_d'(0)=\nabla f(x^\ast)^\top d. \] 所以对所有方向 \(d\) 都为 0，只能说明 \(\nabla f(x^\ast)=0\)。
下面将证明过程写得严谨一点。
证明：
方向函数的局部极小性质
取任意方向 \(d\in\mathbb{R}^n\)，且 \(d\neq 0\)。定义一维函数 \[
\varphi(t)=f(x^\ast+t d),\quad t\in\mathbb{R}.
\]
因为 \(x^*\) 是局部极小点，存在 \(\delta>0\)，当 \(|x-x^\ast|<\delta\) 时 \(f(x)\ge f(x^\ast)\)。对足够小的 \(t\)，例如 \(|t|<\delta/|d|\)，有 \[
|x^\ast+t d-x^\ast| = |t||d| <\delta
\] 从而 \[
\varphi(t)=f(x^\ast+t d)\ge f(x^\ast)=\varphi(0).
\] 因此，\(t=0\) 是一维函数 \(\varphi\) 的局部极小点。
利用一维结论计算方向导数
因为 \(f\) 在 \(x^\ast\) 可微，按链式法则，\(\varphi\) 在 \(0\) 处可导，并且 \[
\varphi'(0)=\nabla f(x^\ast)^\top d.
\]
另一方面，由第一步的一维结论： “若一维函数在点 0 有局部极小值且可导，则导数为 0”。 应用到 \(\varphi\) 上，得到 \[
\varphi'(0)=0.
\]
于是对任意方向 \(d\)，都有 \[
\nabla f(x^\ast)^\top d = 0.
\]
推出梯度为零
现在我们有：对所有 (d^n)， \[
\nabla f(x^\ast)^\top d = 0.
\]
特别地，如果我们令 \(d\) 取标准基向量 \(e_1,\dots,e_n\)，得到 \[
\nabla f(x^\ast)^\top e_i = 0,\quad i=1,\dots,n.
\] 但 \(\nabla f(x^\ast)^\top e_i\) 恰好是 \(\nabla f(x^*)\) 的第 \(i\) 个分量，所以每个分量都为 0，于是 \[
\nabla f(x^\ast)=0.
\]
定理证明完毕。
证明：
方向函数的局部极小性质
取任意方向 \(d\in\mathbb{R}^n\)，且 \(d\neq 0\)。定义一维函数 \[ \varphi(t)=f(x^\ast+t d),\quad t\in\mathbb{R}. \]
因为 \(x^*\) 是局部极小点，存在 \(\delta>0\)，当 \(|x-x^\ast|<\delta\) 时 \(f(x)\ge f(x^\ast)\)。对足够小的 \(t\)，例如 \(|t|<\delta/|d|\)，有 \[ |x^\ast+t d-x^\ast| = |t||d| <\delta \] 从而 \[ \varphi(t)=f(x^\ast+t d)\ge f(x^\ast)=\varphi(0). \] 因此，\(t=0\) 是一维函数 \(\varphi\) 的局部极小点。
利用一维结论计算方向导数
因为 \(f\) 在 \(x^\ast\) 可微，按链式法则，\(\varphi\) 在 \(0\) 处可导，并且 \[ \varphi'(0)=\nabla f(x^\ast)^\top d. \]
另一方面，由第一步的一维结论： “若一维函数在点 0 有局部极小值且可导，则导数为 0”。 应用到 \(\varphi\) 上，得到 \[ \varphi'(0)=0. \]
于是对任意方向 \(d\)，都有 \[ \nabla f(x^\ast)^\top d = 0. \]
推出梯度为零
现在我们有：对所有 (d^n)， \[ \nabla f(x^\ast)^\top d = 0. \]
特别地，如果我们令 \(d\) 取标准基向量 \(e_1,\dots,e_n\)，得到 \[ \nabla f(x^\ast)^\top e_i = 0,\quad i=1,\dots,n. \] 但 \(\nabla f(x^\ast)^\top e_i\) 恰好是 \(\nabla f(x^*)\) 的第 \(i\) 个分量，所以每个分量都为 0，于是 \[ \nabla f(x^\ast)=0. \]
定理证明完毕。
总结一句话：
- 局部极小点沿任意方向都不能“立即下降”，
- ⇒ 所有方向导数都为 0，
- ⇒ 方向导数用内积写就是 (f( x^* ) ^d)，
- ⇒ 对任意 (d) 内积为 0，只能是梯度本身为 0。
这就是“无约束极小点 ⇒ 驻点（梯度为零）”的一阶必要条件。