优化算法（精品）

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,最优化方法,南开大学 马志斌,多维无约束最优化问题 ，其中 。这个问题的求解是指，在 中找一点 ，使得对于任意的 都有 成立。点 就是问题的全局最优点。,对于问题，为了求其最优解，按最优化算法的基本思想是从一个给定的初始点 出发，通过基本迭代公式 ，按照特定的算法产生一串点列 。如果点列收敛，则该点列的极限点为问题的最优解。,常用无约束最优化方法,1.,最速下降法,在基本迭代公式中，每次迭代搜索方向,取为目标函数f（X）的负梯度方向即,，而每次迭代的步长,取为最优步长，由此所确定的算法称为最速下降法。,最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有个严重缺点就是收敛速度慢。,2.,Newton法,如果目标函数f（X）在,上具有连续二阶偏导数，其Hesse矩阵G(X)正定并且可以表达为显式，就可以使用Newton法。,设最优化问题为minf（X,）,，其中f：,二阶可导，Hesse矩阵,f（X）正定。,将f（X）在,处展开成二阶泰勒公式，于是有,显然Q（X）是二次函数，特别由假设知Q（X）还是正定二次函数，所以Q（X）是凸函数且存在唯一全局极小点，为求此最小点，令,即可解得,，亦即,。称,为从点,出发的Newton方向。从初始点开始，每一轮从当前迭代点出发，沿Newton方向并取步长,的算法称为Newton法。,Newton法收敛速度非常快，具有二次收敛的优点，但它存在下面四个严重的缺点：,（1）,尽管每次迭代不会使目标函数f（X）上升，但仍不能保证f（X）下降。当Hesse矩阵非正,定,时，Newton法的搜索就会失败。,（2）,对初始点要求严格。一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的。,（3）,在进行某次迭代时可能求不出搜索方向。由于搜索方向为,，若目标函数在,点Hesse矩阵是奇异的，则,不存在，因而不能构成Newton方向，从而使迭代无法进行。,（4）,Newton方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存相当大。,3.,修正Newton法,为了克服Newton法的缺点，人们保留选取Newton方向作为搜索方向，摒弃其步长恒为1，而用一维搜索法确定其最优步长。由此产生的算法称为修正Newton法（或阻力Newton法）。,修正Newton法克服了Newton法的缺点。特别是，当迭代点接近最优解时，此法具有收敛速度快的优点，对初始点的选择要求不严。但是，修正Newton法仍需要计算的目标函数的Hesse矩阵和逆矩阵，所以计算量和存贮量均很大。另外，当目标函数的Hesse矩阵在某点出现奇异时，迭代将无法进行，因此修正Newton法仍有局限性。,4.,共轭方向法,设,是对称正定矩阵。对于非零向量,，若有,，则称,和,相互A共轭或A正交的。,通常，我们把从任意点,出发，依次沿某组共轭方向进行一维搜索的求解最优化问题的方法，叫做共轭方向法。,一般地，在n维空间中可以找出n个相互共轭的方向，对于n元正定二次函数，从任意初始点出发，顺次沿这n个共轭方向最多做n次直线搜索就可以求得目标函数的极小点。这就是共轭方向法的算法形成的基本思想。,对于n元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就能够求得极小点，那么这种说法称为具有二次终止性。共轭方向法是二次终止的。一般来说，具有二次终止性的算法，在用于一般函数时，收敛速度较快。,5.,共轭梯度法,如果在共轭方向法中初始的共轭向量,恰好取为初始点,处的负梯度,，而以下各共轭方向,由第k迭代点,处的负梯度,与已经得到的共轭向量,的线性组合来确定，即，,k=0，1，n-2，那么就构成了一种具体的共轭方向法。因为每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法。,利用目标函数的梯度信息，可知n个共轭方向,，由此得共轭梯度法。,实际上，可以把共轭梯度法看做是最速下降法的一种改进。当令时，就变为最速下降法。共轭梯度法由于不涉及矩阵，仅仅存储向量，因而存储量小，适合于维数较高的优化问题。另外，共轭梯度法不要求精确的直线搜索。但是，不精确的直线搜索可能导致迭代出来的向量不再共轭，从而降低方法的效能。克服的办法是：重设初始点，即把经过n+1次迭代得到的,作为初始点重新迭代。,6.,变尺度法,我们知道Newton法最突出的优点是收敛速度快，在这一点上其他算法无法比拟。因此，建议凡是Hesse矩阵比较容易求出的问题尽可能使用Newton法求解。然而Newton法还有一个严重缺陷，就是每次迭代都要计算目标函数的Hesse矩阵及其逆矩阵，当问题的维数n比较大时，计算量迅速增加，从而抵消了Newton法的优点。为此，人们开始寻找一种既可以保持Newton法收敛速度快的优点，又可以摆脱Hesse矩阵的计算，这就是变尺度法。,在Newton法中，基本迭代公式,，其中,，,。令,，于是有,，k=0，1，2，其中,是初始点，,和,分别是目标函数f（X）在点,的梯度和Hesse矩阵。为了消除这个迭代公式中的Hesse逆矩阵,，可用某种近似矩阵,来替换它，即构造一个矩阵序列,去逼近Hesse逆矩阵序列,。此时,。为使,确实与,近似并且有容易计算的特点，必须对,附加某些条件：,（1）,为保证迭代公式具有下降性质，要求,中的每一个矩阵都是对称正定的。,（2）,要求,之间的迭代公式具有简单形式。显然,是最简单的形式了，其中,称为校正矩阵。,（3）,必须满足拟Newton条件。所谓,拟,Newton条件为,7.,坐标轮换法,坐标轮换法的寻优思路是：先选定一个初始点,作为第一轮搜索的始点，依次沿n个坐标轴方向进行一维搜索，每次只在一个坐标轴方向进行一维搜索，其他的（n-1）个变量保持不变。在沿第一个坐标轴方向进行一维搜索得到目标函数值的最小点（或近似最小点）,后，再以此点作为始点转到第二个坐标轴方向进行一维搜索得到,，直到沿第n个坐标轴方向搜索结束得到,为一个循环。如果,不满足收敛准则，则以,作为初始点转入下一轮循环，直到经过k次循环，获得满足收敛准则的点,，即作为最优点,。,坐标轮换法的优点是算法简单，计算量小，其缺点是计算效率低，对高维问题尤为突出。因此，坐标轮换法通常用于维数较低的优化问题。,8.,单纯形法,单纯形法是利用对简单几何图形各顶点的目标函数值作相互比较，在连续改变几何图形的过程中，逐步以目标函数值较小的顶点取代目标函数值最大的顶点，从而进行求优的一种方法。,以求二元函数极小点为例，说明单纯形法形成的原理。,设二元函数,在,平面上取不在同一条直线上的三个点,，,和,，并以它们为顶点构成一单纯形三角形。算出各顶点的函数值,，,，,，比较其大小，现假定比较后有,，这说明,点最差，,点最好，,点次差。为了寻找极小点，一般来说应向最差点的反对称方向进行搜索。以,记为,的中点，在,的延长线上取点,，使,，,称为,关于,的反射点。,算出,的函数值,，可能出现以下几种情形：,（1）,这说明搜索方向正确，可进一步扩大效果，继续沿,向前搜索。这时取,，其中为扩张因子，一般取=1.22.0。如果,，说明扩张有利，就可以用,点代替,点构成新的单纯形,。如果,，说明扩张不利，舍弃,，仍以,代替,构成新的单纯形,。,（2）,这说明搜索方向正确，但无须扩张，以,代替,其构成新的单纯形,。,（3）,这表示,点走得太远，应缩回一些。若以表示压缩因子，则有,，常取0.5。以,代替,构成新的单纯形,。,（4）,这时应压缩更多一些，将新点压缩至,至,之间。令,。如果,，则以,代替,构成新的单纯形,，否则认为,方向上所有点的函数值,都大于,，不能沿此方向搜索。这时，可以以,为中心进行缩边。若使顶点,和,向,移近一半距离，得新的单纯形,，以此单纯形为基础再进行寻优。,单纯形法上机占用内存很少，对变量不多且精度要求不高的问题很方便，但当变量个数多于10个以上时，就显得不十分有效了。,常用约束最优化方法,一般的约束最优化问题，其数学模型为,，求解最优化问题，就是要在可行域,中找一个可行点,，使目标函数f（X）取得最小值。,1.,外点罚函数法,根据约束特点（等式或不等式）构造某种“罚函数”，然后把它加入到目标函数中去，使得对约束最优化问题的求解转化为对一系列无约束问题极小点或者无限地向可行域靠近，或者一直保持在可行集内移动，直到收敛于原来约束最优化问题极小点。,构造函数,，其中,。上式中，（X）称为惩罚函数，,，,，i=1，2，l。,是一个逐渐增大的参数，称为惩罚因子。,外点罚函数法的思想就是：当点,时，设法加大不可行点处的函数值，使不可行点不能成为问题在,中的最优解。,外点罚函数法是通过一系列惩罚因子,，k=0，1，2，求,的极小点来逼近原约束问题的最优点。这一系列的无约束极小点,将从约束可行域外部向约束边界运动。实际上，随着惩罚因子的增大，迫使惩罚项的值逐渐减小，从而使,的极小点,沿着某一运动轨迹逐渐接近等式约束面与起作用的不等式约束面上的最优点,。当,趋近于无穷大时，,的极小点就是原问题的最优点,。,2.,内点罚函数法,内点罚函数法的迭代过程均在可行域D内进行，它是通过在D内寻找一串点列X（,）来逼近最优解,。,首先在D的边界设置一道障碍，当从可行域D中的某点,出发进行迭代时，每当迭代点靠近D的边界时，便被此边界上的障碍阻挡碰回，换句话说，所谓阻挡碰回，就是当迭代点靠近D的边界时，离边界越近函数值增加越大，特别当迭代点到达边界上时，函数值变为无穷大。由此可以想象不可能在靠近D的边界上取得最优解，只能在远离D的边界内找到最优解。,构造函数,，其中，,0是一个逐渐减小的参数且趋近于0，称为障碍因子，,称为障碍函数。,内点罚函数法的优点在于每次迭代点都是可行点，当迭代到一定次数时，尽管可能没有达到约束最优点，但可以被接受为一个较好的近似最优点。,在内点罚函数法中，障碍函数的定义域是约束可行域。因此，在求,的最优解时，并不是求它在整个n维欧式空间,中的最优解，而是求,在约束可行域,上,的极小点。这是因为障碍函数,在D的边界上无定义，而在D的外部某些项为负，并且可取绝对值任意大的负值，从而使,趋近于,，所以,在全空间,内的极小点是不存在的。因此，在用无约束优化方法求,的最优解时，要防止越过约束边界而搜索到非可行域中去，这就要求在一位搜索时，要适当控制步长，保证搜索在可行域内进行。,3.,混合罚函数法,外点罚函数法的初始点可以任选，适用于求解具有等式约束与不等式约束的优化问题；而内点罚函数法要求初始点在可行域内，适用于求解不等式约束优化问题。为了综合外点罚函数法和内点罚函数法的优点，常将两种算法结合起来使用，这样便形成了混合罚函数法。,对于同时具有不等式约束和等式约束的优化问题，混合罚函数法采用的罚函数形式又分为内点和外点形式两种。下面只介绍内点形式的混合罚函数，即,。采用内点形式的混合罚函数时，初始点,应选为满足各个不等式约束条件的点，障碍因子,也应按内点罚函数法取为递减序列.在混合罚函数法,中，,的作用是限制搜索跑出不等式的约束确定的区域，相当于内点罚函数法，而,的作用是迫使搜索点向等式约束面靠近，相当于外点罚函数法。,4.,约束坐标轮换法,约束坐标轮换法是在无约束坐标轮换法的基础上，加入由约束函数构成的可行性限制，使每次迭代都必须在可行域内进行。它的基本思想是将一个n维的约束优化问题转化为依次沿n个坐标轴方向轮流进行迭代的一维搜索问题。,约束坐标轮换法通常利用加步搜索法来确定搜索步长。,约束坐标轮换法具有算法明了、迭代简单、便于使用者掌握运用等优点。但是，它的收敛速度慢，对于维数较高的优化问题很费机时。另外，这种方法在某些情况下还会出现“死点”的病态。通常的做法是输入多个初始点，并给出各种不同的初始步长进行多次运算，再从众多的输出解中进行比较而排除伪最优点。,5.,复合形法,复合形