现代设计方法第三章

1、 现代设计方法长安大学工程机械学院建筑机械系长安大学工程机械学院建筑机械系长安大学工程机械学院建筑机械系第三章第三章 优化设计优化设计 优化设计概述优化设计概述1 1 一维探索优化一维探索优化2 2 约束问题的优化约束问题的优化4 4 无约束多维问题的优化无约束多维问题的优化3 3 多目标函数的优化多目标函数的优化5 5 优化设计的数学分析基础优化设计的数学分析基础2 2优化设计概述优化设计概述 优化设计是20世纪60年代初，在电子计算机技术广泛应用的基础上发展起来的一门新的设计方法。主要采用“自动探索”的方式和最优数学方法，在计算机上进行半自动或自动设计，利用最优化原理和方法寻求最优设计参数

2、的一门先进设计技术。优化设计优化设计：根据给定的设计要求和现有的设计条件，应用专业理论和优化方法，在计算机上满足给定设计要求的许多可行方案中，按给定的目标自动地选出最优的设计方案。机械优化设计机械优化设计：在满足一定约束的前提下，寻找一组设计参数，使机械产品单项设计指标达到最优的过程。 优化设计概述优化设计概述优化设计概述优化设计概述机械优化设计机械优化设计 机械设计理论+优化方法得到设计参数的指在一定条件指在一定条件( (各种设计因素各种设计因素) ) 影响下所影响下所能得到的最佳设计值。能得到的最佳设计值。 （相对概念）（相对概念）优化设计概述优化设计概述机械优化设计方法机械优化设计方法1

3、)解析法: 主要利用微分学和变分学的理论，适应解决小型和简单问题；2)数值计算方法: 使利用已知信息，通过迭代计算来逼近最优化问题的解，因此运算量很大，直到计算机出现后才得以实现。 优化设计概述优化设计概述传统设计传统设计：在调查分析的基础上，参考同类产品通过估算、经验类比或试验等方法来确定初始方案，然后通过计算各个参数是否能满足设计指标的要求，如果不符合要求就凭借经验对参数进行修改，反复进行分析计算性能检验参数修改，直到符合设计指标为止。 优化设计优化设计：借助计算机技术，应用一些精度较高的力学的数值分析方法（如有限元法等）进行分析计算，并从大量的可行设计方案中寻找到一种最优的设计方案。 优

4、化设计概述优化设计概述 优化设计问题数学模型的优化设计问题数学模型的：设计变量设计变量、目目标函数标函数和和约束条件约束条件。 * *优化设计问题的数学模型优化设计问题的数学模型一个优化设计问题一般包括三个部分：一个优化设计问题一般包括三个部分：1.1.需要合理选择的一组独立参数，称为需要合理选择的一组独立参数，称为设计变量设计变量；2.2.需要最佳满足的设计目标，这个设计目标是设计变需要最佳满足的设计目标，这个设计目标是设计变 量的函数，称为量的函数，称为目标函数目标函数；3.3.所选择的设计变量必须满足一定的限制条件，称为所选择的设计变量必须满足一定的限制条件，称为 约束条件约束条件（或称

5、设计约束）。（或称设计约束）。优化设计概述优化设计概述* *优化设计问题的数学模型优化设计问题的数学模型在设计过程中进行选择并最终必须确定的各项在设计过程中进行选择并最终必须确定的各项 独立独立参数，称为设计变量。参数，称为设计变量。 设计变量向量：设计变量向量：设计常量：根据设计要求设计常量：根据设计要求事先给定事先给定的参数的参数设计变量：在设计过程中设计变量：在设计过程中进行进行优选的参数优选的参数连续设计变量：有界连续变化的量。连续设计变量：有界连续变化的量。离散设计变量：表示为离散量。离散设计变量：表示为离散量。12Tnxx xx优化设计概述优化设计概述* *优化设计问题的数学模型优

