无约束优化计算方法

第四章无约束问题的最优化方法4.1引言4.2单变量优化计算方法4.3多变量优化计算方法4.4多变量优化计算的梯度方法4.5多变量无约束优化设计方法小结4.1引言目的：求一组使目标函数达到min.内容：一维搜索：求最优步长因子α(k)多维（变量）优化：确定搜索方向坐标轮换法共轭方向法梯度法共轭梯度法牛顿法DFP变尺度法定义:在第K次迭代时，从已知点出发，沿给定方向求最优步长因子α)达到最小值的过程，称为一维搜索。方法：4.2.1搜索区间的确定：4.2单变量优化计算方法数值迭代法：直接法——应用序列消去原理：分数法、黄金分割法近似法——利用多项式函数逼近（曲线拟合）原理：4.2.1搜索区间的确定：4.2.1搜索区间的确定：单峰区间：在区间]内，函数只有一个峰值，则此区间为单峰区间。单峰区间内，一定存在一点α*，当任意一点α单峰区间内，函数可以有不可微点，也可以是不连续函数；，则α*是最优点，也即为最优步长因子α确定的搜索区间必定是一个含有最优点α*的单峰区间。4.2.1搜索区间的确定：给定初始点α为起始点,h为步长前进搜索可得第三个点α+2h,计算f(α则后退运算。（如图）4.2.1搜索区间的确定：4.2.1搜索区间的确定：若不是若是，转第步；若不是若是，转第步；若不是，转第步；若是，转第步；2222222122212122211112111211121112111212121112111112114.2.2黄金分割法(0.618法)4.2.2黄金分割法(0.618)下的部分内对于第(1)、(2)种情况，只要再取一个点α就可进行比较、消去。

但对于第三种情况，就要补充两个点。因此第三种合并为前两种:(1)4.2.2黄金分割法(0.618)的矩形建筑物，若边长能符合以下条件，则最美观：618序列消去法中，为提高效率，减少计算量和存储量，希望在每一次缩短搜索区间迭代过程中两计算点α，在区间中的位置相对于边界来说应是对称的，而且还要求丢去一段后保留点在新区间中的位置与丢去点再原区间中的位置相当。+λ-1=0λ=0.6180339887……0.618法计算程序框3.4二次插值法（抛物线法）的最优点近似的极小值拟合曲线即用抛物线逼近拟用一元二次多项式的一元函数，，代入，已知函数值，及中间任意一点目标函数值的点。三个已知确定二项式系数，需选3.4二次插值法（抛物线法）若满足判断是否满足精度：代替校核以轴的直线上，结论位于一条平行与4.2.3二次插值法（抛物线法）(1)确定初始插值点较，有四种情况（如图）,阴影线部分为丢去的，再对新区间三个新店代号一次作4.2.3二次插值法（抛物线法）算法框图4.2.3二次插值法（抛物线法）与黄金分割法相比，二次插值法充分利用函数值的信息；收敛快；调用函数次数少。4.方法评价:4.2搜索方向与步长：每次以一个变量坐标轴作为搜索方向，将n维的优化问题转化为一维搜索问题。

例，第k轮迭代的第变量坐标轴作一维搜索，求得极值点，若未收敛，则开始第k+1次迭代，直至收敛到最优点4.3.1坐标轮换法算法框图4.3.1坐标轮换法1、先规定初始步长，探测下降方向2、取初始步长的若干倍作为搜索步长t继续向前，直到目标函数值增大，取前一点为本次新点5、不满足精度时取t=(0.1~0.5)4.3.1坐标轮换法例4-1设目标函数求其无约束的最优点（x解：目标函数的等值线及加速步长的搜索路线如图所示。试验步长应正值。轴的移动方向：）取初始点053最优化值为求得最优化点为依次继续下去，最后可试验步长应取负值。方向搜索：4.3.1坐标轮换法4.最优步长法：最优步长法就是利用一维优化搜索方法(如0.618方法或二次插值方法)，求出每维搜索计算的值，如图所示。在这种情况下，每一次沿坐标方向进行搜索计算，都使目标函数值降至最小，如此反复迭代计算，直至达到收敛条4.3.1坐标轮换法方法评价：?方法简单，容易实现。?当维数增加时，效率明显下降。?收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。如图所示，二次就收敛到极值点；如图所示，多次迭代后逼近极值点；如图点为最优点。事实上发生错误。

4.3.2Poweel共轭方向的定义：若沿连接相邻两轮搜索末端的向量方向搜索，收敛速度加快。与同心椭圆族相切，两个切点的连线为共轭方向。目的：以共轭方向打破振荡，加速收敛。阵A共轭。则称这组向量是关于矩设A为正定实对称矩阵正交。若A为单位矩阵I的方向是共轭方向。4.3.2Poweel法（共轭方向法、方向加速法）：共轭方向的性质：二次收敛性。方向进行一维搜索，至出发，依次沿从任意初始点次函数个非零向量，则对于二矩阵共轭的是关于矩阵共轭。中每一个向量关于，也是与向量组，向量搜索，分别得到最优点方向进行一维出发，沿分别从两个初始点个非零向量，对于函数矩阵共轭的是关于个向量则可以构造出是线性无关的向量组，是线性无关的。个非零向量矩阵共轭的这组关于4.3.2Poweel作第三次搜索，求得f，沿此方向分别求得f作两次一维搜索，两个坐标轴方向S，依次沿选初始点x第一轮迭代：4.3.2Poweel迭代。若不满足，则作下一轮是否满足收敛条件：每轮迭代结束时，检验作第三次搜索，求得f，沿此方向一维搜索，分别求得f方向作两次4.3.2Poweel若是正定二次函数，n轮迭代后收敛于最优点维问题，步骤相同。搜索方向：第一轮迭代，沿初始方向组，搜索n+1次得极值点；第二轮迭代，沿方向组n-1个方向和共轭方向搜索n+1次得极值点轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向。

——去除的原则请自学。4.3.2Poweel4.3.2PoweelPoweel法计算框图例4-2用Powell法求函数4.3.2的最优点x。计算精度要求ε＝0.0001解：取初始点，第一轮迭代的搜索方向取两个坐标的单位向量出发，先从方向进行一维最优搜索，计算出最优步长由此得最优点1060替换成立，故应以检验判别条件下降量计算相邻二点函数值的方向上的反射点计算个方向计算第优点方向进行一维搜索得最同理，沿6015max{25一维搜索成立，故沿判别条件次一维搜索。总共进行，故停止运算。，误差已小于精确解4.3.3单纯形法单纯形法单纯形法是一种利用n维设计空间中的几何图形不断向好点移动迭代的一种算法。单纯形法是在n维设计空间内由n+1个顶点组成的几何形体，如在二维空间，单纯形为三角形，在三维空间内为四面体等。若各顶点间的距离相等，则称为正单纯形。三维空间四面体的收缩4.3.3单纯形法单纯形法迭代的基本要点是如何保证单纯形不断地向优点移动并使单纯形缩小直到趋于一点。这个过程是通过所谓反射， 收缩和扩展三种运算实现的。 (j=1，2，…，n+1)计算出它的目标函数值f(x 为单纯形顶点中目标函数值最大的顶点，如图(a)所示，则应以形心为镜面像其对面反射可能获得目标函数值小于它的点x 即称反射点，即其中 为反射系数。

这样x 点的距离为4.3.3 单纯形法 如果 为一个新的单纯形，如图中的三角形x 的目标函数，则这两点刚好是目标函数脊线为镜面的对称点，这时将使搜索过程陷 入死循环，对此可以利用目标函数值次最大值点x 4.3.3单纯形法 如果反射点x 为一个新的目标函数值最小点。此时沿x 方向可以进一步移动，有可能获得更小目标函数值的点。因此，扩展点x 其中为扩展系数，它与x 点的距离为如果f(x ，构成新单纯形，进入下次的运算过程。若f(x ，则表示扩展不成功，仍用x 4.3.3单纯形法 如果反射点x ，但它大于所有其余各点的值，则可用x 点的距离为如果 ，则用x 点，再进行下一次运算过程，反之，这个收缩过程失败，此时可将所有单纯形的 顶点向最好点x 收缩1/2，则用代替所有的顶点，然后再进行运算过程。 liji ji 4.3.3单纯形法 如图所示，在迭代计算中， 由于单纯形不断向最好点 移动和缩小，因此当单纯 形的n+1顶点的目标函数值 的均方差很小，即 就认为算法收敛，终止计 4.4多变量优化设计的梯度方法 4.4.1梯度法（最速下降法）： 搜索方向：目标函数负梯度向量方向代表最速 下降方向，因此选择负梯度向量方向作 为搜索方向，期望很快找到最优点。

梯度法的计算框图：4.4.1 梯度法 迭代过程简单，对初始点的选择，要求不高。 梯度方向目标函数值下降迅速只是个局部性质，从整体来看， 不一定是收敛最快的方向。 以二维二次函数为例，相邻两次的搜索方向是正交的，所以搜 索路径是曲折的锯齿形的；对于 高维的非线性函数直线搜索方法,无约束优化方法,约束优化方法，接近极值点 处，容易陷入稳定的锯齿形搜索 路径。 4.4.2 共轭方向：对梯度法作一个修正，将搜索方向 由负梯度方向旋转一个角度，使相邻 的两次搜索方向由正交变为共轭，成 为二次收敛。 4.4.2共轭梯度法 ，构造新的共轭方向计算β 是否判断 和计算精度选取初始点x 进行一维搜索得X(K+1) K=K+1 重置负梯度方向5.迭代框图 开始采用梯度方向，目标函数值下降快，后又为旋转梯度方向，具有二次收敛性，收敛快。 例4-3 设目标函数为 ，起始 1060 4.4.2共轭梯度法 解：第一次迭代的方向为： 所以 第二次迭代方向 107631 76116 60 4.4.2共轭梯度法 故经两次搜索即达极小点x 103054 所以用一维搜索解析法求 所以 4.4.3 牛顿法和修正牛顿法 点作台劳展开，取二次函数式Φ(x)作为近 似函数,以Φ(x) 的极小值点作为 minmin 由于在x点附近，函数 (x)和f(x)是近似的，所以 若是正定二次函数，一般迭代一次即可；若是严重非线性函数，则可能不收敛，或收敛到鞍点。

)为牛顿步长。 矩阵。为Hesse矩阵的逆 4.4.3牛顿法和修正牛顿法 1060 例4-4设目标函数为 解：先计算所以得 由此可见（与例4-3比较），对于任何正定二次函数，只需迭代一 次，即求出其极小点。可以证明，当目标函数满足一定条件，且初始 点选得较好时，牛顿法的收敛速度是非常快的。 4.4.3牛顿法和修正牛顿法 修正牛顿法：为最优步长因子。 算法框图：4.4.3 牛顿法和修正牛顿法 使用牛顿法时，若目标函数是严重非线性函数，则是否收敛将与初始点有很大关系；而使用修正牛顿法，能保证每次迭代目标 函数值下降，从而放宽了对初始点的要求。 方法评价：梯度法和牛顿法的比较： 1、迭代格式 2、梯度法只需计算一阶偏导数，计算工作量小，远离最优点时函数下降快，接近最优点时收敛速度慢。 3、牛顿法不仅需要计算一阶偏导数，还需计算二阶偏导数矩阵及其 逆矩阵，计算工作量大。但牛顿法具有二阶收敛性，接近最优点 时收敛速度很快。 梯度法和牛顿法的比较 4.4.4 变尺度法 变尺度的定义：每确定一次搜索方向，调整一次模（尺度）的大小，称为变尺度。 基本思想：发扬梯度法和牛顿法各自的优点，避免两者各自的缺点，将两者 结合起来，形成变尺度法。

的优点。 矩阵，而利用了牛顿法 及Hesse矩阵的逆 这样避免计算二阶导数 即为牛顿法。 中间的迭代即为梯度法， 首次迭代时，H为拟牛顿方向。 n的矩阵,一个n 为变尺度矩阵，是 4.4.4变尺度法 变尺度矩阵的构造：原则： 修正矩阵:矩阵。 为第k次迭代时的修正 求解过程见参考书（根据变尺度矩阵 递推公式、拟牛顿 条件，待定向量数 4.4.4变尺度法 算法框图：4.4.4 变尺度法 -1的计算，当目标函数的 一阶导数易求时，以一阶代替二阶导数的计算是有效的方法。 时，又采用二次收敛的共轭方向，总的收敛速度较快。 定性破坏，趋于奇异。4.5 多变量无约束优化设计方法小结 10x60 Poweel法、共轭梯度法、牛顿法、变尺度(DFP)法进 行计算，并进行比较。 4.5 无约束优化设计方法小结 Poweel法 共轭梯度法 牛顿法 变尺度 (DFP)法 迭代次数 搜索次数 搜索方向 收敛速度 存储量 适用维数 稳定性 零阶算法一阶算法 二阶算法 超线性 较慢 二次收敛 收敛最快 二次收敛 最大较大 n

（编辑：52站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!