漫步最优化十一——局部极小与极大的充分必要条件(上)

即便没有那么多浪漫的话， 我也想与你走过每个冬夏。 你的出现是我唯一的心动， 你的与众不同让我难以忘记每个笑容。 越相处越习惯你， 越想拥有你， 只想每分每秒陪伴你的苦与乐。 ——畅宝宝的傻逼哥哥 梯度 g(x) 与海森矩阵 H(x) 在局部极小值点 x∗ 上必须满足某些条件，两个条件集如下：

在局部极小值点 x∗ 处必须满足的条件，他们是必要条件。保证 x∗ 是局部极小值点点条件，他们是充分条件。

充分必要条件可以用许多定理的形式进行描述，这些定理中使用比较广泛的概念就是可行方向的概念。

定义1： δ=αd 是 x 上的变化量，其中 α 是正常数， d 是方向向量，如果 R 是可行域且存在常数α̂ >0使得对所有 α,x+αd∈R ，其中 0≤α≤α̂  ，那么称 d 为点 x 的可行方向。

效果上，如果点 x 沿方向 d 移动有限的距离后依然在 R 中，那么d就是 x 的可行方向向量。

例1： 优化问题的可行域为

R={x:x1≥2,x2≥0}

如图1所示，对于点 x1=[4 1]T,x2=[2 3]T,x3=[1 4]T ，向量 d1=[−2 2]T,d2=[0 2]T,d3=[2 0] 那个是可行方向？

解： 令 α̂ =1 ，在 0≤α≤α̂  范围内的所有 α ，

x1+αd1∈R

d1 是点 x1 处的可行方向；对任意 0≤α≤α̂ 

x1+αd2∈Rx1+αd3∈R

因此 d2,d3 是 x1 的可行方向。

因为不存在常数 α̂ >0 使得

x2+αd1∈Rfor 0≤α≤α̂ 

，所以 d1 不是 x2 处的可行方向。另一方面，存在正数 α̂  使得对 0≤α≤α̂  而言

x2+αd2∈Rx2+αd3∈R

，所以 d2,d3 是 x2 的可行方向。

图1

因为 x3 不在 R 中，所以不存在α̂ 是的对任意的 d

x3+αd∈Rfor 0≤α≤α̂ 

，因此 d1,d2,d3 不是 x3 的可行方向。

一阶必要条件 目标函数要想有极小值，必须满足里两个条件，也就是一阶与二阶条件，一阶条件是一阶导数的形式，如梯度。

定理1： 极小值的一阶必要条件。

如果 f(x)∈C1,x 是局部最小值点，那么对于 x∗ 处的所有可行方向 g(x∗)Td≥0 如果 x∗ 是 R 的内点，那么 g(x∗)=0

证明： (a) 如果 d 是 x∗ 的可行方向，那么

x=x∗+αd∈Rfor 0≤α≤α̂ 

利用泰勒级数

f(x)=f(x∗)+αg(x∗)Td+o(α∥d∥)

如果

g(x∗)Td<0

那么当 α→0 时

αg(x∗)Td+o(α∥d∥)<0

那么

f(x)<f(x∗)

这与假设 x∗ 是极小值相矛盾，因此 x∗ 为极小值的必要条件是

g(x∗)Td≥0

(b) 如果 x∗ 是 R 的内点，所有可行方向的向量均存在，那么由(a)可知，向量 d=d1 产生

g(x∗)Td1≥0

同样的，对于方向 d=−d1

−g(x∗)Td1≥0

因此在这种情况下， x∗ 是极小值的必要条件是

g(x∗)=0

二阶必要条件 二阶必要条件涉及到一阶与二阶导，或者等价的梯度与海森矩阵。

定义1：

令 d 是点 x 处的任意方向向量，如果对任意的 d≠0,dTHd>0,≥0,≤0,<0 ，那么称二次项 dTH(x)d 为正定，半正定，半负定，负定。如果 dTH(x)d 既可以为正也可以为负，那么称其为不定的。如果 dTH(x)d 是正定，半正定等，那么称矩阵 H(x) 为正定，半正定等矩阵。