Lecture10 算法及算法复杂性一维搜索

1、最优化方法最优化方法 Optimization第十讲第十讲算法概述和基础、一维搜索算法概述和基础、一维搜索主要内容主要内容 算法概念算法概念 算法收敛准则算法收敛准则 全局收敛全局收敛, , 局部收敛局部收敛, , 收敛速度收敛速度 算法二次终止性算法二次终止性 算法复杂性算法复杂性 一维搜索一维搜索算法概念算法概念一下降迭代算法一下降迭代算法迭代：迭代：( )(1)( )( )1*lim*0*kkkkkxAxkkxxxxx从一点出发，按照某种规则 ，求出后继点，用代替 ，重复以上过程，得到一个解的序列，若该序列有极限点，即则称它收敛于。下降下降：在每次迭代中，后继点处的函数值要有所减少。在每

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

3、)( )3.( )()min().kkkkkkkxxdf xf xdf xd基于沿搜索方向使目标函数值下降最多，即沿射线求目标函数的极小由于这项工作是求以 为变量的一元函数的极小点，故常称这一过程为（最优）一维搜索，这样确定的步长为最佳步长。定理：定理：(1)( )( )(1)( )(1)( )()min()()0kkkkkkkkkkkTkf xxf xdf xdxxdf xd设目标函数具有一阶偏导数，由下列规则产生：则有。证明：证明：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 9 335 7 253, 2,3,3,2

5、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 设序列收敛于，定义满足的非负数 的上确界为序列的收敛级。pp若序列的收敛

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

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

9、数也应具有较好的性质。数也应具有较好的性质。 2( )*1*|* |2TTfxfxfxxxxxfxxxoxx 若某个算法对任意的若某个算法对任意的正定二次函数正定二次函数，从任意的初始点出发，都，从任意的初始点出发，都能经能经有限步有限步迭代达到其极小点，则称该算法具有迭代达到其极小点，则称该算法具有二次终止性二次终止性。算法的二次终止性算法的二次终止性算法复杂性算法复杂性 描述算法的存储要求和运行时间要求，分为描述算法的存储要求和运行时间要求，分为算法的空间复杂性和算法的时间复杂性。算法的空间复杂性和算法的时间复杂性。利用算法需要的利用算法需要的初等运算次数初等运算次数表示算法的表示算法的时

10、间复杂性时间复杂性。算法复杂性算法复杂性求解实例求解实例I I的算法的的算法的基本计算总次数基本计算总次数C C( (I I) )是实例输入长度是实例输入长度d d( (I I) )的一个函数，该函数被另一个函数的一个函数，该函数被另一个函数g g( (x x) )控制，即存控制，即存在一个函数在一个函数g g( (x x) )和一个常数和一个常数a a，使得，使得 ( )CIag d I多项式时间算法与指数时间算法多项式时间算法与指数时间算法 输入规模输入规模(input size)：表示一个：表示一个实例实例所所需要的字符串长度。需要的字符串长度。 一般的，使用一般的，使用 位二进制就可以

