现代设计方法学优化设计

1、优化设计优化设计n :概述n :优化建模及数学基础n :一维无约束问题寻优 n :多维无约束问题寻优 n :多维约束问题寻优n :优化实例n 第一节第一节第二节第二节第三节第三节第四节第四节第五节第五节第六节第六节第一节:概述 1.1 引 言 1.4 优化设计分类 1.2 优化设计数学模型 1.3 优化设计三大要素 1.5 优化设计迭代算法生产甲种产品每件需使用材料生产甲种产品每件需使用材料9kg9kg、3 3个工时、个工时、4kw4kw电，获利电，获利润润6060元。生产乙种产品每件需用材料元。生产乙种产品每件需用材料4kg4kg、1010个工时、个工时、5kw5kw电，可获利电，可获利12

2、0120元。若每天能供应材料元。若每天能供应材料360kg360kg，有，有300300个工时，个工时，能供能供200kw200kw电。试确定两种产品每天的产量，使每天可能获电。试确定两种产品每天的产量，使每天可能获得的得的利润最大利润最大？ 1212(,)60120f x xxx112()94360gXxx分析：分析：每天生产的每天生产的分别为分别为x1 1, , x2 2件件 1.1 1.1 引引 言言（工时约束）（工时约束）（电力约束）（电力约束）（材料约束）（材料约束）( (利润最大利润最大) )212()310300gXxx312()45200gXxxmaxn用薄钢板制造一个体积为5

3、立方米的汽车货箱，由于运输的货物要求，其长度不小于4米。为了使耗费的钢板最少并减少质量，问应如何选取货箱的长宽高？n设计变量 n目标函数：n约束条件： 123TXxxx123121332min()( ,)2()f Xf x xxxxxxxx123()5h Xxxx11()400gXx22()0gXx 33()0gXx 1.1 1.1 引引 言言n在某建筑工地中要制作10000套钢筋，每套由2.9米、2.1米、1.5米长钢筋组成。它们的直径和材料相同.目前市场上采购到同类的钢筋的长度每根均为7.4米.问应购进多少7.4米长的钢筋才能满足工程的需要?n1 首先分析套裁方案,方案如表: 1.1 1.

4、1 引引 言言2 设以 表示按第i种方案下料的原材料数量,则可得该问题的数学模型为:(1,2,3.8)ix i 12345678123423567134678min2100021000323410000,1,2,3.,8jzxxxxxxxxxxxxxxxxxxxxxxxxj 1.1 1.1 引引 言言n给定一个直角三角形，求包含该三角形的最小正方形。 ABCDDAEabx,sincos,cos,sinxbxaDExbADxaCE 1.1 1.1 引引 言言nmodel:nsets:n object/1.3/: f;nendsetsndata:n a, b = 3, 4; !两个直角边长，修改很