6、化设计问题的数学模型 优化设计的维数：优化设计的维数：设计变量的数目称为优化设计的维数，设计变量的数目称为优化设计的维数， 如有如有n(n=1n(n=1，2 2，)个设计变量，为个设计变量，为n n维维 设计问题。设计问题。 任意一个任意一个特定的向量特定的向量都可以说是一个都可以说是一个“设计设计”12 Txx x123 Txx x x二维和三维的设计空间二维和三维的设计空间优化设计概述优化设计概述* *优化设计问题的数学模型优化设计问题的数学模型 设计空间：设计空间：由由n n个设计向量为坐标所组成的实空间个设计向量为坐标所组成的实空间 设计空间的维数设计空间的维数（设计的自由度设计的自由

7、度）：设计变量愈多，则设）：设计变量愈多，则设计的自由度愈大、可供选择的方案愈多，设计愈灵活，但难计的自由度愈大、可供选择的方案愈多，设计愈灵活，但难度亦愈大、求解亦愈复杂。度亦愈大、求解亦愈复杂。 含有含有210210个设计变量的为个设计变量的为小型小型设计问题设计问题 10501050个为个为中型中型设计问题设计问题 5050个以上个以上的为的为大型大型设计问题设计问题优化设计概述优化设计概述* *优化设计问题的数学模型优化设计问题的数学模型 约束条件：约束条件：在优化设计中，对设计变量在优化设计中，对设计变量取值时的限制条件取值时的限制条件，称为约束条件或设计约束，简称约束。称为约束条件

8、或设计约束，简称约束。 等式约束：等式约束： 对设计变量对设计变量取值的限制最取值的限制最严格（降低设计严格（降低设计维数维数）不等式约束：不等式约束： 要求设计点在设计空间中约束曲面要求设计点在设计空间中约束曲面 的一侧（包括曲面本身）的一侧（包括曲面本身） ( )0h x( ) 0ug x ( )0ug x 优化设计概述优化设计概述* *优化设计问题的数学模型优化设计问题的数学模型 目标函数（评价函数）：目标函数（评价函数）：把设计目标（设计指标）用把设计目标（设计指标）用设计设计 变量的函数形式表示变量的函数形式表示出来，这个函数就叫做目标函数，用出来，这个函数就叫做目标函数，用 它可以

9、评价设计方案的好坏，所以它又被称作评价函数。它可以评价设计方案的好坏，所以它又被称作评价函数。12( )( ,)minnf xf x xx12( )( ,)maxnf xf x xx12( )( ,)minnf xf x xx12( )( ,)nf xf x xx优化设计概述优化设计概述* *优化设计问题的数学模型优化设计问题的数学模型 单目标函数优化问题单目标函数优化问题：在最优化设计问题中，可以在最优化设计问题中，可以只有一只有一 个个目标函数。目标函数。 多目标函数优化问题多目标函数优化问题：当在同一设计中要提出当在同一设计中要提出多个目标函多个目标函 数数时，这种问题称为多目标函数的优

10、化问题。时，这种问题称为多目标函数的优化问题。 1112221212( )( ,)( )( ,)( )( ,)nnqqnf xf x xxf xf x xxfxfx xx1122( )( )( ).( )qqf xW f xW fxW fxWq：加权因子，是个非负系数。：加权因子，是个非负系数。 优化设计概述优化设计概述* *优化设计问题的数学模型优化设计问题的数学模型1212( )( ,)min( )0(1,2, )( )0(1,2,)Tnnuxx xxf xf x xxh xlgxum求设计变量使目标函数且满足约束条件和约束优化问题约束优化问题无约束优化问题：无约束优化问题：=u=0优化设

11、计概述优化设计概述* *优化设计问题的数学模型优化设计问题的数学模型 建立优化的数学模型，在计算机上求得的解，就称为建立优化的数学模型，在计算机上求得的解，就称为优化优化 问题的最优解问题的最优解，它包括：，它包括： 1 1）最优方案（最优点）最优方案（最优点）： 2 2）最优目标函数值最优目标函数值：*12,Tnxx xx*()min( )f xf x优化设计概述优化设计概述* *优化设计问题的数学模型优化设计问题的数学模型建立数学模型要求建立数学模型要求：1 1）希望建立一个尽可能）希望建立一个尽可能完善完善的数学模型，的数学模型，精确精确的的表表 达实际问题；达实际问题；2 2）力求所建

12、立的数学模型尽可能的）力求所建立的数学模型尽可能的简单简单，方便计，方便计算算 求解。求解。优化设计概述优化设计概述* *优化设计问题的数学模型优化设计问题的数学模型作业：作业：现用薄板制造一体积现用薄板制造一体积5m5m3 3，长度不小于，长度不小于4m4m的无上盖的的无上盖的长方体货箱。要求该货箱的钢板耗费量最少，试确定货箱长方体货箱。要求该货箱的钢板耗费量最少，试确定货箱的长、宽和高的尺寸，写出该的长、宽和高的尺寸，写出该优化问题的数学模型。优化问题的数学模型。优化设计概述优化设计概述* *优化设计问题的数学模型优化设计问题的数学模型优化问题的几何解释：优化问题的几何解释：无约束优化问题

13、无约束优化问题：目标函数的极小点就是等值面的中心：目标函数的极小点就是等值面的中心等式约束优化问题等式约束优化问题：设计变量：设计变量x的设计点必须在的设计点必须在 所表示的面或线上所表示的面或线上不等式约束优化问题不等式约束优化问题：可行点：可行点 非可行点非可行点 边界点边界点( )0h x( )0ugx ( )0ugx ( )0ugx优化设计概述优化设计概述* *数学解析法：数学解析法：把优化对象用数学模型描述出来后，用数学解析法（如把优化对象用数学模型描述出来后，用数学解析法（如微分法、变分法等）来求出最优解。微分法、变分法等）来求出最优解。图解法：图解法：直接用作图的方法来求解优化问

14、题，通过画目标函数和约束直接用作图的方法来求解优化问题，通过画目标函数和约束函数的图形，求出最优解。特点是简单、直观，但仅限于函数的图形，求出最优解。特点是简单、直观，但仅限于n2的低维优化的低维优化问题的求解。问题的求解。 数值迭代法：数值迭代法：依赖于计算机的数值计算特点而产生的，它具有一定逻依赖于计算机的数值计算特点而产生的，它具有一定逻辑结构并按一定格式反复迭代计算，逐步逼近优化问题最优解的一种方辑结构并按一定格式反复迭代计算，逐步逼近优化问题最优解的一种方法。不仅可以用于求解法。不仅可以用于求解复杂函数的优化解，还可以用于处理没有数学解析表达复杂函数的优化解，还可以用于处理没有数学解

15、析表达式的优化设计问题。式的优化设计问题。优化设计概述优化设计概述* *数值迭代法数值迭代法数值迭代法的核心：数值迭代法的核心： 1 1）建立搜索方向）建立搜索方向s(k) 2 2）计算最佳步长）计算最佳步长(k) 3 3）如何判断是否找到最优点）如何判断是否找到最优点迭代法的基本思想：迭代法的基本思想：步步逼近、步步下降步步逼近、步步下降优化设计概述优化设计概述* *数值迭代法的迭代终止准则数值迭代法的迭代终止准则（是充分小的正数，且是充分小的正数，且00）1. 1.点距足够小准则：点距足够小准则： 当相邻两个设计点的移动距离已达到充分小时当相邻两个设计点的移动距离已达到充分小时2. 2.函

16、数下降量足够小准则：函数下降量足够小准则： 当函数值的下降量充分小时，也就是前后两个迭代点间当函数值的下降量充分小时，也就是前后两个迭代点间函数的目标函数值充分接近时函数的目标函数值充分接近时11kkxx12()()kkf xf x13()()()kkkf xf xf x优化设计概述优化设计概述* *数值迭代法的迭代终止准则数值迭代法的迭代终止准则（是充分小的正数，且是充分小的正数，且00）3. 3.函数梯度充分小准则：函数梯度充分小准则： 根据极值存在的必要条件（函数极值点的必要条件是函根据极值存在的必要条件（函数极值点的必要条件是函数在这一点的梯度的模为零），则迭代点的函数梯度的模充数在这

17、一点的梯度的模为零），则迭代点的函数梯度的模充分小时，可以作为迭代的终止准则。分小时，可以作为迭代的终止准则。14()kf x优化设计的数学分析基础优化设计的数学分析基础* * 一个多元函数可用一个多元函数可用偏导数偏导数的概念来研究函数沿各坐标方的概念来研究函数沿各坐标方向的变化率。向的变化率。 二元函数的偏导数：二元函数的偏导数：10201201020101201020011102021020022( ,)(,),lim,limxxxxf x xx xxf xx xf xxfxxf xxxf xxfxx一个二元函数在点处的偏导数:优化设计的数学分析基础优化设计的数学分析基础* *01201

18、02010120210200( ,)(,),limsxf x xx xxsf xx xxf xxfss 称函数在点处沿某一方向的变化率为该函数沿此方向的方向导数，公式可以表示为优化设计的数学分析基础优化设计的数学分析基础* *2101x2x10 x20 x0 x1x2xs偏导数偏导数与与方向导数方向导数之间的之间的数量关系数量关系：00010120210200101201020101101202101202021212,lim, lim,(,) lim coscossxssxxf xx xxf xxfssf xx xf xxxxsf xx xxf xx xxxsffxx 0001212cosc

19、osxxxfffsxx优化设计的数学分析基础优化设计的数学分析基础* * 方向导数方向导数 目标函数在设计点沿任意方向目标函数在设计点沿任意方向s的函数值的变化率的函数值的变化率0000012012112i( ,)coscoscoscoscosnnniixnixxxxinf x xxxsfffffsxxxxsx元函数在点 处沿方向 的方向导数可以表示成：其中，是方向 与坐标轴 方向之间夹角的余弦。优化设计的数学分析基础优化设计的数学分析基础* * 作业作业: :21212012112212( )(,),41 1436Tf xf xxx xxssss设目标函数求点处沿 和两个方向的方向导数。向量

20、 的方向为：，向量 的方向为：， 方向导数方向导数2101x2x10 x20 x0 x1x2xs优化设计的数学分析基础优化设计的数学分析基础 梯度梯度 目标函数在设计点目标函数在设计点x处沿设计空间坐标轴一阶偏导数组成的向量处沿设计空间坐标轴一阶偏导数组成的向量0011200122( ,)( ),Txxfxfff x xxf xfxxx二元函数在点 处的梯度是0120102( ,)cos()cosxff x xxsf xs二元函数在点 处的方向导数等于该点处的梯度与方向单位向量的内积。* *优化设计的数学分析基础优化设计的数学分析基础 梯度梯度1 1）梯度是一个向量；）梯度是一个向量；2 2）

21、梯度方向是方向导数最大的方）梯度方向是方向导数最大的方 向，向， 即函数值变化最快的方向即函数值变化最快的方向 ；3 3）梯度方向是等值面（线）法线方向）梯度方向是等值面（线）法线方向 。* *优化设计的数学分析基础优化设计的数学分析基础 多元函数的梯度多元函数的梯度12010200( ,)(,)nnf x xxx xxx函数在点处的梯度是0001212Tnxnxfxffffxfxxxxfx* *优化设计的数学分析基础优化设计的数学分析基础 多元函数的梯度多元函数的梯度 作业：作业： * *221212120,42500Tf x xxxxxx求二元函数在点处函数变化率最大的方向和数值。2212

22、121212,4253 22 2TTfx xxxxxxx求二元函数在点和点处的梯度，并作图表示。方向导数与梯度的关系：方向导数与梯度的关系：000()() cos(, )Txff xsf xf ss 优化设计的数学分析基础优化设计的数学分析基础结论：结论：（1）x0处函数的梯度方向是该点函数 值上升最快的方向，与梯度相反 的方向是该点函数值下降最快的 方向，它们均为等值线（或等直 面）在x0处的法线方向，梯度的 大小就是它的模长;（2）梯度方向仅反映点x0处邻域内的 函数性质，离开该邻域后，沿该 方向的目标函数值就不一定变化 得最快;* *优化设计的数学分析基础优化设计的数学分析基础结论：结论

23、：（3）当=0时,x0处目标函数的方向 导数最大值 ,该方向为 梯度方向; (4) 当=/2时,x0处目标函数的方 向导数值为0,该方向为等值线 (或等直面)在x0处的切线方向; (5) 当=时,x0处目标函数值的变 化率 的最小值为 ； (6) 处目标函数的方向导数等于梯度 在该方向上的投影。0()f x0( )/f xs0()f x * *优化设计的数学分析基础优化设计的数学分析基础* *020002200( )1( )()()()2()f xxxf xf xfxxfxxxxxxxx 在点处的泰勒展开式：其中，一元函数的泰勒展开一元函数的泰勒展开二元函数的泰勒展开二元函数的泰勒展开0000

24、01201020222221210201211222212112211102220( ,)(,)1( ,)(,)22xxxxxf x xx xxffffff x xf xxxxxxxxxxxx xxxxxxxx 在点处的泰勒展开式：其中，优化设计的数学分析基础优化设计的数学分析基础* *二元函数泰勒展开式的矩阵形式：二元函数泰勒展开式的矩阵形式： 0022211211012222212221220001212xxTTffxx xxxfff xf xxxxxxxffx xxf xf xxxfxx 201201020( ,)(,)( )fxf x xx xxH x是函数在点处的Hessian矩阵，

25、用表示对称矩阵对称矩阵二元函数的泰勒展开二元函数的泰勒展开优化设计的数学分析基础优化设计的数学分析基础* *作业：作业：二元函数的泰勒展开二元函数的泰勒展开3322012121( )3391 1Tf xxxxxxx将函数在点处用泰勒展开的方法简化成一个二次函数。22112212( )28910f xxx xxxx将写成向量及矩阵形式优化设计的数学分析基础优化设计的数学分析基础* *多多元函数的泰勒展开元函数的泰勒展开20001()2TTfxfxfxxxfxx 0012Tnxffffxxxx 是函数在该点的梯度是函数在该点的梯度022221121222202122222212nnnnnx xff

26、fxx xx xffffxx xxx xfffxxxxx 多多元函数的元函数的Hessian矩阵矩阵优化设计的数学分析基础优化设计的数学分析基础* *目标函数无约束极值的存在性目标函数无约束极值的存在性0( )0,0,00Tx xf x梯度 00Hessianx xx xH xH x矩阵正定（负定），即的各阶主子式均大于零（或负、正相间）*1212( )( ,)( ,)Tnnf xf x xxxx xx多元函数在点处取得极值必要条件必要条件充分条件充分条件优化设计的数学分析基础优化设计的数学分析基础* *12*12*( )( ,)( ,)HessiannTnf xf x xxxx xxH xH

27、 x多元函数在点处取得极小值的充要条件是：函数在该点的梯度为0，且矩阵正定，即各阶主子式均大于零。12*12*( )( ,)( ,)HessiannTnf xf x xxxx xxH x多元函数在点处取得极大值的充要条件是：函数在该点的梯度为0，且矩阵负定，即各阶主子式负、正相间。目标函数无约束极值的存在性目标函数无约束极值的存在性优化设计的数学分析基础优化设计的数学分析基础* *目标函数无约束极值的存在性目标函数无约束极值的存在性 例题：例题：4222112121( )245,4f xxx xxxx证明函数在点（2）处具有极小值。优化设计的数学分析基础优化设计的数学分析基础* *目标函数的凸

28、性目标函数的凸性 一个下凸的函数，极值点只有一个，并且该点既是一个下凸的函数，极值点只有一个，并且该点既是局部极值点也是全局极值点，称这个函数具有局部极值点也是全局极值点，称这个函数具有凸性凸性。 优化设计的数学分析基础优化设计的数学分析基础* *目标函数的凸性目标函数的凸性 设设n维欧氏空间中的一个集合维欧氏空间中的一个集合, ,若连接其中任意两点若连接其中任意两点x1和和x2的直线都属于的直线都属于，则称这种集合，则称这种集合是一个是一个凸集凸集。 优化设计的数学分析基础优化设计的数学分析基础* *目标函数的凸性目标函数的凸性 具有凸性（表现为单峰性）或只有唯一的局部最优具有凸性（表现为单

29、峰性）或只有唯一的局部最优值，即全局最优值的函数，称为值，即全局最优值的函数，称为凸函数凸函数或或单峰函数单峰函数。 1212121212( )01( )(1)()(1) ()( )( )(1)()(1) ()f xxxf xfxxf xf xf xf xfxxf xf xf x设是一个凸集 上的函数，如果对任何实数（）以及对 中任意两点 和 恒有，则函数就是定义在凸集 上的一个凸函数。如果将上式中的等号去掉而写成严格的不等式：则称（ ）为严格凸函数。优化设计的数学分析基础优化设计的数学分析基础* *目标函数的凸性目标函数的凸性目标函数目标函数与与约束条件约束条件均为均为凸函数凸函数的优化问题

30、称为的优化问题称为凸规划凸规划。 001, |( )()2 |( )0,1,2, 3uRx f xf xRx gxum）若给定点x 则集合是凸集。）凸规划的可行域是凸集。）凸规划的任何局部最优解就是全局最优解。凸规划的性质凸规划的性质优化设计的数学分析基础优化设计的数学分析基础* *目标函数的凸性目标函数的凸性 如果目标函数在如果目标函数在上具有二阶连续导数，则上具有二阶连续导数，则f(x)为凸函为凸函数的充要条件是数的充要条件是H(x)处处半正定。处处半正定。 事先能通过事先能通过Hessian矩阵的正定性判断处目标函数是凸矩阵的正定性判断处目标函数是凸函数，则该函数的极值点就是全域最优点。

31、函数，则该函数的极值点就是全域最优点。优化设计的数学分析基础优化设计的数学分析基础* *目标函数的凸性目标函数的凸性 作业：作业：2212121212( )10460D|,1,2if xxxx xxxxxxi 证明函数在，上是凸函数。2212( )()f xxx 试判断函数的凸性。优化设计的数学分析基础优化设计的数学分析基础* *目标函数有约束极值的存在性目标函数有约束极值的存在性目标函数有约束极值要解决的两个问题：目标函数有约束极值要解决的两个问题：（1 1）判断约束极值点存在的条件；）判断约束极值点存在的条件；（2 2）判断找到的约束极值点是全域最优点还是局部极值点。）判断找到的约束极值点

32、是全域最优点还是局部极值点。优化设计的数学分析基础优化设计的数学分析基础* *目标函数有约束极值的存在性目标函数有约束极值的存在性Kuhn-Tucker优胜条件（优胜条件（K-T条件）条件） min( ) . . ( )0 (1,2, ) ( )0 (1,2,)nuf xxEsth xpgxumq为起作用约束个数为起作用约束个数*()0,()0ijg xh x*( )( ) 0ijig xh x与线性无关*1()()()0(1,2,)qiijjijf xg xhxijqmp 优化设计的数学分析基础优化设计的数学分析基础* *目标函数有约束极值的存在性目标函数有约束极值的存在性Kuhn-Tuck

33、er优胜条件的几何意义优胜条件的几何意义优化设计的数学分析基础优化设计的数学分析基础* *目标函数有约束极值的存在性目标函数有约束极值的存在性Kuhn-Tucker优胜条件的几何意义优胜条件的几何意义 1212k12120,0kkkkkkkkkf xg xgxf xg xgxxf xg xgx1)在极值点处和以及是线 性相关的，或者说可以看做是和 的线性组合。2)如果 点是极小点，那么目标函数的梯度 一定位于两个约束函数的梯度和形 成的夹角内，或者说它们的线性组合系数是正的。 优化设计的数学分析基础优化设计的数学分析基础* *目标函数有约束极值的存在性目标函数有约束极值的存在性Kuhn-Tuc

