34结构优化算法基础之无约束优化方法

1、3.4 无约束优化方法3.4.1 概述大多数实际问题是约束优化问题。约束优化问题的求解转化为一系列的无约束优化问题实现。因此，无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。*0f x无约束优化问题的极值条件解析法数值法数学模型复杂时不便求解可以处理复杂函数及没有数学表达式的优化设计问题1kkkkxxa d搜索方向问题是无约束优化方法的关键。各种无约束优化方法的区别：确定搜索方向的方法不同。无约束优化方法分类利用目标函数的一阶或二阶导数利用目标函数值（最速下降法、共轭梯度法、牛顿法）（坐标轮换法、鲍威尔等）3.4.2 最速下降法优化设计追求目标函数值最小，若搜索方向取该点

2、的负梯度方向，使函数值在该点附近的范围内下降最快。按此规律不断走步，形成以下迭代算法：1kkkkxxaf x以负梯度方向为搜索方向，所以称最速下降法最速下降法或梯度法梯度法。搜索方向确定为负梯度方向，还需确定步长因子ka即求一维搜索的最佳步长，既有 1minminkkkkkkkf xfxaf xfxaf x 0tkkkkfxaf xf x 10tkkf xf x10tkkdd由此可知，在最速下降法中，相邻两个迭代点上的相邻两个迭代点上的函数梯度相互垂直函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。例4-1 求目标函数 221225f xxx的极小点。3.4.3 牛顿

3、型方法前面讨论了一维搜索的牛顿方法。得出一维情况下的牛顿迭代公式1kkkkfxxxfx对于多元函数，在kx泰勒展开，得 f xx 212ttkkkkkkf xf xxxxxf xxx设1kx为函数的极小点，根据极值的必要条件10kx210kkkkf xf xxx112kkkkxxf xf x 这是多元函数求极值的牛顿法迭代公式。例4-2 用牛顿法求 221225f xxx的极小值。对牛顿法进行改进，提出“阻尼牛顿法”112kkkkkxxf xf x1minkkkkkkf xfxa dfxad3.4.4 共轭方向及共轭方向法为了克服最速下降法的锯齿现象，提高收敛速度，发展了一类共轭方向法。搜索方

4、向是共轭方向。一、共轭方向的概念 12ttf xx gxb xc共轭方向的概念是在研究二次函数时引出的。首先考虑二维情况如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象。为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，如果选定这样的搜索方向，对于二元二次函数只需进行两次直线搜索就可以求到极小点。1000 xxa d*111xxa d 1100txff xdd 1d应满足什么条件？对于二次函数 在 处取得极小点的必要条件 f x*x*0f xgxb*111111f xg xa dbgxbagd 1110f xagd 等式两边同乘 得0td010tdgd 0d1d是对g的共轭方向

5、的共轭方向。三、共轭方向法1、选定初始点 ，下降方向 和收敛精度，k=0。0 x0d2、沿 方向进行一维搜索，得kd1kkkkxxa d3、判断 是否满足，若满足则打印1kf x1kx否则转4。4、提供新的共轭方向 ，使 1kd10tjkdgd5、置 ，转2。1kk3.4.5 共轭梯度法共轭梯度法是共轭方向法的一种，共轭向量由迭代点的负梯度构造出来，所以称共轭梯度法。 12ttf xx gxb xc1kkkkxxa d1kkkkxxa dkkggxb从点 出发，沿g某一共轭方向 作一维搜索，到达kxkd1kx11kkggxb而在点 、 处的梯度分别为：kx1kx11kkkkkkggg xxa

6、gd0tjkdgd 10tjkkdg gg得出共轭方向与梯度之间的关系。此式表明沿方向kd进行一维搜索，其终点 与始点 的梯度值差1kxkx1kkgg与 的共轭方向 正交。kdjd若dj和dk对g是共轭的，则 图4-9 共轭梯度法的几何说明3.4.6 变尺度法1kkkkxxhf x变尺度法的基本思想：前面讨论的梯度法和牛顿法，它们的迭代公式可以看作下列公式的特例。变尺度法是对牛顿法的修正，它不是计算二阶导数的矩阵和它的逆矩阵，而是设法构造一个对称正定矩阵h来代替hessian矩阵的逆矩阵。并在迭代过程中，使其逐渐逼近h-1 。由于对称矩阵h在迭代过程中是不断修正改变的，它对于一般尺度的梯度起到

7、改变尺度的作用，因此h又称变尺度矩阵。一、尺度矩阵的概念变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降低到最低限度。对于一般二次函数 12ttf xx gxb xc如果进行尺度变换xqx则在新的坐标系中，函数的二次项变为1122tttx gxx q gqx选择这样变换的目的：降低二次项的偏心程度。若矩阵g是正定的，则总存在矩阵q使tq gqi使得函数偏心度变为零。用q-1 右乘等式两边，得1tq gq再用q左乘等式两边，得tqq gi所以1tqqg说明二次函数矩阵g的逆矩阵，可以通过尺度变换矩阵q求得。这样，牛顿法迭代过程中的牛顿方向可写成：1kktkdgf xqqf

8、x 1kkktkxxqqf x三、变尺度法的一般步骤3.4.7 坐标轮换法坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量的优化问题。因此又称变量轮换法变量轮换法。 其基本原理是将一个多维的无约束最优化问题转化为一系列较低维的最优化问题来求解，简单地说，就是先将(n-1)个变量固定不动，只对第一个变量进行一维搜索得到最优点x1（1）。然后，又保持(n-1)个变量不变，再对第二个变量进行一维搜索到x2（1）等等。 坐标轮换法原理图（坐标轮换法原理图（动画演示动画演示）)0(2)0(1xx)0(2)1(1xx)1(

9、2)1(1xx)2(2)2(1xx2. 搜索方向与步长的确定（1）搜索方向的确定）搜索方向的确定对于第k轮第i次的计算1kkkkiiiixxa d第k轮第i次的迭代方向，它轮流取n维坐标的单位向量。0.1.0kiide 3.搜索步长的确定关于关于 值通常有以下几种取法值通常有以下几种取法（1）加速步长法）加速步长法（2）最优步长法）最优步长法 最优步长法就是利用一维最优搜索方法来完成最优步长法就是利用一维最优搜索方法来完成每一次迭代，即每一次迭代，即此时可以采用此时可以采用0.618方法或二次插值方法来计算方法或二次插值方法来计算 的值。的值。)( ki加速步长法的搜索路线图图414 最优步长法的搜索路线最优步长法的搜索路线4 . 坐标轮换法存在的问题图图415 坐标轮换法在各种不同情况下的效能坐标轮换法在各种不同情况下的效能（a）搜索有效；（）搜索有效；（b）搜索低效；（）搜索低效；（c）搜索无效）搜索无效3.4.8 powell法（方向加速法） powell法是利用共轭方向可以加速收敛的性质所法是利用共轭