无约束优化法

1、第三章无约束优化法概述梯度法牛顿法共轭梯度法坐标轮换法鲍威尔法概述无约束优化问题的一般形式：求设计变量Xx,x,.xT12n使目标函数F（x）min，对X没有任何约束条件。工程实际问题中，无约束结构优化问题很少，多数是有约束条件的。学习无约束结构优化原因：1）工程也有少量无约束结构优化问题，其数学模型就是无约束优化问题，除了在非常接近最小点的情况下，可以按无约束问题处理；2）为研究约束优化问题打下基础；3）约束优化问题可以通过一系列无约束方法达到。无约束优化问题的求解，可以直接应用函数极值问题的求解方程：F0的问题，即求X，使其满足：00X2n个方程组，一般为非线性的，很难用解析方法求解，一般

2、采用数值方法。与其用数值方法求解非线性方程组，倒不如用数值方法直接求解无约束极值问题。数值方法最常用的就是搜索法，其基本思想：从给定的初始点x0出发，按照一定原则寻找搜索方向S0，沿方向S0进行搜索，确定最佳步长0，使得函数沿方向S0下降最快，依次形成迭代公式:XkXkkSkk0,1,2,.各种无约束优化方法的区别在于确定搜索方向Sk的方法，这是无约束优化方法的关键。根据构成搜索方向所使用的信息不同分为：间接法利用目标函数的一阶或二阶导数，如梯度法（最速下降法）、牛顿法、共轭梯度法和变尺度法；直接法直接利用目标函数，如坐标轮换法、鲍威尔法和单形替换法。梯度法最早由1847年柯西提出，是无约束优

