工程优化设计中的数学方法硕士研究生西安电子.pptVIP

3.1搜索算法结构,一、下降算法模型考虑（fs）常用一种线性搜索的方式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。迭代计算：其中为第次迭代的搜索方向，为沿搜索的最佳步长因子（通常也称作最佳步长）。,第三章常用的一维搜索方法,可行方向：设S，dRn,d0,若存在，使，称d为点的可行方向。同时满足上述两个性质的方向称下降可行方向。,下降方向：设S，dRn,d0,若存在，使，称d为在点的下降方向。,模型算法,线性搜索求，新点使x(k+1)S,yes,no,5,3,1,二、收敛性概念：考虑（fs）设迭代算法产生点列x(k)S.1.理想的收敛性：设x*S是g.opt(全局最优解).当x*x(k)或x(k)x*，k，满足时，称算法收敛到最优解x*。,由于非线性规划问题的复杂性，实用中建立下列收敛性概念：2.实用收敛性：定义解集S*=x|x具有某种性质例：S*=x|x-g.optS*=x|x-l.optS*=x|f(x)=0S*=x|f(x)(为给定的实数，称为阈值),2.实用收敛性（续）收敛性：设解集S*，x(k)为算法产生的点列。下列情况之一成立时，称算法收敛：1x(k)S*;2x(k)S*，k，x(k)的任意极限点S*。全局收敛：对任意初始点x(1),算法均收敛。局部收敛：当x(1)充分接近解x*时，算法收敛。,有限步终止,三、收敛速度设算法产生点列x(k)，收敛到解x*，且x(k)x*，k，关于算法的收敛速度，有1.线性收敛：当k充分大时成立。2.超线性收敛：3.二阶收敛：0，是使当k充分大时有,三、收敛速度（续）定理：设算法点列x(k)超线性收敛于x*,且x(k)x*，k，那么证明：只需注意|x(k+1)x*|-|x(k)x*|x(k+1)x(k)|x(k+1)x*|+|x(k)x*|，除以|x(k)x*|并令k，利用超线性收敛定义可得结果。,该结论导出算法的停止条件可用：,四、二次终结性一个算法用于解正定二次函数的无约束极小时，有限步迭代可达最优解，则称该算法具有二次终结性。,问题描述：,已知,并且求出了,处的可行下降方向,从,出发，,沿方向,求如下目标函数的最优解，,或者选取,使得：,常用的一维搜索算法,设其最优解为,（叫精确步长因子），,所以线性搜索是求解一元函数,的最优化问,题（也叫一维最优化问题或,一般地，一维优化问题可描述为：,于是得到一个新点：,一维搜索）。,或解,一般地，线性搜索算法分成两个阶段：,第一阶段确定包含理想的步长因子,（或问题最优解）的搜索区间；,第二阶段采用某种分割技术或插值,方法缩小这个区间。,搜索区间的确定黄金分割法(0.618法)二次插值法Newton法,要点：单峰函数的消去性质、进退算法基本思想、黄金分割法基本思想、重新开始、二次插值法要求、极小化框架、Newton法基本思想、方法比较。,我们主要介绍如下一些搜索方法：,学习的重要性：,1、工程实践中有时需要直接使用；,2、多变量最优化的基础，迭代中经常要用到。,方法分类：,1、直接法：迭代过程中只需要计算函数值；,2、微分法：迭代过程中还需要计算目标函数的导数；,3.2搜索区间的确定,常用的一维直接法有消去法和近似法两类。它们都是从某个初始搜索区间出发，利用单峰函数的消去性质，逐步缩小搜索区间，直到满足精度要求为止。,3.2.1单峰函数,连续单峰函数,不连续单峰函数,离散单峰函数,非单峰函数,定义：如果函数f(x)在区间a,b上只有一个极值点,则称f(x)为a,b上的单峰函数。,单峰函数具有一个重要的消去性质,定理：设f(x)是区间a,b上的一个单峰函数，x*a,b是其极小点，x1和x2是a,b上的任意两点，且ax1x2b，那么比较f(x1)与f(x2)的值后，可得出如下结论：,(I)消去a,x1,(II)消去x2,b,(II)若f(x1)f(x2),x*a,x2,在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，若再计算另一点的函数值，比较后就可进一步缩小搜索区间.,（I）若f(x1)f(x2)，x*x1,b,3.2.2进退算法(或称成功-失败法),如何确定包含极小点在内的初始区间?,（一）基本思想：,由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升。,从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。由两边高，中间低的三点，可确定极小点所在的初始区间。,（二）算法,1、选定初始点a和步长h;,2、计算并比较f(a)和f(a+h)；有前进(1)和后退(2)两种情况：,则步长加倍，计算f(a+3h)。若f(a+h)f(a+3h)，令a1=a,a2=a+3h,停止运算；否则将步长加倍，并重复上述运算。,则将步长改为h。计算f(ah),若f(ah)f(a)，令a1=ah,a2=a+h,停止运算；否则将步长加倍，继续后退。,仅仅找区间！若进一步找最小点，参阅P44!,(三)几点说明缺点：效率低；优点：可以求搜索区间；注意：h选择要适当，初始步长不能选得太小；,3.3区间消去法黄金分割法,消去法的思想：反复使用单峰函数的消去性质，不断缩小包含极小点的搜索区间，直到满足精度为止。,消去法的优点：只需计算函数值，通用性强。,消去法的设计原则：（1）迭代公式简单；（2）消去效率高；（3）对称：x1a=b-x2；（4）保持缩减比：=(保留的区间长度原区间长度)不变。（使每次保留下来的节点，x1或x2，在下一次的比较中成为一个相应比例位置的节点）。,（一）黄金分割,取“”，=0.61803398874189,（二）黄金分割法的基本思想,黄金分割重要的消去性质:,设x1，x2为a,b中对称的两个黄金分割点，,x1为a,x2的黄金分割点,x2为x1,b的黄金分割点,在进行区间消去时，不管是消去a,x1，还是消去x2，b，留下来的区间中还含一个黄金分割点，只要在对称位置找另一个黄金分割点，又可以进行下一次区间消去。,每次消去后，新区间的长度是原区间的0.618倍，经过n次消去后，保留下来的区间长度为0.618nL，需计算函数值的次数为n+1。,黄金分割比0.618，所以此法也称为0.618法。,（三）算法,开始,x*a,x2,x*x1,b,!在迭代过程中，四个点的顺序始终应该是ax1x2b,但在计算第二个分割点时使用x1=a+bx2或x2=a+bx1,由于舍入误差的影响，可能破坏ax1x20时,x在上升段,x*x，去掉a,x.(自己画算法框图),3.4二分法,a,b缩小，当区间a,b的长度充分小时，或者当充分小时，即可将a,b的中点取做极小点的近似点，这时有估计：,我们知道，在极小点,处，,，且,时，,递减，即,，而当,，函数递增，即,若找到一个区间a,b,满足性质,。,，则,a,b内必有,的极小点,，且,，为找此,，,取,，若,，,则在,中有极小点，这时,用,作为新的区间a,b，继续这个过程，逐步将区间,假设f(x)是具有极小点的单峰函数，,则必存在区间a,b，使f(a)0。,由f(x)的连续性可知，必有x*(a,b)，使f(x)=0,优点：计算量较少，总能找到最优点,缺点：要计算导数值，收敛速度较慢，收敛速度为一阶,其中区间a,b的确定,一般可采用“进退法”。,3.5多项式近似法二次插值法,（一）基本思想,对形式复杂的函数，数学运算时不方便,复杂函数f(x),极小点x*,函数近似，最优点也应近似,一次多项式二次多项式三次多项式,?如何构造符合要求的多项式?,（二）二次插值多项式近似法（抛物线法）的基本原理,设目标函数f(x)在三点x1x2x3上的函数值分别为f1,f2,f3,相应的二次插值多项式为P2(x)=a0a1x+a2x2,令P2(x)和f(x)在三点上的函数值相等,三个待定系数,P2(x)的平稳点是P2(x)a1+2a2x=0的解,所以只需求出a1,a2,最后得,其他插值公式参阅P51-52(2)-(4)!三点二次插值公式最常用.,!迭代过程要点！,若任意取x1x2x3三个点，,则求出的x*可能位于给定区间之外或误差太大,最初的三个点x1x20.2,应继续缩小区间。,第四次缩小区间：令x2=x1=0.764,f2=f1=0.282x1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223由于f10.2,应继续缩小区间。,第五次缩小