无约束优化方法

2-4无约束优化方法

无约束优化问题的下降迭代算法具有统一的迭代格式，问题之一是选择搜索方向。根据搜索方向的不同构成方式，分：

1)导数法(解析法)

利用目标函数的一阶导数或二阶导数信息构造搜索方向的方法。

梯度法、牛顿法、共轭梯度法和变尺度法…

条件：

①目标函数求导容易；②目标函数一阶导数连续；③目标函数是设计变量的显函数。

2-4无约束优化方法

2)模式法(直接法)

通过比较几个已知点的函数值构造搜索方向的算法。

如坐标轮换法、共轭方向法、鲍威尔法等。构成搜索方向的信息仅仅是几个有限点上的函数值，难于得到较理想的搜索方向。一般迭代次数较多，收敛速度较慢。Rosenbrock函数x1x2一、梯度法

迭代方向由迭代点的负梯度构成——最速下降法。梯度法迭代公式一、梯度法根据极值的必要条件和复合函数求导公式，有相邻两迭代点的梯度正交最优步长因子k，由一维搜索确定一、梯度法

特点：

(1)算法简单，只计算目标函数一阶导数，占用内存少；(2)初始点任选；(3)初始迭代速度快；(4)

搜索路线正交，收敛速度越来越慢。梯度法程序框图一、梯度法例

用梯度法求解解：①第一次迭代

=0.1一、梯度法②

第二次迭代X(1)为初始点，进行迭代……二、牛顿法

梯度法除在最初几次迭代中函数值下降很快外，总的来说下降不快，且愈接近极值点下降愈慢。寻求使目标函数值下降更快的方法→牛顿法。

基本思路：——利用二次曲线逐点近似原目标函数，以二次曲线的极小点近似原目标函数的极小点并逐渐逼近该点。牛顿法分基本牛顿法和阻尼牛顿法。1.基本牛顿法函数f(X)在点X(k)处展开成泰勒二次近似式设X(k+1)是函数的极小点，有用基本牛顿法求解正定二次函数时，无论从哪个初始点出发，一次计算即可达到极小点。1．基本牛顿法

对于非线性正定函数，二阶泰勒展开式只是原函数的近似式，得到X(k+1)只是原函数的近似极小点。以此点作为下一次迭代的起始点X(k)，能够加快逼近的速度。对于非正定函数，为保证牛顿方向是函数值下降的方向，海赛矩阵必须正定。采用定步长，即使牛顿方向是函数值下降的方向，也不能保证函数值下降，即得到的点并不能始终保持函数的下降性→基本牛顿法有可能失效。2．阻尼牛顿法在迭代中引入步长因子和一维搜索。

阻尼牛顿法在每次迭代中沿牛顿方向作一维搜索，保证迭代点的严格下降性，适用于任何函数，且保证得到的迭代点更加靠近极小点，具有更加理想的收敛效果。牛顿法均指阻尼牛顿法。2．阻尼牛顿法阻尼牛顿法程序框图特点：

(1)具有二阶收敛性，收敛速度快；(2)在极值点附近有效；(3)计算复杂；(4)X(0)位置和函数性态影响计算结果。二、牛顿法例牛顿法求解解

(1)基本牛顿法

=0.1二、牛顿法(2)阻尼牛顿法基本牛顿法计算得二、牛顿法解得=1

三、变尺度法

变尺度法是拟牛顿法。克服牛顿法的缺点，继承其收敛快的优点，具有超线性收敛速度。1959年，Davidon提出变尺度法，Fletcher和Powell改进——DFP法。

优化算法一般迭代公式

三、变尺度法梯度法，搜索方向为负梯度方向牛顿法，搜索方向为牛顿方向统一形式三、变尺度法——梯度法

——牛顿法

在迭代开始时，按负梯度方向搜索；尔后每次迭代时不断调整A(k)，修正搜索方向，使A(k)逐步逼近目标函数的海赛矩阵之逆矩阵；当迭代点临近极小点时，构成的方向就近似为牛顿方向，直指极小点。整个迭代过程收敛速度很快。矩阵A(k)代替海赛矩阵之逆矩阵，且迭代过程中不断改变→变尺度矩阵。三、变尺度法关键：构造变尺度矩阵1.变尺度矩阵构造原则1)算法具有下降性

——为了使方向S(k)=-A(k)g(k)为目标函数值的下降方向，构造的变尺度矩阵A(k)应为正定对称矩阵。

若目标函数f(X)的值沿S(k)下降，则S(k)与X(k)点的负梯度方向之间的夹角应为锐角，即只要A(k)正定，S(k)=-A(k)g(k)必为目标函数值的下降方向。三、变尺度法2）计算方便性——构造的变尺度矩阵A(k)应便于计算，在迭代过程中应逐渐地逼近海赛矩阵之逆矩阵。取单位矩阵I为初始矩阵A(0)E(k)——校正矩阵。2.变尺度矩阵构造Davidon提出，Fletcher和Powell修正，校正矩阵E(k)

三、变尺度法DFP变尺度法在函数f(X)梯度易求的情况下，非常有效。对于多维问题(n>100)，收敛快，效果佳→无约束极值问题优化的最好方法之一。计算程序较复杂，需要较大的存储量，特别是在有舍入误差时，存在数值稳定性不够理想的情况。

三、变尺度法

BFGS变尺度法(Broyden、Fletcher、Goldfarb、Shanno)具有较好的数值稳定性。BFGS法迭代公式与DFP法一样，也是通过校正矩阵来求矩阵，只是求E(k)的公式不同。计算实践发现，使用DFP法变尺度矩阵A(k)有时变为病态的奇异矩阵；BFGS法算法比较稳定，不易出现奇异矩阵，但A(k)偶而可能趋于无穷。使用BFGS法，否则用DFP法。Fletcher增加开关语句(开关算法)DFP变尺度法程序框图三、变尺度法例DFP变尺度法求解解(1)第一次迭代沿负梯度方向，解得=0.1三、变尺度法(2)第二次迭代用DFP变尺度法

