《最优化理论与算法课件》由会员分享，可在线阅读，更多相关《最优化理论与算法课件（24页珍藏版）》请在金锄头文库上搜索。
1、最优化理论与算法,8， 算法,第八章 线性规划的基本性质,算法概念 算法收敛问题,ch8 算法-概念,8.1.1 算法映射,下降，即对某个函数，在每次迭代中后继点处的 函数值要有所减小。,迭代下降算法,考虑极小化问题 f(x) s.t. xS 这里f是目标函数，S是可行域。对于求解这一问题的解答程序或算法可以看作是一个迭代过程，这过程按照规定的一组 指令和终止准则一起产生一个点序列。,ch8 算法概念,Df 8.1.1 算法A是定义在空间X上的点到集映射,即对每一个点xX,给定一个子集A(x)X.,Ch8 算法-概念,ch8 算法概念,如图所示,应用算法A时,经A作用得到一个闭区间,从此区间中
2、 任取一点作为后继点,重复这个过程,得一由算法产生得点列, 在一定条件下,它收敛于问题的解.如 3,2,3/2,5/4, 3,3/2,9/8,33/32, etc.,ch8 算法概念,8.1.2 解集合,为了求解上述问题，要求使用的算法具有这样的性质： 由算法产生的点列收敛于整体最优解 然而，在许多情形下，要满足这一点很难做到。事实上 由于非凸性，问题的规模和其它一些困难，达到整体最优 几乎不可能，因此当达到属于预定集的某一点达到，则可 以停止迭代，这个预定集就称之为解集合 常用的解集合有如下几种类型,Ch8 算法概念,ch8 算法概念,8.1.3 下降函数,Ch8 算法概念,8.1.4 闭映
3、射,Ch8 算法概念,设是整体最优解的集合，即=1。考虑算法映射， 定义为,映射在下图中说明,Ch8 算法概念,此例表明算法在区间(-,2)上 收敛于集中点，而在2，) 上却不收敛于中点， 从而算法不是闭的,显然对任何初始点x12, 由映射A产生的任何序列都收敛于点 x*=2，对初始点x12, 由映射A产生的任何序列都收敛于点 x=1.,Ch8 算法概念,评注：上面例子表明初始点x1选取的重要性：若x1 2则达到收敛于中的点，否则就不能实现。另注意到，在上例中都满足如下条件：,但对任何x12都不收敛于 x*=1 ,即算法不是闭的,1，给出一可行点xk 1,任何后继点xk也是可行的,即xk+1
4、1 2，给出一个不在解集内的可行点xk,任何后继点xk+1满足 f(xk+1)f (xk), 其中f(x)=x2. 即目标函数严格下降。 3，给出一在内的可行点xk(=1),任何后继点xk+1也在内,即 xk+1 =1,Ch8 算法概念,8.1.5, 合成映射,Ch8 算法概念,Ch8 算法概念,Ch8 算法-收敛定理,8.2.1收敛定理,Ch8 算法-收敛定理,Ch8算法-收敛定理,Ch8 算法-收敛定理,Ch8 算法-收敛定理,Ch8 算法-收敛定理,8.2.2实用收敛准则,正如在收敛定理中所指出，若我们达到解集中的一个点时，就终止算法。然而，在大多数情形下，收敛于中 的点仅仅出现在极限意义上，因此我们必须依靠终止迭代过程的某些实际规则，下面给出一些常用的终止规则。这里0和正整数N是预先给定的。,|xk+Nxk| 如果应用映射A的N次后移动的距离小于时，算法终止,Ch8 算法-收敛定理,Ch8 算法-收敛定理,8.2.3 收敛速率,