34、ker优胜条件举例优胜条件举例*2221221122231KT1,0 min( )2, s.t.( )10 ( )0 ( )0Txf xxxxRgxxxgxxgxx 试用条件判定点是否是下面优化问题的极值点。：对于单个变量（一维问题）的直接探索（搜索 或寻查）。多维多维问题的数值迭代法问题的数值迭代法1(0,1,2,)kkkkxxdk1()()()minkkkkkf xf xd 每步为每步为一维一维搜索搜索*()0 1 1）解析法解析法：2 2）数值解法数值解法的基本思想：确定的基本思想：确定 * *所在的搜索区间，所在的搜索区间， 然后根据区间消去原理不断缩小区间，然后根据区间消去原理不断缩

35、小区间， 从而获得从而获得 * *的数值近似解。的数值近似解。* *一维探索优化的数学表达一维探索优化的数学表达 一维探索：只有一个设计变量的直接探索方法一维探索：只有一个设计变量的直接探索方法 解决一维探索优化问题的关键：解决一维探索优化问题的关键： （1）缩短原始可行域的长度；）缩短原始可行域的长度； （2）减少新可行域内的计算量；）减少新可行域内的计算量； （3）改变目标函数的性质降低运算难度。）改变目标函数的性质降低运算难度。 (1)( )( )( )( ) (0,1,2,)()minkkkkkkkkxxs kf xsfxs函数在该区间只有一个极值点。12xxx12()( )()f x

