《[工学]2-4无约束优化方法》由会员分享，可在线阅读，更多相关《[工学]2-4无约束优化方法（53页珍藏版）》请在金锄头文库上搜索。
1、2-4 无约束优化方法,无约束优化问题的下降迭代算法具有统一的迭代格式，问题之一是选择搜索方向。根据搜索方向的不同构成方式，分：1) 导数法(解析法)利用目标函数的一阶导数或二阶导数信息构造搜索方向的方法。梯度法、牛顿法、共轭梯度法和变尺度法 条件：目标函数求导容易；目标函数一阶导数连续；目标函数是设计变量的显函数。,2-4 无约束优化方法,2)模式法(直接法)通过比较几个已知点的函数值构造搜索方向的算法。鲍威尔法。构成搜索方向的信息仅仅是几个有限点上的函数值，难于得到较理想的搜索方向。一般迭代次数较多，收敛速度较慢。,一、梯度法,迭代方向由迭代点的负梯度构成最速下降法。梯度法迭代公式,一、梯
2、度法,根据极值的必要条件和复合函数求导公式，有,相邻两迭代点的梯度正交,最优步长因子k，由一维搜索确定,一、梯度法,特点：(1)算法简单，只计算目标函数一阶导数，占用内存少；(2)初始点任选；(3)初始迭代速度快；(4) 搜索路线正交，收敛速度越来越慢。,梯度法 程序框图,一、梯度法,例 用梯度法求解,解： 第一次迭代, = 0.1,一、梯度法, 第二次迭代X(1)为初始点，进行迭代 ,二、牛顿法,梯度法除在最初几次迭代中函数值下降很快外，总的来说下降不快，且愈接近极值点下降愈慢。寻求使目标函数值下降更快的方法牛顿法。基本思路：利用二次曲线逐点近似原目标函数，以二次曲线的极小点近似原目标函数的
3、极小点并逐渐逼近该点。牛顿法分基本牛顿法和阻尼牛顿法。,1. 基本牛顿法,函数f(X)在点X(k)处展开成泰勒二次近似式,设X(k+1)是函数的极小点，有,用基本牛顿法求解正定二次函数时，无论从哪个初始点出发，一次计算即可达到极小点。,1基本牛顿法,对于非线性正定函数，二阶泰勒展开式只是原函数的近似式，得到X(k+1)只是原函数的近似极小点。以此点作为下一次迭代的起始点X(k) ，能够加快逼近的速度。 对于非正定函数，为保证牛顿方向是函数值下降的方向，海赛矩阵必须正定。采用定步长，即使牛顿方向是函数值下降的方向，也不能保证函数值下降，即得到的点并不能始终保持函数的下降性基本牛顿法有可能失效。,
4、2阻尼牛顿法,在迭代中引入步长因子和一维搜索。,阻尼牛顿法在每次迭代中沿牛顿方向作一维搜索，保证迭代点的严格下降性，适用于任何函数，且保证得到的迭代点更加靠近极小点，具有更加理想的收敛效果。牛顿法均指阻尼牛顿法。,2阻尼牛顿法,阻尼牛顿法 程序框图,特点：(1)具有二阶收敛性，收敛速度快；(2)在极值点附近有效；(3)计算复杂；(4)X(0)位置和函数性态影响计算结果。,二、牛顿法,例 牛顿法求解,解 (1)基本牛顿法, = 0.1,二、牛顿法,(2)阻尼牛顿法基本牛顿法计算得,二、牛顿法,解得 = 1,三、变尺度法,变尺度法是拟牛顿法。克服牛顿法的缺点，继承其收敛快的优点，具有超线性收敛速度
5、。1959年，Davidon提出变尺度法， Fletcher和Powell改进DFP法。,优化算法一般迭代公式,三、变尺度法,梯度法，搜索方向为负梯度方向,牛顿法，搜索方向为牛顿方向,统一形式,三、变尺度法,梯度法,牛顿法,在迭代开始时，按负梯度方向搜索；尔后每次迭代时不断调整A(k)，修正搜索方向，使A(k)逐步逼近目标函数的海赛矩阵之逆矩阵；当迭代点临近极小点时，构成的方向就近似为牛顿方向， 直指极小点。,整个迭代过程收敛速度很快。矩阵A(k)代替海赛矩阵之逆矩阵，且迭代过程中不断改变变尺度矩阵。,三、变尺度法,关键：构造变尺度矩阵,1. 变尺度矩阵构造原则,1) 算法具有下降性,为了使方
6、向S(k) = - A(k)g(k)为目标函数值的下降方向，构造的变尺度矩阵A(k)应为正定对称矩阵。,三、变尺度法,2）计算方便性,构造的变尺度矩阵A(k)应便于计算，在迭代过程中应逐渐地逼近海赛矩阵之逆矩阵。,取单位矩阵I为初始矩阵A(0),E(k)校正矩阵。,三、变尺度法,DFP变尺度法在函数f(X)梯度易求的情况下，非常有效。对于多维问题(n100)，收敛快，效果佳无约束极值问题优化的最好方法之一。计算程序较复杂，需要较大的存储量，特别是在有舍入误差时，存在数值稳定性不够理想的情况。,三、变尺度法,BFGS变尺度法(Broyden、Fletcher、Goldfarb、Shanno)具有
7、较好的数值稳定性。BFGS法迭代公式与 DFP法一样，也是通过校正矩阵来求矩阵，只是求E(k)的公式不同。,计算实践发现，使用DFP法变尺度矩阵A(k)有时变为病态的奇异矩阵；BFGS法算法比较稳定，不易出现奇异矩阵，但A(k)偶而可能趋于无穷。,DFP变尺度法 程序框图,三、变尺度法,例 DFP变尺度法求解,解 (1)第一次迭代沿负梯度方向，解得, = 0.1,三、变尺度法,(2)第二次迭代用 DFP变尺度法,三、变尺度法,DFP变尺度法的迭代次数接近于牛顿法，但不需要计算函数的二阶导数矩阵及其逆矩阵。,四、共轭梯度法,1964年Fletcher和Reeves提出F-R法。1共轭方向的概念与
8、性质设A为一正定对称矩阵，若有一组非零向量满足,称这组向量关于矩阵A共轭。,四、共轭梯度法,对于一般函数，共轭方向性质：若A为n阶实对称正定矩阵，为A共轭的n个非零向量，则这一向量组线性无关。若S(i)是以A共轭的n个非零向量，则对于正定二次函数从任意初始点X(0)出发，依次沿这n个方向进行一维搜索，最多n次即可达到极小点。,四、共轭梯度法,2共轭方向形成共轭方向成方法平行搜索法和基向量组合法。(1)平行搜索法由共轭方向性质知，从不同的两点出发，沿同一方向进行两次一维搜索(进行两次平行搜索)，所得两个极小点的连线方向是与原方向共轭的另一方向。沿该方向作两次平行搜索，又可得到第三个共轭方向。继续
9、下去，得到一个包含n个共轭方向的方向组。,四、共轭梯度法,(2)基向量组合法取n个基向量(单位坐标向量)ei和另一个独立向量S(0)，令向量S(1)为S(0)和e(0)的线性组合，使,S(0)和S(1)共轭，必须,四、共轭梯度法,3共轭梯度方向从任意点X(k)出发，沿负梯度方向作一维搜索得,设与S(k) 共轭的下一个方向S(k+1)由S(k)和点X(k+1)的负梯度的线性组合构成，即,根据共轭条件有,四、共轭梯度法,只需利用相邻两点的梯度就可以构造一个共轭方向。以这种方式产生共轭方向并进行迭代运算的算法称共轭梯度法。对于正定二元二次函数，沿两个共轭梯度方向进行一维搜索，经过两次迭代即可达到极小
10、点。,四、共轭梯度法,对于一般正定二次函数，沿一组共轭梯度方向依次进行一维搜索，最多n次迭代就可达到极小点。对于一般函数，当n次迭代还未达到极小点时，应将第n个迭代点作为新的起始点，重新产生新的一组共轭方向，继续迭代，直到满足收敛精度为止。共轭梯度法具有超线性收敛速度。,共轭梯度法 程序框图,四、共轭梯度法,例 用共轭梯度法求解,解 第一次迭代沿负梯度方向进行搜索, 第二次迭代, = 0.1,四、共轭梯度法,用共轭梯度法经过两次迭代便求得该二元二次优化问题的极小点。迭代路线与DFP法完全相同。,五、鲍威尔法,无约束优化的求导法不能使用，如何确定搜索方向？由前述知，两次平行搜索可以产生一个共轭方
11、向。鲍威尔 (Powell)法就是利用平行搜索逐渐构造共轭方向和共轭方向组，并沿共轭方向进行一维搜索以逐渐逼近极小点的算法。由于共轭方向的产生不需要计算函数的导数属于求解无约束问题的模式法。鲍威尔法具有超线性收敛速度。,五、鲍威尔法,1基本迭代格式以 n个基向量e(i)构成初始方向组，由点X0(0)出发，沿n个坐标轴方向作n次一维搜索得点X0(n) (坐标轮换法)，以X0(n)和X0(0)的连线作为第一个新产生的方向,沿方向S(0)作一维搜索得点X0(n+1) ，以此点作为下一轮迭代的起始点，即,五、鲍威尔法,2.基本鲍威尔法鲍威尔法的基本迭代格式包括共轭方向和方向替换两个步骤。其中方向替换可
12、以采用不同的方式。如果每次产生新的共轭方向S(k)后，去掉原方向组pk中的第一个，而将新的方向S(k)加到该方向组的末尾构成一新的方向 pk+1。,Powell于1964年提出，称基本鲍威尔法。,五、鲍威尔法,在基本算法中，方向组的替换采用固定格式，运算简便。但是由此形成的方向组中，有可能出现几个方向线性相关或近似线性相关的现象。,解 沿坐标轴方向依次进行一维搜索，得最优步长因子和迭代点,五、鲍威尔法,首尾相连得搜索方向,=0，-2/3，-2/9T,下一轮迭代的搜索方向S1(2)、S2(2)、S3(2)= S(1)线性相关S3(2)= -2 S1(2)/3 -2 S2(2)/9,以后各次迭代均
13、在x1=1/2平面内进行降维搜索(极小点X*=0，0，0T) 。,五、鲍威尔法,3.修正鲍威尔法为了防止方向组中新加入的方向与原来的方向线性相关，在用新的方向作替换之前，首先解决是否替换和替换哪个方向,同时成立，表明方向Sk(n)与原方向组线性无关，可以用来进行替换。,五、鲍威尔法,两式满足，替换,替换公式,两式不成立，表明Sk(n)与原方向组中的某些方向线性相关，不能用来进行替换，仍以原方向组中的n个方向进行新的迭代。,五、鲍威尔法,鲍威尔法方向替换,POWELL法 程序框图,五、鲍威尔法,例 用POWELL法求解, = 0.1,解 (1)第一轮迭代 ，取,五、鲍威尔法,1)沿S1(0)进行
14、一维搜索,解得 = 2,2)沿S1(1)进行一维搜索,解得 = 0.5,五、鲍威尔法,3)收敛判断,继续计算,4)求最大下降量,5)构成新的方向,五、鲍威尔法,6)求反射点,7)方向S1(2)的有效性判断,判别式成立,五、鲍威尔法,8)沿S1(2)进行一维搜索,解得 = 1.4,9)进行方向替换，用S1(2)替换S1(0) (1=4大)，得新的方向组,五、鲍威尔法,(2) 第二轮迭代1)沿S2(0)进行一维搜索2)沿S2(1)进行一维搜索3)收敛判断4)求最大下降量5)构成新的共轭方向6)求反射点7)方向S2(2)的有效性判断8)沿S2(2)进行一维搜索,最优点,六、单纯形法,1.基本思想 2.迭代过程映射、扩大和压缩,
