无约束优化方法(已排)

《无约束优化方法(已排)》由会员分享，可在线阅读，更多相关《无约束优化方法(已排)（66页珍藏版）》请在金锄头文库上搜索。

1、第4章 无约束优化方法l第1章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题 大都如此。l为什么要研究无约束优化问题：l(1)有些实际问题，其数学模型本身就是一个无约束优化问题。l(2) 通过熟悉它的解法可以为研究约束优化问题打下良好的基础。l(3)约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部 分，也是优化方法的基础。1各种无约束优化解法的区别：搜索方向的不同分类：（1）不使用导数信息（2）要使用导数。搜索方向的构成问题乃是无约束优化方法的关键。l无约束优化问题是：l求n维设计变量

2、l 使目标函数： 2如何搜索 目标？3函数的负梯度方向是函数值下降最快的方向。 搜索方向d取该点的负梯度方向 (最速下降方向) ，使函数值在该点附近的范围内下降最快 。为了使目标函数值沿搜索方向 能够获得最大的下降 值，其步长因子 应取一维搜索的最佳步长。即有4.1 梯度法4在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的 是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。根据一元函数极值的必要条件和多元复合函数求导公式，得 56例4-1 求目标函数 的极小点。解 取初始点

3、则初始点处函数值及梯度分别为沿负梯度方向进行一维搜索，有为一维搜索最佳步长，应满足极值必要条件 7算出一维搜索最佳步长 第一次迭代设计点位置和函数值 继续作下去，经10次迭代后，得到最优解 8将上例中目标函数 引入变换y1=x1, y2=5x2 则函数f(x)变为：其等值线由椭圆变成一簇同心圆。仍从 即 出发进行最速下降法寻优。 此时：沿负梯度方向进行一维搜索：这一问题的目标函数f(x)的等值线为一簇椭圆。9 为一维搜索最佳步长，可由极值条件：由从而算得一步计算后设计点的位置及其目标函数：10经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：等值线由椭圆变成圆。 1 111l（1）

4、理论明确，程序简单，对初始点要求不严格。l（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。l（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。l（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。梯度法的特点梯度法的特点12利用有 限的信 息！ 13设 为 的极小点 l l基本思想基本思想 ：l l在在x xk k邻域内用一个二次函数邻域内用一个二次函数 来近似代替原目标函数来近似代替原目标函数 ，并将，并将

5、的极小点作为对目标函数的极小点作为对目标函数求优的下一个迭代点求优的下一个迭代点 。经多次迭代，使之逼近目标函 。经多次迭代，使之逼近目标函 数数 的极小点。的极小点。4.2 牛顿法及其改进14这就是多元函数求极值的牛顿法迭代公式。 对于二次函数 ，海赛矩阵是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。 例42 求目标函数 的极小点。解 取初始点15阻尼牛顿法 阻尼因子 ，沿牛顿方向进行一维搜索的最佳步长，由下式求得： l经过一次迭代即求得极小点 ，l函数极小值 。从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻

6、的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升 。16阻尼牛顿法称序框图17牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的主要缺点是每次迭代都要计算函数的二阶导数矩阵，并对该矩阵求逆。这样工作量很大。特别是矩阵求逆，当维数高时工作量更大 。18一般迭代式：梯度法：牛顿法：阻尼牛顿法：梯度法与牛顿法：19变尺度法是在牛顿法的思想上进行了重大改进的一类 方法 1. 基本思想变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。 例如在用最速下降法求 的极小值时 ,需要进行10次迭代才能达到极小点如作变换 y1=x1, y2=5x2把 的尺度放大

7、5倍，则目标函数等值线由一簇椭圆变成一簇同心圆。x24.3 变尺度法20消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。梯度法构造简单，只用到一阶偏导数，计算量小，迭代初期收敛速度快，但当迭代到最优点附近时收敛速度很慢；牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。能不能将两种算法的优点综合起来，扬长避短？21Ak 是需要构造nn的一个对称方阵 ，如Ak=I, 则得到梯度法 ；则得到阻尼牛顿法 ；如当矩阵Ak 不断地迭代而能很好地逼近 时，就可以不再需要计算二阶导

8、数。 变尺度法的关键在于尺度矩阵Ak的产生 。对于二次函数:22进行尺度变换在新的坐标系中，函数f(x)的二次项变为：目的：减少二次项的偏心如G是正定，则总存在矩阵Q，使得：用矩阵Q-1右乘等式两边，得：用矩阵Q左乘等式两边，得：所以上式说明：二次函数矩阵G的逆阵，可以通过尺度变换 矩阵Q来求得。23牛顿迭代公式：记：牛顿方向：迭代公式：A 称为尺度变换矩阵24在例42中如取25求得 ：26中修正矩阵 的不断修正，在迭代中逐步逼近于 因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度 。 1）DFP法（Davidon-Fletcher-Powell)式中。从初始矩阵A0=I(单位矩阵)开始，

