《无约束优化方法(已排).ppt》由会员分享,可在线阅读,更多相关《无约束优化方法(已排).ppt(66页珍藏版)》请在金锄头文库上搜索。
1、第第4章章无约束优化方法无约束优化方法l第第1章所列举的机械优化设计问题,都是在一定的限制条件章所列举的机械优化设计问题,都是在一定的限制条件下追求某一指标为最小,它们都属于约束优化问题。工程问题下追求某一指标为最小,它们都属于约束优化问题。工程问题大都如此。大都如此。l为什么要研究无约束优化问题:为什么要研究无约束优化问题:l(1)有些实际问题,其数学模型本身就是一个无约束优化问有些实际问题,其数学模型本身就是一个无约束优化问题。题。l(2) 通过熟悉它的解法可以为研究约束优化问题打下良好的通过熟悉它的解法可以为研究约束优化问题打下良好的基础。基础。l(3)约束优化问题的求解可以通过一系列无
2、约束优化方法来约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成达到。所以无约束优化问题的解法是优化设计方法的基本组成部分,也是优化方法的基础。部分,也是优化方法的基础。1各种无约束优化解法的区别:搜索方向的不同各种无约束优化解法的区别:搜索方向的不同分类:分类:(1)不使用导数信息)不使用导数信息(2)要使用导数。)要使用导数。搜索方向的构成问题乃是无约束优化方法的关键。搜索方向的构成问题乃是无约束优化方法的关键。l无约束优化问题是:无约束优化问题是:l求求n维设计变量维设计变量l 使目标函数:使目标函数: 2如何搜索如何搜索目标?目标?3
3、函数的负梯度方向是函数值下降最快的方向。函数的负梯度方向是函数值下降最快的方向。搜索方向搜索方向d取该点的负梯度方向取该点的负梯度方向 (最速下降方向最速下降方向) ,使,使函数值在该点附近的范围内下降最快函数值在该点附近的范围内下降最快 。为为了了使使目目标标函函数数值值沿沿搜搜索索方方向向 能能够够获获得得最最大大的的下下降降值,其步长因子值,其步长因子 应取一维搜索的最佳步长。即有应取一维搜索的最佳步长。即有4.1梯度法梯度法4在最速下降法中,相邻两个迭代点上的函数梯度相互垂在最速下降法中,相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向,因此相邻两个搜索方向互直。而搜索方向
4、就是负梯度方向,因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程,走的相垂直。这就是说在迭代点向函数极小点靠近的过程,走的是曲折的路线。形成是曲折的路线。形成“之之”字形的锯齿现象,而且越接近极字形的锯齿现象,而且越接近极小点锯齿越细。小点锯齿越细。根据一元函数极值的必要条件和多元复合函数求导公式,得根据一元函数极值的必要条件和多元复合函数求导公式,得 56例例4-1求目标函数求目标函数 的极小点。的极小点。解取初始点解取初始点则初始点处函数值及梯度分别为则初始点处函数值及梯度分别为沿负梯度方向进行一维搜索,有沿负梯度方向进行一维搜索,有为一维搜索最佳步长,应满足极值必要条
5、件为一维搜索最佳步长,应满足极值必要条件 7算出一维搜索最佳步长算出一维搜索最佳步长 第一次迭代设计点位置和函数值第一次迭代设计点位置和函数值 继续作下去,经继续作下去,经10次迭代后,得到最优解次迭代后,得到最优解 8将上例中将上例中目标函数目标函数 引入变换引入变换 y1=x1, y2=5x2则函数则函数f(x)变为:变为:其其等值线由椭圆变成一簇同心圆。等值线由椭圆变成一簇同心圆。仍从仍从 即即 出发进行最速下降法寻优。出发进行最速下降法寻优。此时:此时:沿负沿负梯度方向进行一维搜索:梯度方向进行一维搜索:这一问题的目标函数这一问题的目标函数f(x)的等值线为一簇椭圆。的等值线为一簇椭圆
6、。9 为一维为一维搜索最佳步长,可由极值条件:搜索最佳步长,可由极值条件:由由从而算得一步计算后设计点的位置及其目标函数:从而算得一步计算后设计点的位置及其目标函数:10经经变换后,只需一次迭代,就可找到最优解。变换后,只需一次迭代,就可找到最优解。这是因为经过尺度变换:这是因为经过尺度变换:等值线由椭圆变成圆。等值线由椭圆变成圆。1 111l(1)理论明确,程序简单,对初始点要求不严格。)理论明确,程序简单,对初始点要求不严格。l(2)对一般函数而言,梯度法的收敛速度并不快,因为最)对一般函数而言,梯度法的收敛速度并不快,因为最速下降方向仅仅是指某点的一个局部性质。速下降方向仅仅是指某点的一
7、个局部性质。l(3)梯度法相邻两次搜索方向的正交性,决定了迭代全过)梯度法相邻两次搜索方向的正交性,决定了迭代全过程的搜索路线呈锯齿状,在远离极小点时逼近速度较快,而在程的搜索路线呈锯齿状,在远离极小点时逼近速度较快,而在接近极小点时逼近速度较慢。接近极小点时逼近速度较慢。l(4)梯度法的收敛速度与目标函数的性质密切相关。对于)梯度法的收敛速度与目标函数的性质密切相关。对于等值线等值线(面面)为同心圆(球)的目标函数,一次搜索即可达到极为同心圆(球)的目标函数,一次搜索即可达到极小点。小点。梯度法的特点梯度法的特点梯度法的特点梯度法的特点12利用有利用有限的信限的信息!息!13设设 为为 的极
8、小点的极小点 l l基本思想基本思想基本思想基本思想 :l l在在在在x xk k邻域内用一个二次函数邻域内用一个二次函数邻域内用一个二次函数邻域内用一个二次函数 来近似代替原目标函数,来近似代替原目标函数,来近似代替原目标函数,来近似代替原目标函数,并将并将并将并将 的极小点作为对目标函数的极小点作为对目标函数的极小点作为对目标函数的极小点作为对目标函数求优的下一个迭代点求优的下一个迭代点求优的下一个迭代点求优的下一个迭代点 。经多次迭代,使之逼近目标函。经多次迭代,使之逼近目标函。经多次迭代,使之逼近目标函。经多次迭代,使之逼近目标函数数数数 的极小点。的极小点。的极小点。的极小点。4.2
9、牛顿法及其改进牛顿法及其改进14这就是多元函数求极值的牛顿法迭代公式。这就是多元函数求极值的牛顿法迭代公式。 对于二次函数对于二次函数 ,海赛矩阵是一个常矩阵,其中各元素,海赛矩阵是一个常矩阵,其中各元素均为常数。因此,无论从任何点出发,只需一步就可找到均为常数。因此,无论从任何点出发,只需一步就可找到极小点。极小点。 例例42求目标函数求目标函数 的极小点。的极小点。解解 取初始点取初始点15阻尼牛顿法阻尼牛顿法 阻尼因子阻尼因子 ,沿牛顿方向进行一维搜索的最佳步长,沿牛顿方向进行一维搜索的最佳步长,由下式求得:由下式求得: l经过一次迭代即求得极小点经过一次迭代即求得极小点 ,l函数极小值
10、函数极小值 。从牛顿法迭代公式的推演中可以看到,迭代点的位从牛顿法迭代公式的推演中可以看到,迭代点的位置是按照极值条件确定的,其中并未含有沿下降方向搜置是按照极值条件确定的,其中并未含有沿下降方向搜寻的概念。因此对于非二次函数,如果采用上述牛顿迭寻的概念。因此对于非二次函数,如果采用上述牛顿迭代公式,有时会使函数值上升代公式,有时会使函数值上升 。16 阻尼牛顿法称序框图阻尼牛顿法称序框图17牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的主要缺点是每次迭代都要计算函数的二阶导数矩阵,并对主要缺点是每次迭代都要计算函数的二阶导数矩阵,并对该矩阵求逆。
11、这样工作量很大。特别是矩阵求逆,当维数该矩阵求逆。这样工作量很大。特别是矩阵求逆,当维数高时工作量更大高时工作量更大 。18一般迭代式:一般迭代式:梯度法:梯度法:牛顿法:牛顿法:阻尼牛顿法:阻尼牛顿法:梯度法与牛顿法:梯度法与牛顿法:19变尺度法是在牛顿法的思想上进行了重大改进的一类变尺度法是在牛顿法的思想上进行了重大改进的一类方法方法 1.基本思想基本思想2.变量的尺度变换是放大或缩小各个坐标。通过尺变量的尺度变换是放大或缩小各个坐标。通过尺3.度变换可以把函数的偏心程度降到最低限度。度变换可以把函数的偏心程度降到最低限度。 例如在用最速下降法求例如在用最速下降法求 的极小的极小值时值时
12、,需要进行需要进行10次迭代才能达到极小点次迭代才能达到极小点 如作变换如作变换 y1=x1, y2=5x2把把 的尺度放大的尺度放大5倍,则目标函数等值线由一簇椭圆倍,则目标函数等值线由一簇椭圆变成一簇同心圆。变成一簇同心圆。x24.3变尺度法变尺度法20消除了函数的偏心,用最速下降法只需一次迭代消除了函数的偏心,用最速下降法只需一次迭代即可求得极小点。即可求得极小点。梯度法构造简单,只用到一阶偏导数,计算量小,梯度法构造简单,只用到一阶偏导数,计算量小,迭代初期收敛速度快,但当迭代到最优点附近时收敛迭代初期收敛速度快,但当迭代到最优点附近时收敛速度很慢;速度很慢;牛顿法收敛很快,对于二次函
13、数只需迭代一次便牛顿法收敛很快,对于二次函数只需迭代一次便达到最优点,对非二次函数也能较快迭代到最优点,达到最优点,对非二次函数也能较快迭代到最优点,但要计算二阶偏导数矩阵及其逆阵,对维数较高的优但要计算二阶偏导数矩阵及其逆阵,对维数较高的优化问题,其计算工作和存储量都太大。化问题,其计算工作和存储量都太大。能不能将两种算法的优点综合起来,扬长避短能不能将两种算法的优点综合起来,扬长避短?21Ak 是需要构造是需要构造nn的一个对称方阵的一个对称方阵 ,如如Ak=I, 则得到梯度法则得到梯度法 ; 则得到阻尼牛顿法则得到阻尼牛顿法 ;如如当矩阵当矩阵Ak 不断地迭代而能很好地逼近不断地迭代而能
14、很好地逼近 时,就可以不再需要计算二阶导数。时,就可以不再需要计算二阶导数。 变尺度法的关键在于尺度矩阵变尺度法的关键在于尺度矩阵Ak的产生的产生 。对于二次函数对于二次函数:22进行尺度变换进行尺度变换在在新的坐标系中,函数新的坐标系中,函数f(x)的二次项变为:的二次项变为:目的:减少二次项的偏心目的:减少二次项的偏心如如G是正定,则总存在矩阵是正定,则总存在矩阵Q,使得:使得: 用矩阵用矩阵Q-1右乘等式两边,得:右乘等式两边,得:用用矩阵矩阵Q左乘等式两边,得:左乘等式两边,得:所以所以上式上式说明:二次函数矩阵说明:二次函数矩阵G的逆阵,可以通过尺度变换的逆阵,可以通过尺度变换矩阵矩
15、阵Q来求得。来求得。23牛顿迭代公式:牛顿迭代公式:记:记:牛顿方向:牛顿方向:迭代公式:迭代公式:A 称为尺度变换矩阵称为尺度变换矩阵24在例在例42中中如取如取25求得:求得:26中修正矩阵中修正矩阵 的不断修正,在迭代中逐步逼近于的不断修正,在迭代中逐步逼近于 因此,一旦达到最优点附近,就可望达到牛顿法的收敛速度。因此,一旦达到最优点附近,就可望达到牛顿法的收敛速度。1)DFP法(法(Davidon-Fletcher-Powell)式中式中。从初始矩阵从初始矩阵A0=I(单位矩阵单位矩阵)开始,通过对公式开始,通过对公式 2. 2.构造尺度矩阵构造尺度矩阵构造尺度矩阵构造尺度矩阵A Ak
16、 k272 2)BFGSBFGS算法算法算法算法( (BroydenBroyden-Fletcher-Gold-Fletcher-Gold frob frob- -ShannoShanno ) )DFP算法由于舍入误差和一维搜索不精确,有可能导致构算法由于舍入误差和一维搜索不精确,有可能导致构造矩阵的正定性遭到破坏,以至算法不稳定。造矩阵的正定性遭到破坏,以至算法不稳定。BFGS算法算法对于维数较高问题具有更好的稳定性。对于维数较高问题具有更好的稳定性。2829取初始变尺度矩阵为单位矩阵取初始变尺度矩阵为单位矩阵A0=I,则第一次搜寻方向为则第一次搜寻方向为 例例例例4-34-3用用用用DFP
17、DFP算法求下列问题的极值:算法求下列问题的极值:算法求下列问题的极值:算法求下列问题的极值:解:解: 1)取初始点)取初始点 ,为了按,为了按DFP法构造第一次法构造第一次搜寻方向搜寻方向d0,需计算初始点处的梯度需计算初始点处的梯度30为一维搜索最佳步长,应满足为一维搜索最佳步长,应满足得得:,2)再按)再按DFP法构造点法构造点x1处的搜寻方向处的搜寻方向d1,需计算需计算l沿沿d0方向进行一维搜索,得方向进行一维搜索,得31代入校正公式代入校正公式=32=第二次搜寻方向为第二次搜寻方向为再沿再沿d1进行一维搜索,得进行一维搜索,得33为一维搜索最佳步长,应满足为一维搜索最佳步长,应满足
18、,得得3)判断)判断x2是否为极值点是否为极值点梯度梯度: 海赛矩阵海赛矩阵 :34梯度为零向量梯度为零向量,海赛矩阵正定。可见点满足极值充海赛矩阵正定。可见点满足极值充要条件,因此为极小点。要条件,因此为极小点。 35当当G为单位矩阵时,为单位矩阵时,假设目标函数假设目标函数f(x) 在极值点附近的二次近似函数为在极值点附近的二次近似函数为对二维对二维情况情况任选取初始点任选取初始点x0沿某个下降方向沿某个下降方向d0作一维搜索,得作一维搜索,得x14.4共轭方向法共轭方向法l1.共轭方向:共轭方向:l 设设G为为nn阶实对称正定矩阵,如果有两个阶实对称正定矩阵,如果有两个n维向量维向量d0
19、和和d1满足满足 ,则称向量,则称向量d0与与d1 关于矩阵关于矩阵G共轭。共轭。36因因为为 是是沿沿d0方方向向搜搜索索的的最最佳佳步步长长,即即在在点点x1处处函函数数f(x)沿沿方方向向d0的的方方向向导导数数为为零零。考考虑虑到到点点x1处处方方向向导导数数与与梯梯度度之之间间的的关关系,故有系,故有如果按最速下降法,选择负梯度方向如果按最速下降法,选择负梯度方向 为搜索方向,则为搜索方向,则将发生锯齿现象将发生锯齿现象 。 取下一次的迭代搜索方向取下一次的迭代搜索方向d1直指极小点直指极小点x* .0d0x0x1x*1 11d1d237那么这样的那么这样的d1方向应该满足什么条件呢
20、方向应该满足什么条件呢 ?对于前述的二次函数对于前述的二次函数:有有当当 时时 。x*是是f(x)极小点,应满足极值必要条件,故有极小点,应满足极值必要条件,故有将等式两边同时左乘将等式两边同时左乘 得:得:l如果能够选定这样的搜索方向,那么对于二元二次函数如果能够选定这样的搜索方向,那么对于二元二次函数只需顺次进行只需顺次进行d0、d1两次直线搜索就可以求到极小点两次直线搜索就可以求到极小点x* ,即有即有38就是使就是使d1直指极小点直指极小点x* , d1所必须满足的条件所必须满足的条件 。两两个个向向量量d0和和d1称称为为G的的共共轭轭向向量量,或或称称d0和和d1对对G是是共共轭方
21、向。轭方向。 2.共轭方向的性质共轭方向的性质性性质质1 若若非非零零向向量量系系d0,d1,d2,dm-1是是对对G共共轭轭,则则这这m个向量是线性无关的。个向量是线性无关的。性质性质2 在在n维空间中互相共轭的非零向量的个数不超过维空间中互相共轭的非零向量的个数不超过n。 性质性质3 从任意初始点出发,顺次沿从任意初始点出发,顺次沿n个个G的共轭方向的共轭方向d0,d1, d2,进行一维搜索,最多经过进行一维搜索,最多经过n次迭代就可以找到的二次次迭代就可以找到的二次函数函数f(x)极小点。极小点。 39关键:新的共关键:新的共轭方向轭方向确定确定40设与设与dk共轭的下一个方向共轭的下一
22、个方向dk+1由由dk和点和点xk+1的负的负梯度的线形梯度的线形组合构成,即:组合构成,即:共轭条件:共轭条件:3. 3.共轭梯度法共轭梯度法共轭梯度法共轭梯度法l共轭梯度法是共轭方向法中的一种,该方法中每一个共共轭梯度法是共轭方向法中的一种,该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。轭向量都是依赖于迭代点处的负梯度而构造出来。l从从xk出发,沿负梯度方向作一维搜索出发,沿负梯度方向作一维搜索:41解解得:得:令令为为函数的泰勒二次展开式函数的泰勒二次展开式则则上两式相上两式相减,并代入减,并代入则:则:42将式将式与式与式两边相乘,并应用两边相乘,并应用共轭条件共轭条件得
23、:得:因此因此43,已知初始点,已知初始点1,1T例题例题例题例题 4-4 4-4求下列问题的极值求下列问题的极值求下列问题的极值求下列问题的极值l解:解: 1)第一次沿负梯度方向搜寻)第一次沿负梯度方向搜寻l计算初始点处的梯度计算初始点处的梯度为一维搜索最佳步长,应满足为一维搜索最佳步长,应满足l迭代精度迭代精度 。 44得得:2)第二次迭代:)第二次迭代:代入代入目标函数目标函数45得得因因收敛。收敛。由由从而有:从而有:46对函数:对函数:基本思想:在不用导数的前提下,在迭代中逐次构造基本思想:在不用导数的前提下,在迭代中逐次构造G的共的共轭方向。轭方向。 1.共轭方向的生成共轭方向的生
24、成jkkkdddjggk+1xxk+1设设xk, xk+1为从不同为从不同点出发,沿同一方点出发,沿同一方向向dj进行一维搜索进行一维搜索而到的两个极小点而到的两个极小点. 4.5鲍威尔方法鲍威尔方法l鲍威尔(鲍威尔(Powell)法是直接利用函数值来构造共轭方向的一法是直接利用函数值来构造共轭方向的一种方法种方法 47另另一一方方面面,对对于于上上述述二二次次函函数数,其其xk, xk+1两两点点处处的的梯梯度可表示为度可表示为:因而有因而有取取这这说说明明只只要要沿沿dj方方向向分分别别对对函函作作两两次次一一维维搜搜索索,得得到到两两个个极极小小点点xk和和xk+1 ,那那么么这这两两点
25、点的的连连线线所所给给出出的的方方向向dk就是与就是与dj一起一起对对G共轭的方向。共轭的方向。l梯度和等值面相垂直的性质梯度和等值面相垂直的性质, dj和和 xk, xk+1两点处的梯度两点处的梯度gk,gk+1之间存在关系之间存在关系:481)任任选选一一初初始始点点x0,再再选选两两个个线线性性无无关关的的向向量量,如如 坐坐 标标 轴轴 单单 位位 向向 量量e1=1,0T和和e2=0,1T作作为为初始搜索方向。初始搜索方向。2)从从x0出出发发,顺顺次次沿沿e1, e1作作一一维维搜搜索索,得得 点点,两两点点连连线线得得一一新新方方向向d1x1x2x0oe1e2d1d2x*12.
26、2.基本算法基本算法基本算法基本算法l二维情况描述鲍威尔的基本算法二维情况描述鲍威尔的基本算法: : 49用用 d1代替代替e1形成两个线性无关向量形成两个线性无关向量d1 ,e2 ,作为下一作为下一轮迭代的搜索方向。再轮迭代的搜索方向。再 从出发,沿从出发,沿d1作一维搜索得点作一维搜索得点 ,作为下一轮迭代的初始点。作为下一轮迭代的初始点。 x1x2x0oe1e2d1d2x*13)从从出出发发 ,顺顺次次沿沿e2,d1 作作一一维维搜搜索索,得得到到点点 ,两两点点连连线线得得一一新方向新方向:沿沿d2作一维搜索得点作一维搜索得点x2 .即是二维问题的极小点即是二维问题的极小点x* .方法
27、的基本迭代格式包括共轭方向产生和方向替换两主要方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。步骤。50 上述基本算法仅具有理论意义上述基本算法仅具有理论意义 。l 把二维情况的基本算法扩展到把二维情况的基本算法扩展到n维,则鲍威尔基本算法的维,则鲍威尔基本算法的要点是:要点是:l在每一轮迭代中总有一个始点(第一轮的始点是任选的在每一轮迭代中总有一个始点(第一轮的始点是任选的初始点)和初始点)和n个线性独立的搜索方向。从始点出发顺次沿个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点,由始点和终点决定了一个新个方向作一维搜索得一终点,由始点和终点决定了一个新的搜索方向。的
28、搜索方向。l用这个方向替换原来用这个方向替换原来n个方向中的一个,于是形成新的搜个方向中的一个,于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定,从这一轮的搜索终新方向排在原方向的最后。此外规定,从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点,作为点出发沿新的搜索方向作一维搜索而得到的极小点,作为下一轮迭代的始点。这样就形成算法的循环下一轮迭代的始点。这样就形成算法的循环513.改进的算法改进的算法在鲍威尔基本算法中,每一轮迭代都用连结始点和在鲍威尔基本算法中,每一轮迭代都用连结始点
29、和终点所产生出的搜索方向去替换原向量组中的第一个向终点所产生出的搜索方向去替换原向量组中的第一个向量,而不管它的量,而不管它的“好坏好坏”,这是产生向量组线性相关的,这是产生向量组线性相关的原因所在。原因所在。 在在改改进进的的算算法法中中首首先先判判断断原原向向量量组组是是否否需需要要替替换换。如如果果需需要要替替换换,还还要要进进一一步步判判断断原原向向量量组组中中哪哪个个向向量量最最坏坏,然然后后再再用用新新产产生生的的向向量量替替换换这这个个最最坏坏的的向向量量,以以保保证逐次生成共轭方向。证逐次生成共轭方向。因为在迭代中的因为在迭代中的n个搜索方向有时会变成线性相关而个搜索方向有时会
30、变成线性相关而不能形成共轭方向。这时张不成不能形成共轭方向。这时张不成n维空间,可能求不到极维空间,可能求不到极小点,所以上述基本算法有待改进。小点,所以上述基本算法有待改进。 52令在令在k次循环中次循环中()分别称为一轮迭代的始点、终点和反射点分别称为一轮迭代的始点、终点和反射点 。l为此,要解决两个关键问题:为此,要解决两个关键问题:l(1)dk1是否较好?是否应该进入新的方向组?即方向是否较好?是否应该进入新的方向组?即方向组是否进行更新?组是否进行更新?l(2)如果应该更新方向组,)如果应该更新方向组, dk1不一定替换方向不一定替换方向 ,而是有选择地替换某一方向而是有选择地替换某
31、一方向 。53记:记:相应的方向为相应的方向为 。为了构成共轭性好的方向组,须遵循下列准则:为了构成共轭性好的方向组,须遵循下列准则:在在k次循环中,若满足条件:次循环中,若满足条件:和和则则选用新方向选用新方向dk,并在第并在第k+1迭代中用迭代中用dk替换对应于替换对应于 的方向的方向 。否则,仍然用原方向组进行第。否则,仍然用原方向组进行第k+1迭代。迭代。因此因此l则在循环中函数下降最多的第则在循环中函数下降最多的第m次迭代是次迭代是54这样重复迭代的结果,后面加进去的向量都彼此对这样重复迭代的结果,后面加进去的向量都彼此对G共共轭,经轭,经n轮迭代即可得到一个由轮迭代即可得到一个由n
32、个共轭方向所组成的方向个共轭方向所组成的方向组。对于二次函次,最多组。对于二次函次,最多n次就可找到极小点,而对一般函次就可找到极小点,而对一般函数,往往要超过数,往往要超过n次才能找到极小点(这里次才能找到极小点(这里“n”表示设计表示设计空间的维数)。空间的维数)。 55。解:(解:(1)第)第1轮迭代计算轮迭代计算, 沿沿e1方向进行一维搜索方向进行一维搜索得得l例例4-5 用改进的鲍威尔法求目标函数用改进的鲍威尔法求目标函数l的最优解。已知初始点的最优解。已知初始点1,1T,迭代精度迭代精度56得得以以 为起点,沿第二坐标轴方向为起点,沿第二坐标轴方向 e2 进行一维搜索进行一维搜索5
33、7确定此轮中的最大下降量及其相应方向确定此轮中的最大下降量及其相应方向 反射点及其函数值反射点及其函数值 检验检验Powell条件条件58构成新的方向构成新的方向 沿沿 方向一维搜索得极小点和极小值方向一维搜索得极小点和极小值,此点为下轮迭代初始点。此点为下轮迭代初始点。 按点距准则检验终止条件按点距准则检验终止条件 需进行第二轮迭代机算。需进行第二轮迭代机算。l由于满足由于满足Powell条件,则淘汰函数值下降量最大的方向条件,则淘汰函数值下降量最大的方向e1,下一轮的基本方向组为下一轮的基本方向组为e2, 。59此此轮轮基基本本方方向向组组为为e2, ,分分别别相相当当于于 , ,起起始始
34、点点为为 。沿沿e2方向进行一维搜索得方向进行一维搜索得 以以 为起点沿为起点沿 方向一维搜索得方向一维搜索得确定此轮中函数值最大下降量及其相应方向确定此轮中函数值最大下降量及其相应方向 l(2)第)第2轮迭代计算轮迭代计算60检验检验Powell条件,淘汰函数值下降量最大的方向条件,淘汰函数值下降量最大的方向e2,下一轮的基本方向组应为下一轮的基本方向组应为 , 。 构成新的方向构成新的方向沿沿 方向进行一维搜索得方向进行一维搜索得l反射点及其函数值反射点及其函数值61(3)第)第3轮迭代计算轮迭代计算此此轮轮基基本本方方向向组组为为 , ,起起始始点点为为 ,先先后后沿沿 , 方向,进行一
35、维搜索,得方向,进行一维搜索,得,检验终止条件检验终止条件 故最优解故最优解 l检验终止条件检验终止条件 62 实际上,前两轮迭代的实际上,前两轮迭代的 , 为共轭方向,由于为共轭方向,由于本例目标函数是二次函数,按共轭方向的二次收敛性,本例目标函数是二次函数,按共轭方向的二次收敛性,故前两轮的结果就是问题的最优解,但每一轮迭代都需故前两轮的结果就是问题的最优解,但每一轮迭代都需要进行要进行n+1次迭代。次迭代。63表2 无约束优化方法搜索方向之间的相互联系搜索方向搜索方向函函数数梯梯度度的的修修正正因因子子所用目标函数所用目标函数信息信息梯度法梯度法I(单位阵)单位阵)一阶导数一阶导数牛顿法牛顿法二阶导数二阶导数共轭梯度法共轭梯度法一阶导数一阶导数变尺度法变尺度法一阶导数,使一阶导数,使(海赛矩阵的逆阵)(海赛矩阵的逆阵)646566