3、化的基本方法。其基本思想：取目标函数的负梯度方向作为迭代的搜索方向，必使函数值下降的速度最快。设在第k次迭代中取得迭代点*从该点出发，取负梯度方向：SkF(Xk)为搜索方向，式中：.(Xk)*(Xk)*(Xk)TOC o 1-5 h z HYPERLINK l bookmark18 F(Xk),，.xxx12n第k1次得到的新点：XkXkkF(Xk)一般步长k1常采用沿负梯度方向做一维搜索：F(Xk)minF(XkkSk)算法特点：初始阶段改进较快，最优解附近改进较慢。具体迭代步骤：.选择初始点X0及迭代精度0，令迭代次数k0；.计算点Xk的梯度F(Xk)及梯度的模F(Xk)|，并令SkF(X

4、k).判断是否满足收敛精度眄F(Xk)|一般情况下，若|F(Xk)|，则Xk为近似最优点，F(Xk)为近似最优值，可以输出最优解XXk，F(X)F(Xk)，否则进行4.从点Xk出发，沿负梯度方向求最优步长，及沿Sk进行一维搜索，求得使函数下降最多的步长因子kminF(Xk1kSk)min().确定新的近似点X0,此点也就是下次迭代的出发点XkXkkSk令kkH，转入2步。例题：用最速下降法求解问题minf(X)4x2x2,12其中,，)t.取初始点(i,ir,允许误差0.1.120解：f在点X(,x)T处的梯度,(X)(8x,2x)T.12i2第一次迭代：令搜索方向(X)(IB,IE)t,00

5、|11%：6442v17故从点出发沿作一维搜索，代入目标函数并求其最小值00f+令即最佳步长因子00得0.i30769XO0.13.769(*,IE)t(D.046152,0.738462)t第二次迭代：令搜索方向(X)(0.369216,1.476924)t,1|:|2.183051.522375从点出发沿作一维搜索，11X(0.101537,0.147682)T第三次迭代：令搜索方向(X)(0.369216,1.476924)t,22|0.7470560.864329从点出发沿作一维搜索，22X(0.009747,0.107217)T3第四次迭代：令搜索方向(X)(0.077976,BQ.

6、214434)t,33|0.0520620.228171从点出发沿作一维搜索，33X(0.019126,0.027816)T4第五次迭代：令搜索方向(X)(D.153008,ID.055632)t,4411|40.0265060.162807从点出发沿作一维搜索，44X(0.001835,0.020195)T5此时,|.(X5)|0.001847满足精度要求，故得问题的最优解为X(0.001835,0.020195)T5实际上，原问题的最优解为(0,0)t梯度法的特点：理论明确，方法简单，概念清楚，计算不量小，对初始点没有严格要求。相邻两次迭代的梯度方向是相互正交的，搜索线路呈直角锯齿形，越靠

7、近极小点，搜索密度越大，收敛越慢。迭代次数与目标函数等值线的形状有关，目标函数若为椭圆族越扁，迭代次数越多，搜索到最优点的难度越大。所谓最速下降方向f(X)仅仅反出对局部来说是最速的下降方向，及但对整体：形的，当迭代点越靠近X,其搜索步长形的，当迭代点越靠近X,其搜索步长q95,心,乂越慢。：试用梯度法求目标函数F(X)(%1)2(X1)2的极小值，设初始点X00,8,0.01o习题二,试用梯度法求目标函数F(X)x225x2的最优解。初始点X02,2t,迭代精度0.05。牛顿法牛顿法的基本思想就是利用二次函数来代替原目标函数,以二次函数的极小点作为原目标函数的极小点的近似,并逐步逼近该点。设

8、一般目标函数f(X)具有一、二阶偏导数，此时，在Xk处做泰勒展开并取值二次项，得：1f(X)(X)f(Xk)时(Xk)t(XXk)(XXk)T2f(Xk)t(XXk)2其中H(Xk)2fXk为f(X)在Xk的海森矩阵，是对称方阵。求f(X)的极小问题转换为(X)的极小值问题。令(X)0，即：f(Xk)H(Xk(XXk)0若H(Xk)为正定，解得：XXkH(Xk).(Xk)由于Xk在极小点附近，X乍为f(x)极小点的下一个近似点XkXkH(Xk).(Xk)其中：搜索方向Sk叫(Xk).(Xk)步长恒为1。例题：用牛顿法求解问题minf(X)4x2x2,12其中，x)t.取初始点(1,1T,允许误

9、差0.1.解：120解：f(X0)2T，2于(X0)故。.2。.2f(X0怖叫(X0)XXS(1,1)T(1,1)T(0,0)Ti00由于IIf(X1)|00.1,迭代结束，得X为问题的最优解。以上例子说明，牛顿法比最速下降法收敛快有定理可以证明，当初始点X0靠近极小点X国寸，牛顿法的收敛速度是很快的。但是，当X0远离X!时，牛顿法可能不收敛，甚至连下降性也保证不了。其原因是：迭代点Xk不一定是目标函数f在搜索方向k上的极小点仅是)在牛顿方向上的极小点。习题三：用牛顿法求目标函数F(X)X225%2的极小点和极小值。取初始点X02,2/习题四：:用牛顿法求F(X)10%2X24X2的最优解，取

10、初始点X02,5t,迭代122精度0.01。修正牛顿法为了弥补牛顿法的上述缺陷，人们把牛顿法作了如下修正：由Xk求Xk时，不直接用迭代公式XkXk2f(Xk)HBf(Xk)，因为这个公式已经把步长限定为1。而是沿着牛顿方向k进行一维搜索。这样就是所谓的阻尼牛顿法，也称为修正牛顿法。阻尼牛顿法一般步骤：选取初始数据。选取初始点X0,给定允许误差0,令k0检验是否满足终止准则。计算(Xk),若|(Xk)|迭代终止，Xk为问题的近似最优解；否则，转Step3.构造牛顿方向。计算.2f(Xk)，取2f(Xk)(Xk)进行一维搜索。求k和Xk，使得f(Xkk)minf(Xk-)0Xk1XkkSk令X:X

11、k-l,返回step2牛顿法特点如果f(%)是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代，就可达到最优点,如不是二次函数,则牛顿法不能一步达到极值点,但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的。牛顿法的收敛速度虽然较快,但要求海森矩阵要可逆,要计算二阶导数和逆矩阵,就加大了计算机计算量和存储量。习题五：用阻尼牛顿法求函数F(X)4(%1)22(%Hl)2%10的最优解，取初1212始点X00,0t,迭代精度0.001。共轭方向法和共轭梯度法共轭方向概念共轭方向的概念是在研究二次函数FX.2XtHXBtXC过程中引出的。考虑二维情形，如果按最速下降法，选择负

12、梯度方向为搜索方向，会产生锯齿现象；为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，如果选定这样的搜索方向，对于二元二次函数只需进行两次直线搜索就可以求到极小点。初选初始点X0沿某个下降方向S0做一维I0是沿S0方向搜索的最佳步长，即在点X1处的函数F(X)沿方向S0的方向导数为零。考虑到点X1处方向导数与梯度之间的关系，有：毛F1S00S0为避免锯齿现象，下一次迭代搜索方向S1指向极小点XXX11S1其中1为方向S1的最佳步长。这样的S1满足什么条件？对于二次函数F(X)在X处取得极小点的必要条件：F*!HX*B0(F1.HX1B)即：FX*!H(X1-iS1)BHX1B11HS1f

13、1*!1HS10上式两边左乘.0.得：S0THS10满足上式的两个量S0和S1称为H的共轭向量，或称S0和S1对H是共轭方向。G是nxn对称正定矩阵，方向向量di,d2,d.的.如果:dTGd0ijij称方向向量di,d2,dm关于G的共轭方向共轭方向性质：1)S0,S1,。关于G共轭，这些向量是线性无关的；2)在N维空间中相互共轭的向量个数不超过N个；3)若G是单位矩阵，则S0，S1，。相互垂直正交；共轭方向法步骤：.选定初始点X0，下降方向S0和收敛精度，迭代次数k0；.沿Sk方向进行一维搜索，得Xk.Xk-kSk；.判断F(Xk)是否满足，若满足则打印输出；否则转4。.提供新的共轭方向S

