最优化设计-4公开课获奖课件赛课一等奖课件.ppt

文档介绍：该【最优化设计-4公开课获奖课件赛课一等奖课件 】是由【梅花书斋】上传分享，文档一共【44】页，该文档可以免费在线阅读，需要了解更多关于【最优化设计-4公开课获奖课件赛课一等奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第四章 无 约 束 优 化 方 法
4-1 概述
4-2 最速下降法
4-3 牛顿型措施
4-4 共轭方向及共轭方向法
4-5 共轭梯度法
4-6 变尺度法
4-7 坐标轮换法
4-8 鲍威尔法
4-9 单形替代法
1
最优化设计/无约束优化措施
§4-1 概 述
无约束优化措施只考虑搜索的适行性，结合罚函数法，也可解约束优化问题。目前，成熟可靠的优化算法中，无约束优化措施占多数，总体上无约束优化措施的有效性及实用性都优于约束优化措施。
无约束优化措施可分为两大类：1)不求导数的直接法，重要有随机措施和直接搜索措施；2)求导数的间接法，按所求导数的最高阶数又可分为一阶措施和二阶措施。二阶措施很少采用。
图4-1为无约束极小化算法的粗框图。在§1-4 中已给出了优化算法的一般搜索迭代公式
xk+1= xk+xk (1－15)
xk+1= xk+kdk (1－16)
注意，在搜索迭代中，由于一维搜索需增长大量计算，因此，并不是所有优化措施都采用一维搜索。
2
最优化设计/无约束优化措施
§4-2 最速下降法 (1)
最速下降法以负梯度方向作为搜索方向并作一维搜索，因此又称为“梯度法”，属于求导数的间接法。它的基本思想早在1847年就已提出。尽管它自身不再被认为是一种有效的措施，但它是许多优化措施尤其是二次收敛措施的基础。
各点的梯度一般各不相似，因此“最速下降方向”仅对某一点附近而言，它具有局部性质。
如图4-2所示，当作一维搜索时，搜索方向是与目的函数等值线相切的，而切点的梯度方向是与等值线正交的。因此，相邻两次搜索方向互相垂直，搜索途径呈严重的“之”字形，尤其是目的函数靠近二次型时更为明显。
可以运用梯度矢量在极值点为零这一重要性质设置收敛准则
f(x*)   
3
最优化设计/无约束优化措施
§4-2 最速下降法 (2)
或

数值微分
数值微分在优化中是一个非常重要的问题，对优化结果影响较大。具体作法是用 代替 ，其中
f = f f0
式中，f0 = f(x0)，是计算偏导数那点 x0 处的目的函数值； f = f(x) = f(x1, x2, ···, xi+xi, ···, xn)，是其他变量保持不变，xi 变化为 xi+xi 时的目的函数值。
xi = (ui  li)
ui 和 li 分别为变量 xi 的估计上限和下限。
尽可能接近
，xi 应取得小一些，但过小又
为使
会引起舍入误差。一般可取
4
最优化设计/无约束优化措施
§4-2 最速下降法 (3)
例4-1 (图4-3) 求 f(x1, x2) = x12+25x22 的极小点。
取初始点 x0 =[2 2]T，则
f(x0) =104
f(x0) =[4 100]T
沿负梯度即[-4 -100]T方向进行一维搜索，有
x1 = x0  0 f(x0) =[2 2]T 0[4 100]T = [2 40 2 1000]T
在x1点
f(x1, x2) =(2 40)2+25(2 1000)2 =(0)
令’(0) = 0，有
2(2 40) (-4)+50(2 1000) (-100)
= -16+320  10000 +5000000
= 5000320  10016 = 0
0 =
得到第一次迭代的成果：
 x1 = [2 40 2 1000]T= [ --2]T
f(x1) =
通过十次迭代，得到最优解：
x* = [0 0]T
f(x* ) =0
5
最优化设计/无约束优化措施
§4-2 最速下降法 (4)
图4-3表达例4-1的搜索途径，目的函数等值线为椭圆。若进行代换
y1 = x1
y2 = 5x2
则 f(x1, x2) 变为(y1, y2)，等值线为一族同心圆。由于圆上任一点的负梯度方向都指向圆心，因此沿负梯度方向通过一次一维搜索即可找到最长处。
图4-5为最速下降法的程序框图。
6
最优化设计/无约束优化措施
§4-3 牛顿型措施 (1)
牛顿法是用目的函数二阶偏导数的间接措施，因类似于解非线性方程的牛顿法而得名，又叫“二阶导数法”、“拟线性法”。
将目的函数泰勒展开，保留到二次项，原目的函数就转变为下列二次型函数：
f(xk)+2f(xk)(x* xk) = 0
对于二次型函数，从理论上来说，牛顿法从任选初始点一步就能收敛到最长处。但对于目的函数不是二次型，或计算机截断误差的影响，往往需要多次迭代才能得到最长处。牛顿法的迭代公式为：
xk+1 = xk  [2f(xk)]-1f(xk) (k=0, 1, 2, ···)
2f(xk)为f(x)在xk点处的海赛矩阵。
f(x)  (x)= f(xk)+f(xk)T(x xk)+
(xxk)T2f(xk)(xxk)
为求极值点，对上式求偏导数，并令
=0，得到
7
最优化设计/无约束优化措施
§4-3 牛顿型措施 (2)
为防止牛顿法收敛到极大点而不是极小点，可在迭代过程中作一维搜索，形成改善的牛顿法—“阻尼牛顿法”，其程序框图见图4-6。
牛顿法的最大缺陷是需要计算海赛矩阵，并求其逆矩阵，计算量很大。
例4-2 用牛顿法求 f(x1, x2) = x12+25x22 的极小点。
取 x0 = [2 2]T
f(x0) = [2x10 50x20] T = [4 100]T
8
最优化设计/无约束优化措施
§4-3 牛顿型措施 (3)
例4-2(续)
由于f(x1, x2)是二次型函数，用牛顿迭代公式，一步就可达到最长处：
对照梯度法和牛顿法迭代公式，可以看出只相差一项海赛矩阵的逆矩阵。因此，牛顿法是对梯度法的深入修正。实际上，梯度法是对目的函数f(x)在点xk的一阶(线性)近似，而牛顿法是对f(x)在点xk 的二阶(二次)近似。
9
最优化设计/无约束优化措施
§4-4 共轭方向及共轭方向法 (1)
共轭方向的概念
二次正定函数的一般形式为：
式中，G为 nn 阶对称正定矩阵，b=[b1, b2,  ,bn]T 为常矢量，c为常数。
对于矩阵 G，若存在两个 n 维非零矢量 d0 和 d1，使 (d0)TGd1=0成立，则称d0和d1是G共轭方向(或G共轭矢量)。尤其地，当G为单位矩阵时，(d0)Td1=0 ，则称d0 和d1是正交的。矢量正交是矢量共轭的特例。
10
最优化设计/无约束优化措施