Lecture6算法和算法复杂性一维搜索

《Lecture6算法和算法复杂性一维搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优化方法Optimization第十一讲第八章算法和算法复杂性第九章一维搜索主要内容算法概念算法收敛准则全局收敛,局部收敛,收敛速度算法二次终止性算法复杂性内点法:路径跟踪法算法概念一．下降迭代算法迭代：下降：在每次迭代中，后继点处的函数值要有所减少。下降迭代算法的步骤：选取搜索方向是最关键的一步，各种算法的区别，主要在于确定搜索方向的方法不同。定理：证明：二．算法映射定义：例：例：xy1y=(x+1)/2A(x(1,k))A(x(2,k))解集合把满足某些条件的点集定义为解集合．当迭代点属于该集合时，停止迭代．常用的解集合：算法收敛问题定义：实用收敛准则收敛速率定义：收敛

2、级p越大，序列收敛得越快；当收敛级p相同时，收敛比β越小，序列收敛得越快。例：例：例：用二次终止性作为判断算法优劣的原因：(1)正定二次函数具有某些较好的性质，因此一个好的算法应能够在有限步内达到其极小点。(2)对于一般的目标函数，若在其极小点处Hesse矩阵正定，因此可以猜想，对正定二次函数好的算法，对于一般目标函数也应具有较好的性质。若某个算法对任意的正定二次函数，从任意的初始点出发，都能经有限步迭代达到其极小点，则称该算法具有二次终止性。算法的二次终止性算法复杂性描述算法的存储要求和运行时间要求，分为算法的空间复杂性和算法的时间复杂性。利用算法需要的初等运算次数表示算法

3、的时间复杂性。算法复杂性求解实例I的算法的基本计算总次数C(I)是实例输入长度d(I)的一个函数，该函数被另一个函数g(x)控制，即存在一个函数g(x)和一个常数a，使得多项式时间算法与指数时间算法输入规模(inputsize)：表示一个实例所需要的字符串长度。一般的，使用位二进制就可以表示任意整数r。线性规划的输入规模为：多项式时间算法与指数时间算法假设问题和解决该问题的一个算法已经给定，若给定该问题的一个实例I，存在多项式函数g(x)，使得成立，则称该算法对实例I是多项式时间算法.若存在g(x)为多项式函数且对该问题任意一个实例I，都有上式成立，则称该算法为解决该问题的多

4、项式时间算法。当g(x)为指数函数时，称相应的算法为指数时间算法。（1）随着问题输入规模的增加，算法的计算量（即算法复杂性）呈多项式增长.（2）一个多项式时间算法利用另一个多项式时间算法作为其“子程序”，构造一个新的复合型算法，则新算法仍是多项式时间算法。多项式时间算法的优点上例用单纯形算法需要2n-1次迭代单纯形算法的复杂性精确线搜索试探法:黄金分割法、Fibonacci法、二分法函数逼近法:Newton法、割线法、抛物线法、三次插值法非精确线搜索Armijo步长规则、Goldstein步长规则、Wolfe步长规则一维搜索精确、非精确线搜索函数逼近法：牛顿法基本思想：在极小

5、点附近用二阶Taylor多项式近似。定理：证明：算法步骤:缺点：初始点选择十分重要。如果初始点靠近极小点，则可能很快收敛；如果初始点远离极小点，迭代产生的点列可能不收敛于极小点。例：解：例：用Newton法求解：非精确搜索Armijo步长规则根据目标函数的Taylor展开式，满足这种规则的步长一定存在。非精确搜索Goldstein步长规则非精确搜索Wolfe步长规则