5、方便;nenddatan f(1) = a * sin(x);n f(2) = b * cos(x);n f(3) = a * cos(x) + b * sin(x);n min = smax(f(1),f(2),f(3);n bnd(0,x,1.57);nEndLINGO应用(引例) 1.1 1.1 引引 言言n现在WW(Wireless Widgets)公司拥有6个仓库，向其8个销售商供应它的产品。要求每个仓库供应不能超量，每个销售商的需求必须得到满足。WW公司需要决策具体的从每个仓库运输多少产品到每个销售商。以使得所花的运输费用最少？ 1.1 1.1 引引 言言3、每件产品运输费用($)

6、:销售商右 V1 V2 V3 V4 V5 V6 V7 V8仓库下 Wh1 6 2 6 7 4 2 5 9 Wh2 4 9 5 3 8 5 8 2 Wh3 5 2 1 9 7 4 3 3 Wh4 7 6 7 3 9 2 7 1 Wh5 2 3 9 5 7 2 6 5 Wh6 5 5 2 2 8 1 4 3二、问题的已知数据： 1.1 1.1 引引 言言 1.1 1.1 引引 言言一一. . 优化优化( (Optimum) )定义：定义：在规定的范围内（或在规定的范围内（或条件下），寻找给定函数取条件下），寻找给定函数取得的最大值（或最小值）的得的最大值（或最小值）的条件。条件。目的：目的：为了在

7、完成某一任务为了在完成某一任务时所作的努力最少、付出最时所作的努力最少、付出最小，而使其收益最大、效果小，而使其收益最大、效果最好。最好。 X0X* f(X*)f(X) 传统设计：传统设计：可行解可行解 优化设计：优化设计：最优解最优解。 1.1 1.1 引引 言言 二二. .传统设计与优化设计的区别传统设计与优化设计的区别方案设计方案设计详细设计详细设计制造样机制造样机测试评估，性能，质量测试评估，性能，质量可否通过？可否通过？传传 统统 设设 计计不通过不通过投投 产产通过通过方案设计方案设计建模评估建模评估详细设计详细设计实验验证实验验证优优 化化 设设 计计改进改进投产投产三三. .

8、优化设计的发展优化设计的发展经典优化设计经典优化设计: :2020世纪世纪4040年代起，数学规划论和计年代起，数学规划论和计算机技术的发展使最优化设计计算成为可能。算机技术的发展使最优化设计计算成为可能。 优化设计从无约束优化设计从无约束有约束优化问题；连续变有约束优化问题；连续变量量离散变量；确定型离散变量；确定型随机型模型；单目标优化随机型模型；单目标优化多目标优化。多目标优化。古典优化思想古典优化思想: :1717世纪发明微积分中的极值问题。世纪发明微积分中的极值问题。现代优化设计：现代优化设计：模拟退火算法、遗传算法、人工神模拟退火算法、遗传算法、人工神经网络算法、蚁群优化算法等。经

9、网络算法、蚁群优化算法等。 从狭义优化设计（零部件参数）转向广义优化设从狭义优化设计（零部件参数）转向广义优化设计（面向产品全系统、设计全过程、全寿命周期）。计（面向产品全系统、设计全过程、全寿命周期）。例如例如, ,针对涉及多领域复杂系统的多学科设计优化。针对涉及多领域复杂系统的多学科设计优化。 1.1 1.1 引引 言言1.21.2 优化设计的数学模型优化设计的数学模型例：轴的一端作用载荷例：轴的一端作用载荷 F=10000N，扭矩，扭矩 T=100Nm；轴长；轴长不得小于不得小于8cm；材料的许用弯曲应力；材料的许用弯曲应力 w=120MPa，许，许用扭剪应力用扭剪应力 = 80MPa，

10、许用挠度，许用挠度 f = 0.01cm；密度；密度 = 7.8t /m，弹性模量，弹性模量E=2105MPa。 分析：分析：是轴的质量最轻是轴的质量最轻:Q min. 要求：要求：设计销轴，在满足上述条件的同时，轴的质量最轻。设计销轴，在满足上述条件的同时，轴的质量最轻。 限制：限制：弯曲强度：弯曲强度：max w 扭转强度：扭转强度： 刚刚 度：度： f f 结构尺寸：结构尺寸： l 8 d 0lFdT1.21.2 优化设计的数学模型优化设计的数学模型 目标函数目标函数 Q = (d2 l)/4 min. 约束函数约束函数 max = Fl / ( 0.1d3 )w = T / ( 0.2

11、d3 ) f = 64 Fl3 / ( 3E d 4 ) f l 8 d 0整理得：整理得： X =x1,x2 T = d ,l T min. f(x)= 0. 785 x12x2 s.t. g1(x)= 8.33 x2 - x13 0 g2(x)= 6.25 - x13 0 g3(x)= 0.34 x23 - x14 0 g4(x)= 8 - x2 0 g5(x)= - x1 012,TnXx xx12()( ,)nf Xf x xx()0 (1,2,)ugXum()0 (1,2,)vh Xpvn优化设计数学模型统一形式优化设计数学模型统一形式：1.21.2 优化设计的数学模型优化设计的数学

12、模型一个完整的规格化的一个完整的规格化的包含有包含有设计变量设计变量 X；目标函数目标函数 ；约束条件约束条件 和和 。它们又被称为：它们又被称为：。当涉及问题要当涉及问题要目标函数时，只要将式中目标函数时，只要将式中改写为改写为 f (X)即可。即可。同样，当同样，当不等式约束不等式约束为：为：“” 时，只要将不等式时，只要将不等式两端同乘以两端同乘以“1”，即可得到，即可得到 “” 的一般形式。的一般形式。 ()f X()0 ugX ( )0 vh X 1.21.2 优化设计的数学模型优化设计的数学模型1.3 1.3 优化设计的三大要素优化设计的三大要素一一. .设计变量：设计变量： 设计

13、变量设计变量：在优化设计过程中是变化的，需要优选的量。：在优化设计过程中是变化的，需要优选的量。 优化设计问题有优化设计问题有 n 个设计变量，用个设计变量，用 xi表示表示 (i = 1, 2, , n) 。设计向量设计向量：用：用 X =x1, x2 , , xnT 表示，表示， 是定义在是定义在 n 维欧氏空间中的一个向量。维欧氏空间中的一个向量。设计参数设计参数：在优化设计过程中保持不变或预先确定数值。：在优化设计过程中保持不变或预先确定数值。1.3 1.3 优化设计的三大要素优化设计的三大要素设计点设计点: X(k)（x1(k), x2 (k), , xn(k)）：）： 例：右图三维

14、空间中例：右图三维空间中第第1设计点：设计点：X(1) = x1(1), x2(1), x3(1)T第第2设计点：设计点：X(2) = x1(2), x2(2), x3(2)T 代表设计空间中的一个点，也代表第代表设计空间中的一个点，也代表第 k 个设计个设计方案。可能是可行方案、也可能不是可行方案。方案。可能是可行方案、也可能不是可行方案。X(1) X(2) X(1) x1x2x30n=2: X=x1, x2T 是二维设计向量；是二维设计向量；n=3: X=x1, x2, x3T 为三维设计向量，设计变量为三维设计向量，设计变量x1, x2, x3 组成一个三维空间；组成一个三维空间；n3:

15、 设计空间是一个想象的超越空间，称设计空间是一个想象的超越空间，称 n 维实属空间。维实属空间。 1.3 1.3 优化设计的三大要素优化设计的三大要素x1(k)x1X(k)x2(k)x20 x1(k)x1X(k)x2(k)x20 x3(k)x3在工程设计中，当有些设计变量的取值要求是离散在工程设计中，当有些设计变量的取值要求是离散型量，则称型量，则称离散设计变量离散设计变量，如齿轮的齿数、模数。，如齿轮的齿数、模数。设计变量的设计变量的个数个数，称为，称为维数维数，它决定了优化问题的，它决定了优化问题的 大小范围大小范围： n110 小型优化问题小型优化问题 ； n1150 中型优化问题；中型

16、优化问题； n 50 大型优化问题。大型优化问题。设计变量设计变量可分为可分为连续变量连续变量和和离散变量离散变量。1.3 1.3 优化设计的三大要素优化设计的三大要素1.3 1.3 优化设计的三大要素优化设计的三大要素设计约束设计约束：设计变量值：设计变量值(设计点设计点)的选择不仅要使目标函数的选择不仅要使目标函数 达到最优值，同时还会受一定的条件限制，这达到最优值，同时还会受一定的条件限制，这 些制约条件称设计约束。些制约条件称设计约束。 不等式约束：不等式约束： gu(X) 0 u = 1, 2, , m 等等 式式 约约 束：束：hv(X) = 0 v = 1, 2 , , p (p

17、 n )例：有三个不等式约束例：有三个不等式约束 g1(X) = - x1 0 g2(X) = - x2 0 g3(X) = x12 + x22 - 1 0 再加一个等式约束再加一个等式约束 h(X) = x1- x2 = 0二二. .约束函数约束函数h(X) = 0 x1x2g1(X) = 0g2(X) = 0g3(X) = 00不等式约束不等式约束将将设计空间设计空间划分为划分为两部分两部分： 一部分一部分 ：满足约束，即满足约束，即 g j (X)0；另一部分：另一部分：则不满足约束，即则不满足约束，即 g j (X)0。故将故将该分界线该分界线或分界面称为或分界面称为约束边界约束边界。

18、等式约束等式约束本身也是约束边界，此时只有约束边界上的点满本身也是约束边界，此时只有约束边界上的点满足约束，边界两边的所有部分都不满足约束。足约束，边界两边的所有部分都不满足约束。1.3 1.3 优化设计的三大要素优化设计的三大要素g(X) = 0g(X) 0g(X) 0 时时 矩阵矩阵正定正定 主子式主子式 0 时时 矩阵矩阵半正定半正定 主子式主子式0时时 矩阵矩阵负定负定 主子式主子式 0 时时 矩阵矩阵半负定半负定四、凸规划四、凸规划对于约束优化问题对于约束优化问题min fX.st0jgX 1,2,.,jm若若 ，fXjgX 都为凸函数，则此问题为凸规划。都为凸函数，则此问题为凸规划

19、。2.42.4 凸集、凸函数与凸规划凸集、凸函数与凸规划凸规划的任何局部最优解就是全局最优解凸规划的任何局部最优解就是全局最优解等式约束优化形式：等式约束优化形式：求解求解消元法消元法拉格朗日乘子法拉格朗日乘子法min fX.st0khX 1,2,.,kl2.52.5 等式约束优化极值条件等式约束优化极值条件1.消元法（降维法）消元法（降维法）2.52.5 等式约束优化极值条件等式约束优化极值条件12min,nf x xx.st12,0knhx xx1,2,.,kl降维处理：降维处理：1112221212,llnllnllllnxxxxxxxxxxxx1.消元法（降维法）消元法（降维法）2.5

20、2.5 等式约束优化极值条件等式约束优化极值条件2123min23fXxxx.st120 xx降维处理：降维处理：12xx方法直观易理解，但是实际操作很困难方法直观易理解，但是实际操作很困难2223min23fXxxx变为无约束优化问题：变为无约束优化问题：2、拉格朗日乘子法（升维法、拉格朗日乘子法（升维法）改造后优化模型改造后优化模型：2.52.5 等式约束优化极值条件等式约束优化极值条件原优化模型原优化模型：1,lkkkF XfXhX拉格朗日函数拉格朗日函数待待 定定 系系 数数min fX.st0khX 1,2,.,kl2、拉格朗日乘子法（升维法）、拉格朗日乘子法（升维法）2.52.5

21、等式约束优化极值条件等式约束优化极值条件1,lkkkF XfXhX0 (1,2,)iFinx 0 (1,2,)kFkl n+l个方程个方程n+l个未知变量个未知变量例例: :用拉格朗日乘子法求下列问题的最优解用拉格朗日乘子法求下列问题的最优解2212121212min()60104. .()80f Xxxxxx xs th Xxx 2212121212(, )()()60104(8)L Xf Xh Xxxxxx xxx 1211020Lxxx 解解 构造拉格朗日函数构造拉格朗日函数1280Lxx 212420Lxxx 令令L=0,得到得到求解得：求解得：*12533()17xxf X 一、一元

22、函数在给定区间上的极值条件一、一元函数在给定区间上的极值条件2.6 2.6 不等式优化极值条件不等式优化极值条件min fX.st10gXax20gXxb引入引入松弛变量松弛变量a1,b1，将不等式约束变成等式约束。，将不等式约束变成等式约束。2211111,0hX agXaaxa2221211,0hX bgXbxbb 11121 11221,F X a bfXhx ahx b 221121fXaxaxbb 根据拉格朗日乘子法，此问题的极值条件：根据拉格朗日乘子法，此问题的极值条件：120FdfXdX1 1120Fbb1 1120Faa2.6 2.6 不等式优化极值条件不等式优化极值条件 22

23、211212,0Fhx bxbbgxb 22111111,0Fhx aaxagxa二二 、库恩塔克条件：、库恩塔克条件：2.6 2.6 不等式优化极值条件不等式优化极值条件*()()0(1,2, )jjj JiigXf Xinxx 0 ()jjJ *0 ()jgXjJ J代表所有起作用的约束代表所有起作用的约束*()()jjj Jf XgX在约束的在约束的极小值处极小值处，函数函数 f(x)的负梯度方向的负梯度方向一定能一定能表示成表示成所有起作用约束梯度所有起作用约束梯度的的非负线性组合非负线性组合库恩塔克条件的几何意义库恩塔克条件的几何意义2.6 2.6 不等式优化极值条件不等式优化极值条

24、件Xk为最优点为最优点Xk不是最优点不是最优点x1x20可行域可行域Xkg1(Xk)g2(Xk)点点Xk处的切平面处的切平面- -f(Xk)f(X)=Cg2(X)=0g1(X)=0 x1x20点点Xk处的切平面处的切平面g1(Xk)g2(Xk)- -f(Xk)g2(X)=0g1(X)=0f(X)=CxkK-TK-T条件的作用：条件的作用：l 判别边界设计点判别边界设计点 x x(k)(k) 为最优点的依据为最优点的依据l 作为约束优化的收敛条件。作为约束优化的收敛条件。x1x20g1g3- -f- -f- -fg1g2g2g3f =5f =4f =2.25f =1f =0.25g2(X) =

25、0g3(X) = 0g1(X) = 0ABC 第三章 一维搜索方法3.3 一维搜索的试探法3.1 搜索区间的确定3.2 区间消去法原理3.4 一维搜索的插值法求解求解最优解的过程，称为最优解的过程，称为( (一一维搜索维搜索) )，所使用的方法称为，所使用的方法称为。 由前由前可知，求某目标函数的最优值时，可知，求某目标函数的最优值时，迭代过迭代过程程每一步的格式都是从每一步的格式都是从某一定点某一定点X(k) 出发，沿着某一使目出发，沿着某一使目标函数下降的规定标函数下降的规定方向方向 S(k)搜索，以找出此方向的搜索，以找出此方向的极小点极小点X(k+1) 。这一过程是各种最优化方法的一种

26、。这一过程是各种最优化方法的一种。一般一般： 首先首先确定确定一个包含函数极小点的一个包含函数极小点的初始区间初始区间，即，即确定确定 函数的搜索区间，该区间必须是函数的搜索区间，该区间必须是单峰区间单峰区间； 然后采用缩小区间或插值逼近的方法然后采用缩小区间或插值逼近的方法得到得到最优步长最优步长， 最终求出该搜索区间内的最终求出该搜索区间内的一维极小点一维极小点。3.1 3.1 搜索区间的确定搜索区间的确定根据函数的变化情况，可将根据函数的变化情况，可将分为分为单峰区间单峰区间和和多峰区间多峰区间。所谓所谓，就是在该区间内的函数变化只有一个峰值，就是在该区间内的函数变化只有一个峰值，即函数

27、的极小值。即函数的极小值。即在即在内的内的的的左侧左侧：函数呈：函数呈，而在而在内的内的极小值点极小值点X* 的的右侧右侧：函数呈：函数呈上升趋势上升趋势。也就是说，也就是说，的函数值呈的函数值呈的变化特征的变化特征。3.1 3.1 搜索区间的确定搜索区间的确定x*abx0f(x)目前在一维优化搜索中确定目前在一维优化搜索中确定单峰区间单峰区间常用的方法常用的方法是是进退试算法进退试算法。 为：为： 1)1) 按照一定的规律给出按照一定的规律给出若干试算点若干试算点， 2)2) 依次比较各依次比较各试算点的函数值试算点的函数值的大小，的大小， 3) 3) 直到找到直到找到相邻三点相邻三点函数值

