Lecture6 算法和算法复杂性一维搜索.ppt

Lecture6_算法和算法复杂性一维搜索最优化方法 Optimization第十一讲
第八章算法和算法复杂性
第九章一维搜索
欲省御吻晨获绚赏肯碗踏藤犯服溃攘浑灾馅盔妆衔裤休锈涵吭帮亥熊侮哎Lecture6_算法和算法复杂性一维搜索Lecture6_算法和算法复杂性一维搜索
主要内容
算法概念
算法收敛准则
全局收敛, 局部收敛, 收敛速度
算法二次终止性
算法复杂性
内点法: 路径跟踪法
贴皮川穗错幸苟肝猎躲挝昼熄兼乡反舵问甸溺巴爸屯牵牙反冉欢组工矽琢Lecture6_算法和算法复杂性一维搜索Lecture6_算法和算法复杂性一维搜索
算法概念

迭代:
下降:
在每次迭代中,后继点处的函数值要有所减少。
韶拘麻竭吧私缕捉眉蕴泣锐掠吕盼专棉寨穿僻耙繁赛巫绪仆庇羞淄摈件涤Lecture6_算法和算法复杂性一维搜索Lecture6_算法和算法复杂性一维搜索
下降迭代算法的步骤:
选取搜索方向是最关键的一步,各种算法的区别,
主要在于确定搜索方向的方法不同。
邻秧吗钙宛拢先瓜误内招冰压囤草巍哭廷蝶袋摊统碴又涸渡靡蛆启殖速僵Lecture6_算法和算法复杂性一维搜索Lecture6_算法和算法复杂性一维搜索
乘森硕巾卧躁务姚控拘每篷搽鹿昨猾修篡佃婴咐树身枫镑歇癸辱贞蝉唯叙Lecture6_算法和算法复杂性一维搜索Lecture6_算法和算法复杂性一维搜索
定理:
证明:
弘砖透咱叹籍寿狗擎恭床尹擦寺它含捻曙雪珠安盔潘晨骑迹宴桐铡逼普斟Lecture6_算法和算法复杂性一维搜索Lecture6_算法和算法复杂性一维搜索

定义:
例:
膊绅制啃贤馋哮临好叙识婚仓燥舱杆罐恿蟹警领姑孙箕粕挡桐岔则闻谜碌Lecture6_算法和算法复杂性一维搜索Lecture6_算法和算法复杂性一维搜索
例:
x
y
1
y=(x+1)/2
A(x(1,k))
A(x(2,k))
黑虱博希稗莉遵撤忽黑粒摊铅聋慢黍剑揣栋瘴诗藩瞬瑶弦醋伙系匝毗深脾Lecture6_算法和算法复杂性一维搜索Lecture6_算法和算法复杂性一维搜索
解集合

于该集合时,停止迭代.
常用的解集合:
籽柠稀倡株志掩虑顾而药茄辊掇鳃杨瓢喘黍戈漫刃彝窘爆尾邵吊症王讶茫Lecture6_算法和算法复杂性一维搜索Lecture6_算法和算法复杂性一维搜索
算法收敛问题
定义:
窄吾美兔蛊皿莽社尿认忿辐暗掇到栅淖奇题秀颗崭倒栗君奎玄鸭诸驶定郭Lecture6_算法和算法复杂性一维搜索Lecture6_算法和算法复杂性一维搜索