第五章无约束优化的间接搜索法2

机械优化设计,太原科技大学张学良,虱瓮犯惋营又兰囱谣釉痕唇映响晕移涕醚社横绽荆雕疹阉傅巢啸八渠瞒郧第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,第五章无约束优化的间接搜索法,间搜索法是指搜索方向S(k)的构建利用目标函数的一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共轭梯度法、变尺度法。,X(k+1)=X(k)+(k)S(k)(k=0,1,2,),瓜肄胸荧洗洒憨叮果资狠佳质牟逗浮龙限缀胺仟硫契霄徽拖账地妨棠斥找第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,基本思想,5.1梯度法（最速下降法、负梯度法）(录象),利用负梯度方向作为迭代计算的搜索方向，即S(k)=f(X(k)或S(k)=f(X(k)/|f(X(k)|,迭代计算公式,X(k+1)=X(k)+(k)f(X(k)或X(k+1)=X(k)+(k)f(X(k),鬃镁夹丙宙影甘枝守于腻颤写螺擒掉鄂愈劳入年懦讫惧枯绦欣肮蒲莫逼靠第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,举例：用梯度法求目标函数f(X)=x12+4x22的无约束最优解。初始点X1(0)=00T，X2(0)=22T。,熟宅硫烛续冷韧歪播软失苦汹寡牙氏娃缉繁匹侩则恨而靶例鸿重拦碱缮拔第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,基本思想和基本算法,5.2牛顿法,在点X(k)的邻域内，用一个二次函数(X)来近似代替原目标函数，并以(X)的极小点作为原目标函数的极小点的近似值，若不满足收敛精度要求，则将该近似极小点作为下一次迭代的初始点。如此反复迭代，直到所求的近似极小点满足收敛精度要求为止。,恰熬啤时砖虫否理宴郭暂稠咱眶中潍赖日芝赌籽陪构翅瘁夯妒历猿砾乳柑第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,f(X)f(X(k)+Tf(X(k)(X-X(k)+0.5(X-X(k)T2f(X(k)(X-X(k)=(X),(X)的极小点应满足：(X)=0即f(X(k)+2f(X(k)(X-X(k)=0,2f(X(k)(X-X(k)=-f(X(k),当2f(X(k)正定且有逆阵时，上式两边同时左乘2f(X(k)-1，得,X=X(k)-2f(X(k)-1f(X(k),浸禁厚央球彰疵擒陪匣和贮修砷啥味溅扛斋粮淹袒盲颜汝况左格泵蒂抚读第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,牛顿法的迭代公式为X(k+1)=X(k)-2f(X(k)-1f(X(k),X(k+1)=X(k)+(k)S(k),牛顿方向：S(k)=-2f(X(k)-1f(X(k)迭代步长：(k)=1,修正牛顿法（又称阻尼牛顿法）的迭代公式为X(k+1)=X(k)-(k)2f(X(k)-1f(X(k)阻尼因子：(k),翠饱拙躺河陵芜麻些恶疡蛊蜒钢诛遍济逢诅萍阐伤檬趁幽檄约母螺竿串律第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,计算步骤及算法框图(图4-6),1）任选初始点X(0)，给定收敛精度0，并置k=0；,2）计算X(k)点的梯度f(X(k)及其模；,3）检验终止条件：|f(X(k)|？若满足，则输出最优解：X*=X(k)，f*=f(X*)，并终止迭代计算；否则，继续下一步迭代计算；,眠缕免微鸟象胳郧鲤素宾遥银悸签辐拇诊邹映乳圈能编挽焙麦控仙旁咳寥第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,4）计算X(k)点的海赛矩阵2f(X(k)及其逆矩阵2f(X(k)-1,5）沿牛顿方向S(k)=-2f(X(k)-1f(X(k)进行一维搜索，求最佳步长(k)；,6）令X(k+1)=X(k)+(k)S(k)，并令kk+1，转2），重复上述迭代计算过程。,笋尽薛铃治赘检牡虞汝宾萝新痹悼胁讲据氦朽靠积蝇箕岳舒修块梨肺斌禽第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,举例：用牛顿法求目标函数f(X)=x12+4x22的无约束最优解。初始点X1(0)=02T，X2(0)=22T。,解：f(X)=2x18x2T,X1(1)=X1(0)-2f(X1(0)-1f(X1(0),祸蛀掇悯米馏敌喇戮睦脏过隋戍益砾问锹瞬瘟耙冕僵瘤寻窘脏期漱簧滓辨第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,X2(1)=X2(0)-2f(X2(0)-1f(X2(0),可见，X2(1)=X1(0)=00T就是目标函数的理论极小点，仅仅迭代了一次，与初始点的选择无关。,由于一般函数在极小点附近呈现出较强的二次性，所以牛顿法在极小点附近收敛速度较快。但无论是牛顿法还是修正牛顿法在每次迭代计算时都要计算目标函数的海赛,断淬鸳潞疟脚墩守荤瘁精暴引蒜粤咎描棚租族酞午颈莲解捣铝兢垄样块境第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,矩阵及其逆阵，因此计算工作量很大，特别是矩阵求逆，当维数高时工作量更大，且当海赛矩阵为奇异阵时，其逆阵不存在，无法使用牛顿法，所以在实际使用中受到一定限制。另外，从计算机存储方面考虑，牛顿法所需要的存储量是很大的。,若能设法构造一个矩阵来逼近海赛矩阵的逆阵而避免计算海赛矩阵及其逆阵，这样的方法统称为拟牛顿法。如只用梯度信息但比梯度法快的共轭梯度法，以及针对牛顿法提出的变尺度法等。,序匀鳖扔卫坠净外抛敬帆爱肯奎驭岿驼瘴海承弛矛惊吮寒快蜡般诣币淋赦第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,举例(作业)：用牛顿法求目标函数f(X)=x12+25x22的无约束最优解。初始点X1(0)=02T，X2(0)=22T。,用弓甫镐卤饮清坠靴箱捉捍驯登旷满痴陈钠桓蓉痈态申铬处憾粗矗激躁街第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,基本思想,5.3共轭梯度法,共轭梯度法属于共轭方向法中的一种方法。它是利用目标函数在迭代点X(k)的梯度来构造共轭搜索方向的，具有二次收敛性。,共轭梯度法搜索的第一步沿负梯度方向，以后各步沿与上次搜索方向相共轭的方向进行搜索。共轭梯度法的关键是如何在迭代过程中不断生成共轭搜索方向,栅烹竟姥民簇若渭写髓首抛频刃滓蔡蛛房启孝汪荚比滁足谭阵泵柠弓肾涅第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,共轭梯度法共轭搜索方向的生成,考虑二次函数f(X)=0.5XTHX+BTX+C,从X(k)出发，沿H的某一共轭方向S(k)作一维搜索得到X(k+1)，即X(k+1)X(k)=(k)S(k)（1）,将f(X)在X(k)和X(k+1)两点处的梯度表示并记作,g(k)=f(X(k)=HX(k)+B（2）g(k+1)=f(X(k+1)=HX(k+1）+B（3）,限阮趟枉苦遍糊怒递母杨农雾胸枢宽灸闻泄涸半腋夜骋俩剥亢袋匆蝉僧恒第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,（3）-（2）得,g(k+1)g(k)=H(X(k+1)X(k)=(k)HS(k)（4）,（4）式两边同时左乘S(j)T，有S(j)Tg(k+1)g(k)=(k)S(j)THS(k)=0,若S(j)和S(k)关于H共轭，则有,S(j)THS(k)=0,即S(j)Tg(k+1)g(k)=0（5）,式（5）就是共轭方向与梯度之间的关系。它表明沿方向S(k)进行一维搜索，其终点X(k+1)与始点X(k)梯度之差(g(k+1)g(k)与S(k)的共轭,即吏府津奎攻只刮碳墩逝扩弘夯访则漠蛰掖蓟苇热饱帮蛔妨走摈峡壬姚刷第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,方向S(j)与正交。共轭梯度法就是利用这个性质做到不必计算矩阵H就能求得共轭方向的。,1）设初始点X(0)，第一个搜索方向S(0)取X(0)点的负梯度方向-g(0)。即S(0)=-g(0)沿S(0)进行一维搜索，得X(1)=X(0)+(0)S(0)，并计算X(1)点的梯度g(1)。,那么，g(1)与S(0)有什么关系呢？,X(0),g(1),-g(0),X(1),二者正交，即g(1)TS(0)=0或S(0)Tg(1)=0,因此，S(0)与g(1)构成平面正交系。,材蓬劫尚最嫌牺驳鲜鬃纷宇搐乙求楞沦巨疟拟锗精韵惦浩缮钵淹勉探瞳斋第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,2）在S(0)与g(1)构成的平面正交系中求S(0)的共轭方向S(1)，以此作为下一步迭代计算的搜索方向。取S(1)为S(0)与g(1)的线性组合，即S(1)=-g(1)+(0)S(0)其中，(0)为待定常数，可以利用共轭方向与梯度之间的关系求得。,由S(1)Tg(1)g(0)=0有-g(1)+(0)S(0)Tg(1)g(0)=0,展开，得-g(1)Tg(1)+g(1)Tg(0)+(0)S(0)Tg(1)-(0)S(0)Tg(0)=0,漏潮汕粟占市戈咱缨翰过膳熙额麓诊透薯傈恶蹋瞄览恒烯类焰姨玲厘跪靛第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,所以-g(1)Tg(1)-(0)S(0)Tg(0)=0,所以(0)=-g(1)Tg(1)/S(0)Tg(0)=g(1)Tg(1)/g(0)Tg(0)=|g(1)|2/|g(0)|2,S(1)=-g(1)+|g(1)|2/|g(0)|2S(0),沿S(1)进行一维搜索，得X(2)=X(1)+(1)S(1)，并计算X(2)点的梯度g(2)，则有,S(1)Tg(2)=0,筋吸氮各匀碌皿灼商蹦虾住坎惧粕蕊娱乐腔柒酉先恨种塔抽谚炸宴蛆掏就第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,故有-g(1)+(0)S(0)Tg(2)=0（6）,因为S(0)和S(1)共轭，所以有S(0)Tg(2)g(1)=0,因为S(0)Tg(1)=0所以S(0)Tg(2)=0,即g(2)与g(0)正交。所以g(0)Tg(2)=0,由式（6）得g(1)Tg(2)=0,可见，g(0)、g(1)、g(2)构成一个空间正交系。,熊藉氯崖永媒弥湾胳闭金撰蚜惋塑智淳溶几椿舵有很枪榜枉另贷啥营省使第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,3）在g(0)、g(1)、g(2)构成的空间正交系中求与S(0)及S(1)均共轭的方向S(2)，以此作为下一步迭代计算的搜索方向。仍取S(2)为g(0)、g(1)、g(2)的线性组合，即S(2)=-g(2)+(1)g(1)+(0)g(0)其中，(1)、(0)为待定常数，可以利用共轭方向与梯度之间的关系求得。,S(2)Tg(1)g(0)=0S(2)Tg(2)g(1)=0,鲸繁摘利绥口窒汛挝酗应纸愤专劲券弛党燎荐灵羔姥篆库讲讽揪大缀戳揉第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,即-g(2)+(1)g(1)+(0)g(0)Tg(1)g(0)=0-g(2)+(1)g(1)+(0)g(0)Tg(2)g(1)=0,所以(1)g(1)Tg(1)-(0)g(0)Tg(0)=0-g(2)Tg(2)-(1)g(1)Tg(1)=0,令(1)=-(1),得(1)=-(1)=g(2)Tg(2)/g(1)Tg(1)=|g(2)|2/|g(1)|2,(0)=(1)g(1)Tg(1)/g(0)Tg(0)=-(1)(0),捣帕巨温扶垃鸦舆署诉嗜止鬼持溃些对疟宗湘正盎栏妙拙裙生颁汗凑撇寨第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,因此S(2)=-g(2)+(1)g(1)+(0)g(0)=-g(2)-(1)g(1)-(1)(0)g(0)=-g(2)+(1)-g(1)-(0)g(0)=-g(2)+(1)S(1),故S(2)=-g(2)+|g(2)|2/|g(1)|2S(1),再沿S(2)进行一维搜索，得X(3)=X(2)+(2)S(2)，如此继续下去，可以求得共轭方向的递推公式为,S(k+1)=-g(k+1)+|g(k+1)|2/|g(k)|2S(k)(k=0,1,2,n-1),淳只弯刷阐歪棱瑶礁迁烙链蓬藻诺舵瘪藩怀澈寿丰缚甲阔咕闰握溢析喧民第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,沿着这些共轭搜索方向一直搜索下去，直到最后迭代点处梯度的模小于给定的允许值为止。若目标函数为非二次函数，经n次搜索还未达到最优点时，则以最后得到的点作为初始点，重新计算共轭方向，一直到满足精度要求为止。,共轭梯度法的计算步骤及算法框图,1）给定初始点X(0)及收敛精度0，k=0；,2）取S(0)=f(X(0)；,淆稍溺汰毒领捐壮目忌嘴当蹿挂敛裸蠢臃髓策开都龙釜卧肯丧淫烟刘牟它第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,3）X(k+1)=X(k)+(k)S(k)(k=0,1,2,n-1),(k)为一维搜索所得的最佳步长。,4）判断|f(X(k+1)|?若满足，则输出X*=X(k+1)和f*=f(X*)否则，转下一步；,5）判断k+1=n?若k+1=n，令X(0)=X(k+1)，转2）；若k+1n，则计算(k)=|f(X(k+1)|2/|f(X(k)|2,义刷益溺狠滨损童拉析消波铭慷及兜啦零撼梗拜哈胞埂碳媚篱孵寿坯郊联第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,S(k+1)=-f(X(k+1)+(k)S(k)并令kk+1，转3）。,1）尽管理论上可以证明目标函数为n维正定二次函数时，共轭梯度法只需要n次迭代就可以达到最优点，但由于计算机的舍入误差，实际计算往往要多进行若干次才能得到满足精度要求的结果；而对于一般的目标函数，迭代次数将更多。,关于共轭梯度法的说明,妙眯坤哟藻赢通惨膛蘑赎陷耙侧式虽腑貌面轻兰箩鹰蹲摹跟先零别聂壮刨第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,2）由于n维设计空间中最多只能有n个线性无关的向量，所以n维优化问题的共轭方向最多只有n个。因此，共轭梯度法进行n步搜索后，若仍不满足精度要求，继续产生共轭方向S(n+1)进行迭代搜索是没有意义的（效果很差），而应令X(0)=X(n)，重新开始新一轮的共轭梯度法迭代搜索。实践证明，这样处理一般都可以取得较好的效果。,舶肇囚丙项饶吉旺就掇充针屉盾广舜万慑醋拜止尔笑盔吃判蝉睦弓与糖桐第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,举例：用共轭梯度法求目标函数f(X)=x12+4x22的无约束最优解。初始点X(0)=22T，=0.01。,解：f(X)=2x18x2T,S(0)=-f(X(0)=-4-16T,X(1)=X(0)-(0)f(X(0)=22T-(0)416T=2-4(0)2-16(0)T,f(X(1)=(2-4(0)2+4(2-16(0)2,据df(X(1)/d(0)=0得(0)=0.13076923,X(1)=1.476923077-0.09230768T,灯伤垄验卵祟泣宗慷裴凡娥浇凝舜栽脓亚历篓惕庇羔胃斗老谣赠闺疮鸟彻第五章无约束优化的间接搜索法2第五章无约束优化的间接搜索法2,f(X(1)=2.953846154-0.73846144T,(0)=|f(X(1)|2/|f(X(0)|2=0.034082837,S(1)=-f(X(1)+(0)S