《无约束优化方法》由会员分享，可在线阅读，更多相关《无约束优化方法（107页珍藏版）》请在金锄头文库上搜索。
1、第四章无约束优化方法第一节概述第第1章所列举的机械优化设计问题，都是在一定章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束的限制条件下追求某一指标为最小，它们都属于约束优化问题。优化问题。约束优化问题的求解转化为一系列的无约束优化问题实现的。因此，无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。坝很侗页土假汹县淑窗框钩镐啪悬啮四庄旋谱晰佩妮镍呆供荧伟姬浪烧跨无约束优化方法无约束优化方法为什么要研究无约束优化问题为什么要研究无约束优化问题为什么要研究无约束优化问题为什么要研究无约束优化问题? ?（1）有有些些实实际际问问题题，其其数数学学
2、模模型型本本身身就就是是一一个个无无约约束束优化问题。优化问题。（2）通通过过熟熟悉悉它它的的解解法法可可以以为为研研究究约约束束优优化化问问题题打打下下良好的基础。良好的基础。（3）约约束束优优化化问问题题的的求求解解可可以以通通过过一一系系列列无无约约束束优优化化方方法法来来达达到到。所所以以无无约约束束优优化化问问题题的的解解法法是是优优化化设设计计方法的基本组成部分，也是优化方法的基础。方法的基本组成部分，也是优化方法的基础。凌共谜优朵鞋匿甚芥谦讥赘氮踩刘衔乔阁鸭镊蜒符营永双搬渭漳淆蹦奶崭无约束优化方法无约束优化方法（4）对对于于多多维维无无约约束束问问题题来来说说，古古典典极极值值理
3、理论论中中令令一一阶阶导导数数为为零零，但但要要求求二二阶阶可可微微，且且要要判判断断海海赛赛矩矩阵阵为为正正定定才才能能求求得得极极小小点点，这这种种方方法法有有理理论论意意义义，但但无无实实用用价价值值。和和一一维维问问题题一一样样，若若多多元元函函数数f(x)不不可可微微，亦亦无无法法求求解解。但但古古典典极极值值理理论论是是无无约约束束优优化化方法发展的基础。方法发展的基础。樟奴蔫玻惯混尧茎广屠营探蔑绸含烂蛆痹崎养饼陋艾蔫叁峨挖绢啥舌蚀潍无约束优化方法无约束优化方法目前已研究出很多种无约束优化方法，它们的目前已研究出很多种无约束优化方法，它们的主要不同点在于主要不同点在于构造搜索方向构
4、造搜索方向上的差别。上的差别。无约束优化问题是：无约束优化问题是：求求n维设计变量维设计变量使目标函数使目标函数 瑚棍钻锰与货哨宦祭构众塞浅岳弹猴噶雪在坞拟扎剿发蘸究中递脊诫赢间无约束优化方法无约束优化方法解析法数值法数学模型复杂时不便求解可以处理复杂函数及没有数学表达式的优化设计问题搜索方向问题是无约束优化方法的关键。各种无约束优化方法的区别：确定搜索方向的方法不同。无约束优化方法分类利用目标函数的一阶或二阶导数利用目标函数值（最速下降法、共轭梯度法、牛顿法）（坐标轮换法、鲍威尔等）赖智逝息咎敞匙妖娱玻洋毗愤窃臣铣发冷伎秽孩嗡笋排廊涨弱酚它浮隙渊无约束优化方法无约束优化方法搜索方向的构成问题
5、乃是无约束优化方法的关键。搜索方向的构成问题乃是无约束优化方法的关键。用直接法寻找极小点时，不必求函数的导数，只要计用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的算目标函数值。这类方法较适用于解决变量个数较少的（n20）问题，一般情况下比间接法效率低。间接法除）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。还要计算其海赛矩阵。乃私未骡扑魏诉涩蚌莉嚣毅复陷狐幽境馏误瑰羞窝悟哲却晓退兆驱痴理临无约束优化方法无约束优化方法苹乌匙伶院尺造禄慎格林
6、僵干杨雅曰檬艺培传蒋彭铱伸荚半养埂粥哭哇右无约束优化方法无约束优化方法第二节最速下降法优化设计追求目标函数值最小，若搜索方向取该点的负梯度方向，使函数值在该点附近的范围内下降最快。按此规律不断走步，形成以下迭代算法：以负梯度方向为搜索方向，所以称最速下降法或梯度法。搜索方向确定为负梯度方向，还需确定步长因子即求一维搜索的最佳步长，既有梭莹董俗门享川祭创掂灸苹洋崩椿英赤响痔负吐苑疵蕾属迂掣探稼杭沉鲁无约束优化方法无约束优化方法由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。蔫褪枷据最铡吕短率实考责滞昧给菲愉吐牲槐姆榷间饮码艳烁
7、械洋蔑祝力无约束优化方法无约束优化方法 在最速下降法中，在最速下降法中，相邻两个迭代点上的函相邻两个迭代点上的函数梯度相互垂直。而搜数梯度相互垂直。而搜索方向就是负梯度方向，索方向就是负梯度方向，因此相邻两个搜索方向因此相邻两个搜索方向互相垂直。这就是说在互相垂直。这就是说在迭代点向函数极小点靠迭代点向函数极小点靠近的过程，走的是曲折近的过程，走的是曲折的路线。形成的路线。形成“之之”字字形的锯齿现象，而且越形的锯齿现象，而且越接近极小点锯齿越细。接近极小点锯齿越细。图图4-2最速下降法的搜索路径最速下降法的搜索路径颇孕硅经枢铂仿绽函抱孵慎吼浑厢件巩漳质筐演溅宽慷遍还下肋妄蛊轮军无约束优化方法
8、无约束优化方法方法特点方法特点（1 1）初始点可任选，每次迭代计算量小，存储）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。然后慢慢逼近局部极小点。（2 2）任意相邻两点的搜索方向是正交的，它的）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。小点时，步长变得很小，越走越慢。 睛婴乐绢伪冈谱乃搂微骏隔突升庚炕宦死章刑劳泌雕嘲
9、玛制欣蔷妖棘张汝无约束优化方法无约束优化方法沿负梯度方向进行一维搜索，有沿负梯度方向进行一维搜索，有为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件例例4 41 1 求目标函数求目标函数 的极小点。的极小点。解解 取初始点取初始点则初始点处函数值及梯度分别为则初始点处函数值及梯度分别为嚣旱硬莫辜洒瀑误肺纳饼蔓闻鸣测泞唁谐润缓厚兑踢胃谷帐页晚录料套闭无约束优化方法无约束优化方法算出一维搜索最佳步长算出一维搜索最佳步长第一次迭代设计点位置和函数值第一次迭代设计点位置和函数值继续作下去，经继续作下去，经1010次迭代后，得到最优解次迭代后，得到最优解拓筹险航父恫样躬煞誊为
10、递帧叹岭凄匈苇趋锣盾观闭仔擦彝胰限辽谊邀仪无约束优化方法无约束优化方法 这个问题的目标函数的等值线为一簇椭圆这个问题的目标函数的等值线为一簇椭圆, ,迭代点从迭代点从走的是一段锯齿形路线，见图走的是一段锯齿形路线，见图4-3。1 1图图4-3诵慷丢你危矛已惹安龚摘吓犀税册巡晤找风钧询甜锗哮兴屋屉米烃隶懒狮无约束优化方法无约束优化方法将上例中目标函数将上例中目标函数引入变换引入变换其等值线由椭圆变成一簇同心圆。其等值线由椭圆变成一簇同心圆。仍从仍从即即出发进行最速下降法出发进行最速下降法寻优。此时：寻优。此时：沿负梯度方向进行一维搜索：沿负梯度方向进行一维搜索：则函数则函数f(f(X X) )变
11、为：变为：y1=x1,y2=5x2芳荆譬购鸭龟窥镰界举粘曼矫胁季判密兽艰句肝猩柒疯平锑爪谍衅舜互忠无约束优化方法无约束优化方法为一维搜索最佳步长，可由极值条件：为一维搜索最佳步长，可由极值条件：由由从而算得一步计算后设计点的位置及其目标函数：从而算得一步计算后设计点的位置及其目标函数：五昏浑兄寇渴骏垒乏伞球纳冕仰朝涟呕暑郎描茂宦殊氰驻钡历蒸格贺征梅无约束优化方法无约束优化方法经变换后，只需一次迭代，就可找到最优解。经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：这是因为经过尺度变换：等值线由椭圆变成圆。等值线由椭圆变成圆。返元抠圭球派钳坞敞榨刀巫娟日遏兄胜短舷磕泻稍佬鸡惩抿兹袋吕
12、钨总氢无约束优化方法无约束优化方法梯度法的特点梯度法的特点（1）理论明确，程序简单，对初始点要求不严格。）理论明确，程序简单，对初始点要求不严格。（2）对一般函数而言，梯度法的收敛速度并不快，因）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。为最速下降方向仅仅是指某点的一个局部性质。（3）梯度法相邻两次搜索方向的正交性，决定了迭代）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈全过程的搜索路线呈锯齿锯齿状，在远离极小点时逼近速度状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。较快，而在接近极小点时逼近速度较慢。（4）梯度法的收敛
13、速度与目标函数的性质密切相关。）梯度法的收敛速度与目标函数的性质密切相关。对于等值线对于等值线(面面)为同心圆（球）的目标函数，一次搜索为同心圆（球）的目标函数，一次搜索即可达到极小点。即可达到极小点。阐卧准百苏柜谴娥略锣窥嵌猿兹碗凯锁锰丸碴卖飞腹竟扶邓拂极恳呻甲阴无约束优化方法无约束优化方法擞村褥邢段贪蒜欧纫尤骋梯匝蔫盟废性抨黔巨卓某泡漠竟固耽职形歇互扳无约束优化方法无约束优化方法第三节牛顿型方法在第三章中，我们已经讨论了一维搜索的牛顿方法。得出一维情况下的牛顿迭代公式对于多元函数，在泰勒展开，得设为函数的极小点，根据极值的必要条件嫉井剁晌贩凌把椿酌赖逛娟悄肢脊盔届涌荒字孺货浅到恳歹呻仑抑脐
14、弦恩无约束优化方法无约束优化方法这是多元函数求极值的牛顿法迭代公式。倚链申鬃快任捞概皋碗滴挥浇裸谐些悄抱矽速畔灭俘杜景飘厦文铬铱蓟铣无约束优化方法无约束优化方法 对于二次函数对于二次函数，海赛矩阵海赛矩阵H H是一个常矩阵，其中是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。需一步就可找到极小点。例例4 42 2 求目标函数求目标函数 的极小点。的极小点。解解 取初始点取初始点藩愤题炽冕赶委鞭绣猴树砧扰车岛卖焙躬炽盼腥中填蕉命自激构度怖润堑无约束优化方法无约束优化方法 从牛顿法迭代公式的推演中可以看到，迭代点从牛顿法迭
15、代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升用上述牛顿迭代公式，有时会使函数值上升。阻尼牛顿法阻尼牛顿法阻尼因子阻尼因子，沿牛顿方向进行一维搜索的最佳沿牛顿方向进行一维搜索的最佳步长，由下式求得：步长，由下式求得：经过一次迭代即求得极小点经过一次迭代即求得极小点函数极小值函数极小值咐滦憎偏逢案稚搽拆摊霍掐炳者实淫谚幻撅阶莉坑剥煎竟婚瞪钥瓮脉遵蔓无约束优化方法无约束优化方法阻尼牛顿法程序框图渊莱滇恋
16、寞蜕盲驻说计诈锨邀若救切郎腮仟青薛湖讼唁檬歌铅鳖弧颈苍药无约束优化方法无约束优化方法方法特点方法特点（1）初始点应选在初始点应选在X*附近，有一定难度；附近，有一定难度；（2）尽管每次迭代都不会是函数值上升，但不能保证尽管每次迭代都不会是函数值上升，但不能保证每次下降每次下降；（3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；不能构造牛顿法方向；（4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的计算量和存储量大。此外，对于二阶不可微的F(X)也也不适用。不
17、适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和具有收敛最快的优点，并为其他的算法提供了思路和理论依据。理论依据。品唉坤仑邵企央土吊亏革月侩首腿燃繁潦麻惶踪迭茂滋唬北儿鱼歼受矿训无约束优化方法无约束优化方法一般迭代式：一般迭代式：梯度法：梯度法：牛顿法：牛顿法：阻尼牛顿法：阻尼牛顿法：梯度法与牛顿法：梯度法与牛顿法：盎宿交衣萨罩跳曳习讳旧倒绘挫崔唱霄执昧叠夺堑捉酌腥训黔炎等沮锭郭无约束优化方法无约束优化方法第四节共轭方向及共轭方向法为了克服最速下降法的锯齿现象，提高收敛速度，发展了一类共轭方向法。搜索方向是
18、共轭方向。一、共轭方向的概念共轭方向的概念是在研究二次函数时引出的。首先考虑二维情况紫豫镰苫汁恨兹韭掸睫舌坏冗因猜桓碳疫倡址呕掇传筷叛贩窄瓶羔凌昏港无约束优化方法无约束优化方法如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象。为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，如果选定这样的搜索方向，对于二元二次函数只需进行两次直线搜索就可以求到极小点。选这轻孩椽绰妮次户颊顶甲鸵疗食株苍些封夫拱碉按凶弃么赁码寺枝贵决无约束优化方法无约束优化方法应满足什么条件？对于二次函数在处取得极小点的必要条件等式两边同乘得是对G的共轭方向。道机癣甲铀件酝埔舔雁嚏饺尝款同让械酸则驮肾件剿业仙侥陛
19、菲最翌认谚无约束优化方法无约束优化方法 就是使就是使d1直指极小点直指极小点x* *， d1所必须满足的条件所必须满足的条件。两两个个向向量量d0和和d1称称为为G的的共共轭轭向向量量，或或称称d0和和d1对对G是共轭方向。是共轭方向。 二二. .共轭方向的性质共轭方向的性质性性质质1 1 若若非非零零向向量量系系d0, ,d1, ,d2,dm-1是是对对G共共轭轭，则这则这m个向量是线性无关的。个向量是线性无关的。性质性质2 2 在在n维空间中互相共轭的非零向量的个数维空间中互相共轭的非零向量的个数不超过不超过n。性质性质3 3 从任意初始点出发，顺次沿从任意初始点出发，顺次沿n个个G的共轭
20、方的共轭方向向d0, ,d1, , d2,进行一维搜索，最多经过进行一维搜索，最多经过n次迭代次迭代就可以找到的二次函数就可以找到的二次函数f( (x) )极小点。极小点。绎响洲嗡敖漆吟蝴湾邹旭妮材拨钟雪淋警懦蜡逝富钳投肚疑舱叠籍拓氢梦无约束优化方法无约束优化方法三、共轭方向法1、选定初始点，下降方向和收敛精度，k=0。2、沿方向进行一维搜索，得3、判断是否满足，若满足则打印否则转4。4、提供新的共轭方向，使5、置，转2。漾封向锐岛察亮齿挡熬戏急奔摔蚌寨舱赌罕柳邢归瞧洲洗松掠字散市纷训无约束优化方法无约束优化方法仅万封葵惟幕籽擒激闺赶艘普透镊投桑拎湿漏唁四便泉坤樊渐梆傅慧脂嘛无约束优化方法无约
21、束优化方法第五节共轭梯度法共轭梯度法是共轭方向法的一种，共轭向量有迭代点的负梯度构造出来，所以称共轭梯度法。从点出发，沿G某一共轭方向作一维搜索,到达而在点、处的梯度分别为：胶牲戴状飘窒芯抿周烟挖淤白率叙点吼辫曹淄阐遣承宾躺士弧虫郡找掠冷无约束优化方法无约束优化方法得出共轭方向与梯度之间的关系。此式表明沿方向进行一维搜索，其终点与始点的梯度值差与的共轭方向正交。案裹诲芯煽筷扁难旁棠鹅拦渭兢颂币岂奉害叁陕他染提纳左绚糯妖羹捐刹无约束优化方法无约束优化方法3.3.共轭梯度法共轭梯度法共轭梯度法是共轭方向法中的一种，该方法中共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负
22、梯度每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。而构造出来。 从从xk出发，沿负梯度方向作一维搜索出发，沿负梯度方向作一维搜索:设与设与dk共共轭的下一个方向轭的下一个方向dk+1由由dk和点和点xk+1的负梯的负梯度的线形组合构成，即：度的线形组合构成，即：共轭条件：共轭条件：峦旱弄劣硷比史谗署哉是棒哪雅嘛弃凿蝎有甩拙炊你建察真哮薛撩贪亥餐无约束优化方法无约束优化方法则：则：解得：解得：令令为函数的泰勒二次展开式为函数的泰勒二次展开式则则上两式相减，并代入上两式相减，并代入酣涅利爱娥强浑眷辫歼燥洱予视涎削狠质放诗想曲叫无蚌葱推粕砸策枷捷无约束优化方法无约束优化方法将式将式与式与式两边
23、相乘，并应用两边相乘，并应用共轭条件共轭条件得：得：因此因此鞭厕痒绒吵荧钩膳啊鹏考夫惨倪浸屑六葬莲楔煌涝奶蜂舆始痔鸿鲁墙窥极无约束优化方法无约束优化方法，已知初始点，已知初始点1,11,1T T例题例题4-4求下列问题的极值求下列问题的极值l解：解：1）第一次沿负梯度方向搜寻）第一次沿负梯度方向搜寻l计算初始点处的梯度计算初始点处的梯度为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足l迭代精度迭代精度 。 控示机挣肥趋虞劫届线窖近睡父难肆到而向柳涕囱永绎妖重掇向衡森外具无约束优化方法无约束优化方法得得:2）第二次迭代：）第二次迭代：代入目标函数代入目标函数畏巫萌型攫照理沉慌涝譬断幕湿辜福渴
24、诬萍缴段咐痰率羌伊活催不渤豌恭无约束优化方法无约束优化方法得得因因收敛。收敛。由由从而有：从而有：肾饵蔡淆秉晶茵暇讯涅榴椭姜苹汞颂函遂蔽凯尿季陇隙苗狙芳申顿甥酉昔无约束优化方法无约束优化方法图4-9共轭梯度法的几何说明惑拱尼刮珍雾此仕轻母毛搜见缀役沈拖叔秤额废矮诲撑艰肋鼓滩枫艺帖山无约束优化方法无约束优化方法臭驰哮兢赔颤簇棺淤蜘伏嚷衔拍速炊意捌商扰颗翟煎迟潞霜籽传烘鸭魁诀无约束优化方法无约束优化方法第六节变尺度法(DFP法)变尺度法的基本思想：前面讨论的梯度法和牛顿法，它们的迭代公式可以看作下列公式的特例。变尺度法是对牛顿法的修正，它不是计算二阶导数的矩阵和它的逆矩阵，而是设法构造一个对称正定
25、矩阵H来代替Hesse矩阵的逆矩阵。并在迭代过程中，使其逐渐逼近H-1。由于对称矩阵H在迭代过程中是不断修正改变的，它对于一般尺度的梯度起到改变尺度的作用，因此H又称变尺度矩阵。起辞骑杖子遂学宝历郧眨箍泅吊删扒钡资冗避焦慈呀怀碎邮躇籽入艳胎相无约束优化方法无约束优化方法DFP变尺度法首先有戴维顿（变尺度法首先有戴维顿（Davidon）与）与1959年提出，又于年提出，又于1963年由弗莱彻（年由弗莱彻（Fletcher）和鲍维尔加）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。以发展和完善，成为现代公认的较好的算法之一。DFP法是基于牛顿法的思想又作了重要改进。这法是基于牛顿法的思想又
26、作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。祸袖谍毫夷林派椿剂衔习蝴啮伤讶耿瓷霸抚惭茫暑咬规寐试坦船神阜眷纳无约束优化方法无约束优化方法1.基本思想基本思想变量的尺度变换是放大或缩小各个坐标。通过尺变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。度变换可以把函数的偏心程度降到最低限度。例如在用最速下降法求例如在用最速下降法求的极小的极小值时值时,需要需要进进行行10次迭代才能达到极小点次迭代才能
27、达到极小点如作变换如作变换y1=x1,y2=5x2把把的尺度放大的尺度放大5倍，则目标函数等值线由一簇倍，则目标函数等值线由一簇椭圆变成一簇同心圆。椭圆变成一簇同心圆。x2等芦乐卜夯扮氖此属治吴捡锦月绎多哦松拳仅磺荷毫瘸舞翘癣适促闲抒渴无约束优化方法无约束优化方法消除了函数的偏心，用最速下降法只需一次迭消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。代即可求得极小点。梯度法构造简单，只用到一阶偏导数，计算量小，梯度法构造简单，只用到一阶偏导数，计算量小，初始点可任选，且开始几次迭代，目标函数值下降很初始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近快；其主要缺点
28、是迭代点接近X*时，即使对二次正定时，即使对二次正定函数收敛也非常慢。函数收敛也非常慢。牛顿法收敛很快，对于二次函数只需迭代一次便牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。化问题，其计算工作和存储量都太大。能不能将两种算法的优点综合起来，扬长避短？能不能将两种算法的优点综合起来，扬长避短？纯负梧蜒痞仿荔屈汇泉光研品饥绢关憋践盗哩乍雨丫岸绊果郴啡娩桃筋舵无约束优化方法无约束优化方法
29、Ak是需要构造是需要构造nn的一个对称方阵的一个对称方阵，如如Ak=I,则得到梯度法则得到梯度法； 则得到阻尼牛顿法则得到阻尼牛顿法；如如当矩阵当矩阵Ak不断地迭代而能很好地逼近不断地迭代而能很好地逼近时，就可以不再需要计算二阶导数。时，就可以不再需要计算二阶导数。变尺度法的关键在于尺度矩阵变尺度法的关键在于尺度矩阵Ak的产生的产生 。对于二次函数对于二次函数:匈钾妻养阂侗夕矢俯籽腔苗婶虑肾酮辕址浊拭旨俗储热彼几雄队粗轴肥幻无约束优化方法无约束优化方法进行尺度变换进行尺度变换在新的坐标系中，函数在新的坐标系中，函数f(x)的二次项变为：的二次项变为：目的：减少二次项的偏心目的：减少二次项的偏心
30、如如G是正定，则总存在矩阵是正定，则总存在矩阵Q，使得：，使得：用矩阵用矩阵Q-1右乘等式两边，得：右乘等式两边，得：用矩阵用矩阵Q左乘等式两边，得：左乘等式两边，得：所以所以上式说明：二次函数矩阵上式说明：二次函数矩阵G的逆阵，可以通过尺度变换的逆阵，可以通过尺度变换矩阵矩阵Q来求得。来求得。惜狠成弘淋羌泅哨海静任换浊等曼堆袄悉妄稼费胁瘪殖绽腊唱谓晓舌硷继无约束优化方法无约束优化方法牛顿迭代公式：牛顿迭代公式：记：记：搜索方向：搜索方向：迭代公式：迭代公式：A A 称为变尺度矩阵称为变尺度矩阵搂桓蹿一惕专湿巩螟铆啤刘莆硅睫悸访帖柒部庐驴脆赦托纺讲蕴膳塑精咋无约束优化方法无约束优化方法在例在例
31、42中中如取如取萝咏净崎冶是努萧颜邦馒阿鹿讲笆置非彝狭继杖谋南孕请响超且沈勋张稳无约束优化方法无约束优化方法求得：求得：附府嚎聪拐婴里铭斤嵌莎骇辛痒某脑湿值婚汉思朴拐措爵为嫌膝碑仅帽驻无约束优化方法无约束优化方法落钝经魔衔忌插赵盯锈蚂缀绥曳圭迢痊坦斧政侨来炉雌焚奋鉴剔万再汉靴无约束优化方法无约束优化方法三、变尺度法的一般步骤三、变尺度法的一般步骤崩揪一手强帕清迅功期燎维槛樊亮涎灰聂冯冤赋耐吧陆缉松饶熔歉做骋蹈无约束优化方法无约束优化方法先漾班渐岔触筷言赏陛屁沁昆帕妨探锹沥桨狙涵葡羞葫蹦朱贡免询劈二义无约束优化方法无约束优化方法DFP算法稠楼眷竿骋可末宴献检诀城益赴善竞猴馈复欠断题膝跺茧分甩桨亭
32、粉钎砚无约束优化方法无约束优化方法DFP算法冬夺损抛哀审改软仆绎鸽谴梅罕丙色省培酉碧贺欺劳致缆搏贰媚批匪坡扭无约束优化方法无约束优化方法DFP算法酪傅漾乍僚栖国息祸梧杂赞暖爹毁吁币隔烘奶笼遂琉底侗掇求掉戎蒜旋晤无约束优化方法无约束优化方法例题例题4-5泞钵跟彩堤蓝踊歹卖崖事喻贼践宣搬埠正颗陈狈话茁图氮么岁遣喘道涩杀无约束优化方法无约束优化方法倦吠嘱旺歇藕毖辊悉募经猎否锐凰俱湖搂蛋仪效足利炙廖意促抖捷邯剪事无约束优化方法无约束优化方法绵氢王卧澜棍勋羔霸犀练及靠横岔仕格艰核压磊杭傻毙健斯皋抗救既骚秘无约束优化方法无约束优化方法第七节坐标轮换法坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变
33、，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量的优化问题。因此又称变量轮换法。其基本原理是将一个多维的无约束最优化问题转化为一系列较低维的最优化问题来求解，简单地说，就是先将(n-1)个变量固定不动，只对第一个变量进行一维搜索得到最优点x1（1）。然后，又保持(n-1)个变量不变，再对第二个变量进行一维搜索到x2（1）等等。添挨帛诬藩眉点刀盈离青绒逊拖隅橱扣白征炕投摹打草盲腐买违该疙凉蜕无约束优化方法无约束优化方法爸右苏稽苇裁敦劈订榜迄乱饮咀套姨抹籽衷著味坷衅盂逊闪后缨茨输枫罕无约束优化方法无约束优化方法图412坐标轮换法原理图哑运溶厢冈廊叫首纲给腿敝蕊益谦粘顷蝇
34、苔纪粗永肆央匡工臼叭韭验违穿无约束优化方法无约束优化方法2.搜索方向与步长的确定对于第k轮第i次的计算第k轮第I次的迭代方向，它轮流取n维坐标的单位向量。鹊颜仍耶绘邪赔夜哀界阴循翁蚊赣帅码涛煤佛转挖沈舆米毋搪逛句邪衔澡无约束优化方法无约束优化方法3.搜索步长的确定关于值通常有以下几种取法（1）加速步长法（2）最优步长法最优步长法就是利用一维最优搜索方法来完成每一次迭代，此时可以采用0.618方法或二次插值方法来计算。除窑膏扇骂着帜批斯拔鬼柴类不司避炕攒滇抠行憨燥蹲毅傣官盎轧纫攘彤无约束优化方法无约束优化方法图413加速步长法的搜索路线辫随酌捂酉舞刀聂篇虞牺精啤搓垄参俘球动霜校写峭飘个轻然抓控俘
35、糊后无约束优化方法无约束优化方法呻听刑猎桃填注疟婚渐蹬怪楼匡肚闪催娠磨唆黔裴罩宦蝇凋退鹿骗蔫藏谰无约束优化方法无约束优化方法图414最优步长法的搜索路线粱瓢瘦腿陵宴动抹咙钦滥吁耙弥肘蓄矽谓郧弥繁喉路臃博平冷娄窟冬动洛无约束优化方法无约束优化方法4.坐标轮换法存在的问题图415坐标轮换法在各种不同情况下的效能（a）搜索有效；（b）搜索低效；（c）搜索无效帧椎康罚谩靖揣妈史捏狄坤勉苑郝坤桃沂罐疡砸星匠绽概瞒首鞘躯歪践苇无约束优化方法无约束优化方法第八节Powell法（方向加速法）Powell法是利用共轭方向可以加速收敛的性质所形成的一种搜索算法。一、共轭方向的生成壤咆浮摹枯众獭思巫瘪游慨涨鸦辕劈梧
36、孝柿创彝摹三拓荷藻增含峙熟斗撤无约束优化方法无约束优化方法厦编迈玄仪隋劈肇奈咙翻狸很汰柴咨苇荚邢贷蝇鳖栈往菠艾蚤蛰止李丰闸无约束优化方法无约束优化方法二、基本算法嘿药驱摆掸纯奴烫崇臀昭杠辐霖佣庭值渤澎瘪工赋握摹食伤珠硅蓝舆魄亡无约束优化方法无约束优化方法三、改进的算法在鲍维尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原来向量组中的第一个向量，而不管它的“好坏”。改进的算法是：首先判断原向量组是否需要替换。如需要替换，在产生新的向量。溅嚼币栈挑辊肌臆郎蔗羌吵谆辖悦碱冀毅覆脂郝通帕缕靖宫陇讥桩炬哇韭无约束优化方法无约束优化方法侨恰动婪骂蓝掐受哑辙当竟组艇训哭茁墨吞沟选瘦扫摸娩
37、永虽蛊部傲谅栏无约束优化方法无约束优化方法第八节Powell法（方向加速法）鲍威尔法是以共轭方向为基础的收敛较鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。快的直接法之一，是一种十分有效的算法。1964年，鲍维尔提出这种算法，其基本思想年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践方向作一维搜索求极小点。并在以后的实践中进行了改进。中进行了改进。勇叹俱史菜漫颜弱韦郑鸿冗概荒镍旋投县饮妆迈匣姿俐
38、能祝赡杯亭待篮汰无约束优化方法无约束优化方法对函数：对函数：基本思想基本思想：在不用导数的前提下，在迭代中逐次构造：在不用导数的前提下，在迭代中逐次构造G的共轭方向。的共轭方向。1.1.共轭方向的生成共轭方向的生成jjkkkdd ddjgg gk+1xxk+1设设xk, , xk+1为从不同为从不同点出发，沿同一方向点出发，沿同一方向dj j进行一维搜索而到进行一维搜索而到的两个极小点。的两个极小点。晌黑希彪查泼至隋旨阴针铰忿翌摇纬忿上胳赶谴煮羞镀灸艾李革吊垃洞榨无约束优化方法无约束优化方法梯度和等值面相垂直的性质梯度和等值面相垂直的性质, ,dj j和和 xk, , xk+1两点两点处的梯度
39、处的梯度gk, ,gk+1之间存在关系之间存在关系: :另另一一方方面面，对对于于上上述述二二次次函函数数，其其xk, , xk+1两两点点处处的的梯度可表示为梯度可表示为: :因而有因而有取取这这说说明明只只要要沿沿dj j方方向向分分别别对对函函作作两两次次一一维维搜搜索索，得得到到两两个个极极小小点点xk和和xk+1 ，那那么么这这两两点点的的连连线线所所给出的方向给出的方向dk k就是与就是与dj j一起对一起对G共轭的方向。共轭的方向。奥肪瞬陌趁诲烟乓盟挛踪下另揪咯脚瑚姨灭贪茵饱耐班爵摄吞裁秋殷殉淆无约束优化方法无约束优化方法2.2.基本算法基本算法二维情况描述鲍威尔的基本算法二维情
40、况描述鲍威尔的基本算法: :1 1）任任选选一一初初始始点点x0，再再选选两两个个线线性性无无关关的的向向量量，如如坐坐标标轴轴单单位位 向向 量量 e1 1=1,0=1,0T T和和e e2 2=0,1=0,1T T作作 为为 初初 始始搜索方向。搜索方向。2 2）从从x0出出发发，顺顺次次沿沿e1 1， e1 1作一维搜索，得作一维搜索，得 点点，两两点点连连线线得一新方向得一新方向d1 1x1x2x0oe1e2d1d2x*1宾脉颧陛谓券擎腰朽窒纶薯蚁虞诸竭拨佰癌臣瑶稚氧巷尊朝够派恨勃非束无约束优化方法无约束优化方法x1x2x0o oe1e2d1d2x*1沿沿d2作一维搜索得点作一维搜索得
41、点x2。 即是二维问题的极即是二维问题的极小点小点x*。方法的基本迭代格式包括共方法的基本迭代格式包括共轭方向产生和方向替换两轭方向产生和方向替换两主要步骤。主要步骤。用用d1代替代替e1 1形成两个线性无关向量形成两个线性无关向量d1 , ,e2 2 ，作为，作为下一轮迭代的搜索方向。再下一轮迭代的搜索方向。再 从出发，沿从出发，沿d1作一作一维搜索得点维搜索得点 ，作为下一轮迭代的初始点。，作为下一轮迭代的初始点。3 3）从从出出发发 ，顺顺次次沿沿e2 2, ,d1作作一一维维搜搜索索，得得到到点点 ，两两点点连连线得一新方向线得一新方向: :助骋偷咒冗仕识蛀胎扫捅狸闹久秉词剑卖懈酬章谱
42、扫希拴慨呜冯啪氨奄受无约束优化方法无约束优化方法 把二维情况的基本算法扩展到把二维情况的基本算法扩展到n维，则鲍威尔维，则鲍威尔基本算法的要点是：基本算法的要点是： 在每一轮迭代中总有一个始点（第一轮的始点在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和是任选的初始点）和n个线性独立的搜索方向。从个线性独立的搜索方向。从始点出发顺次沿始点出发顺次沿n个方向作一维搜索得一终点，由个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。始点和终点决定了一个新的搜索方向。 用这个方向替换原来用这个方向替换原来n个方向中的一个，于是个方向中的一个，于是形成新的搜索方向组。替换的原则是去
43、掉原方向形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。代的始点。这样就形成算法的循环。频弟唯堤烛蹬娠渡狭塌躯随燕鞠棍绽索扒之嘿狰肤领垛蹲啃凿操排熄娃袱无约束优化方法无约束优化方法3 3）若目标函数为正定二次函数，）若目标函数为正定二次函数，n n轮结束后即可到达轮结束后即可到达最优点。最优点。2 2）每轮迭代产生一个新
44、方向取代原来的第一方向，）每轮迭代产生一个新方向取代原来的第一方向，n n轮迭代后可产生轮迭代后可产生n n个彼此共轭的方向个彼此共轭的方向；1 1）开始采用坐标轴方向）开始采用坐标轴方向；PowellPowell基本算法基本算法 上述基本算法仅具有理论意义上述基本算法仅具有理论意义上述基本算法仅具有理论意义上述基本算法仅具有理论意义 。液耙阜樱抗肝抱量材悉盛溃挟摧咒廊殊阔饱蘑枯央慢扮管拘燃损引抬锤策无约束优化方法无约束优化方法 因为在迭代中的因为在迭代中的n个搜索方向有时会变成线性个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成相关而不能形成共轭方向。这时组不成n维空间，维空间，可
45、能求不到极小点，所以上述基本算法有待改进。可能求不到极小点，所以上述基本算法有待改进。3.3.改进的算法改进的算法 在鲍威尔基本算法中，每一轮迭代都用连结始在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的第一个向量，而不管它的“好坏好坏”，这是产生向量，这是产生向量组线性相关的原因所在。组线性相关的原因所在。 在在改改进进的的算算法法中中首首先先判判断断原原向向量量组组是是否否需需要要替替换换。如如果果需需要要替替换换，还还要要进进一一步步判判断断原原向向量量组组中中哪哪个个向向量量最最坏坏，
46、然然后后再再用用新新产产生生的的向向量量替替换换这这个最坏的向量，以保证逐次生成共轭方向。个最坏的向量，以保证逐次生成共轭方向。侦算墟幂敞拜想唬霓竭湃利仪抑讲蛹坍州此胰村溜糖戌宠僻颊醚垮亚阴霍无约束优化方法无约束优化方法为此，要解决两个关键问题为此，要解决两个关键问题：（1）dk1是否较好？是否应该进入新的方向组是否较好？是否应该进入新的方向组？即方向组是否进行更新？即方向组是否进行更新？l（2）如果应该更新方向组，）如果应该更新方向组，dk1不一定替换方不一定替换方向向，而是有选择地替换某一方向，而是有选择地替换某一方向。令在令在k次循环中次循环中（）分别称为一轮迭代的始点、终点和反射点分别
47、称为一轮迭代的始点、终点和反射点。镐哲演鸳削祈自核乾伦软桩适耗忍瞥劣伞虏运研黄班撵闷戌龄慌碗制吭驴无约束优化方法无约束优化方法则在循环中函数下降最多的第则在循环中函数下降最多的第m次迭代是次迭代是记记：相应的方向为相应的方向为。为了构成共为了构成共轭性好的方向组，须遵循下列准则：轭性好的方向组，须遵循下列准则：在在k次循环中，若满足条件：次循环中，若满足条件：和和则选用新方向则选用新方向dk，并在第并在第k+1迭代中用迭代中用dk替换对应于替换对应于的方向的方向。否则，仍然用原方向组进行第。否则，仍然用原方向组进行第k+1迭代。迭代。因此因此久克崭啄福瞳咆谍蕴哟伸武悍横感布柄避沪叶廊徘职耶绳馒
48、筛苏青枫谆枫无约束优化方法无约束优化方法 这样重复迭代的结果，后面加进去的向量都这样重复迭代的结果，后面加进去的向量都彼此对彼此对G共轭，经共轭，经n轮迭代即可得到一个由轮迭代即可得到一个由n个共轭个共轭方向所组成的方向组。对于二次函次，最多方向所组成的方向组。对于二次函次，最多n次就次就可找到极小点，而对一般函数，往往要超过可找到极小点，而对一般函数，往往要超过n次才次才能找到极小点（这里能找到极小点（这里“n”表示设计空间的维数）。表示设计空间的维数）。质仓菩笋揉系幻酮楷倍杯孰和壁耶宫诡烈臣黔悔键峦欢诈今胡曙匣哗篓资无约束优化方法无约束优化方法吝炙源皑捧杖朽届缝岁信壹蒂晚淄蚀神烹妙间卜剂案
49、矮障赃砍丧厢季麓偿无约束优化方法无约束优化方法例例4-5 4-5 用改进的鲍威尔法求目标函数用改进的鲍威尔法求目标函数解：（解：（1 1）第）第1 1轮迭代计算轮迭代计算， 沿沿e1方向进行一维搜索方向进行一维搜索得得。的最优解。已知初始点的最优解。已知初始点1,11,1T T，迭代精度，迭代精度逛消涤悸名套惨乎芹蚁恰腥赶绊宁跪逗唇娄智吩渡莽赘狼宛截路阅无盼研无约束优化方法无约束优化方法以以为起点，沿第二坐标轴方向为起点，沿第二坐标轴方向e2进行一维进行一维搜索搜索得得甜离利乱伤讥涯债逆揩浩耪洋卡伎鱼踢梯沙宜执铬磺酪邻惦冲咕简钟颇缚无约束优化方法无约束优化方法确定此轮中的最大下降量及其相应方向
50、确定此轮中的最大下降量及其相应方向 反射点及其函数值反射点及其函数值检验检验PowellPowell条件条件曝奖始镁愈鼎奋喝买赦珐三榔疥咕幼最解捕耶达援瞥瘁怯测鸵低致喂咒仓无约束优化方法无约束优化方法由于满足由于满足PowellPowell条件，则淘汰函数值下降量最条件，则淘汰函数值下降量最大的方向大的方向e1，下一轮的基本方向组为，下一轮的基本方向组为e2，。构成新的方向构成新的方向沿沿方向一维搜索得极小点和极小值方向一维搜索得极小点和极小值，此点为下轮迭代初始点。此点为下轮迭代初始点。按点距准则检验终止条件按点距准则检验终止条件需进行第二轮迭代机算。需进行第二轮迭代机算。仓部贾痉跋橇吠赖惠
51、封贡宜婉豌沦菲卫楚挫浚奉朔针幌沼捉拍剪疼鞘演锨无约束优化方法无约束优化方法（2 2）第）第2 2轮迭代计算轮迭代计算此此轮轮基基本本方方向向组组为为e2，分分别别相相当当于于，起始点为起始点为。沿沿e2方向进行一维搜索得方向进行一维搜索得以以 为起点沿为起点沿方向一维搜索得方向一维搜索得确定此轮中函数值最大下降量及其相应方向确定此轮中函数值最大下降量及其相应方向疾丘壳次喊娜泌镍贫西锐夷安幌给吩埠澡甘从料猜阴开崔盂羽咸即训蒂嚎无约束优化方法无约束优化方法反射点及其函数值反射点及其函数值检验检验Powell条件，淘汰函数值下降量最大的方条件，淘汰函数值下降量最大的方向向e2，下一轮的基本方向组应为
52、，下一轮的基本方向组应为 ， 。构成新的方向构成新的方向沿沿方向进行一维搜索得方向进行一维搜索得做镜绥汰刀矛行墨媳空舱食盟痢若里瑰决挪缆真棉具薯啼聋搞荷及头间欧无约束优化方法无约束优化方法检验终止条件检验终止条件（3 3）第）第3 3轮迭代计算轮迭代计算此此轮轮基基本本方方向向组组为为 ，起起始始点点为为，先先后沿后沿，方向，进行一维搜索，得方向，进行一维搜索，得，故最优解故最优解检验终止条件检验终止条件演缨蒂琴危删并杨羡剪率妊馒让掳贝父袖呜湿殿烦锄炯仅玲垒吓蹦却状蒂无约束优化方法无约束优化方法 实实际际上上，前前两两轮轮迭迭代代的的 ，为为共共轭轭方方向向，由由于于本本例例目目标标函函数数是
53、是二二次次函函数数，按按共共轭轭方方向向的的二二次次收收敛敛性性，故故前前两两轮轮的的结结果果就就是是问问题题的的最最优优解解，但但每每一一轮轮迭迭代代都都需需要进行要进行n+1次迭代。次迭代。灼错帆泊殖诬股列瓶痹搪现率伺咨傣速皋颜炊讯投赢蒂摘蛇坟榆捎界类剐无约束优化方法无约束优化方法第九节第九节单纯形方法单纯形方法基本思想基本思想单纯形替换法也是一种不使用导数的求解无单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优
54、的点，而是从一个单纯一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。形迭代到另一个更优的单纯形。仇蛰戈省胳涛烧丝华馏惺泰套敖噶斜暗丹废堪淋僚优皑尧戮沽塑雕攒蚊向无约束优化方法无约束优化方法定义：单纯形定义：单纯形 n维空间中的恰好有维空间中的恰好有n+1个顶点（极点）的有界的个顶点（极点）的有界的凸多面体称之为一个单纯形。凸多面体称之为一个单纯形。根据定义，可知，一维空间中的单纯形是线段，根据定义，可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。形则是四面体。在单纯形替换算法中，从一
55、个单纯形到另一个单在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这纯形的迭代主要通过反射、扩张、收缩和缩边这4个操个操作来实现。下面以二维问题为例来对作来实现。下面以二维问题为例来对4种操作进行说明种操作进行说明（参见下图）。（参见下图）。紫闷垒奠袒卤捉咐蛆链酉辙判粤畦咖炎柯再实愚腮友身韶岔载中穷吟完国无约束优化方法无约束优化方法（1 1）反射）反射设除了最劣点设除了最劣点X X1 1以外的基余顶点的中心为以外的基余顶点的中心为X X4 4，作，作X X1 1关于点关于点X X4 4的对称点的对称点X X5 5，称，称X X5 5为为X X1 1的反射点。求
56、反射点的过程称的反射点。求反射点的过程称之为反射。之为反射。（2 2）扩张）扩张在得到反射点在得到反射点X X5 5之后，如果之后，如果X X5 5优于原单纯形的最劣优于原单纯形的最劣点（即有点（即有 ），表明反射方向（），表明反射方向（X X5 5X X1 1）是有利方向，）是有利方向，反射成功。若进一步有反射成功。若进一步有 ，可沿反射方向前进适当，可沿反射方向前进适当的距离到点的距离到点X X6 6。X X6 6称之为扩张点，求扩张点的过程称之为扩张。扩称之为扩张点，求扩张点的过程称之为扩张。扩张之后，若扩张点张之后，若扩张点X X6 6优于反射点优于反射点X X5 5，则扩张成功，以，
57、则扩张成功，以X X6 6取代取代X X1 1，得，得新单纯形新单纯形XX6 6,X,X2 2,X,X3 3 ；否则，扩张失败，舍弃扩张点，以反射；否则，扩张失败，舍弃扩张点，以反射X X5 5点点取代取代X X1 1，得新单纯形，得新单纯形XX5 5,X,X2 2,X,X3 3 。设当前的单纯形的顶点为设当前的单纯形的顶点为X X1 1，X X2 2，X X3 3，且有，且有幽饺责笼欢挤印微要她套蹈弱熄玩锚赁惭返屿锭裴哄茸柴曹撤菇龚校猜拐无约束优化方法无约束优化方法如果出现如果出现 。表示反射完全失败，应退回到介于。表示反射完全失败，应退回到介于X X4 4与与X X1 1之间的某个点之间的
58、某个点X X8 8。（3 3）收缩）收缩在得到反射点在得到反射点X X5 5之后，如果有之后，如果有表示反射部分成功，方向（表示反射部分成功，方向（X X5 5X X1 1）虽然是有利方向，但）虽然是有利方向，但X X5 5前前进过远，应收缩到介于进过远，应收缩到介于X X4 4与与X X5 5之间的某个点之间的某个点X X7 7。上述两种从反射点向上述两种从反射点向X1方向后退的过程都称之为收缩。方向后退的过程都称之为收缩。如果收缩点优于原来的最劣点如果收缩点优于原来的最劣点X1，称收缩成功，并以收缩点，称收缩成功，并以收缩点取代原最劣点，构成新单纯形取代原最劣点，构成新单纯形X7,X2,X
59、3或或X8,X2,X3；否则，；否则，称之为收缩失败，舍弃收缩点。称之为收缩失败，舍弃收缩点。痛卸辗演隔衍蔡罪淮绑损安黎华莉挽悬咋耘深扒脸磊归厨万侥吁奋驯宙沽无约束优化方法无约束优化方法（4）缩边）缩边若收缩失败，则应压缩当前单纯形的边长：令最若收缩失败，则应压缩当前单纯形的边长：令最优点优点X3不动，而其余顶点向不动，而其余顶点向X3方向压缩，使边长缩短（通常缩方向压缩，使边长缩短（通常缩短一半），以产生新单纯形。如下图所示，点短一半），以产生新单纯形。如下图所示，点X1压缩到点压缩到点X9，点点X2压缩到点压缩到点X10，得新单纯形，得新单纯形X9,X10,X3，这一过程称之为缩，这一过程
60、称之为缩边。边。叮些镊瞩撇液理坞男姿打潦偿液扑一定迸携罕竹话馁媚窑仕丸菇敲咨扁将无约束优化方法无约束优化方法二、单纯形替换算法二、单纯形替换算法设初始点为设初始点为X X0 0，初始边长，初始边长h h，e ei i为坐标轴方向的单位向量为坐标轴方向的单位向量 ，预定正数预定正数（2 2）比较各项点）比较各项点X Xi i的函数值，挑出其中的最优点，记为的函数值，挑出其中的最优点，记为X XL L；最劣；最劣点，记点，记X XH H；次差点，记为；次差点，记为X Xw w；（3 3）求反射中心）求反射中心其中，其中，a0，通常取，通常取a=1；（1 1）令）令；输出输出XL，为原问题近似极小点
61、；否则，转（，为原问题近似极小点；否则，转（2）。）。构造新单纯形；构造新单纯形；（4）根据不同）根据不同情情况，分别进行扩张，况，分别进行扩张，收缩或缩边，其中收缩因子收缩或缩边，其中收缩因子（5）如果满足）如果满足贾忱夏琢鬼墓苹韵葡姥锨徘益猩鹅倒牟寅漠俏布各裹徒列诱活减贬氓窃肥无约束优化方法无约束优化方法央欣士弧议盛钝骑得揽诀忻白亥绞赢遣锗多出铰神蛇识馏甄焰鉴咨姬哺巳无约束优化方法无约束优化方法烁团咙浊增滦港扼靶总宰肘寅灶试孕宠哈噶椅乃逝卷饲馁抱朴墨互奈卑温无约束优化方法无约束优化方法柞浪堪兽尚堤宰渐貉鸡灭罩宫瘫雅谅思壳婪傲掌力喀蜂掏褂毅爷帮腹挛泄无约束优化方法无约束优化方法表表1 1 无
62、约束优化方法搜索方向之间的相互联系无约束优化方法搜索方向之间的相互联系间接法间接法搜索方向搜索方向函函数数梯梯度度的的修修正正因子因子所用目标函数所用目标函数信息信息梯度法梯度法I I（单位阵）（单位阵）一阶导数一阶导数（阻阻尼尼）牛牛顿法顿法二阶导数二阶导数共轭梯度法共轭梯度法一阶导数一阶导数变尺度法变尺度法一阶导数，使一阶导数，使（海赛矩阵的逆阵）（海赛矩阵的逆阵）畴羡拂伞名椽吏繁政侣鄂命练孔辫犹票渍恢烹训滨氰同剩教碧潮混氟纽揍无约束优化方法无约束优化方法无约束优化方法无约束优化方法间接法总结间接法总结1、梯度法、梯度法方向方向负梯度负梯度用到一阶导数用到一阶导数适合于精度不高或用于复杂函
63、数寻找一个好的初始点适合于精度不高或用于复杂函数寻找一个好的初始点2、牛顿法、牛顿法用到一阶导数和海色矩阵，具有二次收敛性用到一阶导数和海色矩阵，具有二次收敛性要求海色矩阵奇异，且维数不宜太高要求海色矩阵奇异，且维数不宜太高3、共轭梯度法、共轭梯度法用到一阶导数，具有二次收敛性用到一阶导数，具有二次收敛性4、变尺度法、变尺度法(DFP法法)收敛快，效果好，被认为是目前最有效的无约束优化收敛快，效果好，被认为是目前最有效的无约束优化方法。适用于维数较高，具有一阶偏导数的目标函数方法。适用于维数较高，具有一阶偏导数的目标函数厕鸥载悦罗涅奄窟暮铡寥廓察煌咀宏箍轩刮甫蝶茁瞻解酪凉迭晦谷帆蝗尊无约束优化
64、方法无约束优化方法1、坐标轮换法、坐标轮换法计算效率较低计算效率较低适合维数较低，目标函数无导数或导数较难求得适合维数较低，目标函数无导数或导数较难求得2、Powell法法具有二次收敛性，收敛速度较快，可靠性高，被认具有二次收敛性，收敛速度较快，可靠性高，被认为是直接法中最有效的方法之一为是直接法中最有效的方法之一3、单纯形法、单纯形法思路清楚，收敛慢思路清楚，收敛慢无约束优化方法无约束优化方法直接法总结直接法总结跨艘问粒彬彝昆饿仑拆耽珊北添极毋肢撞马拯橙负愁共汉摄井蚊成觅挖跳无约束优化方法无约束优化方法第四章第四章无约束优化作业无约束优化作业嘲木秉赁施武心洞昭皮娄筋聚长伎刮袒而槛导玄焙郡其夯实侧陇朽秩移搅无约束优化方法无约束优化方法
