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

文档介绍：Lecture6算法和算法复杂性一维搜索
主要内容
算法概念
算法收敛准则
全局收敛, 局部收敛, 收敛速度
算法二次终止性
算法复杂性
内点法: 路径跟踪法
算法概念
一．下降迭代算法
迭代：
下降：
在每次迭代中，后继点处的函数值要有所减少。
下降迭代算法的步骤：
选取搜索方向是最关键的一步，各种算法的区别，
主要在于确定搜索方向的方法不同。
定理：
证明：
二．算法映射
定义：
例：
例：
x
y
1
y=(x+1)/2
A(x(1,k))
A(x(2,k))
解集合
把满足某些条件的点集定义为解集合．当迭代点属
　于该集合时，停止迭代．
常用的解集合：
算法收敛问题
定义：
实用收敛准则