[工学]4无约束优化方法

《[工学]4无约束优化方法》由会员分享，可在线阅读，更多相关《[工学]4无约束优化方法（140页珍藏版）》请在金锄头文库上搜索。

1、无约束优化方法,可以利用极值定义，将上式变成求以下方程 这是个n个变量n个方程的方程组， 并且一般是非线性的。 与其使用数值计算方法求解非线性 方程组，不如用数值计算方法直接 求解无约束优化问题,无约束优化问题是：求n维设计变量,使目标函数 ，而对 没有任何限制条件。,数值求优的方法主要是爬山法 爬山法是利用已有的信息，通过计算点的一步一步 的直接移动，逐步逼近并最后达到最优点。 即给定初始点和搜索方向，沿该方向寻找最优点。,每一步计算都应该达到两个目的： （）获得目标函数的改进值 （）为下一步计算给出有用的信息,爬山法的计算过程分两步： （）选择爬山方向即搜索方向 （）在确定的方向上选择适当

2、的步长进行探索 搜索方向和步长的生成及确定的方法不同，就派生出不同的n维无约束优化问题的算法,无约束极小算法的粗框图,随机方向法,1、方向 （1）随机选择一个方向 （2）随机选择一个下降方向 （3）随机选择n个下降方向，选下降最多的方向 2、步长 （1）随机选择一个步长 （2）随机选择一个下降步长 （3）加速步长法：先选择一个下降步长h， 再以h的a(a1)倍向前搜索，直到不下降为止 3、找不到方向：以h的b(b1)倍缩小步长，重找方向,1)选择一个初始点x，令x=x,步长a= a ; 2) 产生k个n维随机单位向量，结合x、a计算出k个随机点xj (jl，2，k)； 3)在k个随机点中，找出

3、函数值最小随机点xL ，产生可行搜索方向； 找不到则a=0.67a，返回(2) 4)从初始点x出发，沿可行搜索方向d以步长1.33a进行迭代计算，直至探索到一个目标函数值不再下降的新点x，返回(2) 5) 收敛条件,随机方向法流程示例,坐标轮换法,该方法是每次搜索只允许一个变量变化，其余变量保持不变。他把多变量问题转换成单变量的优化问题，在搜索过程中可以不需要目标函数的导数。,迭代步骤： （1）第1次迭代时，先固定 x2= x2(0) 变量值不动，由 初始点X(0) 沿 x1 轴向进行一维探索，得到该轴方向上的 最优点 X(0,1)=x1(1), x2(0) ； （2）固定 x1=x1(1)

4、变量值不动，由初始点 X(0,1) 沿 x2 轴向进行一维探索，得到该轴方向上的最优点 X(1)=x1(1), x2(1) （3）将 X (1) 作为第1次迭代的改进点，之后，完全依照第1 次的步骤进行第2、3、k次的坐标轮换迭代，直到满足精度要求后停止迭代。,坐标轮换法的基本原理,x1,x2,X*,X(0,1),X(1),X(2),X(3),X(0),0,x1(0),x1(1),x1(2),x1(3),x1*,x2(0),x2(1),x2(2),x2(3),x2*,一维搜索步长选择 （1）随机选择一个下降步长 （2）进退法加速步长法： 进退法选择一个下降步长h， 再以h的a(a1)倍向前搜索

5、，直到不下降为止 （3）,否则 ，进行下一轮搜索，一直到满足精度要求为止。,对于n个变量的函数，若在第k轮沿第i个坐标方向 进行搜索，其迭代公式为,其中搜索方向取坐标方向，即,若 ，则 ，,不同性质目标函数坐标轮换法的求优效能,收敛速度很快,收敛速度很慢,求优失效,最速下降法,所以，某点x处下降率最大的方向是其负梯度方向，称为最速下降方向。,前面已经讨论过：,最速下降法,最速下降法即是以负梯度方向作为搜索方向，又称梯度法。,所以，相邻两个迭代点上的函数梯度方向互相垂直,根据一元函数极值的必要条件和复合函数求导公式，得：,相邻两个迭代点上的函数梯度方向互相垂直，因此相邻两个搜索方向互相垂直。即在