9、通过对公式 2. 2.构造尺度矩阵构造尺度矩阵A Ak k272 2）BFGSBFGS算法算法( (BroydenBroyden-Fletcher-Gold-Fletcher-Gold frob frob- -ShannoShanno ) )DFP算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法不稳定。BFGS算法对于维数较高问题具有更好的稳定性。2829取初始变尺度矩阵为单位矩阵A0=I，则第一次搜寻方向为 例例4-34-3 用 用DFPDFP算法求下列问题的极值：算法求下列问题的极值：解： 1）取初始点 ，为了按DFP法构造第一次搜寻方向d0，需计算初始点处的

10、梯度30为一维搜索最佳步长，应满足得:,2）再按DFP法构造点x1处的搜寻方向d1，需计算l沿d0方向进行一维搜索，得31代入校正公式=32=第二次搜寻方向为再沿d1进行一维搜索，得33为一维搜索最佳步长，应满足,得3）判断x2是否为极值点梯度: 海赛矩阵 :34梯度为零向量,海赛矩阵正定。可见点满足极值充要条件，因此为极小点。 35当G为单位矩阵时，假设目标函数f(x) 在极值点附近的二次近似函数为对二维情况任选取初始点x0沿某个下降方向d0作一维搜索，得x14.4 共轭方向法l1.共轭方向：l 设G为nn阶实对称正定矩阵，如果有两个n维向量d0和d1满足 ，则称向量d0与d1 关于矩阵G共

11、轭。36因为 是沿d0方向搜索的最佳步长，即在点x1处函数f（x）沿 方向d0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有如果按最速下降法，选择负梯度方向 为搜索方向，则 将发生锯齿现象 。取下一次的迭代搜索方向d1直指极小点x* .0d0x0x1x*1 11d1d237那么这样的d1方向应该满足什么条件呢 ?对于前述的二次函数:有当 时 。x*是f(x)极小点，应满足极值必要条件，故有将等式两边同时左乘 得：l如果能够选定这样的搜索方向，那么对于二元二次函数 只需顺次进行d0、d1两次直线搜索就可以求到极小点x* ，即有38就是使d1直指极小点x* ， d1所必须满足的条件

12、。两个向量d0和d1称为G的共轭向量，或称d0和d1对G是共轭方向。 2.共轭方向的性质性质1 若非零向量系d0,d1,d2,dm-1是对G共轭，则这m个向量是线性无关的。 性质2 在n维空间中互相共轭的非零向量的个数不超过n。 性质3 从任意初始点出发，顺次沿n个G的共轭方向d0,d1, d2,进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。 39关键：新的共轭方向确定40设与dk共轭的下一个方向dk+1由dk和点xk+1的负梯度的线形组合构成，即：共轭条件：3. 3.共轭梯度法共轭梯度法l共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构

13、造出来。l从xk出发，沿负梯度方向作一维搜索:41解得：令为函数的泰勒二次展开式则上两式相减，并代入则：42将式与式两边相乘，并应用共轭条件得 ：因此43，已知初始点1,1T例题例题 4-4 4-4 求下列问题的极值 求下列问题的极值l解： 1）第一次沿负梯度方向搜寻l计算初始点处的梯度为一维搜索最佳步长，应满足l迭代精度 。 44得:2）第二次迭代：代入目标函数45得因收敛。由从而有：46对函数：基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。 1.共轭方向的生成jkkkdddjg gk+1xxk+1设xk, xk+1为从不同点出发，沿同一方向dj进行一维搜索而到的两个极小点.

14、4.5 鲍威尔方法l鲍威尔（Powell）法是直接利用函数值来构造共轭方向的一种方法 47另一方面，对于上述二次函数，其xk, xk+1两点处的梯度可表示为:因而有取这说明只要沿dj方向分别对函作两次一维搜索，得到两个极小点xk和xk+1 ，那么这两点的连线所给出的方向dk就是与dj一起对G共轭的方向。l梯度和等值面相垂直的性质, dj和 xk, xk+1两点处的梯度gk,gk+1之间存在关系:481）任选一初始点x0，再选两个线性无关的向量 ，如坐标轴单位向量 e1=1,0T和e2=0,1T作为初始搜索方向。2）从x0出发，顺次沿e1， e1作一维搜索，得 点，两点连线得一新方 向d1x1x

15、2x0oe1e2d1d2x*12. 2.基本算法基本算法l二维情况描述鲍威尔的基本算法: 49用 d1代替e1形成两个线性无关向量d1 ,e2 ，作为下一 轮迭代的搜索方向。再 从出发，沿d1作一维搜索得点 ，作为下一轮迭代的初始点。 x1x2x0oe1e2d1d2x*13）从出发 ，顺次沿 e2,d1 作一维搜索，得到点 ，两点连线得一 新方向:沿d2作一维搜索得点x2 .即是二维问题的极小点x* .方法的基本迭代格式包括共轭方向产生和方向替换两主要 步骤。 50上述基本算法仅具有理论意义 。l 把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是：l在每一轮迭代中总有一个始点（第一轮的始点是任选的 初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一