28、按函数值按“高高- -低低- -高高” 变化的变化的单峰区间单峰区间为止为止3.1 3.1 搜索区间的确定搜索区间的确定进退试算法的进退试算法的如下：如下：(2)将将0及及0+h 代入目标函数代入目标函数 f(x) 进行计算并比较大小进行计算并比较大小(1)给定给定初始点初始点0和和初始步长初始步长h3.1 3.1 搜索区间的确定搜索区间的确定f(x)x0aba0f(a0)a0+hf(a0+h)a0+3hf(a0+3h)f(x)x0aba0-hf(a0-h)a0f(a0)a0+hf(a0+h) 若若f(0+h) f(0+3h) ，则所计算的相邻三点，则所计算的相邻三点 的函数值已具的函数值已具

29、“高高-低低-高高”特征，这时可确定特征，这时可确定 搜索区间搜索区间(3)若若f(0 ) f(0+h)，则表明极小点在试算点，则表明极小点在试算点 的右侧，需做的右侧，需做前进试算前进试算。00, 3abh否则，将步长再加倍，并重复上述运算。否则，将步长再加倍，并重复上述运算。3.1 3.1 搜索区间的确定搜索区间的确定 在做在做前进运算前进运算时，为加速计算，可将步长时，为加速计算，可将步长h 增加增加2倍，并取计算新点为倍，并取计算新点为0+h+2h=0+3h(4)若若 f(0) f(0) ，则，则搜索区间搜索区间可取为可取为00, ahbh否则，将步长加倍，继续后退，重复否则，将步长加