6、迭代点向函数极小点靠近的过程中，走的是之字形的曲折路线。 可以看出，在远离极小点的地方，每次迭代可以使函数值有较多的下降，而在接近极小点的地方，由于锯齿现象使每次迭代行进的距离缩短，因而收敛速度减慢。 从局部上看，在一点附近函数的下降是快的，但从整体上看则走了许多弯路。,求目标函数 的极小点。,解 取初始值,则初始点处函数值及梯度分别为,沿负梯度方向进行一维搜索，有,为一维搜索最佳步长，应满足极值必要条件,从而算出一维搜索最佳步长,及第一次迭代设计点位置和函数值,经过10次迭代，得到最优值,若将上例的目标函数,引入变换,其等值线就由一族椭圆变成一族同心圆，,仍从 即 开始寻优,此时有,沿负梯度

7、 方向进行一维搜索，有,为一维搜索最佳步长，可由极值条件算得,得到第一次迭代的结果就是最优解,最速下降法的收敛速度与变量的尺度关系很大，下面是最速下降收敛速度的估计式,式中 的海赛矩阵最大特征值； 其最小特征值。,对于等值线为椭圆的二次型函数 ，其海赛矩阵,两个特征值分别为 。因此,可见等值线为椭圆的长短轴相差越大，收敛就越慢。,两个特征值相等 ，因此,代入（4-4），有,得,即经过一次迭代便可到达极值点。,梯度法的特点,（1）理论明确，程序简单，对初始点要求不严格。 （2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。 （3）梯度法相邻两次搜索方向的正交

8、性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。 （4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。 （5）应用最速下降法可以使头几次迭代的收敛速度很快，所以它可与其他方法配合使用,编程示例：,目标函数：min f(x0,d,a) 求函数值(标量) ：f(题号,初始点向量 x0,方向向量d,步长 a) 求方向导数值(标量)：f1(题号,初始点向量 x0,方向向量d,步长 a) 求梯度值(向量)：g(题号, x) 或 g(题号,初始点向量 x0,方向向量d,步长 a) 一维搜索函数：

9、 fmin(一维搜索方法,题号,初始点向量 x0,方向向量d,初始步长 a0) 多变量搜索函数： fmins(多变量方法, 一维搜索方法,题号,初始点向量 x0 ,初始步长 a0),function y=f(no,x0,d,a) x=x0+a*d; if no=1 y=x(1)*x(1)*x(1)*x(1)+2*x(2)*x(2)*x(2)*x(2); end function y=f(no,x0,d,a) x=x0+a*d; if no=1 y=4*x(1)*x(1)*x(1)*d(1)+8*x(2)*x(2)*x(2)*d(2); end function y=g(no,x) if no=

10、1 y=4*x(1)*x(1)*x(1);8*x(2)*x(2)*x(2); end,function x,y=fmin(m1,no,x0,d,a0,e) a1,a3,a2=range(no,x0,d,a0); if m1=1 x,y=gold(no,x0,d,a1,a3,e); end function xx,yy=gold(no,x0,d,a,b,e) r=0.618; a1=b-0.618*(b-a); y1=f(no,x0,d,a1); a2=a+0.618*(b-a); y2=f(no,x0,d,a2); aa=(a+b)/2; xx=x0+d*aa; yy=f(no,x0,d,aa

11、);,function x,y=tidu(n1,no,x0,a0,e) x2=x0;x1=x2-e; while norm(x2-x1)=e x1=x2; d=-g(no,x1); x2=fmin(n1,no,x1,d,a0,e); end x=x2;y=f(no,x2,1,0);,不精确的一维搜索,一维搜索过程是最优化方法的最基本组成部分，精确的一维搜索方法通常需要花费很大的工作量，特别是当迭代点远离问题的解时，精确的求解一个一维子问题通常不是十分有效率的。 另外，在实际上，很多优化方法，例如拟牛顿法，其收敛速度并不依赖于精确一维搜索过程。 因此，只要保证目标函数值在每一步都有满意的下降，使