36、f xf x“高高低低高高”* * （进退法/成功失败法）：12xxx 12( )( )( )f xf xf x“高高低低高高”* * 的基本步骤：10210112212320332332123132300122312231.()()() ,2xhxxhyf xyf xyyxxhyf xyyyyyyyx xyyhhxxxxyyyy选定初始点 ，初始步长 ，计算点，然后比较函数值和的大小。2.若，则试探方向正确，计算点和，比较 和 的大小。如果，则形成，找到所需的区间，即；如果，则需要继续向前搜索，这时候令，同时令，开01231313 , min( ,),max( ,)hyyya bx xx x

37、始新一轮的试探（这时候的是原来的二倍，步长加长了），直到找到时，新的搜索区间是。* * 的基本步骤：1200122121121212232033231233.2, ,() , min(yyhhxxxxyyxxyyxxxxxhffxyyyyya bx 若，则试探方法错误，需要反向，即令， 并且将和交换，即：；，然后得到新的和，用新的向前推出 （这里的已经反向了）。这时就得 到了新的三个点，以及三个试探点的函数值，则继续前 面的比较与，直至找到 时，新的搜索区间 是1313,),max(,)xxx。* * 例：例：210( )710 , 01f xxxa bxh试用进退法确定函数的一维优化的初始搜