30、倍，继续后退，重复上述步上述步骤骤，直到满足，直到满足单峰区间单峰区间条件为止。条件为止。3.1 3.1 搜索区间的确定搜索区间的确定f(b1)f(a1)f(b1)f(a1)f(b1)af(a1) 搜索区间确定搜索区间确定之后，采用区间消去法逐步之后，采用区间消去法逐步缩短搜索区间缩短搜索区间，找到极小点的数值近似解。找到极小点的数值近似解。 假定在搜索区间内假定在搜索区间内a,b 任取两点任取两点a1、b1,且且a1f2 f1f2 f1=f2 f(x) f(x) f(x) (1)f1f2, 新区间为新区间为a1,b(3)f1=f2, 新区间为新区间为a1,b1对于上述对于上述缩短后的新区间缩

31、短后的新区间，可在其内再取一个，可在其内再取一个新点新点，然后，然后将此点和该区间内剩下的那一点进行函数值大小的比较，将此点和该区间内剩下的那一点进行函数值大小的比较，以再次按照以再次按照上述方法上述方法，进一步，进一步缩短区间缩短区间，这样不断进行下，这样不断进行下去，直到去，直到所保留的区间所保留的区间缩小到给定的误差范围内，而得到缩小到给定的误差范围内，而得到近似最优解近似最优解。12ff新区间为新区间为a1, bf(b1)af(a1) a1 b1bf(b1)f(a1)a1ab b1f(b1)f(a1)a1bab1111222(1)(),( )(),()aabaff aaabaff a一