14、k，使SjTHSk0，j0,1,2,.k.kkH，转2。共轭梯度法共轭梯度法是共轭方向法的一种，共轭向量有迭代点的负梯度构造出来，所以称共轭梯度法。该法于1964年由弗里茨和里乌斯两人提出。首先研究共轭方向与梯度之间关系：FX-XtHXBtXC2从点Xk出发，沿H的某一共轭方向Sk做一维搜索，到达Xk点即：XkXkkSk在点Xk，Xk处的梯度g，g为kkgHXkB，gHXkBkk有：ggH(XkXk)kHSkkk若Sj,Sk对H是共轭的，有：.j.HSk0(SkBigk代入上式得：Sj(SkBigkkk得出共轭方向与梯度之间的关系。此式表明沿方向Sk进行一维搜索，其终点Xk和始点Xk的梯度之差

15、双Jg）与Sk的共轭方向SJ正交。如下图所示。坐标轮换法以上方法都要计算目标函数的偏导数，属于间接法。大量的工程问题目标函数往往很复杂，有的没有明显的解析表达式，其导数难以获得或根本不存在，间接法无法使用，只能借助直接法。坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量的优化问题。又称变量轮换法，也称降维法。其基本原理是将一个多维的无约束最优化问题转化为一系列较低维的最优化问题来求解，简单地说，就是先将nH个变量固定不动，只对第一个变量进行一维搜索得到最优点X1，然后，又保持n个变量1不变，再对第二个变量进行一

16、维搜索到X1等等，直到所有变量进行后完成一轮，再进行下2一轮的变换，把N维优化问题转化为一系列一维优化问题。X的右上角表示迭代的轮数，右下角表示该轮中的两个迭代点。搜索方向与步长的确定对于第k轮第i次的计算：XkXkkSki1,2,n.iiii其中Xk第k轮第iH次迭代起始点；iSk第k轮第i次搜索方向，它轮换取n维坐标的单位向量，iSke010叽其中第i分量为1,其余为0.iik第k轮第i次迭代步长因子。i步长可正可负,一般采用最优步长法,就是沿坐标轴方向搜索中,利用黄金分割法等确定沿该方向上的具有最小目标函数的步长,即：F(XkkSk)minF(XkSk)i*iiii例题：坐标轮换法求目标

17、函数F(X)%2%2%10%4%60的无约束最优解。121212取初始点X00,0叽迭代精度0.1。解：第一轮：沿S：即1方向进行一维搜索，取X0X0，因为X11X0-1S110卜1访需dF(XdF(X1)d12BH001minF(X1)2H10H60111得：15x1以X1以X1为起点，沿e2方向进行一维搜索,因为X2-X尸2S2噌卜2i准i2minF(X1)2525B504B602935222222dF(X1)2B90d22”_5得：4.5X1.2.检测：|x2xi|J524.526.7进行第二轮。精确解：x8,x6,F8。12min习题六:用坐标轮换法求函数F(X)2x23x28x10的

18、无约束最优解，取初始点X01,2t，迭代精度0.01。坐标轮换法的问题W11a)当函数白睛叫UW11a)当函数白睛叫U长短轴平伊则网b)当函数的返次其长短轴与强解Mc)当函国恒愈1长沼轴h”屣余运!用其陆芳去。找才刎修6)鲍威尔法Powell法是利用共轭方向可以加速收敛的性质所形成的一种搜索算法，又称方向加速法。共轭方向的生成9攵敛快，多次搜索方台华1,血任回坐标士闻都无法使函数下降，改71抻占0/卜/1设Xk、Xk从不同点出发，沿同一方向Sj进行一维搜索得到两个极小点，根据梯度与等值面垂直性质，Sj与Xk、Xk两点的梯度ggk存在以下关系:0k同时：由二维推广至N维，鲍威尔算法就是在每轮开始点和终止点决定新的搜索方向，把这个新方向替换原来N