没有合适的资源?快使用搜索试试~ 我知道了~
考卷资料-旧版1
需积分: 0 0 下载量 67 浏览量
2022-08-03
22:10:46
上传
评论
收藏 1.86MB PDF 举报
温馨提示
试读
3页
考卷资料-旧版1
资源详情
资源评论
资源推荐
方向导数与最下方向
凸函数及其性
性
性
设𝑓𝑥是二阶可微的,则𝑓𝑥在开凸集𝑅上为凸函
数的充分必要条件是对一切𝑥 ∈ 𝑅,𝐻𝑒𝑠𝑠𝑒矩阵
𝐻𝑥为半正定的。若𝐻𝑥为正定的,则𝑓𝑥为严格
凸函数。
最优的判定
充分梯度,海赛矩阵
必要梯度,海赛矩阵
满足充要为非奇异点,必要不充分为非奇异点
二分法
𝒙
∗
∈𝒂
𝒏
,𝒃
𝒏
𝒄
𝒏
=𝒂
𝒏
+ 𝒃
𝒏
/
𝒙
𝟏
𝒏
= 𝒄
𝒏
−
𝜺
𝒙
𝟐
𝒏
= 𝒄
𝒏
−
𝜺
𝒊𝒇 𝒇𝒙
𝟏
𝒏
𝒇𝒙
𝟐
𝒏
𝒂
𝒏𝟏
= 𝒂
𝒏
,𝒃
𝒏𝟏
= 𝒙
𝟐
𝒏
𝒊𝒇 𝒇𝒙
𝟏
𝒏
𝒇𝒙
𝟐
𝒏
𝒂
𝒏𝟏
= 𝒙
𝟏
𝒏
,𝒃
𝒏𝟏
= 𝒃
𝒏
获得新的搜索区间𝒂
𝒏𝟏
𝒃
𝒏𝟏
且 𝒙
∗
∈
𝒂
𝒏𝟏
,𝒃
𝒏𝟏
例
𝒇
𝒙
=𝒙
𝟑
− 𝒙
𝟐
− 𝒙 +
𝒙∈
,
; 𝒙
∗
= ; 𝜺 =; 𝒂
𝟎
= , 𝒃
𝟎
=
𝒄
𝟎
= , 𝒙
𝟏
𝟎
= 𝒙
𝟐
𝟎
=
𝒇
= 𝒇
=−
𝒂
𝟏
=𝒙
𝟏
𝟎
=, 𝒃
𝟏
=𝒃
𝟎
=
𝒄
𝟏
= , 𝒙
𝟏
𝟏
= 𝒙
𝟐
𝟏
=
𝒇
=− 𝒇
=
𝒂
𝟐
= 𝒂
𝟏
=, 𝒃
𝟐
= 𝒙
𝟐
𝟏
=
区等分法
点等分法
𝒙
𝟏
𝒏
= 𝒂
𝒏
+
𝒃
𝒏
− 𝒂
𝒏
𝒙
𝟐
𝒏
= 𝒂
𝒏
+
𝒃
𝒏
− 𝒂
𝒏
𝐈𝐟 𝒇𝒙
𝟏
𝒏
𝒇𝒙
𝟐
𝒏
𝒂
𝒏𝟏
= 𝒂
𝒏
,𝒃
𝒏𝟏
=𝒙
𝟐
𝒏
𝐈𝐟 𝒇𝒙
𝟏
𝒏
𝒇𝒙
𝟐
𝒏
𝒂
𝒏𝟏
= 𝒙
𝟏
𝒏
,𝒃
𝒏𝟏
= 𝒃
𝒏
𝑳
𝒏𝟏
=
𝑳
𝒏
每次检查 个点
点等分法
𝒙
𝟏
𝒏
= 𝒂
𝒏
+
𝒃
𝒏
− 𝒂
𝒏
𝒙
𝟐
𝒏
= 𝒂
𝒏
+
𝒃
𝒏
− 𝒂
𝒏
𝒙
𝟑
𝒏
= 𝒂
𝒏
+
𝒃
𝒏
− 𝒂
𝒏
𝒊𝒇 𝒇𝒙
𝟏
𝒏
=𝒎𝒊𝒏𝒇𝒙
𝒊
𝒏
𝒂
𝒏𝟏
= 𝒂
𝒏
,𝒃
𝒏𝟏
= 𝒙
𝟐
𝒏
𝒊𝒇 𝒇𝒙
𝟐
𝒏
=𝒎𝒊𝒏𝒇𝒙
𝒊
𝒏
𝒂
𝒏𝟏
= 𝒙
𝟏
𝒏
,𝒃
𝒏𝟏
= 𝒙
𝟑
𝒏
𝒊𝒇 𝒇𝒙
𝟑
𝒏
=𝒎𝒊𝒏𝒇𝒙
𝒊
𝒏
𝒂
𝒏𝟏
= 𝒙
𝟐
𝒏
,𝒃
𝒏𝟏
= 𝒃
𝒏
斐波契法
、 初始搜索区间 𝑳
𝟏
= 𝒃
𝟎
− 𝒂
𝟎
、计算下一(第二)搜索区间 𝑳
𝟐
=
𝑭
𝒏𝟏
𝑳
𝟏
𝑭
𝒏
+
𝟏
𝒏
𝜺
𝑭
𝒏
、更新𝒙
𝟏
与 𝒙
𝟐
、计算两点函数值,比较后确定新区间 𝒂
𝟏
与 𝒃
𝟏
、是否迭代到𝒏
精度关系 𝑳
𝒏
=
𝑳
𝟏
𝑭
𝒏𝟐
𝜺
𝑭
𝒏
例题
求 𝒇
𝒕
= 𝒕
𝟐
− 𝒕 + 的似极小点区为
精度𝜹 =
解
𝒇𝒕为下单峰函数用微分法可知𝒕
∗
= , 𝒇𝒕
∗
=
𝑳
𝒏
=
𝑳
𝟏
𝑭
𝒏𝟐
𝜺
𝑭
𝒏
𝜺=
时
𝑳
𝒏
=
𝑳
𝟏
𝑭
𝒏
𝑳
𝒏
=
𝑳
𝟏
𝑭
𝒏
𝑭
𝒏
算𝑳
𝟐
=
𝑭
𝒏𝟏
𝑳
𝟏
𝑭
𝒏
𝑭
𝟑
𝑳
𝟏
𝑭
𝟒
=
𝟓
𝟖
×
算𝒂
𝟏
,𝒃
𝟏
𝒙
𝟏
𝟏
𝒃
𝟎
− 𝑳
𝟐
= −
𝒙
𝟐
𝟏
𝒂
𝟎
+ 𝑳
𝟐
=− +
𝒇
𝒙
𝟏
𝟏
= 𝒇
𝒙
𝟐
𝟏
= 𝒇
𝒙
𝟐
𝟏
𝒇
𝒙
𝟏
𝟏
更新区 𝒂
𝟏
𝒂
𝟎
=−, 𝒃
𝟏
𝒙
𝟐
𝟏
=
更新点𝒙
𝟐
𝟐
= 𝒙
𝟏
𝟏
𝒙
𝟏
𝟐
= 𝒂
𝟏
𝒃
𝟏
𝒙
𝟐
𝟐
法
渐近收敛率𝐥𝐢𝐦
𝒏→
𝑳
𝒏
𝑳
𝒏𝟏
𝑭
𝒏
=
𝟏
√
𝟓
𝟏 +
√
𝟓
𝟐
𝒏𝟏
−
𝟏 −
√
𝟓
𝟐
𝒏𝟏
证明对于黄金分割法
𝑳
𝒏
𝑳
𝒏𝟏
= 𝛌=
𝐥𝐢𝐦
𝒏→
𝑳
𝒏
𝑳
𝒏𝟏
=
对于
𝑳
𝒏
𝑳
𝒏𝟏
=
𝑭
𝒏𝟏
𝑭
𝒏
=
𝟏
√
𝟓
𝟐
𝒏
𝟏
√
𝟓
𝟐
𝒏
𝟏
√
𝟓
𝟐
𝒏𝟏
𝟏
√
𝟓
𝟐
𝒏𝟏
𝐥𝐢𝐦
𝒏→
𝑳
𝒏
𝑳
𝒏𝟏
𝟏
√
𝟓
𝟐
𝒏
𝟏
√
𝟓
𝟐
𝒏𝟏
=
例题
求 𝒇
𝒕
= 𝒕
𝟐
− 𝒕 + 𝟐的似极小点区为
精度𝜹 = 使用 法。
算𝒂
𝟏
,𝒃
𝟏
𝒙
𝟏
𝟏
𝒂
𝟎
+ ×𝒃
𝟎
− 𝒂
𝟎
=
𝒙
𝟐
𝟏
𝒂
𝟎
+ ×𝒃
𝟎
− 𝒂
𝟎
𝒇
𝒙
𝟏
𝟏
= , 𝒇
𝒙
𝟐
𝟏
= 𝒇
𝒙
𝟐
𝟏
𝒇
𝒙
𝟏
𝟏
更新区 𝒂
𝟏
𝒂
𝟎
=−𝟏
𝒃
𝟏
𝒙
𝟐
𝟏
=
更新点 𝒙
𝟏
𝟐
= 𝒂
𝟏
×𝒃
𝟏
− 𝒂
𝟏
𝒙
𝟐
𝟐
= 𝒙
𝟏
𝟏
由于
𝒃
𝟑
𝒂
𝟑
𝟐
= 𝜹= 算法止
𝒙
∗
=
𝒙
𝟏
𝟑
𝒙
𝟐
𝟑
𝟐
𝒇𝒙
∗
法
、给定初始点𝒙
𝟎
,初始步长𝒉
𝟎
、考察𝒇𝒙
𝟎
,𝒇𝒙
𝟎
+ 𝒉
、 𝒊𝒇 𝒇𝒙
𝟎
+ 𝒉𝒇𝒙
𝟎
后退一步计算 𝒇𝒙
𝟎
− 𝝀𝒉 ,𝟎 𝝀𝟏
𝒇𝒙
𝟎
− 𝝀
𝒉 𝒇𝒙
𝟎
𝒙
∗
∈𝒙
𝟎
− 𝝀
𝒉,𝒙
𝟎
+ 𝒉
𝒊𝒇 𝒇𝒙
𝟎
+ 𝒉𝒇𝒙
𝟎
前进一步计算 𝒇𝒙
𝟎
+ 𝝀𝒉 ,𝝀 𝟏
𝒇𝒙
𝟎
+ 𝝀
𝒉 𝒇𝒙
𝟎
+ 𝒉
𝒙
∗
∈𝒙
𝟎
,𝒙
𝟎
+ 𝝀
𝒉
多式插值法
假搜索点𝒙
𝟎
= 𝟎,方向 𝒅
算𝒈
𝟎
,𝒈𝟏
𝒊𝒇 𝒈
𝟏
𝒈
𝟎
算 𝒈
𝝀
,
𝝀=
𝟏
𝟐
,
𝟏
𝟒
,
𝟏
𝟖
…𝒖𝒏𝒕𝒊𝒍 𝒈
𝝀
𝒈
𝟎
𝒂 =𝟎,𝒃=𝝀,𝒄=𝟐𝝀, 根据二次式插值算
𝝀
=手写
𝒊𝒇 𝒈
𝟏
𝒈𝟎 算𝒈
𝝀
,𝝀=
𝟐,𝟒, 𝟖 …𝒂,𝒃,𝒄,𝒖𝒏𝒕𝒊𝒍 𝒈
𝒄
𝒈
𝒃
,根据二次式插
值算
𝒊𝒇 𝒈
𝝀
𝒈
𝒃
𝝀
𝟏
= 𝝀
𝒊𝒇 𝒈
𝝀
𝒈
𝒃
𝝀
𝟏
= 𝒃
例
求 𝒇
𝒙
= 𝒙
𝟑
− 𝒙
𝟐
− 𝒙 + 的近似极小点,𝒙
𝟎
=
,𝒅=
𝒈
𝝀
= 𝒇
𝒙
𝟎
+ 𝝀𝒅
= 𝒇
𝝀
= 𝝀
𝟑
− 𝝀
𝟐
− 𝝀 +
𝒈
= , 𝒈
=
∵𝒈
𝒈
∴ 𝝀 =, 𝒈
= 𝒈
𝒂 =, 𝒃 =, 𝒄 =
𝝀
=
最下法梯度法
取初始点𝒙
𝟎
∈ 𝑬
𝒏
,允许误差 𝜺 𝟎
计算负梯度方向 𝒅
𝒑
=−𝜵𝒇
𝒙
𝒑
𝒅
𝒑
=−
𝜵𝒇
𝒙
𝒑
‖
𝜵𝒇
𝒙
𝒑
‖
进行一维搜索𝒎𝒊𝒏
𝒌
𝒇𝒙
𝒑
+ 𝒌𝒅
𝒑
𝒙
𝒑𝟏
= 𝒙
𝒑
+ 𝒌𝒅
𝒑
精度判断为
‖
𝒅
𝒑
‖
𝜺
例题
求𝑚𝑖𝑛𝑓
𝑥
=
𝑥
−
+
𝑥
− 𝑥
𝑥
=,
𝜀=
解
𝛻𝑓
𝑥
=
𝑥
−
+
𝑥
− 𝑥
−
𝑥
− 𝑥
𝛻𝑓
𝑥
=
−
𝑑
=−𝛻𝑓
𝑥
=
−
𝑥
=𝑥
+ 𝑘
𝑑
=
+ 𝑘
−
=
𝑘
−𝑘
+
𝑚𝑖𝑛𝑓
𝑥
=
𝑘
−
+
𝑘
− −𝑘
+
𝑘
=
𝑥
=
×
− × +
=
⋮
当进行第七次迭代时,𝑥
=
,此时
‖
𝑑
‖
=
满足要求。
梯度法对于二次函数的
例题 求𝒎𝒊𝒏𝒇
𝒙
=
𝟏
𝟐
𝒙
𝟏
𝟐
+ 𝟐𝒙
𝟐
𝟐
𝒙
𝟎
=𝟒,𝟒
𝑻
𝑸 =
𝟏𝟎
𝟎𝟐
𝒌
∗
=−
𝒙
𝑻
𝑸
𝟐
𝒙
𝒙
𝑻
𝑸
𝟑
𝒙
𝒙
𝒑
𝒌
∗
=−
𝒙
𝟏
= 𝒙
𝟎
+ 𝒌𝜵𝒇
𝒙
𝟎
=
−
=
−
牛法
给定初始点 ,允许误差 置
若
‖
𝜵𝒇
𝒙
𝒌
‖
停止,得解𝒙
𝒌
,否则,令
𝒙
𝒌𝟏
= 𝒙
𝒌
− 𝜵
𝟐
𝒇
𝒙
𝒌
𝟏
𝜵𝒇
𝒙
𝒌
,,转
例题
求 𝒇
𝒙
= 𝒙
𝟏
𝟐
+ 𝒙
𝟏
𝒙
𝟐
+ 𝒙
𝟐
𝟐
+ 𝒙
𝟏
+ 𝒙
𝟐
的似极
小点。使用牛法。
𝜵𝒇 =
𝒙
𝟏
+ 𝒙
𝟐
+
𝒙
𝟏
+ 𝒙
𝟐
+
,𝑯=
𝑯
𝟏
=
−
−
𝒙
𝒏𝟏
= 𝒙
𝒏
− 𝑯
𝟏
𝒙
𝒏
𝜵𝒇𝒙
𝒏
=
𝒙
𝟏
𝒏
𝒙
𝟐
𝒏
−
−
−
𝒙
𝟏
+ 𝒙
𝟐
+
𝒙
𝟏
+ 𝒙
𝟐
+
=
−
−
二导数法广义牛法
取初始点𝒙
𝟎
∈ 𝑬
𝒏
,允许误差 𝜺 𝟎
计算梯度方向 𝒅
𝒑
=−𝜵
𝟐
𝒇𝒙
𝒑
𝟏
𝜵𝒇
𝒙
𝒑
进行一维搜索𝒎𝒊𝒏
𝒌
𝒇𝒙
𝒑
+ 𝒌𝒅
𝒑
𝒙
𝒑𝟏
= 𝒙
𝒑
+ 𝒌𝒅
𝒑
精度判断为
‖
𝒅
𝒑
‖
𝜺
例题
𝒎𝒊𝒏𝒇
𝒙
= 𝒙
𝟏
𝟐
+ 𝒙
𝟐
𝟐
𝒙
𝟎
=,
𝑻
精度为
解𝜵𝒇
𝒙
=
𝒙
𝟏
𝒙
𝟐
𝜵
𝟐
𝒇
𝒙
=
𝜵𝒇
𝒙
𝟎
=
𝜵
𝟐
𝒇
𝒙
𝟏
=
𝟏
𝟐
𝟎
𝟏
𝟏
𝟓𝟎
‖
𝜵𝒇
𝒙
𝟎
‖
=
𝒅
𝟎
=−
𝜵
𝟐
𝒇
𝒙
𝟎
𝟏
𝜵𝒇
𝒙
𝟎
=−
=−
𝒎𝒊𝒏
𝒌
𝒇
𝒙
𝟎
+ 𝒌𝒅
𝟎
= − 𝒌
𝟐
+ ×
-𝒌
𝟐
=
× − 𝒌
𝟐
𝒅𝒇
𝒅𝒌
=−
− 𝒌
= 𝒌=
𝒙
𝟏
= 𝒙
𝟎
+ 𝒌𝒅
𝟎
=,
𝑻
+ −,−
𝑻
=,
𝑻
‖
𝜵𝒇
𝒙
𝟏
‖
= ,故达最优。
共梯度法
取初始点𝒙
𝟎
初始方向𝒗
𝟎
=−𝜵𝒇
𝒙
𝟎
𝒙
𝒊
= 𝒙
𝒊𝟏
+ 𝝀
𝒊𝟏
𝒗
𝒊𝟏
𝝀
𝒊𝟏
取
𝒎𝒊𝒏𝒇𝒙
𝒊𝟏
+ 𝝀𝒗
𝒊𝟏
𝒗
𝒊
=−𝜵𝒇
𝒙
𝒊
+
𝜵𝒇
𝒙
𝒊
𝟐
𝜵𝒇
𝒙
𝒊𝟏
𝟐
𝒗
𝒊𝟏
𝒙
𝟎
𝒙
𝒏
回
例
𝒎𝒊𝒏𝒇𝒙
𝟏
,𝒙
𝟐
=
𝟑
𝟐
𝒙
𝟏
𝟐
𝟏
𝟐
𝒙
𝟐
𝟐
− 𝒙
𝟏
𝒙
𝟐
− 𝟐𝒙
𝟏
𝒙
𝟎
=−𝟐,𝟒
第 次代
𝜵𝒇
𝒙
𝟎
=𝟑𝒙
𝟏
− 𝒙
𝟐
− 𝟐,𝒙
𝟐
− 𝒙
𝟏
𝑻
=−𝟏𝟐, 𝟔
𝑻
𝒅
𝟎
=−𝜵𝒇
𝒙
𝟎
=𝟏𝟐,−𝟔
𝑻
𝒙
𝟏
= 𝒙
𝟎
+ 𝝀𝒅
𝟎
=−𝟐,𝟒
𝑻
+𝟏𝟐𝝀,−𝟔𝝀
𝑻
=−𝟐+ 𝟏𝟐𝝀,𝟒 − 𝟔𝝀
𝑻
𝒇
𝒙
𝟏
=
𝟑
𝟐
−𝟐 + 𝟏𝟐𝝀
𝟐
𝟏
𝟐
𝟒 − 𝟔𝝀
𝟐
−
−𝟐 +
𝟏𝟐𝝀
𝟒 − 𝟔𝝀
− 𝟐
−𝟐 + 𝟏𝟐𝝀
𝒇
𝝀
𝒙
𝟏
= 𝟔𝟏𝟐𝝀 − 𝟏𝟖𝟎 = 𝟎
𝝀=
𝟓
𝟏𝟕
𝒙
𝟏
=
𝟐𝟔
𝟏𝟕
,
𝟑𝟖
𝟏𝟕
𝑻
第 次代
𝒙
𝟏
=
𝟐𝟔
𝟏𝟕
,
𝟑𝟖
𝟏𝟕
𝑻
𝜵𝒇
𝒙
𝟏
=𝟑𝒙
𝟏
− 𝒙
𝟐
− 𝟐,𝒙
𝟐
− 𝒙
𝟏
𝑻
=
𝟔
𝟏𝟕
,
𝟏𝟐
𝟏𝟕
𝑻
𝒅
𝟏
=−𝜵𝒇
𝒙
𝟏
+
‖
𝜵𝒇
𝒙
𝟏
‖
𝟐
‖
𝜵𝒇
𝒙
𝟎
‖
𝟐
𝒅
𝟎
=−
𝟔
𝟏𝟕
,
𝟏𝟐
𝟏𝟕
𝑻
+
𝟔
𝟏𝟕
,
𝟏𝟐
𝟏𝟕
𝑻
𝟐
‖
−𝟏𝟐,𝟔
𝑻
‖
𝟐
∙
𝟔
𝟏𝟕
,
𝟏𝟐
𝟏𝟕
𝑻
=−
𝟗𝟎
𝟐𝟖𝟗
,
𝟐𝟏𝟎
𝟐𝟖𝟗
𝑻
𝒙
𝟐
= 𝒙
𝟏
+ 𝝀𝒅
𝟏
=
𝟐𝟔
𝟏𝟕
,
𝟑𝟖
𝟏𝟕
𝑻
+ −
𝟗𝟎𝝀
𝟐𝟖𝟗
,
𝟐𝟏𝟎𝝀
𝟐𝟖𝟗
𝑻
𝝀=
𝟏𝟕
𝟏𝟎
𝒙
𝟐
=𝟏,𝟏
𝑻
𝜵𝒇
𝒙
𝟐
= 𝟎
已达最优。
变尺度法 拟牛法的一种
()
(1)
1
(1)
1
()
() ()
() () () ()
0
( 1) ( ) (
1, , 0,
2, ,
( )
1
3,
4, , , ,
()()
Se E
Se H I
gf
Se d H g
Se d
f d f d
d
定初始 允差
出在 处梯度
令
从出发沿 一搜求 使
令
)
,
( 1)
( 1)
(1) ( 1)
( 1) ( ) ( 1) ( ) ( )
11
1
5, ,
( ) ,
,,,6
6, , , 2; , 7
7, ( ), , ,
(10.4.18) , : 1, 3
Se
f
Se
Se Se Se
Se g f g g
H Se
检
是否满收敛准则
停
止得 否则
则令 否则
令
公式
例
艾苛尔
- 粉丝: 26
- 资源: 307
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0