32、、适用范围一、适用范围 适用于适用于a, b区间上的任何区间上的任何单谷函数单谷函数求极小值问题。对求极小值问题。对函数除要求函数除要求“单峰单峰”外不作其他要求，甚至可以外不作其他要求，甚至可以不连不连续续。适应面相当广。基本原理为。适应面相当广。基本原理为区间消去法区间消去法3.3 3.3 黄金分割法黄金分割法黄金分割法插入两点：黄金分割法插入两点：f(a2)af(a1) a1 a2bf(a2)af(a1) a1b a221510.61823.3 3.3 黄金分割法黄金分割法212ab11-13(1-)2aab黄金分割法程序框图黄金分割法程序框图 开开 始始输入输入a, b, , 120.

33、382()0.618()xabaxaba12( )()f xf x22121111,0.382(),( )bx xx ffxabaff x11212222,0.618(),()ax xxffxabaff x结结 束束*0.5(),()xabff xaf(x2)f(x1)b x1 x2b x2f(x2) x1例例 3-1 用黄金分割法求函数用黄金分割法求函数f(x)=3x3-4x+2的极小点，的极小点， 初始点初始点 x0=0, 步长步长h=1,精度精度 =0.2。解：解：1）确定初始区间确定初始区间 x1=x0=0, f1=f(x1)=2 x2=x0+h=0+1=1 f2=f(x2)=1 由于

34、由于f1f2, 应继续向前探测应继续向前探测 x3= x0+2h=0+2=2 f3=f(x3)=18 由于由于f2f3,可知初始区间已经找到，即可知初始区间已经找到，即 a, b=x1, x3=0, 23.3 3.3 黄金分割法黄金分割法f(x1)=2x1=0f(x2)=1x2=1f(x3)=18x3=2ab2）用黄金分割法缩小区间用黄金分割法缩小区间 第一次缩小区间：第一次缩小区间： x1=0+0.382(2-0)=0.764, f1=0.282 x2=0+0.618(2-0)=1.236, f2=2.72 由于由于f10.2,应继续缩小区间应继续缩小区间3.3 3.3 黄金分割法黄金分割法

35、f(x1)=0.282x1=0.764f(x2)=2.72x2=1.236abb3.3 3.3 黄金分割法黄金分割法第二次缩小区间：第二次缩小区间： 令令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382 (1.236-0)=0.472, f1=0.317 由于由于f1f2, 故故新区间新区间a, b=x1, b=0.472, 1.236 由于由于 b-a=1.236-0.472=0.7640.2, 应继续缩小区间应继续缩小区间f(x1)=0.282x1=0.764f(x2)=2.72x2=1.236abbx2f(x2)x1f(x1)a 第三次缩小区间：第三次缩小区间：

36、令令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618 (1.236-0.472)=0.944, f2=0.747 由于由于f10.2, 应继续缩小区间。应继续缩小区间。3.3 3.3 黄金分割法黄金分割法 第四次缩小区间：第四次缩小区间： 令令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382 (0.944-0.472)=0.652, f1=0.223由于由于f10.2, 应继续缩小区间。应继续缩小区间。第五次缩小区间：第五次缩小区间：令令 x2=x1=0.652, f2=f1=0.223 x1=0.472+0.382 (0.764

37、-0.472)=0.584, f1=0.262由于由于f1f2, 故故新区间新区间a,b=x1,b=0.584, 0.764因为因为 b-a=0.764-0.584=0.180.2, 停止迭代。停止迭代。黄金分割法黄金分割法求的的极小点与极小值：求的的极小点与极小值： x=0.5 (0.584+0.764)=0.674, f(x)=0.2223.3 3.3 黄金分割法黄金分割法求导运算求导运算求的极小点与极小值：求的极小点与极小值： x=0.667, f(x)=0.222一、牛顿法一、牛顿法3.4 3.4 插值方法插值方法利用一点的利用一点的函数值函数值、一阶导数一阶导数以及以及二阶二阶导数导

38、数构造二次多项构造二次多项式。用构造的二次式。用构造的二次多项式的极小点作多项式的极小点作为原函数极小点的为原函数极小点的近似。近似。x*xf(x) x20(x) x0f(x) 1(x) x1一、牛顿法一、牛顿法设设f(x)为一个连续可微的函数，则在点为一个连续可微的函数，则在点x0附近附近进行泰勒展开并保留到二次项：进行泰勒展开并保留到二次项：2000001( )( )()()()()()2f xxf xfxxxfxxx1( )0 x用二次函数用二次函数(x)的极小点的极小点x1作为作为f(x)极小点的一个近似极小点的一个近似点。根据极值必要条件点。根据极值必要条件:3.4 3.4 插值方法

