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

机械优化设计2017年5月上

海

海

事

大

学SHANGHAIMARITIMEUNIVERSITY何军良12:241上海海事大学ShanghaiMaritimeUniversity

1909

2009

2004

1912

19587机械优化设计中的几个问题1优化设计概述2优化设计的数学基础2目录CONTENTS3一维搜索方法4无约束优化方法5线性规划6约束优化方法12:24第三章一维搜索方法

概述01

搜索区间确定与区间消去法原理

一维搜索的试探方法

一维搜索的插值方法02030412:243第三章一维搜索方法求解优化问题的基本解法有：解析法和数值解法解析法：即利用数学分析(微分、变分等）的方法，根据函数（泛函）极值的必要条件和充分条件求出其最优解析解的求解方法。在目标函数比较简单时，求解复杂度尚可接受。局限性：工程优化问题的目标函数和约束条件往往比较复杂，有时甚至还无法用数学方程描述，在这种情况下应用数学分析方法就会带来麻烦。数值迭代法的基本思路：是进行反复的数值计算，寻求目标函数值不断下降的可行计算点，直到最后获得足够精度的最优点。这种方法的求优过程大致可归纳为以下步骤：3.1概述3.1.1基本思路12:2445第三章一维搜索方法3.1概述3.1.1基本思路12:24第三章一维搜索方法（1）首先初选一个尽可能靠近最小点的初始点X（0），从X（0）出发按照一定的原则寻找可行方向和初始步长，向前跨出一步达到X（1）点；（2）得到新点X（1）后再选择一个新的使函数值迅速下降的方向及适当的步长，从X（1）点出发再跨出一步，达到X（2）点，并依此类推，一步一步地向前探索并重复数值计算，最终达到目标函数的最优点。3.1概述3.1.1基本思路12:246第三章一维搜索方法在中间过程中每一步的迭代形式为：式中：X（k）——第k步迭代计算所得到的点，

称第k步迭代点，亦为第k步设计方案；

a（k）——第k步迭代计算的步长；

S（k）——第k步迭代计算的探索方向。迭代法逐步逼近最优点的探索过程如图。运用迭代法，每次迭代所得新的点的目标函数都应满足函数值下降的要求迭代法要解决的问题：选择搜索方向、确定步长因子、给定收敛准则3.1概述3.1.1基本思路12:24783.1概述3.1.2一维问题是多维问题的基础求目标函数f(X)的极小点，从理论上说需要求解方程：其中，。那么如何来求f(X)的极小点呢？基本思想:这种方法是逐次迭代的方法，在电子计算机上很容易实现。因此，它在优化设计中被广泛地采用。第三章一维搜索方法12:249第三章一维搜索方法一维搜索方法解析法高等数学已学过，即利用一维函数的极值条件一维搜索方法数值解法分类有试探法和插值法。

求

解析法：步骤:1.f(X(k)+αS(k)

)

沿S(k)方向在x(k)点进行泰勒展开；

2.取二次近似：

对于：3.1概述3.1.2一维问题是多维问题的基础12:2410第三章一维搜索方法步骤:3.对α求导，令其为零;

步骤:4.求的最优步长

3.1概述3.1.2一维问题是多维问题的基础12:2411dk方向上任何一点可以表示为，

其中α是步长因子，为实系数，此时dk方向上任何一点的目标函数值为。那么在沿dk方向求f(X)的极小点，这就是求一元函数的极小问题，它可表示为：这个过程称为一维搜索过程。如：则：当：

第三章一维搜索方法3.1概述3.1.2一维问题是多维问题的基础12:24一维搜索示意图12:2412133.1.2α的确定方法（1）取下降步长--能使目标函数值下降的步长。上例中：F0=52,取α

=3，得F1=10<F0。故α

=3是下降步长。（2）取最优步长上例中：令，

α*是最优步长。（3）最优步长直接解析求法对α求导并令其等于0，给出极值点α*应满足条件：直接利用f(X)函数而不需要把它化成步长因子α的φ(α)函数。第三章一维搜索方法3.1概述12:24143.1概述3.1.3一维搜索的基本思想（1）确定一个包含最优点的初始搜索区间特点：高--低--高（2）将含最优点的区间不断缩小当该区间的长度小于预先给定的一个很小的正数ε，则可认为该区间中的某点(如中点)是最优点。*区间缩短率：λ=新区间长度/原区间长度第三章一维搜索方法12:24153.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）（1）基本思想--试探后作前进或后退计算设函数f(α)存在极小点α*，则初始区间为包含极小点α*的区间[a,b]。假设f(α)为单谷连续函数，通过进退搜索方式确定相邻的三个迭代点α1、α2、α3，若其函数值f1、f2、f3呈现大、小、大的变化趋势，便可以定义出初始区间[α1,α3]。第三章一维搜索方法12:2416第三章一维搜索方法3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）12:2417（2）进退法的计算步骤1.给定初始迭代点α0及初始步长h0，令α1←α0、h←h0、f1←f(α1)；2.计算新的试探点α2=α1+h，计算f2←f(α2)；3.比较函数值f1和f2的大小，确定是前进探测还是后退探测。若f1>f2，则h←h0,向前探测；否则，令h←-h0，使α1和α2交换位置,向后探测；4.产生新的试探点α3=α2+h，令f3←f(α3)；5.比较函数值f2和f3的大小，确定初始区间。若f3>f2，则初始区间已经得到；否则，倍增步距，令h=2h,继续进行搜索，直到产生的新探测点α3满足f3>f2，则初始区间为[a,b]=[α1,α3]。向后探测时，若f3>f2，则初始区间为[a,b]=[α3,α1]。第三章一维搜索方法3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）12:24右图表示沿α的正向试探。每走一步都将区间的始点、中间点沿试探方向移动一步（进行换名）。经过三步最后确定搜索区间[α1，α3]，并且得到区间始点、中间点和终点α1

<α2<α3

及所对应的函数值y1

>

y2<y3y1y3→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

及所对应的函数值y1

>

y2<y3，从而形成的单谷区间为一维搜索区间[α3，α1]

12:2419khx1x2x30h0初始点初始点+h01h0初始点初始点+h0初始点+2h022h0初始点+h0初始点+2h0初始点+4h034h0初始点+2h0初始点+4h0初始点+8h0（3）前进搜索步骤表3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）第三章一维搜索方法12:2420khx1x2x30h0初始点初始点+h01h0初始点+h0初始点初始点-h022h0初始点初始点-h0初始点-3h034h0初始点-h0初始点-3h0初始点-7h0（4）后退搜索步骤表3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）第三章一维搜索方法22第三章一维搜索方法进退法确定区间的算法框图3.2搜索区间的确定与区间消去法原理3.2.1确定搜索区间的进退法（外推法）（4）算法程序12:242312:2424例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确定搜索区间的进退法（外推法）12:2425例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确定搜索区间的进退法（外推法）12:2426搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。假定在搜索区间内[a,b]任取两点a1，b1，对应函数值为f(a1)，f(b1)。第三章一维搜索方法3.2搜索区间的确定与区间消去法原理3.2.2区间消去法12:2427存在三种可能情况：第三章一维搜索方法3.2搜索区间的确定与区间消去法原理3.2.2区间消去法12:24283.3一维搜索的试探法（黄金分割法）3.3.1基本思路该法适用于[a,b]区间上单谷函数极小值问题。在搜索区间[a,b]内适当加入两点α1,α2，并计算其函数值。α1,α2将区间分成三段，然后利用区间消去法，通过比较函数值大小删除其中一段，使搜索区间缩短，在保留区间进行同样处理，直到搜索区间缩小到指定精度为止。它适用于[a,b]区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广。第三章一维搜索方法12:2429黄金分割法对插入点的要求：1、插入点

α1、α2

的位置相对于区间[a,b]两端具有对称性，即：为待定常数；2、在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。1）为预先给定的误差限。2）缩短区间的总次数第三章一维搜索方法3.3一维搜索的试探法（黄金分割法）3.3.1基本思路12:2430（1）关于λ=0.618证明证：其正根为：第三章一维搜索方法3.3一维搜索的试探法（黄金分割法）3.3.1基本思路12:2431（2）缩小区间总次数的证明证：即：或第三章一维搜索方法3.3一维搜索的试探法（黄金分割法）3.3.1基本思路12:2432第三章一维搜索方法黄金分割法要求插入的两点：

黄金分割法区间消去示意：f(a1)f(a2)f(a1)f(a2)a1

a1

a2abab

a23.3一维搜索的试探法（黄金分割法）3.3.1基本思路12:24333.3一维搜索的试探法（黄金分割法）3.3.2基本步骤1.给出搜索区间[a,b]，收敛精度ε，λ=0.6182.计算α1，α2以及对应的函数值f(α1)、

f(α2)；3.根据区间消去法原理缩短搜索区间，为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。如果f(α1)<f(α2)，则新区间＝[α,α2]

令b=α2,α2=α1,f(α2)=

f(α1)，记N0=0；如果f(α1)≥f(α2)，则新区间＝[α1,b]

令a=α1,

α1=α2,f(α1)=

f(α2)，记N0=0；

第三章一维搜索方法12:24344.检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解，如果条件不满足则转向步骤（5）。5.产生新的插入点：N0=0，则取N0=1，则取第三章一维搜索方法

转向步骤(3)进行新的区间缩小。3.3一维搜索的试探法（黄金分割法）3.3.2基本步骤12:2435这种方法的基本原理是：在搜索区间[a,b]内按照如下规则对称地取两点a1和a2：α1=a+0.382(b-a)，α2=a+0.618(b-a)。计算它们的函数值f1=f(a1),f2(a2),比较两者大小。有两种可能：若f1≥f2,如图（a）所示。极小值点必在区间[α1,b]内，消去区间[a,a1]，令a=α1，产生新区间[α1,b]。新区间α1与原区间α2重合，可令α1=α2，f1=f2，这样可少找一个新点和节省一次函数值计算。第三章一维搜索方法3.3一维搜索的试探法（黄金分割法）3.3.2基本步骤12:2436若f1<f2,如图（b）所示。极小值点必在区间[a,a2]内，消去区间[α2,b]，令b=α2，产生新区间[a,

α2]。同样，新区间α2与原区间α1重合，可令α2=α1，f2=f1，这样可少找一个新点和节省一次函数值计算。第三章一维搜索方法3.3一维搜索的试探法（黄金分割法）3.3.2基本步骤12:2437第三章一维搜索方法3.3一维搜索的试探法（黄金分割法）3.3.2基本步骤12:2438第三章一维搜索方法3.3一维搜索的试探法（黄金分割法）3.3.2基本步骤12:2439第三章一维搜索方法3.3一维搜索的试探法（黄金分割法）3.3.2基本步骤12:2440第三章一维搜索方法12:2441第三章一维搜索方法3.3一维搜索的试探法（黄金分割法）3.3.2基本步骤12:2442例3-3用黄金分割法求f(α)=α2+2α的极小值α*，搜索区间是-3≤α≤5。解：迭代序号aα1α2by1比较y20-30.0561.94450.115<7.6671-3-1.1110.0561.944-0.987<0.1152-3-1.832-1.1110.056-0.306>-0.9873-1.832-1.111-0.6650