12、用不是非常精确的一维搜索，就可以大大节省工作量。,单纯形法,在实际工程的最优化问题中，目标函数的导数往往很难求出或根本无法求出。 单纯形法只需要计算目标函数值，不需计算导数，因此计算比较简单，其几何概念也比较清晰，属于直接法一类的无约束最优化方法。 直接法的一个优点即是适用于不知道目标函数的具体数学表达式的情况。,单纯形法,单纯形：n维空间中由n+1个线性独立的点构成的简单图形或凸多面体。 可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。 单纯形法： (1) 根据问题的维数n，选取n+1个顶点构成的单纯形 (2) 求出这些顶点处的目标函数值并加以比较

13、，确定有最大值的点及函数下降方向 (3) 再设法找到一个新的比较好的点替换那个有最大值的点，从而构成新的单纯形。 (4) 随着迭代的进行，单纯形将向着最优点收缩。 新单纯形的构造方法有反射、扩张、压缩、收缩等,（1）反射 设除了最劣点X1以外的基余顶点的中心为X4， 作X1关于点X4的对称点X5，称X5为X1的反射点。 求反射点的过程称之为反射。,设当前的单纯形的顶点为X1，X2，X3，且有,（2）扩张在得到反射点X5之后， 如果X5优于原单纯形的最劣点（即有 ）， 表明反射方向（X5X1）是有利方向，反射成功。 若进一步有 ，可沿反射方向前进适当的距离到点X6。 X6称之为扩张点，求扩张点的

14、过程称之为扩张。 扩张之后，若扩张点X6优于反射点X5，则扩张成功，以X6取代X1，得新单纯形X6,X2,X3； 否则，扩张失败，舍弃扩张点，以反射X5点取代X1，得新单纯形X5,X2,X3。,如果出现 。表示反射完全失败，应退回到介于X4与X1之间的某个点X8。,（3）压缩在得到反射点X5之后，如果有,表示反射部分成功，方向（X5X1）虽然是有利方向，但X5前进过远，应压缩到介于X4与X5之间的某个点X7。,上述两种从反射点向X1方向后退的过程都称之为压缩。如果压缩点优于原来的最劣点X1，称压缩成功，并以压缩点取代原最劣点，构成新单纯形X7,X2,X3或X8,X2,X3；否则，称之为压缩失败

15、，舍弃压缩点。,（4）收缩若压缩失败，则应缩短当前单纯形的边长： 令最优点X3不动，而其余顶点向X3方向收缩，使边长缩短（通常缩短一半），以产生新单纯形。 如下图所示，点X1收缩到点X9，点X2收缩到点X10，得新单纯形X9,X10,X3，这一过程称之为压缩。,牛顿型方法,一维情况下牛顿迭代公式,利用目标函数,在点,处的二阶Taylor,展开式去近似目标函数，,用二次函数的极小点,去逼近目标函数的极小点,基本思想:,多维情况下牛顿迭代公式,根据极值的必要条件，得：,对正定二次函数来说，上述的泰勒展开式不是近似的，而是精确的。海赛矩阵是一个常数矩阵，其中各元素均为常数。 因此，用牛顿法求解正定二次函数时，无论从哪个初始点出发，计算所得牛顿方向直指极小点，而且步长等于1 二次收敛的概念：如果某一种迭代方法能够使二次型函数在有限次迭代内达到极小点，则称此迭代方法是二次收敛的。,求目标函数 的极小点。,解 取初始值,则：,代入牛顿法迭代方法，得：,对于一般非线性函数，点Xk+1只是原函数的一个近似极小点。故将此点作为下一个迭代Xk+1。 另外，从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜索的概念。 因此对于非正定函数，如果采用上述牛顿法迭代公式，有时会使函数值上升，为了解决