38、索区间。其中，设初始点，初始搜索步长。* * 通过外推法，我们可以确定一个包含一元函数极值点的搜索区间，为了进一步找到极小点，我们需要不断的缩小搜索区间，消去不可能包含极小点的区间，使区间在缩小的过程中逐步向极小点靠拢，最后缩小到极小点附近一个极小的领域内。 这个时候，如果我们规定一个足够小的正数，称为收敛精度。则当区间长度达到足够小，即 取该区间的中点 作为极值点，这才能完成整个一维搜索 。kkba*1()2kkxab* * ：不断缩小区间所用的原理。 包括：1）直接法：直接比较试选点的函数值； 2）间接法：利用函数导数值的变化信息。* * 111111 , ()( )a bababf af

39、 b假定在搜索区间内任取两点 和 ，且，并计算和，可能出现三种情况：11111111111. ()( ) ,2. ()( ), 3. ()( ),f af ba bf af ba bf af ba b，由于函数的单峰性，极小点一定在内；，极小点一定在内；，极小点一定在内。* * 111111 , ()( )a bababf af b假定在搜索区间内任取两点 和 ，且，并计算和，可能出现三种情况：11111111.()( ) ,2.()( ),f af ba bf af ba b若，则取为缩短后的搜索区间；若，则取为缩短后的搜索区间。* * , ,( )a bxfx假定在搜索区间内取一点 并计算

