《无约束优化法》由会员分享，可在线阅读，更多相关《无约束优化法（14页珍藏版）》请在金锄头文库上搜索。
1、第三章无约束优化法概述梯度法牛顿法共轭梯度法坐标轮换法鲍威尔法概述无约束优化问题的一般形式：求设计变量X 工XiK . X使目标函数F（X） min，对X没有任何约束条件。工程实际问题中，无约束结构优化问题很少，多数是有约束条件的。学习无约束结构优化原因：1）工程也有少量无约束结构优化问题，其数学模型就是无约束优化问题， 除了在非常接近最小点的情况下，可以按无约束问题处理；2）为研究约束优化问题打下基础；3）约束优化问题可以通过一系列无约束方法达到。无约束优化问题的求解，可以直接应用函数极值问题的求解方程：iF =0的问题，即求X，使其满足：CX1cF cx2n个方程组，一般为非线性的，很难用
2、解析方法求解，一般采用数值方法。与其用数值方法求解非线性 方程组，倒不如用数值方法直接求解无约束极值问题。数值方法最常用的就是搜索法，其基本思想：从给定的初始点x0出发，按照一定原则寻找搜索方向S。，沿方向S。进行搜索，确定最佳步长：，使得函数沿方向S0下降最快，依次形成迭代公式：Xk i=XkgkSkk=0,1,2,各种无约束优化方法的区别在于确定搜索方向Sk的方法，这是无约束优化方法的关键。根据构成搜索方向所使用的信息不同分为：（1）间接法利用目标函数的一阶或二阶导数，如梯度法（最速下降法）、牛顿法、共轭梯度法和变尺度法；梯度法最早由1847年柯西提出，是无约束优化的基本方法。其基本思想：
3、取目标函数的负梯度方向作为迭代的搜 索方向，必使函数值下降的速度最快。k设在第k次迭代中取得迭代点X,从该点出发，取负梯度方向：Sk _F(Xk)为搜索方向，式中：*)二匡gm兰曲GX.CX2dxn第k1次得到的新点：X =x F(X)k1 kk一般步长、丫- k= 1常采用沿负梯度方向做一维搜索：、k 1k k kF(X) = min F(Xy S )算法特点：初始阶段改进较快，最优解附近改进较慢。具体迭代步骤：1. 选择初始点X0及迭代精度；0,令迭代次数k=0 ；2. 计算点Xk的梯度、F(Xk)及梯度的模、F(Xk),并令SkUF(X)3. 判断是否满足收敛精度IPF(X)卜S一般情)
4、兄下，若pF*)，则Xk为近似最优点，F(X)为近似最优值，可以输出最优解X” = kXF(X ) =F(X )，否则进行 4.k4. 从点Xk出发，沿负梯度方向求最优步长:-k,及沿Sk进行一维搜索，求得使函数下降最多的步长因子：-kmin F(Xk: kSk) =min ()X-：.kSkk1 =Xk令父1 ，转入2步。例题：用最速下降法求解问题min f (X) = 4x 2 X2,其中X=(X!5x2)t.取初始点X(1,1),允许误差；=0.1.解：f在点 X(X!5x2)t处的梯度 If (X) =(8n,2x2)t.第一次迭代：令搜索方向，八- f (X0-8,-2)t,*64
5、4=2、17 故从点X0出发沿S)作一维搜索，代入目标函数并求其最小值minf(X0+.Z S)=min：(二)令：(,二)=0 即最佳步长因子得 0.130769:0=X (1,1) T 0.13.769(-8, _2)t =(-0.046152,0.738462)t第二次迭代：令搜索方向3 - f(XJ =(0.369216, -1.476924)S = .218305 =1.522375;从点人出发沿包作一维搜索，X2 = (0.101537, 0.147682) t第三次迭代：令搜索方向s2-； f(X 2)=(0.369216,-1.476924)52 =:; 0.747056 =0
6、.864329从点X2出发沿S2作一维搜索，X 3 =(-0.009747, 0.107217) t第四次迭代：令搜索方向S3 - f(X3) =(0.077976, -0.214434)53 = 0052062 0.228171从点x3出发沿s3作一维搜索，X4 = (0.019126, 0.027816) t第五次迭代：令搜索方向 S4 - _f (X4) =(-0.153008, -0.055632)T,S40.026506 0.162807 .;从点x4出发沿s4作一维搜索，X5=( .001835,0.020195)T此时，If(X5)= .0.001847 : : :,满足精度要求
7、，故得问题的最优解为X =(-0.001835,0.020195) t实际上，原问题的最优解为X 二(0,0)T梯度法的特点：1. 理论明确，方法简单，概念清楚，计算量小，对 初始点没有严格要求。2. 相邻两次迭代的梯度方向是相互正交的，搜索线 路呈直角锯齿形，越靠近极小点，搜索密度越 大，收敛越慢。3. 迭代次数与目标函数等值线的形状有关，目标函 数若为椭圆族越扁，迭代次数越多，搜索到最优 点的难度越大。4.所谓最速下降方向-(Xk )仅仅反映了 f在点X k处的局部性质，对局部来说是最速的下降方向，但对整体求解过程并不一定使目标值下降得最快。最速下降法逼近极小点X的路线是锯齿形的，当迭代点
8、越靠近X，其搜索步长就越小，因而收敛速度越慢。2 2试用梯度法求目标函数F (X) = (Xj-1) ( X2-1)的极小值，设初始点+25x；的最优解。初始点x=2,2t，迭代精Xo二 0,九；=0.01。习题二：试用梯度法求目标函数F(X)度；=0.05。牛顿法牛顿法的基本思想就是利用二次函数来代替原目标函数，以二次函数的极小点作为原目标函数的极小点的近似，并逐步逼近该点。k设一般目标函数f(x)具有一、二阶偏导数，此时，在X处做泰勒展开并取值二次项，f(X)(X) = f(xk) if (Xk)T(X _xk) 1(X _xk八 2f(Xk)T(X _xk)其中H (xk) J 2f X
9、k f(X)在 Xk的海森矩阵，是对称方阵。求f (X)的极小问题转换为(X)的极小值问题。令I凶=0,即:Vf (X )kH (X )(X kX )=0k若H (Xk)为正定，解得：X =xkH 二(Xk)l f (Xk)由于Xk在极小点附近，X “作为f(x)极小点的下一个近似点X*k-H(X$f(X)其中：搜索方向sk- -H(XkP f(X)步长恒为1 o例题：用牛顿法求解问题min f (X) =4x； x；,其中X=(X1,X2)T取初始点Xo=(1,1),允许误差；=0.1.解：f (Xo) =(8,2)T,l2l2f(X。)卞01f(X)+ 2，故；，椿&.2修0)七 f(X)
10、=-； 1-(1,1)T 一00,0)TXAXoSo=(1,1：)由于f (X1)0 0.1,迭代结束，得x1为问题的最优解。以上例子说明，牛顿法比最速下降法收敛快有定理可以证明，当初始点X。靠近极小点X ”时，牛顿法的收敛速度是很快的。但是，当X远离X时寸，牛顿法可能不收敛，甚至连下降性也保证不了。其原因是：迭代点Xk1不一定是目标函数f在搜索方向sk上的极小点仅是(X)在牛顿方向上的极小点。 klk习题三：用牛顿法求目标函数F (X) = x?+25x；的极小点和极小值。取初始点X = 2, 2t习题四：用牛顿法求F(X) =10x14x2+2的最优解，取初始点X=2,5t，迭代精度；=0
11、1。修正牛顿法为了弥补牛顿法的上述缺陷，人们把牛顿法作了如下修正：由Xk求Xk 1时，不直接用迭代公式Xk二xk- P2f(xk)t f (Xk),其因为这个公式已经把步长限定为1。而是沿着牛顿方向Sk进行一维搜索。这样就是所谓的阻尼牛顿法，也称为修正牛顿法。阻尼牛顿法一般步骤：1选取初始数据。选取初始点X0,给定允许误差；0,令k = 02检验是否满足终止准则。计算、f(Xk)，若f(Xk)：；，迭代终止，Xk为问题的近似最优解；否则，转steps.3构造牛顿方向。计算2f(Xk)，取Sk 一、2f (XA f (X)4进行一维搜索。求：k和Xki,使得f (X : skSA min f(X
12、k ：二 Sk)xk 1 = xk 讦叭”令 k :二 k 1,返回 step2牛顿法特点如果f (x)是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代，就可达到最优点,如不是二次函 数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似，因此牛顿法的收敛速 度还是很快的。牛顿法的收敛速度虽然较快，但要求海森矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量。2 2习题五：用阻尼牛顿法求函数F(XA4(xA1) +2(x2 T) +/+X2+1。的最优解，取初始点=0,0丁，迭代精度；=0001。共轭方向法和共轭梯度法共轭方向概念共轭方向的概念是在研究二次函
13、数1F XXtHX BtX C过程中引出的。考虑二维情形，如果按最速下降 法，选择负梯度方向为搜索方向，会产生锯齿现 象；为避免锯齿的发生，取下一次的迭代搜索方 向直接指向极小点，如果选定这样的搜索方向， 对于二元二次函数只需进行两次直线搜索就可 以求到极小点。X。初选初始点X。沿某个下降方向S。做一维搜索， 得X1=-0是沿s。方向搜索的最佳步长，即在点X1处的函数F(X)沿方向s。的方向导数为零。考-1F lX虑到点X1处方向导数与梯度之间的关系，有：)= F X1 S = 0为避免锯齿现象，下一次迭代搜索方向S1指向极小点xX “ = 1 *W其中1为方向S1的最佳步长。1这样的S满足什
14、么条件？对于二次函数F (X)在X处取得极小点的必要条件：F X二 HX*B = 0C F X1= HX1B)即：FX*= HX : 9) B = HXF : HFX1 ：用=0上式两边左乘拾0.得：-S tHS1 =0满足上式的两个量S0和S1称为H的共轭向量，或称S0和S1对H是共轭方向。G是nxn寸称正定矩阵，方向向量di, d2, -, -dm的m r如果:diT Gq =0-i = j称方向向量di, d2,dm关于G的共轭方向共轭方向性质：o i1) S , S ,。关于G共轭，这些向量是线性无关的；2) 在N维空间中相互共轭的向量个数不超过N个;3) 若G是单位矩阵，贝uS， 1s ,。相互垂直正交；共轭方向法步骤：1.选定初始点X。，下降方向S。和收敛精度；，迭代次数k=0 ；2-沿Sk方向进行一维搜索，得Xk d *:-kSk ；3. 判断F(Xk*)|兰是否满足，若满足则打印输出；否则转4。4. 提供新的共轭方向Sk*，使&了 HSk* = , j =0，l，2，k5. k=k 1，转 2。共轭梯度法共轭梯度法是共轭方向法的一种，共轭向量有迭代点的负梯度构造出来，所以称共轭梯度法。该法于1964年由弗里茨和里乌斯两人提出。首先研究共轭方向与梯度之间关系：1F
