8最优化理论与算法.ppt

《8最优化理论与算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最优化理论与算法§8，算法第八章线性规划的基本性质算法概念算法收敛问题ch8算法-概念8.1.1算法映射下降，即对某个函数，在每次迭代中后继点处的函数值要有所减小。迭代下降算法考虑极小化问题f(x)s.t.xS这里f是目标函数，S是可行域。对于求解这一问题的解答程序或算法可以看作是一个迭代过程，这过程按照规定的一组指令和终止准则一起产生一个点序列。ch8算法－概念Df8.1.1算法A是定义在空间X上的点到集映射,即对每一个点xX,给定一个子集A(x)X.Ch8算法-概念ch8算法－概念如图所示,应用算法A时,经A作用得到一个闭区间,从此区间中任取一点作为后继点,重

2、复这个过程,得一由算法产生得点列,在一定条件下,它收敛于问题的解.如{3,2,3/2,5/4,…}{3,3/2,9/8,33/32,…}etc.x*=1xk+1xkxk+1A(x)x*=1xk+1xkxk+1A(x)ch8算法－概念8.1.2解集合为了求解上述问题，要求使用的算法具有这样的性质：由算法产生的点列收敛于整体最优解然而，在许多情形下，要满足这一点很难做到。事实上由于非凸性，问题的规模和其它一些困难，达到整体最优几乎不可能，因此当达到属于预定集的某一点达到，则可以停止迭代，这个预定集就称之为解集合常用的解集合有如下几种类型Ch8算法－概念ch8算法－概念8.1

3、.3下降函数Ch8算法－概念8.1.4闭映射Ch8算法－概念设是整体最优解的集合，即={1}。考虑算法映射，定义为映射在下图中说明Ch8算法－概念此例表明算法在区间(-,2)上收敛于集中点，而在[2，)上却不收敛于中点，从而算法不是闭的显然对任何初始点x12,由映射A产生的任何序列都收敛于点x*=2，对初始点x1<2,由映射A产生的任何序列都收敛于点x^=1.Ch8算法－概念评注：上面例子表明初始点x1选取的重要性：若x1<2则达到收敛于中的点，否则就不能实现。另注意到，在上例中都满足如下条件：但对任何x12都不收敛于x*=1,即算法不是闭的1

4、，给出一可行点xk1,任何后继点xk也是可行的,即xk+112，给出一个不在解集内的可行点xk,任何后继点xk+1满足f(xk+1)

5、解集中的一个点时，就终止算法。然而，在大多数情形下，收敛于中的点仅仅出现在极限意义上，因此我们必须依靠终止迭代过程的某些实际规则，下面给出一些常用的终止规则。这里0和正整数N是预先给定的。

6、

7、xk+Nxk

8、

9、<如果应用映射A的N次后移动的距离小于时，算法终止Ch8算法-收敛定理Ch8算法-收敛定理8.2.3收敛速率