算法和一维搜索10_121901301

1、最优化方法最优化方法 Optimization清 华 大 学 数 学 科 学 系 张立平办公室：荷二219# 电话：62796907-8033E-mail: 算法和一维搜索算法和一维搜索算法的主要内容算法的主要内容 算法概念算法概念 算法收敛准则算法收敛准则 全局收敛全局收敛, , 局部收敛局部收敛, , 收敛速度收敛速度 算法二次终止性算法二次终止性算法概念算法概念一下降迭代算法一下降迭代算法迭代：迭代：( )(1)( )( )1*lim*0*kkkkkxAxkkxxxxx从一点出发，按照某种规则 ，求出后继点，用代替 ，重复以上过程，得到一个解的序列，若该序列有极限点，即则称它收敛于。下降

2、下降：在每次迭代中，后继点处的函数值要有所减少。在每次迭代中，后继点处的函数值要有所减少。下降迭代算法的步骤：下降迭代算法的步骤：。，置选定某一初始点0. 1)0(kx。确定搜索方向)(. 2kd。迭代点，以产生下一个求步长出发，沿方向从)1()()(. 3kkkkxdx。，返回止迭代；否则，令小点，若是，则停是否为极小点或近似极检查21:. 4)1(kkxk 选取搜索方向是最关键的一步，各种算法的区别，选取搜索方向是最关键的一步，各种算法的区别， 主要在于确定搜索方向的方法不同。主要在于确定搜索方向的方法不同。 k确定步长 的主要方法令它等于某一常数。. 1。可任意选取步长能使目标函数值下降

3、，可接受点算法，即只要k. 2( )( )( )( )( )( )3.( )()min().kkkkkkkxxdf xf xdf xd基于沿搜索方向使目标函数值下降最多，即沿射线求目标函数的极小由于这项工作是求以 为变量的一元函数的极小点，故常称这一过程为（最优）一维搜索，这样确定的步长为最佳步长。定理：定理：。则有由下列规则产生：具有一阶偏导数，设目标函数0)()(min)()()1()()1()()()1(kTkkkkkkkkkkkdxfdxxdxfdxfxxf证明：证明：0)()()(0)()()()()()()(kTkkkkTkkkkkkkkkddxfddxfdxf而的驻点。为是最优步

4、长，则若记二算法映射二算法映射定义：定义：,2:2nXXXEA X给定集合记其幂集（即所有子集构成的集合）为，称集值映射为一个算法映射(algorithm mapping).例：例：(0)(1)()min|,0 ,|( )|()nnkkLPcx Axb xXxxLPA xyyLPyxxXxA x考虑标准形式的线性规划令为的基本可行解 ，若定义算法映射为的基本可行解,并且 和 的基矩阵是相邻的 ，那么对于任意一个基本可行解，迭代格式就生成一个相邻的基本可行解序列。例：例：2min. .1.xstx考虑下列非线性规划：11,(1)1;2( )1(1),11.2xxA xxx定义算法映射：3 53

5、9 335 7 253, 2,3,3,2 42 8 323 6 24A利用算法 可以产生不同的点列：xy1y=(x+1)/2A(x(1,k)A(x(2,k)解集合解集合把满足某些条件的点集定义为把满足某些条件的点集定义为解集合解集合当迭代点属当迭代点属于该集合时，停止迭代于该集合时，停止迭代常用的解集合：常用的解集合：|( )0|,( ),xf xx xKKTx xS f xbb 为点其中 是某个可接受的目标函数值。算法收敛问题算法收敛问题定义：定义：(1)( ):2XkA XYXxYAxAY设 为解集合，为算法映射。给定一个集合，若对于任意的初始点，算法映射 所产生的序列中任一收敛子序列的极

6、限都属于 ，则称算法映射 在 上收敛。().().Yglobal convergenceYlocal convergence若集合 是任意选取的（该集合不必限定在解集合的很小领域内），则相应的收敛性称为若集合 只能取接近 的点集，则相应的收敛性称为全局收敛性局部收敛性实用收敛准则实用收敛准则(1)( )(1)( )( )1.kkkkkxxxxx或者( )(1)( )(1)( )()()2.()().()kkkkkf xf xf xf xf x或者( )3.()().kf x无约束最优化中收敛速率收敛速率定义：定义：( )(1)_( )( )*lim*kkpkkkp 设序列收敛于，定义满足的非负

7、数 的上确界为序列的收敛级。pp若序列的收敛级为 ，则序列是 级称收敛的。11p序列是以收敛比 线性若且，则称收敛的。1,10pp若或者且，则序列是超线称性收敛的。收敛级收敛级p越大，序列收敛得越快；当收敛级越大，序列收敛得越快；当收敛级p相同时，收敛比相同时，收敛比越小，越小，序列收敛得越快。序列收敛得越快。 例：例： 01kaa 11lim0lim1,lim(1)()0kkkkkkrkkkaaaaraaaa 又且当时 ，以收敛比 线性收敛于 。例：例：20 | 1kaa1111222222222lim0limlim1,lim(2)kkkkkkkkkrkkkaaaaraaaa 又且当时 ，是

8、2级收敛的。例：例：1kk111(1)1lim0111limlim011111limlim(1)111kkkkkkkkkpkpkkkkkkkkkkkkkpkkkk 又是超线性收敛的。用二次终止性作为判断算法优劣的原因用二次终止性作为判断算法优劣的原因：(1)(1)正定二次函数具有某些较好的性质，因此一个好的算法应正定二次函数具有某些较好的性质，因此一个好的算法应能够在有限步内达到其极小点。能够在有限步内达到其极小点。(2)(2)对于一个一般的目标函数，若在其极小点处的对于一个一般的目标函数，若在其极小点处的HesseHesse矩阵矩阵正定，正定，因此可以猜想，对正定二次函数好的算法，对于一般目

9、标函因此可以猜想，对正定二次函数好的算法，对于一般目标函数也应具有较好的性质。数也应具有较好的性质。 2( )*1*|* |2TTfxfxfxxxxxfxxxoxx 若某个算法对于任意的正定二次函数，从任意的初始点出发，若某个算法对于任意的正定二次函数，从任意的初始点出发，都能经有限步迭代达到其极小点，则称该算法具有都能经有限步迭代达到其极小点，则称该算法具有二次终止性二次终止性。算法的二次终止性算法的二次终止性一维搜索的主要内容一维搜索的主要内容 精确线搜索精确线搜索 试探法试探法: 黄金分割法、黄金分割法、Fibonacci法、二分法法、二分法 函数逼近法函数逼近法: Newton法、割线

10、法、抛物线法、法、割线法、抛物线法、 三次插值法三次插值法 非精确线搜索非精确线搜索 Armijo步长规则、步长规则、Goldstein步长规则、步长规则、 Wolfe步长规则步长规则( )( )0()min()kkLSf xd( )( )( )( )min(Exact Line Search).kkkkkkkfxdfxd如果求得的 ，使得则称该一维搜索为精确一维搜索称为最优步长( )( )( )(Inexact Line Search).kkkkkf xdf x如果存在 ，使得则称该一维搜索为非精确一维搜索精确、非精确线搜索精确、非精确线搜索 0.618法法(Golden Section M

11、ethod)定义定义:上的单峰函数。是闭区间则称，时，当，时，当，有意的上的极小点，并且对任在是上的一元实函数，是定义在闭区间设,)()()(*)()(*,)(*,)(1212122121baxfxfxfxxxfxfxxxxbaxxbaxfxbaxf 0 a x1x2x*x1 x2 b x f(x)(a) 0 a x* x1 x2 b x f(x) f(x) f(x)(b)性质：通过计算区间性质：通过计算区间a, b内两个不同点处的函数值，内两个不同点处的函数值，就能确定一个包含极小点的子区间。就能确定一个包含极小点的子区间。 定理：定理：121212121221( ) , , , ( )()

12、 ,( )()( )(), ( )( )f xa bx xa bxxf xf xxa xf xf xf xf xxx bf xf x设是上的单峰函数，且，若，则对任意，有，若，则对任意，有。0.618法的基本思想：法的基本思想：通过取试探点使包含极小点的区间不断缩短，当区间通过取试探点使包含极小点的区间不断缩短，当区间长度小到一定程度时，区间上各点的函数值均接近极长度小到一定程度时，区间上各点的函数值均接近极小值，因此任意一点都可以作为极小点的近似。小值，因此任意一点都可以作为极小点的近似。 0.618法的计算公式法的计算公式:1111 , , ,(),()1()(),.2()(),.kkkk

13、kkkkkkkkkkkkkkkkkkkkkkfa bxa bkxa ba bffffxbabbffxaaa b 设 在上单峰，极小点，设进行第 次迭代时，有，取试探点，规定，计算。若，则有，令若，则有，令11,1,.2().kkkkkkkkkkkkkka bbababa 确定使它们满足：（ ）在中的位置是对称的，即（ ）每次迭代区间长度缩短比例相同，即)2()() 1 (11kkkkkkkkababab)(2)()(11kkkkkkkkkkabbbbaff得代入，时，当)(2)()(11kkkkkkkkkkababaaff得代入，时，当)()(1 (kkkkkkkkabaaba).()()()

14、(1,)()(211111111kkkkkkkkkkkkkkkkkkkkkkkabaaabaaaaabakabaffk，点次迭代中，需要取试探在第，则次迭代得出设在第算量。不必重新计算，减少计，则若令1121kkk(1)()()kkkkkkkkabaaba).)(1 ()()1 ()(1 ()(1 ()(1 ()(1 ()(1 ()(1 (1,)()(211111111kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkabaababaabababababakbbaffk，点次迭代中，需要取试探在第，则次迭代得出设在第算量。不必重新计算，减少计，则，即若令112211kkk618. 0

15、251, 025112得解方程)(618. 0)(382. 0kkkkkkkkabaabaa1,b1,L0bk-ak ,( , ),(0,1). 取 步 长其 中是 满 足 下 式 的 最 小 非 负 整 数 :Armijo步长规则步长规则根据目标函数的根据目标函数的Taylor展开式，展开式， 满足这种规则的步长一定满足这种规则的步长一定存在。存在。非精确搜索非精确搜索()()()()()()()()()()2()()(),()()(1)().0kkkkkTkkkkkTkfxdfxfxdfxdfxfxd 1设(0,). 取 步 长满 足 下 式 :由 于 充 分 小 时 ,第 二 式 必 不

16、 成 立 ,故 该 规 则 在保 证 目 标 函 数 下 降 的 前 提 下 ,使 下 一 迭 代 点 尽 可能 远 离 当 前 迭 代 点 .Goldstein步长规则步长规则()()()0,0.kkkfxdGoldstein 定 理 : 若()=关 于有 下 界则 必 存 在满 足步 长 规 则()()()()()111()()()212()0,()().0.0,()(1)()kTkkkTkkkTkfxdfxfxdfxfxd 证 明 : 由 于故()=在 充 分 小 时 ,()在()的 上 方由 于()关 于有 下 界 故()和()在的 正 半 轴 有 交 点 . 类 似 地 , ()=和()在的 正 半 轴 也 有 交 点 .取()和()与()的 一 个