40、它的导数值，可能出现三种情况：*1. ( )0 , 2. ( )0 , 3. ( )0fxx bfxa xfxxx，则新区间是；，则新区间是；，则在此点就是极小点。x fxabxx0 x fxabxx0 fxxabx0* * ： 缩短后的新区间长度（0 1）缩短前的原区间长度* * ：它是按照某种给定的规律来确定区间内插入点的位置的。插入点位置的确定是为了使区间缩短的更快，而不管函数值的分布规律。它包括：黄金分割法（0.618法）、裴波纳契（Fibonacci）法等。：这种方法是根据某点处的某些信息（如函数值、一阶导数、二阶导数等）来构造一个差值函数来逼近原来的函数，用插值函数的极小点作为区间

41、的插入点。它包括：二次差值法、三次插值法等。通过比较单峰区间内两个内分点的函数值，不断舍弃单峰区间的左端或者右端的一部分，使区间按照固定区间缩短率（=0.618）逐步缩短，直到极小点所在的区间缩短到给定的误差范围内，而得到近似最优解。 每次区间缩短都取相等的区间缩短率（），同时插入点距离两个端点有对称性。 0.61812()0.618()()0.618()bbabbaabaaba12121122 1 , 2 , ()0.618() ()0.618()()()a ba bxxxbbabbaxabaabayf xyf x）给定初始单峰区间和收敛精度 ，将 赋值为0.618）在区间内，取两个内分点

