机器学习笔记之最优化理论与方法——无约束优化问题[最优性条件]
引言
本节将介绍无约束优化问题，主要介绍无约束优化问题最优解的相关性质。
无约束优化问题
无约束优化问题的数学符号表示如下：
仅需要对目标函数进行最小化，没有可行域的条件限制。
min f ( x ) \min f(x) minf(x)
在实际问题中，很多问题可以被建模成无约束优化问题。例如：线性回归方法中的最小二乘估计问题。对应数学符号表示如下：
很明显，最小二乘函数 ∥ A x − b ∥ 2 2 \|\mathcal A x - b\|_2^2 ∥Ax−b∥22明显是一个凸函数：其二次型系数矩阵 A T A \mathcal A^T\mathcal A ATA必然是半正定矩阵。
f ( x ) = ∥ A x − b ∥ 2 2 = ( A x − b ) T ( A x − b ) = x T [ A T A ] x + b T A x − x T A T b + b T b \begin{aligned} f(x) & = \|\mathcal Ax - b\|_2^2 \\ & = (\mathcal Ax - b)^T(\mathcal Ax - b) \\ & = x^T [\mathcal A^T\mathcal A] x + b^T \mathcal A x - x^T \mathcal A^T b + b^Tb \end{aligned} f(x)=∥Ax−b∥22=(Ax−b)T(Ax−b)=xT[ATA]x+bTAx−xTATb+bTb
因而该问题可以更精确地描述为无约束凸优化问题。
min ∥ A x − b ∥ 2 2 \min \|\mathcal A x - b\|_2^2 min∥Ax−b∥22
可以采用适当方法将约束优化问题转换为无约束优化问题。例如最优化问题概述中提到的罚函数法。
无约束优化问题最优解的定义
- 局部最优解 ：假设 x ˉ \bar{x} xˉ是关于目标函数 f ( ⋅ ) f(\cdot) f(⋅)无约束优化问题的局部最优解，对于 ∀ x ∈ N ϵ ( x ˉ ) \forall x \in \mathcal N_\epsilon(\bar{x}) ∀x∈Nϵ(xˉ)，必然有：
其中N ϵ ( x ˉ ) \mathcal N_{\epsilon}(\bar{x}) Nϵ(xˉ)表示包含点x ˉ \bar{x} xˉ，并且使用ϵ \epsilon ϵ表示范围的邻域。例如:( x ˉ − ϵ , x ˉ + ϵ ) (\bar{x} - \epsilon,\bar{x} + \epsilon) (xˉ−ϵ,xˉ+ϵ)
f ( x ) ≥ f ( x ˉ ) f(x) \geq f(\bar{x}) f(x)≥f(xˉ) - 全局最优解：相比于局部最优解，假设 x ∗ x^* x∗是关于目标函数 f ( ⋅ ) f(\cdot) f(⋅)无约束优化问题的全局最优解，对于 ∀ x ∈ R n \forall x \in \mathbb R^n ∀x∈Rn，必然有：
f ( x ) ≥ f ( x ∗ ) f(x) \geq f(x^*) f(x)≥f(x∗) - 严格最优解：与凸函数：定义与基本性质中提到的严格凸函数类似，其核心是消除掉取等的情况。关于严格最优解，同样可以分为严格局部最优解与严格全局最优解。对应数学符号表示如下：
{ ∀ x ∈ R n , x ≠ x ∗ ⇒ f ( x ) > f ( x ∗ ) ∀ x ∈ N ϵ ( x ˉ ) , x ≠ x ˉ ⇒ f ( x ) > f ( x ˉ ) \begin{cases} \forall x \in \mathbb R^n,x \neq x^* \Rightarrow f(x) > f(x^*) \\ \forall x \in \mathcal N_{\epsilon}(\bar{x}), x \neq \bar{x} \Rightarrow f(x) > f(\bar{x}) \end{cases} {∀x∈Rn,x=x∗⇒f(x)>f(x∗)∀x∈Nϵ(xˉ),x=xˉ⇒f(x)>f(xˉ)
对应图像表示如下：
根据凸函数的定义可以看出， f ( ⋅ ) , G ( ⋅ ) f(\cdot),\mathcal G(\cdot) f(⋅),G(⋅)都是凸函数。其中 f ( ⋅ ) f(\cdot) f(⋅)中描述的红色点是严格最优解；而红色点 G ( x ∗ ) \mathcal G(x^*) G(x∗)是最优解的条件下， ∃ x ≠ x ∗ ⇒ f ( x ) = f ( x ∗ ) \exist x \neq x^* \Rightarrow f(x) = f(x^*) ∃x=x∗⇒f(x)=f(x∗)。那么该函数的最优解不是严格最优解。
无约束优化问题的最优性条件
针对无约束优化问题 ⇒ min f ( x ) \Rightarrow \min f(x) ⇒minf(x)：
无约束优化问题的充要条件
如果目标函数 f ( x ) f(x) f(x)是凸函数，则存在如下等价条件：
关于无约束凸优化问题,详细解释见最优化理论与方法——凸优化问题(上),这里不再赘述。
x ∗ is Optimal ⇔ ∇ f ( x ∗ ) = 0 x^* \text{ is Optimal } \Leftrightarrow \nabla f(x^*) = 0 x∗ is Optimal ⇔∇f(x∗)=0
无约束优化问题的必要条件
如果目标函数 f ( x ) f(x) f(x)不是凸函数，只是一般函数，上述的充要条件不一定成立，但一定满足如下必要条件：
如果x ∗ x^* x∗是最优解，那么它一定是平稳点；如果f ( ⋅ ) f(\cdot) f(⋅)在x ∗ x^* x∗位置的Hessian Matrix ⇒ ∇ 2 f ( x ∗ ) \text{Hessian Matrix} \Rightarrow \nabla^2 f(x^*) Hessian Matrix⇒∇2f(x∗)存在，那么该矩阵至少是半正定矩阵；如果将f ( ⋅ ) f(\cdot) f(⋅)退化成一元函数,必然有：f ′ ′ ( x ∗ ) ≥ 0 f''(x^*) \geq 0 f′′(x∗)≥0。
x ∗ is Optimal ⇒ { ∇ f ( x ∗ ) = 0 ∇ 2 f ( x ∗ ) ≽ 0 x^* \text{ is Optimal } \Rightarrow \begin{cases} \nabla f(x^*) = 0 \\ \nabla^2 f(x^*) \succcurlyeq 0 \end{cases} x∗ is Optimal ⇒{∇f(x∗)=0∇2f(x∗)≽0
证明：
- 已知 x ∗ x^* x∗是最优解，不妨设： ∇ f ( x ∗ ) ≠ 0 \nabla f(x^*) \neq 0 ∇f(x∗)=0，必然存在负梯度方向： d = − ∇ f ( x ∗ ) d = - \nabla f(x^*) d=−∇f(x∗)。
以 x ∗ x^* x∗为起始点，沿着负梯度方向前进较小的一段距离： f ( x ∗ + λ ⋅ d ) f(x^* + \lambda \cdot d) f(x∗+λ⋅d)，并将其进行泰勒展开：
思路：前进一小段距离后，必然会导致目标函数值下降;从而x ∗ x^* x∗不是最优解了，产生矛盾。
f ( x ∗ + λ ⋅ d ) = f ( x ∗ ) + 1 1 ! λ [ ∇ f ( x ∗ ) ] T d + O ( λ ∥ d ∥ ) λ ∈ ( 0 , 1 ) f(x^* + \lambda \cdot d) = f(x^*) + \frac{1}{1!} \lambda [\nabla f(x^*)]^Td + \mathcal O(\lambda \|d\|) \quad \lambda \in (0,1) f(x∗+λ⋅d)=f(x∗)+1!1λ[∇f(x∗)]Td+O(λ∥d∥)λ∈(0,1)
经过整理，有：
关于λ \lambda λ范围后面不再赘述。
f ( x ∗ + λ ⋅ d ) − f ( x ∗ ) λ = [ ∇ f ( x ∗ ) ] T d + O ( λ ∥ d ∥ ) λ \frac{f(x^* + \lambda \cdot d) - f(x^*)}{\lambda} = [\nabla f(x^*)]^T d + \frac{\mathcal O(\lambda \|d\|)}{\lambda} λf(x∗+λ⋅d)−f(x∗)=[∇f(x∗)]Td+λO(λ∥d∥)
将 d = − ∇ f ( x ∗ ) d = -\nabla f(x^*) d=−∇f(x∗)代入，必然有：
[ ∇ f ( x ∗ ) ] T d = − ∣ ∣ ∇ f ( x ∗ ) ∣ ∣ 2 < 0 [\nabla f(x^*)]^T d = - ||\nabla f(x^*)||^2 < 0 [∇f(x∗)]Td=−∣∣∇f(x∗)∣∣2<0
当 λ ⇒ 0 \lambda \Rightarrow 0 λ⇒0时，有：
lim λ ⇒ 0 f ( x ∗ + λ ⋅ d ) − f ( x ∗ ) λ = lim λ ⇒ 0 { [ ∇ f ( x ∗ ) ] T d ⏟ < 0 + O ( λ ⋅ ∥ d ∥ ) λ ⏟ = 0 } < 0 \mathop{\lim}\limits_{\lambda \Rightarrow 0} \frac{f(x^* + \lambda \cdot d) - f(x^*)}{\lambda} = \mathop{\lim}\limits_{\lambda \Rightarrow 0} \left\{\underbrace{[\nabla f(x^*)]^T d}_{< 0} + \underbrace{\frac{\mathcal O(\lambda \cdot \|d\|)}{\lambda}}_{=0}\right\} < 0 λ⇒0limλf(x∗+λ⋅d)−f(x∗)=λ⇒0lim⎩ ⎨ ⎧<0 [∇f(x∗)]Td+=0 λO(λ⋅∥d∥)⎭ ⎬ ⎫<0
从而：
lim λ ⇒ 0 f ( x ∗ + λ ⋅ d ) − f ( x ∗ ) λ < 0 ⇒ lim λ ⇒ 0 f ( x ∗ + λ ⋅ d ) < f ( x ∗ ) \mathop{\lim}\limits_{\lambda \Rightarrow 0} \frac{f(x^* + \lambda \cdot d) - f(x^*)}{\lambda} < 0 \Rightarrow \mathop{\lim}\limits_{\lambda \Rightarrow 0} f(x^* + \lambda \cdot d) < f(x^*) λ⇒0limλf(x∗+λ⋅d)−f(x∗)<0⇒λ⇒0limf(x∗+λ⋅d)<f(x∗)
此时，发现了存在比 f ( x ∗ ) f(x^*) f(x∗)还要小的函数值 f ( x ∗ + λ ⋅ d ) f(x^* + \lambda \cdot d) f(x∗+λ⋅d)，这意味着： x ∗ x^* x∗不是最优解。与条件矛盾，得证。也将 ∇ f ( x ∗ ) = 0 \nabla f(x^*) = 0 ∇f(x∗)=0称作一般函数 f ( ⋅ ) f(\cdot) f(⋅) x ∗ x^* x∗是最优解的一阶必要条件。 - 二阶必要条件证明：已知 x ∗ x^* x∗是最优解，必然有： ∇ f ( x ∗ ) = 0 \nabla f(x^*) = 0 ∇f(x∗)=0。假设 x ∗ x^* x∗位置的 Hessian Matrix ⇒ ∇ 2 f ( x ∗ ) \text{Hessian Matrix} \Rightarrow \nabla^2 f(x^*) Hessian Matrix⇒∇2f(x∗)低于半正定矩阵，必然有：
∃ d ≠ 0 ⇒ d T ∇ 2 f ( x ∗ ) d < 0 \exist d \neq 0 \Rightarrow d^T \nabla^2 f(x^*) d < 0 ∃d=0⇒dT∇2f(x∗)d<0
以 x ∗ x^* x∗为起始点， d d d为下降方向前进较小的一段距离： f ( x ∗ + λ ⋅ d ) f(x^* + \lambda \cdot d) f(x∗+λ⋅d)，并将其进行泰勒展开：
与平稳点的证明相似，只不过需要二阶泰勒展开~
f ( x ∗ + λ ⋅ d ) = f ( x ∗ ) + 1 1 ! λ ⋅ [ ∇ f ( x ∗ ) ] T ⏟ = 0 d + 1 2 ! λ ⋅ d T ∇ 2 f ( x ∗ ) d + O ( λ 2 ⋅ ∥ d ∥ 2 ) = f ( x ∗ ) + 1 2 ! λ ⋅ d T ∇ 2 f ( x ∗ ) d + O ( λ 2 ⋅ ∥ d ∥ 2 ) \begin{aligned} f(x^* + \lambda \cdot d) & = f(x^*) + \frac{1}{1!} \lambda \cdot \underbrace{[\nabla f(x^*)]^T}_{=0}d + \frac{1}{2!} \lambda \cdot d^T \nabla^2 f(x^*) d + \mathcal O(\lambda^2 \cdot \|d\|^2) \\ & = f(x^*) + \frac{1}{2!} \lambda \cdot d^T \nabla^2 f(x^*) d + \mathcal O(\lambda^2 \cdot \|d\|^2) \end{aligned} f(x∗+λ⋅d)=f(x∗)+1!1λ⋅=0 [∇f(x∗)]Td+2!1λ⋅dT∇2f(x∗)d+O(λ2⋅∥d∥2)=f(x∗)+2!1λ⋅dT∇2f(x∗)d+O(λ2⋅∥d∥2)
经过整理，并令 λ ⇒ 0 \lambda \Rightarrow 0 λ⇒0，有：
lim λ ⇒ 0 f ( x ∗ + λ ⋅ d ) − f ( x ∗ ) λ 2 = 1 2 d T ∇ 2 f ( x ∗ ) d ⏟ < 0 + O ( λ 2 ⋅ ∥ d ∥ 2 ) λ 2 ⏟ = 0 < 0 \mathop{\lim}\limits_{\lambda \Rightarrow 0} \frac{f(x^* + \lambda \cdot d) - f(x^*)}{\lambda^2} = \frac{1}{2}\underbrace{d^T \nabla^2 f(x^*) d}_{<0} + \underbrace{\frac{\mathcal O(\lambda^2 \cdot \|d\|^2)}{\lambda^2}}_{=0} < 0 λ⇒0limλ2f(x∗+λ⋅d)−f(x∗)=21<0 dT∇2f(x∗)d+=0 λ2O(λ2⋅∥d∥2)<0
从而 f ( x ∗ + λ ⋅ d ) < f ( x ∗ ) f(x^* + \lambda \cdot d) < f(x^*) f(x∗+λ⋅d)<f(x∗)，从而与条件矛盾。因此：最优解 x ∗ x^* x∗对应的 ∇ 2 f ( x ∗ ) ≽ 0 \nabla^2 f(x^*) \succcurlyeq 0 ∇2f(x∗)≽0恒成立。
相反，如果存在某点 x ∗ x^* x∗，使得： ∇ f ( x ∗ ) = 0 \nabla f(x^*) = 0 ∇f(x∗)=0且 ∇ 2 f ( x ∗ ) ≽ 0 \nabla^2 f(x^*) \succcurlyeq 0 ∇2f(x∗)≽0，那么点 x ∗ x^* x∗是否为最优解 ? ? ?不一定。例如： f ( x ) = x 3 f(x) = x^3 f(x)=x3，其函数图像表示如下：
在 x = 0 x = 0 x=0处的梯度 ∇ f ( x ) ∣ x = 0 = 0 \nabla f(x)|_{x=0} = 0 ∇f(x)∣x=0=0；二阶梯度 ∇ 2 f ( x ) ∣ x = 0 = 0 \nabla^2 f(x) |_{x = 0} = 0 ∇2f(x)∣x=0=0，均满足条件；但该点是一个鞍点，而不是最优解点。
无约束优化问题的充分条件
如果 f ( ⋅ ) f(\cdot) f(⋅)不是凸函数，只是一般函数，如果存在某点 x ∗ x^* x∗，满足： ∇ f ( x ∗ ) = 0 , ∇ 2 f ( x ∗ ) ≻ 0 \nabla f(x^*) =0,\nabla^2 f(x^*) \succ 0 ∇f(x∗)=0,∇2f(x∗)≻0，那么 x ∗ x^* x∗是严格最优解；
其中∇ 2 f ( x ∗ ) ≻ 0 \nabla^2 f(x^*) \succ 0 ∇2f(x∗)≻0表示函数f ( ⋅ ) f(\cdot) f(⋅)在x ∗ x^* x∗点处的Hessian Matrix \text{Hessian Matrix} Hessian Matrix是正定矩阵。需要注意的是，这里的严格最优解可能是严格局部最优解或者严格全局最优解。
证明：
要证上式，即证： ∀ x ∈ N ϵ ( x ∗ ) , f ( x ∗ ) < f ( x ) \forall x \in \mathcal N_{\epsilon}(x^*),f(x^*) < f(x) ∀x∈Nϵ(x∗),f(x∗)<f(x)。
- 以 x ∗ x^* x∗为起始点，朝着任意方向 d d d前进较小的距离，得到新的函数结果： f ( x ∗ + λ ⋅ d ) f(x^* + \lambda \cdot d) f(x∗+λ⋅d)。观察： f ( x ∗ + λ ⋅ d ) f(x^* + \lambda \cdot d) f(x∗+λ⋅d)与 f ( x ∗ ) f(x^*) f(x∗)之间的大小情况。使用泰勒公式展开：
为了简单起见，仅关注d d d的方向，而令d d d大小∥ d ∥ = 1 \|d\| = 1 ∥d∥=1
f ( x ∗ + λ ⋅ d ) = f ( x ∗ ) + 1 1 ! λ ⋅ [ ∇ f ( x ∗ ) ] T ⏟ = 0 d + 1 2 ! λ 2 d T ∇ 2 f ( x ∗ ) ⏟ ≻ 0 d + O ( λ 2 ) ∥ d ∥ 2 = 1 f(x^* + \lambda \cdot d) = f(x^*) + \frac{1}{1!} \lambda \cdot\underbrace{[\nabla f(x^*)]^T}_{=0} d + \frac{1}{2!} \lambda^2 d^T \underbrace{\nabla^2 f(x^*)}_{\succ 0}d + \mathcal O(\lambda^2) \quad \|d\|^2 = 1 f(x∗+λ⋅d)=f(x∗)+1!1λ⋅=0 [∇f(x∗)]Td+2!1λ2dT≻0 ∇2f(x∗)d+O(λ2)∥d∥2=1
整理上式，观察 f ( x ∗ + λ ⋅ d ) − f ( x ∗ ) f(x^* + \lambda \cdot d) - f(x^*) f(x∗+λ⋅d)−f(x∗)结果：
lim λ ⇒ 0 f ( x ∗ + λ ⋅ d ) − f ( x ∗ ) λ 2 = 1 2 d T ∇ 2 f ( x ∗ ) d > 0 \mathop{\lim}\limits_{\lambda \Rightarrow 0} \frac{f(x^* + \lambda \cdot d) - f(x^*)}{\lambda^2} = \frac{1}{2}d^T \nabla^2 f(x^*) d > 0 λ⇒0limλ2f(x∗+λ⋅d)−f(x∗)=21dT∇2f(x∗)d>0
从而 f ( x ∗ + λ ⋅ d ) > f ( x ∗ ) f(x^* + \lambda \cdot d) > f(x^*) f(x∗+λ⋅d)>f(x∗)。这意味着：在 x ∗ x^* x∗范围的小的邻域内， f ( x ∗ ) f(x^*) f(x∗)是最小值，并且是严格最小值，得证。
Reference \text{Reference} Reference：
最优化理论与方法-第五讲-无约束优化问题（一）