三、变尺度法DFP变尺度法的迭代次数接近于牛顿法，但不需要计算函数的二阶导数矩阵及其逆矩阵。四、共轭梯度法1964年Fletcher和Reeves提出→F-R法。

1．共轭方向的概念与性质设A为一正定对称矩阵，若有一组非零向量满足称这组向量关于矩阵A共轭。当A为单位矩阵时，有称向量Si相互正交。共轭是正交推广，正交是共轭特例。四、共轭梯度法③从任意两个点X1(0)和X2(0)出发，分别沿同一方向S(0)进行一维搜索，得到两个一维极小点X1(1)和X2(1)，连接此两点构成的向量与原方向关于该函数的二阶导数矩阵相共轭。对于一般函数，共轭方向性质：①若A为n阶实对称正定矩阵，S(i)为A共轭的n个非零向量，则这一向量组线性无关。②若S(i)是以A共轭的n个非零向量，则对于正定二次函数从任意初始点X(0)出发，依次沿这n个方向进行一维搜索，最多n次即可达到极小点。四、共轭梯度法2．共轭方向形成共轭方向形成方法——平行搜索法和基向量组合法。

(1)平行搜索法由共轭方向性质③知，从不同的两点出发，沿同一方向进行两次一维搜索(进行两次平行搜索)，所得两个极小点的连线方向是与原方向共轭的另一方向。沿该方向作两次平行搜索，又可得到第三个共轭方向。继续下去，得到一个包含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)的负梯度的线性组合构成，即根据共轭条件有四、共轭梯度法只需利用相邻两点的梯度就可以构造一个共轭方向。以这种方式产生共轭方向并进行迭代运算的算法称共轭梯度法。对于正定二元二次函数，沿两个共轭梯度方向进行一维搜索，经过两次迭代即可达到极小点。四、共轭梯度法对于一般正定二次函数，沿一组共轭梯度方向依次进行一维搜索，最多n次迭代就可达到极小点。对于一般函数，当n次迭代还未达到极小点时，应将第n个迭代点作为新的起始点，重新产生新的一组共轭方向，继续迭代，直到满足收敛精度为止。共轭梯度法具有超线性收敛速度。

共轭梯度法程序框图四、共轭梯度法例用共轭梯度法求解解①第一次迭代沿负梯度方向进行搜索②第二次迭代=0.1四、共轭梯度法

用共轭梯度法经过两次迭代便求得该二元二次优化问题的极小点。迭代路线与DFP法完全相同。

五、坐标轮换法

无约束优化的求导法不能使用，如何确定搜索方向？1、坐标轮换法的基本原理坐标轮换法又称变量轮换法，其基本原理是将一个多维无约束优化问题转化为一系列一维优化问题求解，即依次沿着坐标轴的方向进行一维搜索，求得极小点。以二维为例说明。再对n维作进一步解释。2、特点简单易行，但效率低下，收敛速度很慢。六、鲍威尔法

由前述知，两次平行搜索可以产生一个共轭方向。鲍威尔(Powell)法就是利用平行搜索逐渐构造共轭方向和共轭方向组，并沿共轭方向进行一维搜索以逐渐逼近极小点的算法。由于共轭方向的产生不需要计算函数的导数→属于求解无约束问题的模式法。鲍威尔法具有超线性收敛速度。六、鲍威尔法1．基本迭代格式以n个基向量e(i)构成初始方向组，由点X0(0)出发，沿n个坐标轴方向作n次一维搜索得点X0(n)(坐标轮换法)，以X0(n)和X0(0)的连线作为第一个新产生的方向沿方向S(0)作一维搜索得点X0(n+1)，以此点作为下一轮迭代的起始点，即以S(0)代换原方向组中的某基向量，构成新的方向组。从点X1(0)出发，分别沿n个方向作n次一维搜索，得点X1(n)。令则S(1)与S(0)相共轭。六、鲍威尔法2.基本鲍威尔法鲍威尔法的基本迭代格式包括共轭方向和方向替换两个步骤。其中方向替换可以采用不同的方式。如果每次产生新的共轭方向S(k)后，去掉原方向组pk中的第一个，而将新的方向S(k)加到该方向组的末尾构成一新的方向pk+1。Powell于1964年提出，称基本鲍威尔法。六、鲍威尔法

在基本算法中，方向组的替换采用固定格式，运算简便。但是由此形成的方向组中，有可能出现几个方向线性相关或近似线性相关的现象。

例从X(0)=[1/2，1，1/2]T出发，用基本鲍威尔法求函数极小点解沿坐标轴方向依次进行一维搜索，得最优步长因子和迭代点六、鲍威尔法i

SiαiXi1[1，0，0]T0[1/2，1，1/2]T2[0，1，0]T-2/3[1/2，1/3，1/2]T3[0，0，1]T-2/9[1/2，1/3，5/18]T首尾相连得搜索方向=[0，-2/3，-2/9]T下一轮迭代的搜索方向S1(2)、S2(2)、S3(2)=S(1)线性相关S3(2)=-2S1(2)/3-2S2(2)/9以后各次迭代均在x1=1/2平面内进行降维搜索(极小点X*=[0，0，0]T)。六、鲍威尔法3.修正鲍威尔法为了防止方向组中新加入的方向与原来的方向线性相关，在用新的方向作替换之前，首先解决是否替换和替换哪个方向同时成立，表明方向Sk(n)与原方向组线性无关，可以用来进行替换。六、鲍威尔法两式满足，替换替换公式