39、插值方法xf(x) x1x20(x) x*f(x) 1(x) x00010()()()0fxfxxx即即0100()()fxxxfx依此类推可得依此类推可得牛顿迭代公式：牛顿迭代公式：1()()kkkkfxxxfx一、牛顿法一、牛顿法3.4 3.4 插值方法插值方法x2x1x0 x*f(x) f(x) 0(x) 1(x) 在在x0处用一抛物线处用一抛物线(x)代替曲线代替曲线 f(x)，相当于用一斜直线相当于用一斜直线 (x)代替曲线代替曲线 f (x) 。这样各个近似点。这样各个近似点是通过对作是通过对作f (x)切切线求得与轴的交点线求得与轴的交点找到的，所以有时找到的，所以有时牛顿法又称

40、作切线牛顿法又称作切线法。法。x2x1x0 x*f(x) f(x) 0(x) 1(x) f (x) f (x) x*x0 1(x) x2x11kkxx牛顿法牛顿法开开 始始计算计算 ，*1kxx给定初始点给定初始点 ，误差，误差 ,令令k=00 x( ),( )kkf xf x计算计算 ，1()()kkkkfxxxfx1kk结结 束束数值数值 k 0 1 2 3 4 3 5.1667 4.33474 4.03960 4.00066 -52 153.35183 32.30199 3.38299 0.00551 24 184.33332 109.44586 86.86992 84.04720 5.

41、1667 4.33474 4.03960 4.00066 4.00059 2.1667 0.83196 0.29514 0.03894 0.00007kxkfxkfx给定初始点给定初始点x0=3，=0.001，计算公式：，计算公式：1()()kkkkfxxxfx 2122412fxxx函数的二阶导数：函数的二阶导数：32( )4121216fxxxx解：解： 函数的一阶导数：函数的一阶导数：3.4 3.4 插值方法插值方法1kx1kkxx= 优点优点：1）收敛速度快。）收敛速度快。 缺点缺点：1）要计算函数的一阶和二阶导数，增加每次）要计算函数的一阶和二阶导数，增加每次 迭代的工作量。迭代的工

42、作量。 2）数值微分计算函数二阶导数，舍入误差将）数值微分计算函数二阶导数，舍入误差将 严重影响牛顿法的收敛速度，严重影响牛顿法的收敛速度， f (x)的值越的值越 小问题越严重。小问题越严重。 3）牛顿法要求）牛顿法要求初始点离极小点不太远初始点离极小点不太远，否则，否则 可能使极小化序列发散或收敛到非极小点。可能使极小化序列发散或收敛到非极小点。一、牛顿法一、牛顿法3.4 3.4 插值方法插值方法1()()kkkkfxxxfx(1)( )()( )kkKkXXd二、二次插值法（二、二次插值法（）在给定的在给定的单峰区间单峰区间中，利用目标函数上的中，利用目标函数上的三个点三个点来来构构造造

43、一个一个二次插值函数二次插值函数，以近似地表达，以近似地表达原目标函数原目标函数 f(a)，并，并求这个插值函数的求这个插值函数的极小点极小点近似作为原目标函数的近似作为原目标函数的极小点极小点。3.4 3.4 插值方法插值方法2( )=ABCp xxxB=-2Cpxf(x)xf1x1f2x2f3x3xpx*y0 xxp1x1x2xpx3xy0 x*y1y2ypy3x1x2xpx*y1y2ypyp1xpxp1x1x2xpx3xy0 x*y1y2ypy3x2x3xy0 x*y2ypy3yp1211112222223333p( )ABCp()ABCp()ABCxxxfxxxfxxxf构造的构造的上

44、的三个点上的三个点: : 解得解得系数系数222222231312123122331231312123122331()()()()()()()()()()()()xxfxxfxxfBxxxxxxxxfxxfxxfCxxxxxx 222222231312123231312123()()()122 ()()()pxxfxxfxxfBCxxfxxfxxf 二、二次插值法（二、二次插值法（）3.4 3.4 插值方法插值方法2pxx二次插值法二次插值法开开 始始计算计算 ，*2min,pyyy给定给定 ,123123x x x y y y ,ppx y缩短区间名缩短区间名称置换称置换结结 束束x1x2x

45、px3xy0 x*y1y2ypy3x1x2xpx3x0 x*yy1y2ypy3*2min,pyyy二次插值法程序编制换名方法二次插值法程序编制换名方法(1)(1)1) x2xp y2yp y2xp y2 ypyp y2y2y3xpx1x2x3xx3x2 y2ypypy1y2xpx1x2x3xx1（1 1）二次插值法只要求）二次插值法只要求f (x)连续，不要求其一阶可微；连续，不要求其一阶可微； （2 2）收敛速度比黄金分割法快，但可靠性不如黄金分割）收敛速度比黄金分割法快，但可靠性不如黄金分割 法好，程序也较长。法好，程序也较长。特点：特点：3.4 3.4 插值方法插值方法二、二次插值法（二

