无约束最优性条件

Views: --

无约束最优性条件回答的是：在一个内点附近，若任何方向都不能让目标下降，函数的导数必须长什么样。

方向导数

沿方向 dd 的一维函数

ϕ(t)=f(x+td)\phi(t)=f(x+td)

满足

ϕ′(0)=∇f(x)Td.\phi'(0)=\nabla f(x)^Td.

若这个内积小于零，dd 是严格下降方向；若大于零，−d-d 是下降方向。只要 ∇f(x)≠0\nabla f(x)\ne0，取 d=−∇f(x)d=-\nabla f(x) 就一定下降。

一阶必要条件

若 ff 可微，x∗x^* 是无约束局部极小点，则

∇f(x∗)=0.\nabla f(x^*)=0.

证明：若梯度非零，沿负梯度方向的小步会降低目标，矛盾。

满足梯度为零的点叫驻点，不一定是极小点。例如 f(x)=x3f(x)=x^3 的零点是驻点但不是极值，f(x,y)=x2−y2f(x,y)=x^2-y^2 的原点是鞍点。

二阶必要条件

若 ff 二阶可微，x∗x^* 是局部极小点，则

∇f(x∗)=0,∇2f(x∗)⪰0.\nabla f(x^*)=0,\qquad \nabla^2f(x^*)\succeq0.

因为任意方向的一元限制 ϕ(t)\phi(t) 在零处极小，必须有

ϕ′′(0)=dT∇2f(x∗)d≥0.\phi''(0)=d^T\nabla^2f(x^*)d\ge0.

二阶充分条件

若

∇f(x∗)=0,∇2f(x∗)≻0,\nabla f(x^*)=0,\qquad \nabla^2f(x^*)\succ0,

则 x∗x^* 是严格局部极小点。由 Taylor 展开：

f(x∗+s)=f(x∗)+12sTHs+o(∥s∥2),f(x^*+s)=f(x^*)+\frac12s^THs+o(\lVert s\rVert^2),

正定二次项在足够小邻域内压过高阶余项。

若 Hessian 仅半正定，条件无法判断。例如 x4x^4 在零点是严格极小，而 x3x^3 不是，二者零点二阶导数都为零。

Hessian 的判定

对称矩阵 HH：

  • 全部特征值正：正定；
  • 全部非负：半正定；
  • 有正有负：不定，驻点为鞍点。

手算可用顺序主子式：HH 正定当且仅当所有顺序主子式为正。二维矩阵

[abbc]\begin{bmatrix}a&b\\b&c\end{bmatrix}

正定等价于 a>0a>0 且 ac−b2>0ac-b^2>0。

凸函数的升级结论

若 ff 凸且可微，则

∇f(x∗)=0\nabla f(x^*)=0

不仅必要，而且足以推出全局最优。若 ff 严格凸，解还唯一。

考试要点

  • 先解驻点，再逐点判 Hessian，不能只写一个矩阵。
  • Hessian 不定可直接判鞍点；半正定不能直接判极小。
  • 局部极值点若在定义域边界，一阶梯度未必为零；无约束内点前提不能漏。
  • 方向导数符号是判断某个给定方向是否下降的最快方法。

评论