本文主要是介绍漫步最优化十一——局部极小与极大的充分必要条件(上),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
即便没有那么多浪漫的话,
我也想与你走过每个冬夏。
你的出现是我唯一的心动,
你的与众不同让我难以忘记每个笑容。
越相处越习惯你,
越想拥有你,
只想每分每秒陪伴你的苦与乐。
——畅宝宝的傻逼哥哥
梯度 g(x) 与海森矩阵 H(x) 在局部极小值点 x∗ 上必须满足某些条件,两个条件集如下:
- 在局部极小值点 x∗ 处必须满足的条件,他们是必要条件。
- 保证 x∗ 是局部极小值点点条件,他们是充分条件。
充分必要条件可以用许多定理的形式进行描述,这些定理中使用比较广泛的概念就是可行方向的概念。
定义1: δ=αd 是 x 上的变化量,其中 α 是正常数, d 是方向向量,如果 R 是可行域且存在常数
效果上,如果点 x 沿方向 d 移动有限的距离后依然在 R 中,那么
例1: 优化问题的可行域为
如图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≤α≤α̂ 范围内的所有 α ,
d1 是点 x1 处的可行方向;对任意 0≤α≤α̂
因此 d2,d3 是 x1 的可行方向。
因为不存在常数 α̂ >0 使得
,所以 d1 不是 x2 处的可行方向。另一方面,存在正数 α̂ 使得对 0≤α≤α̂ 而言
,所以 d2,d3 是 x2 的可行方向。
图1
因为 x3 不在 R 中,所以不存在
,因此 d1,d2,d3 不是 x3 的可行方向。
一阶必要条件
目标函数要想有极小值,必须满足里两个条件,也就是一阶与二阶条件,一阶条件是一阶导数的形式,如梯度。
定理1: 极小值的一阶必要条件。
- 如果 f(x)∈C1,x 是局部最小值点,那么对于 x∗ 处的所有可行方向
g(x∗)Td≥0 - 如果 x∗ 是 R 的内点,那么
g(x∗)=0
证明: (a) 如果 d 是 x∗ 的可行方向,那么
利用泰勒级数
如果
那么当 α→0 时
那么
这与假设 x∗ 是极小值相矛盾,因此 x∗ 为极小值的必要条件是
(b) 如果 x∗ 是 R 的内点,所有可行方向的向量均存在,那么由
同样的,对于方向 d=−d1
因此在这种情况下, x∗ 是极小值的必要条件是
二阶必要条件
二阶必要条件涉及到一阶与二阶导,或者等价的梯度与海森矩阵。
定义1:
- 令 d 是点 x 处的任意方向向量,如果对任意的 d≠0,dTHd>0,≥0,≤0,<0 ,那么称二次项 dTH(x)d 为正定,半正定,半负定,负定。如果 dTH(x)d 既可以为正也可以为负,那么称其为不定的。
- 如果 dTH(x)d 是正定,半正定等,那么称矩阵 H(x) 为正定,半正定等矩阵。
这篇关于漫步最优化十一——局部极小与极大的充分必要条件(上)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!