46、、二次插值法（）例例 3-3 用二次插值法求函数用二次插值法求函数f(X)=3x3-4x+2的极小点，的极小点， 给定给定 x0=0, =0.2。解解 1）确定初始区间确定初始区间:a,b=0,22）用二次插值法逼近极小点用二次插值法逼近极小点 相邻三点的函数值相邻三点的函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式：代入公式：2222222313121232313121231 ()()()2 ()()()pxxfxxfxxfxxxfxx fxxfxp0.555, fp=0.292 在新区间，相邻三点的函数值在新区间，相邻三点的函数值: x1=0,

47、 x2=0.555, x3=1; f1=2, f2=0.292, f3=1. xp=0.607, fp=0.243 由于由于fpx2, 新区间新区间a, b=x2, b=0.555,1 |x2-xp |=|0.555-0.607|=0.0520.2, 迭代终止。迭代终止。 x*= 0.607, f*=0.243由于由于fpf2, xp 0.2, 应继续迭代。应继续迭代。yp y2y2y3xpx3x2x1x2x3xx2x3xp 第四章 无约束优化方法4.1 最速下降法4.2 牛顿型方法4.3 共轭梯度法4.6 鲍威尔方法4.4 变尺度法4.5 坐标轮换法4.7 单形替换法无约束优化问题表达形式：

48、无约束优化问题表达形式：12TnXx xx求设计变量求设计变量()minf X 使目标函数使目标函数 数值迭代算法公式数值迭代算法公式:1kkkkXXa d从选定的某从选定的某初始点初始点X0出发，沿着以一定规律产生出发，沿着以一定规律产生的的搜索方向搜索方向d k,取适当的取适当的迭代步长迭代步长ak ,逐次搜寻函逐次搜寻函数值下降的新迭代点数值下降的新迭代点Xk+1,使之逐步逼近最优点使之逐步逼近最优点X*。概概 述述无约束优化无约束优化方法分类方法分类间接法间接法:利用目标函数的利用目标函数的一阶或二阶导数一阶或二阶导数直接法直接法:利用利用目标函数值目标函数值最速下降法、牛顿法、共轭梯

49、度法、变尺度法最速下降法、牛顿法、共轭梯度法、变尺度法坐标轮换法、鲍威尔方法、单形替换法等坐标轮换法、鲍威尔方法、单形替换法等 把把初始点初始点X0 、搜索方向搜索方向d k、迭代步长迭代步长ak 称为优化方称为优化方法算法的三要素。其中搜索方向法算法的三要素。其中搜索方向d k从根本上决定若从根本上决定若一个算法的成败、收敛速率的快慢等。一个算法的成败、收敛速率的快慢等。 无约束优化方法主要不同点在于无约束优化方法主要不同点在于构造搜索方向构造搜索方向上的上的差别。差别。 概概 述述满足收敛条满足收敛条件？件？开开 始始给定给定X0、d0*XXa d形成新的形成新的 d计算最佳步长计算最佳步

50、长 ，使，使 极小极小 *()f Xd结结 束束搜索方向搜索方向 d 取该点负梯度方向取该点负梯度方向-f(X) (最速下最速下降方向降方向)，使函数值在，使函数值在该点附近该点附近的范围内下降最的范围内下降最快。快。4.1 4.1 最速下降法最速下降法1(0,1,2,)kkkkXXdk1() (0,1,2,)kkkkXXaf Xkx1x20为了使目标函数值沿搜索方向为了使目标函数值沿搜索方向-f(Xk) 能够获得最大能够获得最大的下降值，其步长因子的下降值，其步长因子 ak 应取一维搜索的最佳步长应取一维搜索的最佳步长:1()kf X4.1 4.1 最速下降法最速下降法( )()kkf Xa

51、 f X 可以得最佳步长可以得最佳步长设：设：( )0 根据一元函数极值的必要条件根据一元函数极值的必要条件()kkkf Xaf Xmin ()kkaf Xa f X 复合函数求导公式得复合函数求导公式得 ( ) 1()()0kTkf Xf X1()0kTkdd4.1 4.1 最速下降法最速下降法由此可知，在最速下降法中，相邻两个迭代点由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直上的函数梯度相互垂直(正交正交)。而搜索方向就。而搜索方向就是负梯度方向，因此是负梯度方向，因此相邻两个搜索方向相邻两个搜索方向互相垂互相垂直直。( )()kkkf Xaf X ()Tkkkf Xf X

52、()kf X01()kkkkXXaf X相邻两个搜索方向的关系相邻两个搜索方向的关系迭代点向函数极小点靠迭代点向函数极小点靠近的过程，走的是曲折近的过程，走的是曲折的路线。形成的路线。形成“之之”字字形的锯齿现象。在远离形的锯齿现象。在远离极小点的位置，每次迭极小点的位置，每次迭代可使函数值有较多的代可使函数值有较多的下降。在接近极小点的下降。在接近极小点的位置，由于锯齿现象使位置，由于锯齿现象使每次迭代行进的距离缩每次迭代行进的距离缩短，收敛速度减慢。短，收敛速度减慢。 最速下降法的搜索路径最速下降法的搜索路径4.1 4.1 最速下降法最速下降法x1x201kkXX开开 始始计算计算 ，1*

53、kXX给定初始点给定初始点 ，误差，误差 ,令令k=00a()kkdf X计算计算 ，1kkkkXXd1kk计算计算 ，:min ()kkkkf Xd结结 束束4.1 4.1 最速下降法最速下降法例例41 用最速下降法求下列目标函数的极小点。用最速下降法求下列目标函数的极小点。初始点为初始点为 X (0)=2, 2T解解 初始点梯度为：初始点梯度为：01(0)22()50 xxf Xx沿负梯度方向进行一维搜索沿负梯度方向进行一维搜索:(1)(0)(0)0()XXf X2212()25f Xxx1()kkkkXXaf X24-2100 000242 10041000为一维搜索最佳步长，应满足极值

