《机械优化设计》第四章-无约束优化方法

《机械优化设计》Mechanicaloptimizationdesign第四章无约束优化方法第四章无约束优化方法第一节概述，数值解法：是利用已有的信息，通过计算点一步一步地直接移动，逐步逼近最后达到最优点。1(0,1,)kkkkxxdk1）选择迭代方向即探索方向；2）在确定的方向上选择适当步长迈步进行探索第四章无约束优化方法第一节概述，无约束优化方法可以分成两类：•一类是利用目标函数的一阶或二阶导数的无约束优化方法（如最速下降法、共轭梯度法、牛顿法及变尺度法）；•另一类只利用目标函数的无约束优化方法（如坐标轮换法、单形替换法及鲍威尔法等）。第四章无约束优化方法第二节最速下降法，定义：最速下降法就是采用使目标函数值下降得最快的负梯度方向作为探索方向，来求目标函数的极小值的方法，又称为梯度法。1()(0,1,)kkkkxxfxk最速下降法的迭代公式第四章无约束优化方法第二节最速下降法，最速下降法的迭代步骤：011*10();3minmin4||;1,kkkkkkkkkkkkkxkdfxfxadaxxadxxxxkk1）给定初始点和收敛精度，置；2）计算梯度，并构造搜索方向）用一维搜索的方法求解得最佳步长，代入得到新的迭代点；）若，则停止迭代，得最优解否则，转到第二步。第四章无约束优化方法第二节最速下降法2212()25fxxx例：用最速下降法求目标函数的极小点。，1()(0,1,)kkkkxxfxk第四章无约束优化方法第二节最速下降法，最速下降法的特点：1）对初始搜索点无严格要求；2）收敛速度不快；3）相邻两次迭代搜索方向互相垂直，在远离极值点处收敛快，在靠近极值点处收敛慢；4）收敛速度与目标函数值的性质有关，对等值线是同心圆的目标函数来说，经过一次迭代就可以达到极值点。第四章无约束优化方法第三节牛顿型法，牛顿型法的基本思想：利用二次曲线来逐点近似原目标函数，以二次曲线的极小点来近似原目标函数的极小点并逐渐逼近该点。基本牛顿法的迭代公式：11(0,1,2)()kkkkkkxxdkdGxfx第四章无约束优化方法第三节牛顿型法，基本牛顿法的迭代公式：11(0,1,2)()kkkkkkxxdkdGxfx02212121[1,1],0.1min()224Txfxxxxxx例：用基本牛顿法求解下列无约束优化问题，已知。第四章无约束优化方法第三节牛顿型法，基本牛顿法的迭代公式：11(0,1,2)()kkkkkkxxdkdGxfx阻尼牛顿法的迭代公式：11(0,1,2,)()kkkkkkkxxdkdGxfx第四章无约束优化方法第三节牛顿型法，阻尼牛顿法的迭代步骤：01111*1,0;()()()()34||;1,kkkkkkkkkkkkkkkxkfxGxGxdGxfxxxddxxxxkk1）给定初始点收敛精度，置2）计算、和，得到；）求，其中，是沿着进行一维搜索的最佳步长；）检查收敛精度。若，则停止迭代，得最优解否则，转到第二步继续进行搜索。第四章无约束优化方法第三节牛顿型法，02212121[1,1],0.1min()224Txfxxxxxx例：用阻尼牛顿法求解下列无约束优化问题，已知。阻尼牛顿法的迭代公式：11(0,1,2,)()kkkkkkkxxdkdGxfx第四章无约束优化方法第四节共轭方向及共轭方向法，10[()]0Tfxd在下一次迭代时，选择搜索方d1指向极小点x*，*111xxad•共轭方向以二元函数为例：我们任意选择一个初始点x0点，沿着某个下降方向d0作一维搜索1000xxad12TTfxxGxbxc010TdGd第四章无约束优化方法第四节共轭方向及共轭方向法，•共轭方向01m101m1Gnmddd()0(,0,1,,1)()dddGGiTjdGdijmij设是nn对称正定矩阵，若维空间中有个非零向量、、、满足则称、、、对共轭，或称它们是的共轭方向。•正交01m1GI()0()dddiTjddij当=（单位矩阵）时，有，即向量、、、互相正交。第四章无约束优化方法第四节共轭方向及共轭方向法，•共轭方向的性质01m1001n1*dddG()m2nn3xnGdddn1x2TTfxxGxbxc性质1：若非零向量系、、、是对实对称正定矩阵共轭的，则这个向量是线性无关的。性质：在维空间中互相共轭的非零向量个数不超过。性质：从任意初始点点出发，顺次沿个的共轭方向、、、进行一维搜索，最多经过次迭代就可以找到二次函数的极小点。第四章无约束优化方法第四节共轭方向及共轭方向法，•共轭方向法的步骤00k111111xdkd340j012k5kk+1kkkkkkTkjkxxadfxxddGd）选定初始点，下降方向和收敛精度，置0；2）沿方向进行一维搜索，得；）判断是否满足，满足则打印，否则，转到第四步；）提供新的共轭方向，使，，，，；）置，转第二步。第四章无约束优化方法第四节共轭方向及共轭方向法，•共轭方向的形成•格拉姆-斯密特向量系共轭化的方法111,0iiriirrdvdn个线性无关的向量系vi（i=0,1，…，n-1）一组独立向量dr（r=0,1，…，n-1）11,()()jTiijjTjdGvdGd1110()()jTiijiijTjjdGvdvddGd第四章无约束优化方法第四节共轭方向及共轭方向法012210G=121012ddd例：求的一组共轭向量系、、。，1110()()jTiijiijTjjdGvdvddGd111,0iiriirrdvd11,()()jTiijjTjdGvdGd第四章无约束优化方法第五节共轭梯度法，共轭梯度法：先沿最速下降方向(负梯度方向)探索第一步，然后沿与该负梯度方向相共轭的方向进行探索。第四章无约束优化方法第五节共轭梯度法，共轭方向与梯度之间的关系：1()0Tjkkdgg它表示沿着方向dk做一维搜索，它的终点xk+1与始点xk的梯度之差与dk的共轭方向dj正交。第四章无约束优化方法第五节共轭梯度法，共轭梯度法递推公式：21112||||||||(0,1,2,,1)kkkkkgdgdgkn第四章无约束优化方法第五节共轭梯度法，共轭梯度法步骤：001(1)*1*10121;(),0;3);4)(),()(),5||||kkkkkkkkkkkkkdfxkdxxdfxxxfxfxknxxg1)给定初始点x和计算精度2）取x的负梯度方向作为搜索方向：置沿方向作一维搜索得判断收敛：若满足则令，结束迭代；否则，转到第五步；）若，则令，转到第二步开始新的一轮的迭代；否则，转到第六步；6）构造新的共轭方向112,||||1,kkkkkdgdgkk，令转到第三步。第四章无约束优化方法第五节共轭梯度法，共轭梯度法步骤：第四章无约束优化方法第五节共轭梯度法221212112(,)242fxxxxxxx例：用共轭梯度法求二次函数的极小点及极小值。，共轭梯度法21112||||||||(0,1,2,,1)kkkkkgdgdgkn设法构造出一个对称正定矩阵来代替，并在迭代过程中使逐渐逼近,那么就简化了牛顿法的计算，并且保持了牛顿法收敛快的优点。kH1()kGx1()kGx第四章无约束优化方法第六节变尺度法（拟牛顿法）kH，变尺度法的基本思想：1()kkkdGxfx牛顿方向：1(0,1,2)kkkkkxxHfxk变尺度法的迭代公式：尺度矩阵第四章无约束优化方法第六节变尺度法（拟牛顿法），尺度矩阵12TTfxxGxbxcxQx12TTxQGQxG正定TQGQI牛顿迭代公式：1kkTkkxxQQfx1TQQGTHQQ1kkkkkxxHfx目的：目标函数的偏心率减小到零。第四章无约束优化方法第六节变尺度法（拟牛顿法），变尺度矩阵的建立：1kkkkkxxHfx变尺度法的迭代公式：搜索方向：=kkkkkdHfxHg尺度矩阵应具备的条件：1）为正定对称矩阵；2）具有简单的迭代形式:3）满足拟牛顿条件：令则111()kkkkkHggxx1kkkHHE1kkkygg1kkksxx1kkkHys第四章无约束优化方法第六节变尺度法（拟牛顿法），变尺度法的一般步骤：0000011111*11)2)()03)=4)(),5)66)kkkkkkkkkkkkkkkkkkxgfxHHIkdHgdxxdgfxsxxyggxxnH选定初始点和收敛精度；计算，选定初始对称正定矩阵（如），置；计算搜索方向；沿方向进行一维搜索，计算，；判断是否满足迭代终止条件，若满足则，停机，否则转到；若迭代次后还没有找到极小点，重置为单位矩阵011277)13kkkkIxxHHEkk，并以当前设计点为初始点，返回进行下一轮迭代，否则转到；计算矩阵，置，返回。第四章无约束优化方法第六节变尺度法（拟牛顿法），变尺度法的流程图：第四章无约束优化方法第六节变尺度法（拟牛顿法），DFP算法：DFP算法的校正公式1(0,1,2,)TTkkkkkkkkkkTTkkkkkssHyyHHHEHksyyHy第四章无约束优化方法第六节变尺度法（拟牛顿法），DFP算法：221212112DFP,242fxxxxxxx例：用算法求的极值解。1(0,1,2,)TTkkkkkkkkkkTTkkkkkssHyyHHHEHksyyHy第四章无约束优化方法第七节坐标轮换法，基本思想：每次仅对多元函数的一个变量沿其坐标轴进行一维探索，其余各变量均固定不动，并依次轮换进行一维探索的坐标轴，完成第一轮探索后再重新进行第二轮探索，直到找到目标函数在全域上的最小点为止。目的：将一个多维的无约束最优化问题，转化为一系列的一维问题来求解。第四章无约束优化方法第七节坐标轮换法，二维问题第四章无约束优化方法第七节坐标轮换法，第k轮迭代公式：1(0,1,2,,1,2,,)kkkkiiiixxdkin[00100]kTiide11()()kkkkiiiifxdfx包括正负第四章无约束优化方法第七节坐标轮换法，步长α的几种取法：•随机选择方法•加速步长法•最优步长法（一维搜索方法，如：黄金分割法、二次插值法，来确定最优步长）11()()kkkkiiiifxdfx11min()()kkkkkiiiiifxdfxd第四章无约束优化方法第七节坐标轮换法，加速步长法：1111)2)()()3)()J1()J4)kkiikkkkkiiiiiikiikiihffxfxdffxffx先以试验步长确定步长的正负，当沿坐标轴正方向探索能使目标函数值减小时，则取正值，否则应取负值；按所取步长计算目标函数值若，则取加速步长，使其沿同一方向延伸；若延伸至第次时，则延伸至第次为止。当步长不宜延伸而宜缩小时，亦可缩小，也是一直到函数值达到最小值为止；改kid变方向，在新的方向上重复前述过程，直到函数值达到最小值为止，终止计算。第四章无约束优化方法第七节坐标轮换法，坐标轮换法的流程图第四章无约束优化方法第七节坐标轮换法，坐标轮换法的特点：计算简单、概念清楚、易于掌握；但搜索路线较长（需要经过多次曲折迂回的路径才能达到极值点），计算率较低，特别是当维数很高时很费时，所以坐标轮换