机械优化设计(第3、4次课)

机械优化设计2017年5月上海海事大学SHANGHAIMARITIMEUNIVERSITY何军良23:481上海海事大学ShanghaiMaritimeUniversity19092009200419121958机械优化设计中的几个问题优化设计概述优化设计的数学基础2目录CONTENTS一维搜索方法无约束优化方法线性规划约束优化方法23:48第三章一维搜索方法概述01搜索区间确定与区间消去法原理一维搜索的试探方法一维搜索的插值方法02030423:483第三章一维搜索方法求解优化问题的基本解法有：解析法和数值解法解析法：即利用数学分析(微分、变分等）的方法，根据函数（泛函）极值的必要条件和充分条件求出其最优解析解的求解方法。在目标函数比较简单时，求解复杂度尚可接受。局限性：工程优化问题的目标函数和约束条件往往比较复杂，有时甚至还无法用数学方程描述，在这种情况下应用数学分析方法就会带来麻烦。数值迭代法的基本思路：是进行反复的数值计算，寻求目标函数值不断下降的可行计算点，直到最后获得足够精度的最优点。这种方法的求优过程大致可归纳为以下步骤：3.1概述3.1.1基本思路23:484精确一维搜索不精确一维搜索区间收缩法函数逼近法牛顿法（切线法）抛物插值法、三次插值法加步探索法（进退法、成功失败法）Fibonacci法0.618法二分法5第三章一维搜索方法3.1概述3.1.1基本思路23:48第三章一维搜索方法（1）首先初选一个尽可能靠近最小点的初始点X（0），从X（0）出发按照一定的原则寻找可行方向和初始步长，向前跨出一步达到X（1）点；（2）得到新点X（1）后再选择一个新的使函数值迅速下降的方向及适当的步长，从X（1）点出发再跨出一步，达到X（2）点，并依此类推，一步一步地向前探索并重复数值计算，最终达到目标函数的最优点。3.1概述3.1.1基本思路23:486第三章一维搜索方法在中间过程中每一步的迭代形式为：式中：X（k）——第k步迭代计算所得到的点，称第k步迭代点，亦为第k步设计方案；a（k）——第k步迭代计算的步长；S（k）——第k步迭代计算的探索方向。迭代法逐步逼近最优点的探索过程如图。运用迭代法，每次迭代所得新的点的目标函数都应满足函数值下降的要求迭代法要解决的问题：选择搜索方向、确定步长因子、给定收敛准则3.1概述3.1.1基本思路11()()0,1,2,kkkkkkSFFkxxxx23:48783.1概述3.1.2一维问题是多维问题的基础求目标函数f(X)的极小点，从理论上说需要求解方程：()0fX其中，12(,,,)TnXxxx。那么如何来求f(X)的极小点呢？基本思想:011,,,,kkXXXX011()(),,()()kkfXfXfXfX这种方法是逐次迭代的方法，在电子计算机上很容易实现。因此，它在优化设计中被广泛地采用。第三章一维搜索方法23:489第三章一维搜索方法一维搜索方法解析法高等数学已学过，即利用一维函数的极值条件一维搜索方法数值解法分类有试探法和插值法。𝝋′𝜶𝒌∗=𝟎,𝜶𝒌∗求𝒇(𝐱𝒌+𝟏)=𝒇(𝐱𝒌+𝜶𝒌𝒔𝒌)=𝝋(𝜶𝒌解析法：步骤:1.f(X(k)+αS(k))沿S(k)方向在x(k)点进行泰勒展开；2.取二次近似：𝒇𝒙𝒌+𝜶𝑺𝒌≈𝒇(𝒙𝒌)+𝛁𝒇(𝒙𝒌)𝑻𝜶𝑺𝒌+𝟏𝟐𝜶𝟐𝑺𝒌𝑻𝑮(𝒙𝒌)𝑺𝒌对于：3.1概述3.1.2一维问题是多维问题的基础23:4810第三章一维搜索方法步骤:3.对α求导，令其为零;𝒅𝒅𝜶𝒇(𝒙𝒌+𝜶𝑺𝒌)=𝟎步骤:4.求的最优步长𝜶𝒌=−𝛁𝒇(𝒙𝒌)𝑻𝑺𝒌𝑺𝒌𝑻𝑮(𝒙𝒌)𝑺𝒌3.1概述3.1.2一维问题是多维问题的基础23:4811dk方向上任何一点可以表示为，其中α是步长因子，为实系数，此时dk方向上任何一点的目标函数值为。kkkdXX1kkfXd那么在沿dk方向求f(X)的极小点，这就是求一元函数的极小问题，它可表示为：这个过程称为一维搜索过程。52128)(212221xxxxXF如：52202521282212221xxxxF则：0000,11TTXd当：kkfXd:minkkfXd𝑋=00+𝛼11=𝛼𝛼第三章一维搜索方法3.1概述3.1.2一维问题是多维问题的基础23:48)2,1,0(1kSXXkkk一维搜索示意图23:4812133.1.2α的确定方法（1）取下降步长--能使目标函数值下降的步长。4200dFd上例中：F0=52,取α=3，得F1=10F0。故α=3是下降步长。2*F（2）取最优步长上例中：令，α*是最优步长。（3）最优步长直接解析求法211()()()()()()()22TTTTfXdfXdfXdGdfXdfXdGd对α求导并令其等于0，给出()fXd极值点α*应满足条件：*()0TTdfXdGd*()TTdfXdGd直接利用f(X)函数而不需要把它化成步长因子α的φ(α)函数。第三章一维搜索方法3.1概述23:48143.1概述3.1.3一维搜索的基本思想（1）确定一个包含最优点的初始搜索区间特点：高--低--高（2）将含最优点的区间不断缩小当该区间的长度小于预先给定的一个很小的正数ε，则可认为该区间中的某点(如中点)是最优点。*区间缩短率：λ=新区间长度/原区间长度第三章一维搜索方法23:48153.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）（1）基本思想--试探后作前进或后退计算设函数f(α)存在极小点α*，则初始区间为包含极小点α*的区间[a,b]。假设f(α)为单谷连续函数，通过进退搜索方式确定相邻的三个迭代点α1、α2、α3，若其函数值f1、f2、f3呈现大、小、大的变化趋势，便可以定义出初始区间[α1,α3]。第三章一维搜索方法23:4816第三章一维搜索方法3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）23:4817（2）进退法的计算步骤1.给定初始迭代点α0及初始步长h0，令α1←α0、h←h0、f1←f(α1)；2.计算新的试探点α2=α1+h，计算f2←f(α2)；3.比较函数值f1和f2的大小，确定是前进探测还是后退探测。若f1f2，则h←h0,向前探测；否则，令h←-h0，使α1和α2交换位置,向后探测；4.产生新的试探点α3=α2+h，令f3←f(α3)；5.比较函数值f2和f3的大小，确定初始区间。若f3f2，则初始区间已经得到；否则，倍增步距，令h=2h,继续进行搜索，直到产生的新探测点α3满足f3f2，则初始区间为[a,b]=[α1,α3]。向后探测时，若f3f2，则初始区间为[a,b]=[α3,α1]。第三章一维搜索方法3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）23:48右图表示沿α的正向试探。每走一步都将区间的始点、中间点沿试探方向移动一步（进行换名）。经过三步最后确定搜索区间[α1，α3]，并且得到区间始点、中间点和终点α1α2α3及所对应的函数值y1y2y3y1y3→y2y2→y1a3→a2a2→a1a1Oaa3h0h02h0正向搜索的外推法3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）第三章一维搜索方法y1←y2a2←a3a1←a2←a1Oaa32h0h0h0y3y1←y2←y1y2←y3a1←a2反向搜索的外推法3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）第三章一维搜索方法右图表示开始沿α的正向试探，但由于函数值上升而改变试探方向，最后得到了区间始点、中间点和终点α1α2α3及所对应的函数值y1y2y3，从而形成的单谷区间为一维搜索区间[α3，α1]23:4819khx1x2x30h0初始点初始点+h01h0初始点初始点+h0初始点+2h022h0初始点+h0初始点+2h0初始点+4h034h0初始点+2h0初始点+4h0初始点+8h0（3）前进搜索步骤表3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）第三章一维搜索方法23:4820khx1x2x30h0初始点初始点+h01h0初始点+h0初始点初始点-h022h0初始点初始点-h0初始点-3h034h0初始点-h0初始点-3h0初始点-7h0（4）后退搜索步骤表3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）第三章一维搜索方法22第三章一维搜索方法进退法确定区间的算法框图3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）（4）算法程序23:482323:48functionabh0=input('h0=?');x0=input('x0=?');h=h0;x1=x0;f1=fx(x1);x2=x1+h;f2=fx(x2);iff2f1h=-h;x3=x1;f3=f1;x1=x2;f1=f2;x2=x3;f2=f3;endh=2*h;x3=x2+h;f3=fx(x3);whilef2=f3x1=x2;f1=f2;x2=x3;f2=f3;h=2*h;x3=x2+h;f3=fx(x3);endifh0a=x3;b=x1elsea=x1;b=x3;end24例3-1用进退法确定函数f(x)=3x3-8x+9的一维优化初始区间，给定初始x1=0，初始化进退距h0=0.1。解：khx1y1x2y2x3y310.10.1090.18.2030.27.42420.20.18.2030.27.4240.45.99230.40.27.4240.45.9920.84.13640.80.45.9920.84.1361.68.488可得，初始搜索区间[a,b]=[0.4,1.6]。第三章一维搜索方法3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）23:4825例3-2用进退法确定函数f(x)=3x3-8x+9的一维优化初始区间，给定初始x1=1.8，初始化进退距h0=0.1。解：可得，初始搜索区间[a,b]=[0.3,1.5]。khx1y1x2y2x3y310.1-0.11.812.0961.914.3771.914.3771.812.0961.710.1392-0.21.812.0961.710.1391.57.1253-0.41.710.1391.57.1251.14.1934-0.81.57.1251.14.1930.36.681运用进退法确定出初始搜索区间[a,b]后，便可采用一维优化方法来求出函数f(x)在区间内的最优点x*。第三章一维搜索方法3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）23:4826搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。假定在搜索区间内[a,b]任取两点a1，b1，对应函数值为f(a1)，f(b1)。第三章一维搜索方法3.2搜索区间的确定与区间消去法原理3.2.2区间消去法23:4827存在三种可能情况：11()()fafb11()()fafb11()()fafb1[,]ab1[,]ab11[,]ab第三章一维搜索方法3.2搜索区间的确定与区间消去法原理3.2.2区间消去法23:48283.3一维搜索的试探法（黄金分割法）3.3.1基本思路该法适用于[a,b]区间上单谷函数极小值问题。在搜索区间[a,b]内适当加入两点α1,α2，并计算其函数值。α1,α2将区间分成三段，然后利用区间消去法，通过比较函数值大小删除其中一段，使搜索区间缩短，在保留区间进行同样