第3章迭代终止准则及一维搜索方法教材

一维牛顿法也称为一维牛顿-拉夫逊方法，是一种迭代的优化算法，用于求解一维非线性函数的极值点。

这种方法通过利用函数的二阶导数信息来逼近极值点，并在每次迭代中更新搜索方向，以快速收敛到最优解。

一维牛顿法的具体步骤如下：
初始化：选择初始点x0，并设定迭代终止条件，如迭代次数或函数值的收敛阈值。

计算一阶和二阶导数：计算函数f(x)在当前点xk处的一阶导数f'(xk)和二阶导数f''(xk)。

更新搜索方向和步长：根据二阶导数的信息，计算搜索方向dk和步长αk。

更新当前点：计算新的点xk+1 = xk + αk * dk。

判断终止条件：检查是否满足终止条件，如果满足则停止迭代，否则返回步骤2。

例如，对于函数f ( x ) = x 3 −2 sin ⁡( x ) f(x) = x^3 - 2\sin(x)f(x)=x3−2sin(x)，在A AA点处对函数f ( x ) f(x)f(x)展开，得到近似的二次函数φ( x ) \varphi(x)φ(x)，φ( x ) \varphi(x)φ(x)的最小值在B BB点处取得，高斯牛顿法的下一步迭代点即为与B BB点横坐标相等的C CC点。

如此，只需数次，迭代能够达到很高的精度，可见牛顿法收敛速度快。

吉林大学教师教案（20 07 ~2008 学年第二学期）课程名称：机械优化设计年级：20XX级01-09班教研室：机械设计及自动化任课教师：李风吉林大学教务处制教案等值线—等高线●等值线●等高线：●它是由许多具有相同目标函数值的设计点所构成的平面曲线。

课后小结1：人字架的优化数学模型2：数学模型的基本构成第二节机械优化问题示例第三节优化设计问题的数学模型2学时五、优化问题的几何解释●无约束优化问题就是在没有限制的条件下，对设计变量求目标函数的极小点。

在设计空间内，目标函数是以等值面的形式反映出来的，则无约束优化问题的极小点即为等值面的中心。

●约束优化问题是在可行域内对设计变量求目标函数的极小点，此极小点在可行域内或在可行域边界上。

课后小结1．机械优化设计数学模型的一般形式2：优化设计的数学基础，梯度的概念第四节优化设计问题的基本解法●求解优化问题：解析解法●数值的近似解法。

2学时●解析解法：把所研究的对象用数学方程(数学模型)描述出来，然后再用数学解析方法(如微分、变分方法等)求出优化解。

●数值解法：只能通过大量试验数据用插值或拟合方法构造一个近似函数式，再来求其优化解，这种方法是属于近似的、迭代性质的数值解法。

不仅可用于求复杂函数的优化解，也可以用于处理没有数学解析表达式的优化设计问题。

因此，它是实际问题中常用的方法。

●可以按照对函数导数计算的要求，把数值方法分为需要计算函数的二阶导数、一阶导数和零阶导数(即只要计算函数值而不须计算其导数)的方法。

●由于数值迭代是逐步逼近最优点而获得近似解的，所以要考虑优化问题解的收敛性及迭代过程的终止条。

收敛性是指某种迭代程序产生的序列收敛于第二章优化设计的数学基础第一节多元函数的方向导数与梯度二、二元函数的梯度考虑到二元函数具有鲜明的几何解释，并且可以象征性地把这种解释推广到多元函数中去，所以梯度概念的引入也先从二元函数人手。

等值线—等高线●等值线●等高线：●它是由许多具有相同目标函数值的设计点所构成的平面曲线。

第三章 牛顿法§3.1 最速下降法一、最速下降法在极小化算法中，若每次都以迭代点处的负梯度方向为搜索方向，产生的算法称为最速下降法，它是无约束最优化算法中最简单、最基本的算法。

算法描述：1） 给出初始点0n x R ∈，允许误差0ε>，0k =； 2） 计算k k d g =-，若k g ε≤，Stop 令 *k x x ≈； 3） 由一维搜索确定步长因子k α，使得()min ()k k k k k f x d f x d ααα≥+=+4） 令1k k k k x x d α+=+，1k k =+，go to 2).二、最速下降算法的收敛性定理3.1 设1f C ∈，则最速下降算法产生的点列{}k x 的每个聚点均为驻点。

证明：设x 是{}k x 的一个聚点，则存在子序列{}1k K x ，使得1lim k k K x x ∈=令()k k d f x =-∇，由1f C ∈，知{}1()k K f x ∇是收敛序列，故{}1k K d 有界，且1lim ()k k K d f x ∈=-∇由定理2.6有2()(())()0Tf x f x f x ∇-∇=-∇=故有 ()0f x ∇=。

定理 3.2 设()f x 二次连续可微，且2()f x M ∇≤，则对任何给定的初始点0n x R ∈，最速下降算法或有限终止，或lim ()k k f x →∞=-∞，或lim ()0k k f x →∞∇=。

证明：不妨设k ∀，()0k f x ∇≠。

由定理2.5有211()()()2k k k f x f x f x M+-≥∇ 于是 []120101()()()()()2kk k i i i i i f x f x f x f x f x M -+==-=-≥∇∑∑令k →∞，由{()}k f x 为单调下降序列，则要么lim ()k k f x →∞=-∞，要么 lim ()0k k f x →∞∇=。

一维搜索方法：（方法比较）“成功—失败”法、二分法、0.618法（黄金分割法）、牛顿法、二次插值法、D.S.C法、Powell法、D.S.C—Powell组合法。

1、“成功—失败”法：主要思想：从一点出发，按一定的步长搜索新点，若成功，加大步长继续搜索，否则，缩短步长小步后退。

此方法可以求最优解所在区间，称为“搜索区间”。

2、二分法：主要思想：区间[a,b]的中间值x0，判断f（x）的导数在三个点处的值，舍去一部分区间再求f(x)的极小值。

3、0.618法：等比例收缩原则，每次留下来的区间长度是上次留下来的区间长度的w倍。

以及对称原则、去坏留好原则。

W=0.6184、牛顿法：基本思想：在极小值点附近用目标函数的二阶泰勒多项式近似代替目标函数，从而求得目标函数的极小值点的近似值。

5、二次插值法：牛顿法是在x k附近的目标函数用泰勒多项式近似代替，而此法是将f(x)用二次插值多项式p(x)近似代替。

把p(x)的极小值点作为f(x)极小值点的代替，从来求得函数的极小值。

6、D.S.C法：主要思想：利用成功—失败法寻找靠近极小值点的三点，进行二次插值。

优点是：收敛速度快，且不要求函数可微。

7、Powell法：基本思想：在搜索方向开始得到三点x0,x1,x2后，作二次插值，求得最小值x，在四点中去坏留好，在余下的三点中再作二次插值……8、D.S.C—Powell组合法：几种方法比较：D.S.C—Powell组合法是非常好的一种方法，它比任何一个单个方法都好D.S.C—Powell组合法与0.618法比较：D.S.C—Powell法中函数值的计算要比黄金分割法少得多，一般来讲它优于黄金分割法。

但：D.S.C—Powell法不一定能收敛到最优解。

最速下降法与修正牛顿法：对于正定二次函数，牛顿法一步可以求得最优解，对于非二次函数，牛顿法并不能保证有限次求得其最优解，但由于目标函数在极小值的附近近似于二次函数，故当初始点靠近极小值时，牛顿法收敛的速度比较快。