54、必要条件为一维搜索最佳步长，应满足极值必要条件 (1)2200()(24)25(2 100)f X4.1 4.1 最速下降法最速下降法008(24)5000(2 100)0算出一维搜索最佳步长算出一维搜索最佳步长 06260.020 030 7231 2524.1 4.1 最速下降法最速下降法第一次迭代设计点位置和函数值第一次迭代设计点位置和函数值 0(1)20241.919 8772 1000.307178 5 10X(1)()3.686164f X继续作下去，经继续作下去，经10次迭代后，得到最优解次迭代后，得到最优解 00TX()0f X最速下降法评价：最速下降法评价：迭代过程简单，对初

55、始点选择迭代过程简单，对初始点选择要求不高。要求不高。梯度方向目标函数值下降迅速梯度方向目标函数值下降迅速只是个只是个局部性质局部性质，从整体来看，从整体来看，不一定是收敛最快的方向。不一定是收敛最快的方向。梯度法相邻两次搜索方向的正梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近点时逼近速度较快，而在接近极小点时逼近速度较慢。极小点时逼近速度较慢。4.1 4.1 最速下降法最速下降法X(k)S(k)S(k+1)X(k+1)X(k+2)X(k+3)X*f(X)=Ckf(X)=Ck+1f(

56、X)=Ck+31 1、牛顿法、牛顿法 在在Xk邻域内用一个二次函数邻域内用一个二次函数(X) 来近似代替原来近似代替原目标函数，并将目标函数，并将(X)的极小点作为对目标函数的极小点作为对目标函数f(X) 求优的下一个迭代点。经多次迭代，使之逼近目求优的下一个迭代点。经多次迭代，使之逼近目标函数标函数f(X) 的极小点。的极小点。 ()()()() ()1()()2kkTkkTkf XXf Xf XXXXXXX G1()0kX1()()0kkkf XXXG4.2 4.2 牛顿型方法牛顿型方法()X设设 为为 的极小值点：的极小值点：1kX11()kkkXXGf X牛顿法迭代公式牛顿法迭代公式:

57、 4.2 4.2 牛顿型方法牛顿型方法1()()kkkG XXf X 11()()kkkXXGf X 1()()0kkkf XXXG例例42 用牛顿法求下列目标函数的极小点。初始用牛顿法求下列目标函数的极小点。初始点为点为X0=2,2T解解 初始点梯度：初始点梯度：1(0)22()50 xf Xx海赛矩阵海赛矩阵:222112(0)222212()ffxx xG Xffx xx 2212()25f Xxx11()kkkXXGf X410020050带入到牛顿迭代公式带入到牛顿迭代公式 ：海赛矩阵逆阵：海赛矩阵逆阵：11()kkkXXGf X11021050G1010()XXGf X102402

58、121000050 4.2 4.2 牛顿型方法牛顿型方法牛顿法缺陷：牛顿法缺陷： 从牛顿法迭代公式的推演中可以看到，迭从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并代点的位置是按照极值条件确定的，其中并未含有沿下降方向未含有沿下降方向搜寻的概念。因此对于搜寻的概念。因此对于非非二次函数二次函数，如果采用上述牛顿迭代公式，有，如果采用上述牛顿迭代公式，有时会使函数值上升。时会使函数值上升。4.2 4.2 牛顿型方法牛顿型方法11()kkkXXGf X2、阻尼牛顿法、阻尼牛顿法 11()kkkkkkkXXdXGf Xk:阻尼因子阻尼因子 ，沿牛顿方向进行，沿牛顿方向进行

59、一维搜索的一维搜索的 最佳步长最佳步长，由下式求得：，由下式求得： 1()()min()kkkkkkkf Xf Xdf Xd4.2 4.2 牛顿型方法牛顿型方法1kkXX开开 始始给定初始点给定初始点 ，误差，误差 ,令令k=00a 计算计算 ，1()kkdGf X计算计算 ，1kkkkXXd1kk计算计算 ，:min ()kkkkf Xd阻尼牛顿法阻尼牛顿法4.2 4.2 牛顿型方法牛顿型方法1*kXX结结 束束牛顿型方法评价：牛顿型方法评价： （1） 若迭代点的海赛矩阵为奇异，则很难甚至无若迭代点的海赛矩阵为奇异，则很难甚至无 法求逆矩阵，进而不能构造牛顿法方向；法求逆矩阵，进而不能构造牛

60、顿法方向； （2） 不仅要计算梯度，还要求海赛矩阵及其逆矩不仅要计算梯度，还要求海赛矩阵及其逆矩 阵，计算量和存储量大。阵，计算量和存储量大。 4.2 4.2 牛顿型方法牛顿型方法为了克服最速下降法的锯齿现象，提高收敛速度为了克服最速下降法的锯齿现象，提高收敛速度;同时克服牛顿型方法需要计算二阶导数及其逆阵，同时克服牛顿型方法需要计算二阶导数及其逆阵，计算量大的现象，发展了一类共轭方向法。该方计算量大的现象，发展了一类共轭方向法。该方法的搜索方向是法的搜索方向是共轭方向共轭方向。一、共轭方向的概念一、共轭方向的概念12TTfXX GXb Xc4.34.3 共轭梯度法共轭梯度法 式中：式中：c为