无约束优化法

第三章无约束优化法概述梯度法牛顿法共轭梯度法坐标轮换法鲍威尔法概述无约束优化问题的一般形式：求设计变量12[,,...]TnXxxx使目标函数()minFx，对X没有任何约束条件。工程实际问题中，无约束结构优化问题很少，多数是有约束条件的。学习无约束结构优化原因：1）工程也有少量无约束结构优化问题，其数学模型就是无约束优化问题，除了在非常接近最小点的情况下，可以按无约束问题处理；2）为研究约束优化问题打下基础；3）约束优化问题可以通过一系列无约束方法达到。无约束优化问题的求解，可以直接应用函数极值问题的求解方程：0F的问题，即求X，使其满足：1200...FxFxn个方程组，一般为非线性的，很难用解析方法求解，一般采用数值方法。与其用数值方法求解非线性方程组，倒不如用数值方法直接求解无约束极值问题。数值方法最常用的就是搜索法，其基本思想：从给定的初始点0x出发，按照一定原则寻找搜索方向0S，沿方向0S进行搜索，确定最佳步长0，使得函数沿方向0S下降最快，依次形成迭代公式：1kkkkXXS0,1,2,...k各种无约束优化方法的区别在于确定搜索方向kS的方法，这是无约束优化方法的关键。根据构成搜索方向所使用的信息不同分为：（1）间接法利用目标函数的一阶或二阶导数，如梯度法（最速下降法）、牛顿法、共轭梯度法和变尺度法；（2）直接法直接利用目标函数，如坐标轮换法、鲍威尔法和单形替换法。梯度法最早由1847年柯西提出，是无约束优化的基本方法。其基本思想：取目标函数的负梯度方向作为迭代的搜索方向，必使函数值下降的速度最快。设在第k次迭代中取得迭代点kx，从该点出发，取负梯度方向:()kkSFX为搜索方向，式中：12()()()(),,....TkkkknFXFXFXFXxxx第1k次得到的新点：1()kkkkXXFX一般步长1k常采用沿负梯度方向做一维搜索：1()min()kkkkFXFXS算法特点：初始阶段改进较快，最优解附近改进较慢。具体迭代步骤：1.选择初始点0X及迭代精度0，令迭代次数0k；2.计算点kX的梯度()kFX及梯度的模()kFX，并令()kkSFX3.判断是否满足收敛精度()kFX。一般情况下，若()kFX，则kX为近似最优点，()kFX为近似最优值，可以输出最优解kXX，()()kFXFX，否则进行4.4.从点kX出发，沿负梯度方向求最优步长k，及沿kS进行一维搜索，求得使函数下降最多的步长因子kmin()min()kkkFXS5.确定新的近似点1kX，此点也就是下次迭代的出发点1kkkkXXS令1kk，转入2步。例题：2120000,)()(8,2).()(8,2),644217TTTfXxfXxxfXf1000解：在点（x处的梯度第一次迭代：令搜索方向SS故从点X出发沿S作一维搜索，代入目标函数并求其最小值min(X+S)=min()令()=0即最佳步长因子得10.130769110.13.769(8,2)(0.046152,0.738462)TTTX0（，）22122min()4,,).(1,1),0.1.TTfXxxx10用最速下降法求解问题其中X=(x取初始点X允许误差1111222()(0.369216,1.476924),2.183051.522375(0.101537,0.147682)()(0.369216,1.476924),TTTfXXfX1第二次迭代：令搜索方向SS从点X出发沿S作一维搜索，第三次迭代：令搜索方向S22333330.7470560.864329(0.009747,0.107217)()(0.077976,0.214434),0.0520620.228171TTXfX23S从点X出发沿S作一维搜索，第四次迭代：令搜索方向SS从点X出发沿S作一维搜索，4(0.019126,0.027816)TX梯度法的特点：1.理论明确，方法简单，概念清楚，计算量小，对初始点没有严格要求。2.相邻两次迭代的梯度方向是相互正交的，搜索线路呈直角锯齿形，越靠近极小点，搜索密度越大，收敛越慢。3.迭代次数与目标函数等值线的形状有关，目标函数若为椭圆族越扁，迭代次数越多，搜索到最优点的难度越大。4.习题一：试用梯度法求目标函数2212()(1)(1)FXxx的极小值，设初始点0[0,0]TX，0.01。习题二：试用梯度法求目标函数2212()25FXxx的最优解。初始点0[2,2]TX，迭代精度0.05。牛顿法牛顿法的基本思想就是利用二次函数来代替原目标函数，以二次函数的极小点作为原目标函数的极小点的近似，并逐步逼近该点。设一般目标函数()fx具有一、二阶偏导数，此时，在kX处做泰勒展开并取值二次项，444455()(0.153008,0.055632),0.0265060.162807(0.001835,0.020195)()0.001847,TTfXXfX4第五次迭代：令搜索方向SS从点X出发沿S作一维搜索，此时，满足精度要求，故得问题的最优解为5(0.001835,0.020195)(0,0)TTX实际上，原问题的最优解为X()kkfXfXXX所谓最速下降方向仅仅反映了在点处的局部性质，对局部来说是最速的下降方向，但对整体求解过程并不一定使目标值下降得最快。最速下降法逼近极小点的路线是锯齿形的，当迭代点越靠近，其搜索步长就越小，因而收敛速度越慢。得：其中2()()kkHXfX为()fX在kX的海森矩阵，是对称方阵。求()fX的极小问题转换为()X的极小值问题。令()0X，即：()())0kkkfXHXXX（若()kHX为正定，解得：1()()kkkXXHXfX由于kX在极小点附近，X作为()fx极小点的下一个近似点11()()kkkkXXHXfX其中：搜索方向1()()kkkSHXfX步长恒为1。例题：以上例子说明，牛顿法比最速下降法收敛快21()()()()()()()()2kkTkkTkTkfXXfXfXXXXXfXXX22122min()4,,).(1,1),0.1.TTfXxxx10用牛顿法求解问题其中X=(x取初始点X允许误差2002121000010011()(8,2),()1()][()]()1(1,1)(1,1)(0,0)()00.1,TTTTfXfXfXfXfXXXSfXX80解：，故02108[，S102由于迭代结束，得为问题的最优解。001kkXXXXXf有定理可以证明，当初始点靠近极小点时，牛顿法的收敛速度是很快的。但是，当远离时，牛顿法可能不收敛，甚至连下降性也保证不了。其原因是：迭代点不一定是目标函数在搜索方向S上的极小点,仅是（x）在牛顿方向上的极小点。习题三：用牛顿法求目标函数2212()25FXxx的极小点和极小值。取初始点0[2,2]TX习题四：用牛顿法求22122()1042FXxxx的最优解，取初始点0[2,5]TX，迭代精度0.01。修正牛顿法其步牛顿法特点如果()fx是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代，就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似，因此牛顿法的收敛速度还是很快的。牛顿法的收敛速度虽然较快，但要求海森矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量。习题五：用阻尼牛顿法求函数221212()4(1)2(1)10FXxxxx的最优解，取初始点0[0,0]TX，迭代精度0.001。1121[()]()1kkkkkkkXXXXfXfX为了弥补牛顿法的上述缺陷，人们把牛顿法作了如下修正：由求时，不直接用迭代公式，因为这个公式已经把步长限定为。而是沿着牛顿方向S进行一维搜索。这样就是所谓的阻尼牛顿法，也称为修正牛顿法。012211,00(),(),3.()[()](),kkkkkkkkXkfXfXXStepfXfXfXXk阻尼牛顿法一般步骤：1选取初始数据。选取初始点给定允许误差，令2检验是否满足终止准则。计算若迭代终止，为问题的近似最优解；否则，转3构造牛顿方向。计算，取S4进行一维搜索。求和使得01()min():1,2kkkkkkfXfXXXkkstepkkkSSS令返回共轭方向法和共轭梯度法共轭方向概念共轭方向的概念是在研究二次函数12TTFXXHXBXC过程中引出的。考虑二维情形，如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象；为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，如果选定这样的搜索方向，对于二元二次函数只需进行两次直线搜索就可以求到极小点。初选初始点0X沿某个下降方向0S做一维搜索，得1X1000XXS0是沿0S方向搜索的最佳步长，即在点1X处的函数()FX沿方向0S的方向导数为零。考虑到点1X处方向导数与梯度之间的关系，有：1100()0TFXFxSS为避免锯齿现象，下一次迭代搜索方向1S指向极小点X111XXS其中1为方向1S的最佳步长。这样的1S满足什么条件？对于二次函数()FX在X处取得极小点的必要条件：**0FXHXB11()FXHXB即：*111111111()0FXHXSBHXBHSFXHS上式两边左乘0TS得：010TSHS满足上式的两个量0S和1S称为H的共轭向量，或称0S和1S对H是共轭方向。G是n×n对称正定矩阵，方向向量d1,d2,···,dm的m≤n.如果：0TijdGdij称方向向量d1,d2,···,dm关于G的共轭方向共轭方向性质：1）0S，1S，。。。关于G共轭，这些向量是线性无关的；2）在N维空间中相互共轭的向量个数不超过N个；3）若G是单位矩阵，则0S，1S，。。。相互垂直正交；共轭方向法步骤：1.选定初始点0X，下降方向0S和收敛精度，迭代次数0k；2.沿kS方向进行一维搜索，得1kkkkXXS；3.判断1()kFX是否满足，若满足则打印输出；否则转4。4.提供新的共轭方向1kS，使10TjkSHS，0,1,2,...jk5.1kk，转2。共轭梯度法共轭梯度法是共轭方向法的一种，共轭向量有迭代点的负梯度构造出来，所以称共轭梯度法。该法于1964年由弗里茨和里乌斯两人提出。首先研究共轭方向与梯度之间关系：12TTFXXHXBXC从点kX出发，沿H的某一共轭方向kS做一维搜索，到达1kX点即：1kkkkXXS在点kX，1kX处的梯度kg，1kg为kkgHXB，11kkgHXB有：11()kkkkkkggHXXHS若jS，kS对H是共轭的，有：0TjkSHS代入上式得：1[]()0jTkkSgg（111kkkkkgSgSg）得出共轭方向与梯度之间的关系。此式表明沿方向kS进行一维搜索，其终点1kX和始点kX的梯度之差1()kkgg与kS的共轭方向jS正交。如下图所示。坐标轮换法以上方法都要计算目标函数的偏导数，属于间接法。大量的工程问题目标函数往往很复杂，有的没有明显的解析表达式，其导数难以获得或根本不存在，间接法无法使用，只能借助直接法。坐标轮换法是每次