42、和 ，并计算其函数值： 和，12221221211111211211213 , ,()() , , ,yya xa xxbx xx yyxbbayf xyyx bx bxax xxy）比较函数值大小，根据区间消去法原理缩短区间：若，则极小点必在区间内，即为新区间,则为新区间内的第一个试验点，即令，而另一个试验点可按下式算出，它的函数值为；若，则极小点必在区间内，即为新区间，则为新区间内的第一个试验点，即令2222(),()yxabayf x，而另外一个试验点可以按下式给出。212*4315()()2yybabyxabyf x）进行迭代终止条件检验，检查区间是否缩短到足够小和函数值是否收敛到足够

43、近，即和，如果不满足条件，则转到第 ）步；满足条件则继续执行下一步。）输出最优解和最优函数值。2*( )2 ,35f xxxxx如图所示，对函数当给定搜索区间时，试用黄金分割法求极小点 。 和黄金分割法相似，都是在搜索区间内对称的取点，通过比较两点函数值逐步缩小初始单峰区间来搜索出满意的极小点x*。 与黄金分割法不同的是：黄金分割法每次迭代式按照同一区间缩短率=0.618来缩短区间，而斐波那契法每次迭代的区间缩短率是不同的，它是按斐波那契数列Fn产生的分数序列为缩短率来缩短区间的。， ，011FF12(2,3,)nnnFFFn斐波那契数： 凡是满足递推关系而产生的正数序列Fn，就称为斐波那契数

44、。n n0 0 1 1 2 23 34 45 56 67 78 89 910101111121213131414FnFn1 1 1 1 2 23 35 58 813132121343455558989144144233233377377610610 ，n n0 0 1 1 2 23 34 45 56 67 78 89 910101111121213131414FnFn1 1 1 1 2 23 35 58 813132121343455558989144144233233377377610610 区间缩短率区间缩短率用相邻两数的用相邻两数的前一数前一数与与后一数后一数之之比比产生，如计产生，如计

45、算五个点的函数值（即迭代四次，每次区间缩短率分别为算五个点的函数值（即迭代四次，每次区间缩短率分别为123412514342134233253 8521 32nnnnnnnnFFFFFFFFFFFFFFFF11234518FF ，n n0 0 1 1 2 23 34 45 56 67 78 89 910101111121213131414FnFn1 1 1 1 2 23 35 58 813132121343455558989144144233233377377610610 推广到计算推广到计算n n个点的函数值，经过个点的函数值，经过n-1n-1次迭代所获得的次迭代所获得的区间总缩短率区间总缩

46、短率为为11211nnnFFF ，11(1)1/n21/0.61830.618nnnnFFF）斐波那契法开始计算第一个内点（即第一次缩短率）就要用到，也就是首先要确定计算函数的次数（即计算的总点数 ），否则无法确定缩短率）与黄金分割法相比，收敛效果好，即计算相同试点数，斐波那契法总区间缩短率。黄金分割法的区间总缩短率。）斐波那契法每次的区间缩短率是变化的，当计算函数值的点数较多时，其区间缩短率将逼近。 ，11111101121a,b2nn11|()()Fn1,(2,3,)nnnnnnnnnnnnbababababaFbaFFFFFFn）由外推法（进退法）选定初始单峰区间。）确定所需计算的试点总

47、数（即计算函数的次数） 。当给定区间缩短率的绝对精度 时，经过次迭代，最后获得的新区间长度（）必须满足。而，故。由即可从斐波那契数列表或按推算出相应的 。112111223a,b(), (), (), ()nnnnFFxabaxbbaff xff xFF）确定试点并计算相应的函数值，在区间内的两个试点： ，212221211211211112122122*114 ,() , ,()15(),()2nnffa xbx xxffxabxff xffx bax xxffxabxff xbaxabff x）比较函数值的大小后进行区间缩短。若，即为新区间，并作如下置换：即令若时，得新区间，并作如下置换：

48、）检查迭代终止条件：，若满足，则输出最优解，若不满足，则转入（4），继续进行迭代。 我们就可以根据几个试验点的函数值，利用插值方法建立函数的某种近似表达式，进而求得函数的极小值，并用它作为原函数极小点的近似值。这种方法称为插值法，或函数逼近法 。利用一点的函数值，一阶导数值和二阶导数值来构造此二次函数。利用三点的函数值形成一个抛物线来构造二次函数 。 ， ，01*11k01()()()2()3|4411kkkkkkkkkxfxfxfxxxfxxxxxkk给定初始点 ，控制误差 ，令。）计算和；）求。）若，则求得近似解，停止计算，否则转到第（ ）步；）令转到第（ ）步。用切线代替弧逐渐逼近函数极

