2实用收敛性(续) ▲收敛性:设解集S*≠{(}为算法产生的点 列。下列情况之一成立时,称算法收敛 1°x)∈S;←有限步终止 2°)的,Vk,{x的任意极限点eS。 ▲全局收敛:对任意初始点①,算法均收敛。 局部收敛:当x()充分接近解κ时,算法收敛
2.实用收敛性（续） ▲收敛性：设解集S*≠ ，{x (k) }为算法产生的点 列。下列情况之一成立时，称算法收敛： 1°x (k) ∈S*; 2° x (k) S* ， k，{x (k) }的任意极限点∈S* 。 ▲全局收敛：对任意初始点x (1) ,算法均收敛。 局部收敛：当x (1) 充分接近解x*时，算法收敛。 有限步终止
三、收敛速度 设算法产生点列{),收敛到解x,且xx, Vk,关于算法的收敛速度,有 1线性收敛:x=x<1当k充分大时成立。 2超线性收敛:mx1-x‖ k (k 3二阶收敛:彐a>0,是使当k充分大时有 (k+1) C (k)
三、收敛速度 设算法产生点列{x (k) }，收敛到解x*，且x (k)≠x* ， k，关于算法的收敛速度，有 1.线性收敛： 当k充分大时成立。 2.超线性收敛： 3.二阶收敛： ﹥0，是 使当k充分大时有 0 || || || || lim ( ) * ( 1) * = − − + → x x x x k k k − − + ( ) * 2 ( 1) * || || || || x x x x k k 1 || || || || ( ) * ( 1) * − − + x x x x k k
、收敛速度(续) 定理:设算法点列{的超线性收敛于x*,且x6)x*, k,那么 (k+ 1)X ( k→>o (k)=X 证明:只需注意 lk+)-x211x()-x|≤|x+)-x(≤|x(+)x2 +x)-x28,除x()-x*1并会x→0,利用超线 性收敛定义可得结果。 该结论导出算法的停止条件可用: x(+)-x6|k公或f(x()-f(x)E
三、收敛速度（续） 定理：设算法点列{x (k) }超线性收敛于x*,且x (k)≠x* ， k，那么 证明：只需注意 | ||x(k+1) –x * || -|| x(k) –x* || |≤ ||x(k+1) –x (k) || ≤ ||x(k+1) –x * || +|| x(k) –x* || ，除以|| x(k) –x* || 并令k→∞，利用超线 性收敛定义可得结果。 1 || || || || lim ( ) * ( 1) = − − + → x x x x k k (k) k 该结论导出算法的停止条件可用： ( ) 1 ( ) || || k k x x + − ( ) 1 ( ) | ( ) ( ) | k k f x f x + 或 −
四、二次终结性 ▲一个算法用于解正定二次函数的无约束极小 时,有限步迭代可达最优解,则称该算法具 有二次终结性
四、二次终结性 ▲一个算法用于解正定二次函数的无约束极小 时，有限步迭代可达最优解，则称该算法具 有二次终结性
常用的一维搜索算法 问题描述: 已知xk,并且求出了x处的可行下降方向Pk, 从x出发,沿方向酽求如下目标函数的最优解, minf(=+ad")=mind(a) >0 >0 或者选取a>0使得 k=mina>ovi
问题描述： 已知 , k x 并且求出了 k x 处的可行下降方向 , k p 从 k x 出发，沿方向 k d 求如下目标函数的最优解， 或者选取 min min ( ) ( ) k k 0 0 f x d + = 0 k 使得： min 0 0 ( ) T k k k k = + = f x d d 常用的一维搜索算法