11、位二进制就可以表示任意整数表示任意整数r。 线性规划的输入规模为：线性规划的输入规模为：21log r 22212211121log1log1log |1log |1log |2log |(, ,)njjmnmijjijiLmncabmnmnPPA b c为中所有非零数的乘积多项式时间算法与指数时间算法多项式时间算法与指数时间算法 ( ( )C Iag d I假设问题和解决该问题的一个算法已经给定，若给定该问题假设问题和解决该问题的一个算法已经给定，若给定该问题的一个实例的一个实例I I，存在，存在多项式函数多项式函数g g( (x x) )，使得，使得成立，则称该算法对实例成立，则称该算法对

12、实例I I是是多项式时间算法多项式时间算法. .若存在若存在g g( (x x) )为多项式函数且对该问题任意一个实例为多项式函数且对该问题任意一个实例I I ，都有，都有上式成立，则称该算法为解决该问题的多项式时间算法。上式成立，则称该算法为解决该问题的多项式时间算法。当当g g( (x x) )为指数函数时，称相应的算法为为指数函数时，称相应的算法为指数时间算法指数时间算法。（1 1）随着问题输入规模的增加，算法的计算量（即）随着问题输入规模的增加，算法的计算量（即算法复杂性）呈多项式增长算法复杂性）呈多项式增长. .（2 2）一个多项式时间算法利用另一个多项式时间算）一个多项式时间算法利

13、用另一个多项式时间算法作为其法作为其“子程序子程序”，构造一个新的复合型算法，构造一个新的复合型算法，则新算法仍是多项式时间算法。则新算法仍是多项式时间算法。多项式时间算法的优点多项式时间算法的优点122min10. .21010,2,0,1,2,nn iiiijiijj iixstxxinxin上例用单纯形算法需要上例用单纯形算法需要2n-1次迭代次迭代单纯形算法的复杂性单纯形算法的复杂性 精确线搜索精确线搜索 试探法试探法: 黄金分割法、黄金分割法、Fibonacci法、二分法法、二分法 函数逼近法函数逼近法: Newton法、割线法、抛物线法、法、割线法、抛物线法、 三次插值法三次插值法

14、 非精确线搜索非精确线搜索 Armijo步长规则、步长规则、Goldstein步长规则、步长规则、 Wolfe步长规则步长规则一维搜索一维搜索( )( )0()min()kkLSf xd( )( )( )( )min(Exact Line Search).kkkkkkkfxdfxd如果求得的 ，使得则称该一维搜索为精确一维搜索称为最优步长( )( )( )(Inexact Line Search).kkkkkf xdf x如果存在 ，使得则称该一维搜索为非精确一维搜索精确、非精确线搜索精确、非精确线搜索 函数逼近法：牛顿法函数逼近法：牛顿法基本思想：基本思想：在极小点附近用二阶在极小点附近用二

15、阶Taylor多项式近似。多项式近似。)(minxf2)()()()()()(21)()()(kkkkkxxxfxxxfxfx 令( )( )( )( )()()()0kkkxfxfxxx又令)()()()()()()1()1(kkkkkxfxfxxxx ，则的驻点，记作得定理：定理：(1)()( )()0()0kfxxfxfxxxxx设存在， 满足，初点充分接近 ，则牛顿法产生的序列至少以二级收敛速度收连续三阶导敛于数。证明：证明：)()()(xfxfxxA 射牛顿法可定义为算法影|)(xxx定义函数x设解集合为)(,)()1()(kkkxAxxx设(1)(1)( )( )( )( )( )

16、( )( )( )( )( )( )( )( )2( )( )()|()1()()()()|()|1( )()()() |()|11() |( )|()|2kkkkkkkkkkkkkkkkkxxxfxxxxfxfxxfxfxfxfxfxxxfxfxxxfxxfx其中 在和 之间。21)(21)(| )(| ,| )(|0, 0)()()(kxfkxfxxxkkxxxfxfxfkk 处，有的闭区间上的每一点和使得在包含时，存在接近当连续，和(1)( )2( )21()2kkkkxxxxxk是二级收敛。12)1(12)1( xxkkxx，使得充分接近取初点| |)()1()1()(xxxxxxxx

17、xXxkkk且有。上连续在为紧集，是下降函数，且xxXxAXk)()(算法步骤算法步骤:(0)1.,0,0 xk给定初始点允许误差置。. 3;,| )(|. 2)()(否则转则停止计算，得点若kkxxf。，返回置计算点21,)(. 3)()()()1()1( kkxfxfxxxkkkkk缺点：缺点：初初始始点选择十分重要。如果初始点靠近极小点，则点选择十分重要。如果初始点靠近极小点，则可能很快收敛；如果初始点远离极小点，迭代产生的点可能很快收敛；如果初始点远离极小点，迭代产生的点列可能不收敛于极小点。列可能不收敛于极小点。 例：例：.01. 0),21 (5minxxex2)0(x取初始点解：

18、解：00002. 06096. 13012. 5012. 0612. 12349. 5349. 0677. 11388. 7388. 220)()()( kkkxfxfxk为近似解。6096. 1x0( )minarctg*0.xf xt dtx最优解例：例：用用Newton法求解：法求解：21( ),( )1fxarctg xfxx1110.7854220.57080.51781.325830.11690.11631.013740.001061kkkkxfxfx1121.1071523.53571.295213.50313.95kkkkxfxfx非精确搜索非精确搜索()()()()()00 1,()()()kmkkkmkkmkTkmfxdfxfxd设 ,( , ),(0,1). 取 步 长其 中是 满 足 下 式 的 最 小 非 负 整 数 :Armijo步长规则步长规则根据目标函数的根据目标函数的Taylor展开式，展开式， 满足这种规则的步长一定满足这种规则的步长一定存在。存在。非精确搜索非精确搜索()()()()()()()()()()2()()(),()()(1)().0kkkkkTkkkkkTkfxdfxfxdfxdfxfxd 1设(0,)