49、值的一种方法。 ，1() (0,1,2,)()kkkkfxxxkfx ，： 1）每一次迭代都要计算函数的二阶导数，增加了计算工作量； 2）对初始点的要求较高，如果选不好，可能使数列发散或收敛到一个不是极小点的点上。 ，43212( )27843f xxxxx例：试用牛顿法求的近似极小值，已知探索区间为a,b=3,4, =0.05。 ， 在给定的单峰区间在给定的单峰区间a,b内，利用函数上的内，利用函数上的三个点三个点来构来构造一个造一个二次插值函数二次插值函数p(x)，以近似地表达原目标函数，以近似地表达原目标函数f(x)，并求这个插值函数的极小点近似作为原目标函数的极小并求这个插值函数的极小

50、点近似作为原目标函数的极小点。它是以点。它是以目标函数的二次插值函数目标函数的二次插值函数的的极小点极小点作为作为新的新的中间插入点中间插入点，进行区间缩小的一维搜索方法。，进行区间缩小的一维搜索方法。 ， 2P xabxcx211111222222233333P xabxcxyf xP xabxcxyf xP xabxcxyf x123xxx*113212cxxxc31131yycxx21121223yycxxcxx*/2xbc ， ，123132112233211*3121123123*11321,1(),(),(),();22( ):,1(),2xxxxa xbxabyf xyf xyf

51、 xyycyyxxp xxccxxxxcxxxyf xc）给定初始搜索区间a,b和迭代精度 ，取点时令求）计算二次插值函数的极值点和第一次插值时转到第三步，否则转到第4步。 ，*22122*223*22322*221*2222*2,4|xxyyxxxxxxyyxxxxyyxxxxxxyyxxyyxxyyyyy3）缩短搜索区间，形成新的区间a,b:当且时，,，转到第二步；当且时，转到第二步；当且时，转到第二步；当且时，转到第二步；）判断迭代是否终止：满足或或，迭代终止，输出，如果则得到极值*22pxyy点是 ；若极值点为；不满足，转第二步。 ( )sin45f xxx例：试用二次插值法求的近似极

52、小点及极小值，已知。 ，2( )(3) , 1,7,0.01f xxa b例：试用二次插值法求函数的最优解，已知初始单峰区间给定计算精度。，多维搜索：多维搜索：是利用是利用已有已有的信息，通过计算点一步一步地的信息，通过计算点一步一步地直接移动计算点，直接移动计算点，逐步逼近逐步逼近最后达到最优点。最后达到最优点。 1(0,1,)kkkkxxdk1 1）选择迭代方向即探索方向；）选择迭代方向即探索方向；2 2）在确定的方向上选择适当步长迈步进行探索）在确定的方向上选择适当步长迈步进行探索 ， 一类是利用目标函数的一阶或二阶导数的无约束优 化方法（如一阶梯度法法、共轭梯度法、二阶梯度 及变尺度法

53、）； 另一类只利用目标函数的无约束多维问题优化方法 （如坐标轮换法、单纯形法及鲍威尔法等）。， 采用使目标函数值下降得最快的负梯度方向作为探索方向，求目标函数的极小值的方法，又称最速下降法。1()(0,1,)kkkkxxf xk一阶梯度法的迭代公式， 011*10();3minmin4|;1,kkkkkkkkkkkkkxkdf xfxdxxdxxxxkk 1）给定初始点 和收敛精度 ，置；2）计算梯度，并构造搜索方向）用一维搜索的方法求解的 最佳步长，代入得到新的迭代点；）若，则停止迭代，得最优解否则， 转到第二步。2212 ( )25 =f xxx用一阶梯度法求目标函数的极小点。迭代精度0.

54、1。， 1）对初始搜索点无严格要求； 2）收敛速度不快； 3）相邻两次迭代搜索方向互相垂直，在远离极值点处 收敛快，在靠近极值点处收敛慢； 4）收敛速度与目标函数值的性质有关，对等值线是同 心圆的目标函数来说，经过一次迭代就可以达到极 值点。， 利用二次曲线来逐点近似原目标函数，以二次曲线的极小点来近似原目标函数的极小点并逐渐逼近该点。 基本牛顿法的迭代公式：基本牛顿法的迭代公式：11 (0,1,2)()kkkkkkxxdkdG xf x ，01111*1,0;()()()()34|;1,kkkkkkkkkkkkxkf xG xG xdG xf xxxdxxxxkk 1）给定初始点收敛精度 ，置2）计算、和，得到；）求；）检查收敛精度。若，则停止迭代，得最优解 否则，转到第二步继续进行搜索。， 1）迭代次数较多时，计算量较大； 2）如果二阶偏导数矩阵为零，其逆矩阵不存在， 二阶梯度法失效。，22