04 无约束优化方法.ppt

*第四章无约束优化方法滤茂弱卞郑套肮刚剥妨很彰忙众示襄政重畔景滴惋扼扇彻硝截佛沫收质草04无约束优化方法04无约束优化方法*,但无约束优化方法仍是优化方法中最基本的组成部份,因为解约束问题的一些有效方法就是将约束问题转化为无约束问题求解。何况还有很多问题本身就是无约束问题,人们对无约束优化方法研究也比较成熟。解无约束优化问题的一类方法是需利用函数的一阶或二阶导数,它们要充分利用函数的解析式子故称为解析法(间接法)。另一类方法在迭代过程中只需计算函数值,故称直接法。相对直接法而言解析法又称间接法。因为解析法充分利用了函数的解析性质,所以它们的收敛速度多数比直接法快,但可靠性一般较低。哈散慧耙伞戈荧港酪排捧苛蝎城秧糕廓缺观堤焊豪壳制预等葬蠢冉覆刨祟04无约束优化方法04无约束优化方法*(GradientMethod):沿着梯度方向函数值上升最快;沿负梯度方向函数值下降最快。用负梯度方向作为搜索的方向,即:或用单位负梯度矢量来表示这种方法是用函数变化率最大的方向作为搜索方向,又称最速下降法。二、迭代公式涎倦膜快困祷圈制夺秒穗襄坠气砾暂扑篷卑郁世梆祁淘巾膀歹怠洼卸绿克04无约束优化方法04无约束优化方法*或式中,步长λk可以任选,只要保证f(X(k+1))<f(X(k))。通常是沿负梯度方向进行一维搜索,找出其最优点作为下一步的迭代点。即:三、迭代过程及程序框图四、练****用梯度法求解f(X)=x12+2x22的极小点设初始点X(0)=[4,4]T要求迭代一次,并验证相邻两次迭代的搜索方向互相垂直。段瘫墨峻腺道矽栋脾秦榨呸家雌具莱罩帅从倍垄残戊闺螺仕译奴乍隐做涩04无约束优化方法04无约束优化方法*五、梯度法讨论优点:程序简单,每次迭代所需的计算量小,贮存量也少;对初始点要求不高,即使从一个不太好的初始点出发,往往也能收敛到局部极小点。缺点:收敛的速度慢。原因:最速下降是函数值在某一点的变化率而言,是一个局部的性质,从全局来看并不是最速下降方向。因此梯度法的搜索路线呈直角锯齿形状,所得到的搜索点为绕道逼近最优点的,除非目标函数是圆。s幅砍韩菠桌钓证有豢珍包集弊搐胜瓜窥柬昆怕芹卵售调访踢兵吹雀多祝钧04无约束优化方法04无约束优化方法*(Newton’sMethod)(X)在迭代点X(k)具有一阶、二阶的连续偏导数,则可将其展开成Taylor级数,并略去高于二次的项,得到:二次函数φ(X)的极值点如果将X作为一个逼近点X(k+1),牛顿法的一般迭代公式式中如果f(X)是正定二次函数,则H(X)是个常数矩阵,逼近式X(k)=X*是准确的,由X(k)出发只要迭代一次可得到极小点。摧牛台掣现的撵们脸壹阶滤歇钒域菊合愧倡釜惶犹乡添午闺定梢法岗喻决04无约束优化方法04无约束优化方法*(1).收敛的速度快,即使到了最优点邻域时也很快收敛于函数的局部最优点。(2).采用定步长迭代,因而就不能保证每次迭代中目标函数是下降的。原因:φ(X)仅为目标函数f(X)在X(k)点附近的近似表达式。X(k+1)点是φ(X)在牛顿方向上的极小点,而非原函数的极小点。解决办法:阻尼牛顿法。123450123-1-2FCDABE钢储客祭足膀塔狮磕拉芍勘殷眩载嘎滁憾肉阑刘先茶殉垃感亩惠耳笛杉疗04无约束优化方法04无约束优化方法*-[H(X(k))]-1f(X(k))作一维搜索,迭代公式:其中λk使在f(X)的Hessian矩阵H(X(k))处处正定的情况下,阻尼牛顿法能保证每次迭代函数值有所下降。即保持了牛顿法收敛快的特性,又不要求初始点选得很好。、。原因:Hessian矩阵不定。胚襄腿裸脂随吸传避汝夸羊僳侧契僧缕悠转漫市排庞页眩隆溯绊婿鲍娟掸04无约束优化方法04无约束优化方法*,其逆阵不存在,就不能构成牛顿方向,迭代无法进行。。是否能找到另一种更好的方法?,只需计算目标函数的一阶导数,对初始点的要求不高,能较好的突破函数的非二次性而迅速趋近于极值点;,一但迭代点进入极值点的邻近区域时很快地收敛于最优点。迷好充爹顿大匪蒋万岩垒骂卡千陈婶舅札盒倡右雪女让球鞠折曙乘注掸翼04无约束优化方法04无约束优化方法*(oordinateMethod),将一个n维问题转化为一系列的一维优化问题来求解。每次将n-1个变量固定,只对一个变量作一维搜索。进行一维搜索找到X1(1)进行一维搜索找到X2(1)进