第三章 非线性规划-无约束问题的最优化方法

《第三章 非线性规划-无约束问题的最优化方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、研究生课程《工程数学》之“最优化方法”第三章无约束问题的最优化方法能源与动力工程学院CollegeofEnergyandPowerEngineering第三章无约束问题的最优化方法第一节变量轮换法第二节最速下降法第三节牛顿法第四节共轭梯度法本章主要介绍构造无约束问题(多维)搜索方向的方法。这些方法大致可分为两类：第一类：直接搜索方法。在搜索过程中，只用到目标函数值，不需要计算其导数。例如，变量轮换法第二类：解析方法。在搜索过程中，要用到目标函数的导数。例如最速下降法、牛顿法、共轭梯度法等。一、基本思想认为最有利的搜索方向是各坐标轴的方向，因此它轮流按各坐标的

2、方向搜索最优点。过程：从某一个给定点出发，按第i个坐标轴xi的方向搜索时，假定有n个变量，则只有xi在变化，其余(n-1)个变量都取给定点的值保持不变。这样依次从x1到xn做了n次单变量的一维搜索，完成了变量轮换法的一次迭代。第一节变量轮换法二、算法步骤设问题为记即ei为第i个分量为1，其余分量为0的单位向量。第1步：给定初始点第2步：从x(1)出发，先沿第1个坐标轴方向e1进行一维搜索，记求得的最优步长为l1，则可得到新的点x(2)：第一节变量轮换法再从x(2)出发，先沿第2个坐标轴方向e2进行一维搜索，记求得的最优步长为l2，则可得到新的点x(3)：……

3、完成了变量轮换法的一次迭代第一节变量轮换法第3步：令x(1)=x(n+1)，返回第二步，再沿着各坐标轴方向依次进行一维搜索。直到最新点x(n+1)满足给定的精度要求为止，输出x(n+1)作为f(x)极小点的近似值。1.坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量的优化问题；特点总结：2.算法的基本思想简单，不需要进行导数运算；3.搜索效率低，收敛速度慢，只有对那些具有特殊结构的函数使用起来尚好。第一节变量轮换法第一节变量轮换法例题1用变量轮换法求解给定初始点当时，停止迭代

4、答案：第二节最速下降法解：从初始点出发，沿x1轴方向e1进行一维搜索：第二节最速下降法再从x(2)点出发，沿x2轴方向e2进行一维搜索：第二节最速下降法再从x(3)点出发，沿x3轴方向e3进行一维搜索：故即为极小点。f(x(4))=0第二节最速下降法因为，故以x(4)点作为新的x(1)，进行新一轮迭代。设问题为一、基本思想式中f(x)具有一阶连续偏导数，有极小点x*。若现已求得x*的第k次近似值x(k)，为了求得第k+1次近似值x(k+1)，需选定方向p(k)。p(k)有什么特征呢？令，其中p(k)为某个下降方向。现将f(x)在p(k)处展开：第二节最速下降

5、法略去无穷小，可以得到由于所以上式表明了搜索方向p(k)应该满足的条件：p(k)与x(k)点的梯度的点积小于0。第二节最速下降法因为当搜索方向确定后，进行下面的一维搜索：显然，只有时，目标函数值f(x)在x(k)点附近下降最快，称之为负梯度方向。可以用已经学过的一维搜索方法进行搜索，求得步长因子第二节最速下降法也可以用求导的方法得出最优步长因子第二节最速下降法二、最速下降法的算法步骤第2步：求梯度向量的范数第1步：给定初始点，及终止误差，令k=0若，停止计算，输出x(k)作为极小点的近似值，否则转到下一步。第3步：构造负梯度方向第4步：进行一维搜索，求得最佳

6、步长因子后，令然后再令k=k+1，转到第二步。第二节最速下降法例题2用最速下降法求解下述函数的极小点。给定初始点答案：第二节最速下降法解：求最佳步长l0第二节最速下降法则：第二节最速下降法三、最速下降法的锯齿现象第二节最速下降法一、基本思想为了寻求收敛速度较快的求解无约束问题的优化算法，可在每一轮迭代时用适当的二次函数，如x(k)点的二阶Taylor多项式来近似目标函数，并用迭代点x(k)处，指向近似二次函数的极小点方向作为搜索方向p(k)。二、牛顿方向和牛顿方法设问题为式中f(x)在x(k)点处具有二阶连续偏导数，且在点x(k)处的黑塞矩阵正定，x(k)是

7、f(x)的一个极小点的第k轮估计值。第三节牛顿法第三节牛顿法令则1.求Q(x)的平稳点：(数)(向量)(矩阵)第三节牛顿法令，记x(k+1)为Q(x)的平稳点将b,A的关系式代入上式，可以得到令—牛顿方向所以实际上，牛顿法已经规定步长因子第三节牛顿法2.牛顿法的算法步骤第2步：求梯度向量，并计算第1步：给定初始点，及终止误差，令k=0若，停止迭代，输出x(k)作为极小点的近似值，否则转到下一步。第3步：构造牛顿方向。根据确定第4步：根据计算x(k+1)作为下一轮迭代点，令k=k+1，转第2步。第三节牛顿法例题3用牛顿法求解给定初始点答案：与最速下降法的对比：

8、(1)牛顿法对于二次正定函数只需做1次迭代就得到最优