1、,机械优化设计 Mechanical optimization design,本课程的要求,1.课程的最终成绩构成：考试成绩（70%） 平时成绩（20%） 实验（30%） 2.实行点名制度，旷课一次平时成绩扣5分。请假需要正式假条。 3.按时、按质、按量、独立完成作业，发现大量抄袭的情况，只有看到的 第一本作业有成绩，其余就算没交。作业一次不交平时成绩扣5分。 4.课堂上不许大声说话，有问题请举手或下课讨论；上课过程中，手机不 许响，响一次平时成绩扣5分。 5.上课请积极回答问题，回答问题正确平时成绩加5分，回答错误平时成绩 加1分。,绪论,优化设计是20世纪60年代初，在电子计算机技术广泛应
2、用的基础上发展起来的一门新的设计方法。它是以电子计算机为计算工具，利用最优化原理和方法寻求最优设计参数的一门先进设计技术。,绪论,一、定义：,优化设计： 根据给定的设计要求和现有的设计条件，应用专业理论和优化方法，在计算机上满足给定设计要求的许多可行方案中，按给定的目标自动地选出最优的设计方案。,机械优化设计： 在满足一定约束的前提下，寻找一组设计参数，使机械产品单项设计指标达到最优的过程。,绪论,一、定义：,机械优化设计：机械设计理论 优化方法 得到设计参数的最优值,指在一定条件(各种设计因素) 影响下所能得到的最佳设计值。 （相对概念）,绪论,一、定义：,机械优化设计方法包括： 1)解析法
3、: 主要是利用微分学和变分学的理论，适应于解决小型和简单的问题； 2)数值计算方法: 使利用已知的信息，通过迭代计算来逼近最优化问题的解，因此它的运算量很大，直到计算机出现后才得以实现。,绪论,二、从传统设计到优化设计：,传统设计：在调查分析的基础上，参考同类产品通过估算、经验类比或试验等方法来确定初始方案，然后通过计算各个参数是否能满足设计指标的要求，如果不符合要求就凭借经验对参数进行修改，反复进行分析计算性能检验参数修改，直到符合设计指标为止。,优化设计：借助计算机技术，应用一些精度较高的力学的数值分析方法（如有限元法等）进行分析计算，并从大量的可行设计方案中寻找到一种最优的设计方案。,绪
4、论,二、从传统设计到优化设计：,优化设计与传统设计相比有以下三点特点： 设计的思想是最优设计，需要建立一个能够正确反映实际设计问题的优化数学模型； 设计的方法是优化方法，一个方案参数的调整是计算机沿着使方案更好的方向自动进行的，从而选出最优方案； 设计的手段是计算机，由于计算机的运算速度快，分析和计算一个方案只需要几秒甚至千分之一秒，因而可以从大量的方案中选出“最优方案”。,绪论,三、本课程的主要内容：,机械优化设计包括： 1）建立优化设计问题的数学模型 2）选择恰当的优化方法 3）编程求解最优的设计参数,绪论,三、本课程的主要内容：,本课程的研究内容： 优化的原理与算法 本课程分为八章进行讨
5、论： 第一章，介绍优化设计的基本概念； 第二章，介绍优化设计算法中用到的数学基础知识，为后面几章的学习打好基础； 第三、四、五、六章分别介绍一位搜索、无约束优化、线性规划和约束优化的原理与算法，这些都是本课程学习的重点； 第七章，介绍多目标及离散变量优化方法； 第八章，介绍几种机械优化设计的实例，说明如何应用优化方法解决机械设计问题。,绪论,四、机械优化设计的发展趋势：,1）模糊优化设计技术 2）面向产品创新设计的优化技术 3）广义优化设计技术 4）产品全寿命周期的优化设计技术 5）CAD/CAPP/CAM集成系统中的优化技术 6）智能优化算法 7）多学科综合优化,第一章 优化设计概述,第一节
6、 人字架的优化设计,如图所示的人字架由两个钢管构成， 其顶点受外力2F=3105N。 人字架的跨度2B=152cm， 钢管壁厚T=0.25cm， 钢管材料的弹性模量E=2.1105Mpa， 材料密度=7.8103kg/m3， 许用压应力y= 420MPa。 求在钢管压应力不超过许用压应力y 和失稳临界应力e的条件下， 人字架的高h和钢管平均直径D，使钢管总质量m为最小。,第一章 优化设计概述,第一节 人字架的优化设计,人字架的优化设计问题归纳为 求x=D hT 使质量m(x)min 满足强度约束条件 和稳定约束条件,第一章 优化设计概述,第一节 人字架的优化设计,第一章 优化设计概述,第一节
7、人字架的优化设计,第一章 优化设计概述,第一节 人字架的优化设计 解析法：,第一章 优化设计概述,第一节 人字架的优化设计 解析法：,等值线越往里，函数值越小; 等值线愈稀疏说明目标函数值的变化愈慢； 无约束时,等值线族的共同中心就是函数的极小值。,第一章 优化设计概述,第一节 人字架的优化设计 作图法：,等值线（面）：函数f(x)的值依次为一系列常数ci时，变量x取得的一系列值的集合。,求极值就是求等值线的中心！,第一章 优化设计概述,第一节 人字架的优化设计 作图法：,等值线（面）：函数f(x)的值依次为一系列常数ci时，变量x取得的一系列值的集合。,二维设计问题，等值线为平面曲线。 对于
8、三维设计问题，其等值函数是一个面，叫做等值面； 对于n 维设计问题则为等值超越曲面。,第一章 优化设计概述,第一节 人字架的优化设计 作图法：,由图中数据得：D*=6.43cm，h*=76cm，在极值点处m*=8.47kg,第一章 优化设计概述,第三节 优化设计问题的数学模型,一个优化设计问题一般包括三个部分： 1.需要合理选择的一组独立参数，称为设计变量； 2.需要最佳满足的设计目标，这个设计目标是设计变量的函数，称为目标函数； 3.所选择的设计变量必须满足一定的限制条件，称为约束条件（或称设计约束）。,优化设计问题的数学模型的三要素：设计变量、目标函数和约束条件。,第一章 优化设计概述,第
9、三节 优化设计问题的数学模型,设计变量： 在设计过程中进行选择并最终必须确定的各项独立参数，称为设计变量。 设计变量向量：,第一章 优化设计概述,第三节 优化设计问题的数学模型,优化设计的维数：设计变量的数目称为优化设计的维数，如有n(n=1，2，)个设计变量，则称为n维设计问题。,任意一个特定的向量都可以说是一个“设计”。,第一章 优化设计概述,第三节 优化设计问题的数学模型,设计空间：由n个设计向量为坐标所组成的实空间称作设计空间。 一个“设计”，就是设计空间中的一个点，这个点可以看成是设计变量向量的端点（始点是坐标原点），称这个点式设计点。 设计空间的维数（设计的自由度）：设计变量愈多，
10、则设计的自由度愈大、可供选择的方案愈多，设计愈灵活，但难度亦愈大、求解亦愈复杂。 含有210个设计变量的为小型设计问题； 1050个为中型设计问题； 50个以上的为大型设计问题。,第一章 优化设计概述,第三节 优化设计问题的数学模型,约束条件：在优化设计中，对设计变量取值时的限制条件，称为约束条件或设计约束，简称约束。,第一章 优化设计概述,第三节 优化设计问题的数学模型,目标函数（评价函数）：在优化设计中，把设计目标（设计指标）用设计变量的函数形式表示出来，这个函数就叫做目标函数，用它可以评价设计方案的好坏，所以它又被称作评价函数。,第一章 优化设计概述,第三节 优化设计问题的数学模型,单目
11、标函数优化问题：在最优化设计问题中，可以只有一个目标函数。 多目标函数优化问题：当在同一设计中要提出多个目标函数时，这种问题称为多目标函数的优化问题。,第一章 优化设计概述,第三节 优化设计问题的数学模型,优化问题的数学模型,第一章 优化设计概述,第三节 优化设计问题的数学模型,建立优化的数学模型，在计算机上求得的解，就称为优化问题的最优解，它包括： 1）最优方案（最优点）： 2）最优目标函数值：,第一章 优化设计概述,第三节 优化设计问题的数学模型,建立数学模型要求： 1）希望建立一个尽可能完善的数学模型，精确的表达实际问题； 2）力求所建立的数学模型尽可能的简单，方便计算求解。,第一章 优
12、化设计概述,第三节 优化设计问题的数学模型,例：现用薄板制造一体积5m3，长度不小于4m的无上盖的立方体货箱。要求该货箱的钢板耗费量最少，试确定货箱的长、宽和高的尺寸。（写出该优化问题的数学模型）,例：有一块薄板，宽度为24cm，长度为100cm，制成如图所示的梯形槽，问斜边长l和倾角为多大时，梯形槽的容积最大。（写出该优化问题的数学模型）,第一章 优化设计概述,第三节 优化设计问题的数学模型,优化问题的几何解释：,无约束优化问题：目标函数的极小点就是等值面的中心； 等式约束优化问题：设计变量x的设计点必须在 所表示的面或线上，为起作用约束。 不等式约束优化问题：可行点 非可行点 边界点,第一
13、章 优化设计概述,第三节 优化设计问题的数学模型,优化问题的几何解释：,第一章 优化设计概述,第四节 优化设计问题的基本解法,数学解析法： 把优化对象用数学模型描述出来后，用数学解析法（如微分法、变分法等）来求出最优解。 图解法： 直接用作图的方法来求解优化问题，通过画目标函数和约束函数的图形，求出最优解。特点是简单、直观，但仅限于n2的低维优化问题的求解。 数值迭代法： 依赖于计算机的数值计算特点而产生的，它具有一定逻辑结构并按一定格式反复迭代计算，逐步逼近优化问题最优解的一种方法。不仅可以用于求解复杂函数的优化解，还可以用于处理没有数学解析表达式的优化设计问题。,例1：求下列二维优化问题的
14、最优解,图解法,s.t.,X2,O,（2，2）,h (X),g1(X),g3(X),X1,g2(X),练习1：求下列二维优化问题的最优解,练习2：已知优化问题,画出此优化问题的目标函数等值线和约束曲线，并确定 （1）可行域的范围（用阴影画出） （2）在图中标出无约束最优解 和约束最优解 （3）若加入等式约束 在图中标出约束最优解,g2(X),g1(X),g3(X),g4(X),X1,X2,A,B,C,h (X),o,第一章 优化设
15、计概述,第四节 优化设计问题的基本解法,数值迭代法的基本步骤：,数值迭代法的核心： 1）建立搜索方向dk 2）计算最佳步长k 3）如何判断是否找到最优点,迭代法的基本思想： 步步逼近、步步下降,第一章 优化设计概述,第四节 优化设计问题的基本解法,数值迭代法的迭代终止准则（是充分小的正数，且0）,1.点距足够小准则： 当相邻两个设计点的移动距离已达到充分小时。 2.函数下降量足够小准则： 当函数值的下降量充分小时，也就是前后两个迭代点间函数的目标函数值充分接近时。,第一章 优化设计概述,第四节 优化设计问题的基本解法,数值迭代法的迭代终止准则：,3.函数梯度充分小准则： 根据极值存在的必要条件
16、（函数极值点的必要条件是函数在这一点的梯度的模为零），则迭代点的函数梯度的模充分小时，可以作为迭代的终止准则。,第二章 优化设计的数学基础,第一节 多元函数的方向导数和梯度,一个多元函数可用偏导数的概念来研究函数沿各坐标方向的变化率。 二元函数的偏导数：,第二章 优化设计的数学基础,第一节 多元函数的方向导数和梯度,方向导数：,2,1,o,偏导数与方向导数之间的数量关系：,第二章 优化设计的数学基础,第一节 多元函数的方向导数和梯度,多元函数的方向导数：,第二章 优化设计的数学基础,第一节 多元函数的方向导数和梯度,例：,第二章 优化设计的数学基础,第一节 多元函数的方向导数和梯度,梯度：,第
17、二章 优化设计的数学基础,第一节 多元函数的方向导数和梯度,梯度：,梯度的性质： 1）梯度是一个向量； 2）梯度方向是方向导数最大的方向，即函数值变化最快（函数值变化率最大）的方向 ； 3）梯度方向是等值面（线）的法线方向 。,第二章 优化设计的数学基础,第一节 多元函数的方向导数和梯度,多元函数的梯度：,第二章 优化设计的数学基础,第一节 多元函数的方向导数和梯度,例题：,解： 函数变化率最大的方向就是 梯度方向，用单位向量 表 示，函数变化率最大的数值就 是梯度的模 。,第二章 优化设计的数学基础,第一节 多元函数的方向导数和梯度,例题：,第二章 优化设计的数学基础,第二节
18、多元函数的泰勒展开,一元函数,第二章 优化设计的数学基础,第二节 多元函数的泰勒展开,二元函数：,二元函数泰勒展开式的矩阵形式：,对称矩阵,第二章 优化设计的数学基础,第二节 多元函数的泰勒展开,多元函数泰勒展开式的矩阵形式：,是函数在该点的梯度,第二章 优化设计的数学基础,第二节 多元函数的泰勒展开,多元函数的海赛矩阵：,第二章 优化设计的数学基础,第二节 多元函数的泰勒展开,例：,第二章 优化设计的数学基础,第二节 多元函数的泰勒展开,二次二维函数用向量和矩阵的表示方法：,第二章 优化设计的数学基础,第二节 多元函数的泰勒展开,二次n维函数用向量和矩阵的表示方法：,第二章 优化设计的数学基
19、础,第二节 多元函数的泰勒展开,几种特殊类型函数的梯度：,第二章 优化设计的数学基础,第二节 多元函数的泰勒展开,二次型：,第二章 优化设计的数学基础,第二节 多元函数的泰勒展开,正定矩阵：,第二章 优化设计的数学基础,矩阵正定与负定的判定：,正定：矩阵A正定的条件是A的各阶主子式大于零； 负定：矩阵A负定的条件是各阶主子式负、正相间。,第二节 多元函数的泰勒展开,第二章 优化设计的数学基础,第三节 无约束优化问题的极值条件,必要条件,充分条件,第二章 优化设计的数学基础,第三节 无约束优化问题的极值条件,第二章 优化设计的数学基础,第三节 无约束优化问题的极值条件,例：,第二章 优化设计的数
20、学基础,第四节 凸集、凸函数和凸规划,当极值点x*能使f（x*）在整个可行域中为最小值（最大值）时，即在整个可行域中对任一 x都有f（x）f（x*）（或者f（x）f（x*） ）时，则x* 就是全局极小点（全局极大点）。,全局极值点（最优点）：,第二章 优化设计的数学基础,第四节 凸集、凸函数和凸规划,若f（x*）为局部可行域中的极小值（极大值）而不是整个可行域中的最小值（或最大值）时，则称x*为局部极小点（局部极大点）。,局部极值点（相对极值点）：,第二章 优化设计的数学基础,第四节 凸集、凸函数和凸规划,一个下凸的函数，它的极值点只有一个，并且该点既是局部极值点也是全局极值点，我们就称这个函
21、数具有凸性。,函数的凸性（单峰性）：,第二章 优化设计的数学基础,第四节 凸集、凸函数和凸规划,设R是一个点集（或区域），若连接其中任意两点x1和x2的直线都属于R，则称这种集合R是一个凸集。,凸集：,第二章 优化设计的数学基础,第四节 凸集、凸函数和凸规划,凸集的性质：,第二章 优化设计的数学基础,第四节 凸集、凸函数和凸规划,具有凸性（表现为单峰性）或只有唯一的局部最优值，即全局最优值的函数，称为凸函数或单峰函数。,凸函数：,第二章 优化设计的数学基础,第四节 凸集、凸函数和凸规划,1若f (x)为定义在凸集R上的一个凸函数，且是一个正数（0），则f (x)也必是定义在凸集R上的凸函数。
22、2定义在凸集R上的两个凸函数f 1 (x)和f 2 (x) ，其和 f (x) = f 1 (x) f 2 (x) 也一定是该凸集上的一个凸函数。 3若f 1 (x) 、f 2 (x)是定义在凸集R上的两个凸函数，和为两个任意正数，则函数f 1 (x) f 2 (x) 仍是R上的凸函数。 4若定义在凸集R上的一个凸函数f (x)有两个最小点x1和x2则这两点处的函数值f (x1) 和f (x2) 必相等，否则，其中较大的点就不是f (x)的最小点了。 5若x1和x2是定义在凸集R上的一个凸函数f (x)的两个最小点，则其连接线段上的一切点必为f (x)的最小点。,凸函数的性质：,第二章 优化设
23、计的数学基础,第四节 凸集、凸函数和凸规划,凸性条件：,第二章 优化设计的数学基础,第四节 凸集、凸函数和凸规划,例：,例：,第二章 优化设计的数学基础,第四节 凸集、凸函数和凸规划,凹函数：,凸函数,下凸有极小值,上凸有极大值,凹函数,第二章 优化设计的数学基础,第四节 凸集、凸函数和凸规划,凸规划：,目标函数与约束条件均为凸函数的优化问题称为凸规划。,凸规划的性质,第二章 优化设计的数学基础,第五节 等式约束优化问题的极值条件,等式约束优化问题的数学模型：,消元法降维法 拉格朗日乘子法升维法,解 法,第二章 优化设计的数学基础,第五节 等式约束优化问题的极值条件,消元法：,（二维）,（一维
24、）,二元函数（一个等式约束）：,第二章 优化设计的数学基础,第五节 等式约束优化问题的极值条件,n元函数（l个等式约束条件）：,（ n-l 维无约束优化问题 ）,消元法,第二章 优化设计的数学基础,第五节 等式约束优化问题的极值条件,n元函数（l个等式约束条件）：,拉格朗日乘子法,极值必要条件,第二章 优化设计的数学基础,第五节 等式约束优化问题的极值条件,极值必要条件,几何意义： 在等式约束的极值点上，目标函数的负梯度等于各约束函数梯度的线性组合。,第二章 优化设计的数学基础,第五节 等式约束优化问题的极值条件,例：,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,求解不等
25、式约束优化问题的基本思想： 将不等式约束条件变成等式约束条件。 具体做法： 引入松弛变量。,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,拉格朗日函数：,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,拉格朗日函数：,极值条件,一元函数,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,极值条件,一元函数,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,起作用约束的下标集合：,一元函数,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,极值条件,库恩塔克条件,第二章 优化设计的数学基础,第六节 不等式约束优
26、化问题的极值条件,库恩塔克条件,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,库恩塔克条件,几何意义： 在约束极小值点x*处，函数f(x)的负梯度一定可以表示成所有起作用约束在改点的梯度（法向量）的非负线性组合。,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,库恩塔克条件的几何意义（二维）：,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,库恩塔克条件的几何意义（二维）：,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,库恩塔克条件的几何意义（二维）：,结论：,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极
27、值条件,同时具有等式和不等式约束的优化问题：,库恩塔克条件：,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,库恩塔克条件举例：,第二章 优化设计的数学基础,第六节 不等式约束优化问题的极值条件,库恩塔克条件举例：,第三章 一维搜索方法,一维搜索：对于单个变量（一维问题）的直接探索（搜索 或寻查）。,多维问题的数值迭代法,每步为一维搜索,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,单峰区间：函数在该区间只有一个极值点。,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,确定搜索区间的外推法（进退法/成功失败法）：,第三章 一维搜索方法,第二节 搜
28、索区间的确定与区间消去法原理,确定搜索区间的外推法的基本步骤：,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,确定搜索区间的外推法的基本步骤：,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,确定搜索区间的外推法的程序流程图：,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,例：,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,一维搜索的基本原理： 通过外推法，我们可以确定一个包含一元函数极值点的搜索区间，为了进一步找到极小点，我们需要不断的缩小搜索区间，消去不可能包含极小点的区间，使区间在缩小的过程中逐步向极小点靠拢，最后缩小到极小点
29、附近一个极小的领域内。 这个时候，如果我们规定一个足够小的正数，称为收敛精度。则当区间长度达到足够小，即 取该区间的中点 作为极值点，这才能完成整个一维搜索 。,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,区间消去原理：不断缩小区间所用的原理。 包括：1）直接法：直接比较试选点的函数值； 2）间接法：利用函数导数值的变化信息。,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,直接法,第三章 一维搜索
30、方法,第二节 搜索区间的确定与区间消去法原理,直接法,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,间接法,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,区间缩短率：,第三章 一维搜索方法,第二节 搜索区间的确定与区间消去法原理,一维搜索方法的分类： 试探法：它是按照某种给定的规律来确定区间内插入点的位置的。插入点位置的确定是为了使区间缩短的更快，而不管函数值的分布规律。它包括：黄金分割法（0.618法）、裴波纳契（Fibonacci）法等。 插值法（函数逼近法）：这种方法是根据某点处的某些信息（如函数值、一阶导数、二阶导数等）来构造一个差值函数来逼近原来的函数
31、，用插值函数的极小点作为区间的插入点。它包括：二次差值法、三次插值法等。,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法（0.618法）：,基本原理： 通过比较单峰区间内两个内分点的函数值，不断舍弃单峰区间的左端或者右端的一部分，使区间按照固定区间缩短率（=0.618）逐步缩短，直到极小点所在的区间缩短到给定的误差范围内，而得到近似最优解。,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法（0.618法）：,黄金分割法的内分点的选取原则：每次区间缩短都取相等的区间缩短率（），同时插入点距离两个端点有对称性。,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法（0.
32、618法）： 计算步骤：,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法（0.618法）： 计算步骤：,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法（0.618法）： 计算步骤：,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法（0.618法）： 程序框图：,第三章 一维搜索方法,第三节 一维搜索的试探法,黄金分割法（0.618法）： 例：,第三章 一维搜索方法,第三节 一维搜索的试探法,斐波那契法： 和黄金分割法相似，都是在搜索区间内对称的取点，通过比较两点函数值逐步缩小初始单峰区间来搜索出满意的极小点x*。 与黄金分割法不同的是：黄金分割法每次迭代式按照
33、同一区间缩短率=0.618来缩短区间，而斐波那契法每次迭代的区间缩短率是不同的，它是按斐波那契数列Fn产生的分数序列为缩短率来缩短区间的。,，,第三章 一维搜索方法,第三节 一维搜索的试探法,斐波那契法：,，,第三章 一维搜索方法,第三节 一维搜索的试探法,斐波那契法：,，,区间缩短率用相邻两数的前一数与后一数之比产生，如计算五个点的函数值（即迭代四次，每次区间缩短率分别为,第三章 一维搜索方法,第三节 一维搜索的试探法,斐波那契法：,，,推广到计算n个点的函数值，经过n-1次迭代所获得的 区间总缩短率为,第三章 一维搜索方法,第三节 一维搜索的试探法,斐波那契法的特点：,，,第三章 一维搜索
34、方法,第三节 一维搜索的试探法,斐波那契法的迭代步骤：,，,第三章 一维搜索方法,第三节 一维搜索的试探法,斐波那契法的迭代步骤：,，,第三章 一维搜索方法,第四节 一维搜索的插值方法,插值法（函数逼近法）： 我们就可以根据几个试验点的函数值，利用插值方法建立函数的某种近似表达式，进而求得函数的极小值，并用它作为原函数极小点的近似值。这种方法称为插值法，或函数逼近法 。 牛顿法（切线法）：利用一点的函数值，一阶导数值和二阶导数值来构造此二次函数。 抛物线法（二次插值法）：利用三点的函数值形成一个抛物线来构造二次函数 。,，,第三章 一维搜索方法,第四节 一维搜索的插值方法,牛顿法（切线法）：
35、用切线代替弧逐渐逼近函数极值的一种方法。,，,第三章 一维搜索方法,第四节 一维搜索的插值方法,牛顿法的计算步骤：,，,第三章 一维搜索方法,第四节 一维搜索的插值方法,，,牛顿法的缺点： 1）每一次迭代都要计算函数的二阶导数，增加了计算工作量； 2）对初始点的要求较高，如果选不好，可能使数列发散或收敛到一个不是极小点的点上。,第三章 一维搜索方法,第四节 一维搜索的插值方法,，,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法（抛物线法）：,，,基本思想： 在给定的单峰区间a,b内，利用函数上的三个点来构造一个二次插值函数p()，以近似地表达原目标函数f()，并求这个插值函数的极
36、小点近似作为原目标函数的极小点。它是以目标函数的二次插值函数的极小点作为新的中间插入点，进行区间缩小的一维搜索方法。,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法（抛物线法）：,，,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法（抛物线法）：,，,缩小搜索区间： 用插值函数p()的极小点p作为原目标函数的极小点*的近似解，通常不能满足给定的迭代精度要求，所以需要多次缩短搜索区间，使p的点列中的各点依次逐步逼近*。,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法（抛物线法）：,，,缩小搜索区间：,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插
37、值法（抛物线法）：,，,缩小搜索区间：,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法（抛物线法）：,，,计算步骤：,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法（抛物线法）：,，,计算步骤：,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法（抛物线法）：,，,第三章 一维搜索方法,第四节 一维搜索的插值方法,二次插值法（抛物线法）：,，,第四章 无约束优化方法,第一节 概 述,，,数值解法：是利用已有的信息，通过计算点一步一步地直接移动，逐步逼近最后达到最优点。,1）选择迭代方向即探索方向； 2）在确定的方向上选择适当步长迈步进行探索,第四章 无约束
38、优化方法,第一节 概 述,，,无约束优化方法可以分成两类： 一类是利用目标函数的一阶或二阶导数的无约束优化方 法（如最速下降法、共轭梯度法、牛顿法及变尺度法）； 另一类只利用目标函数的无约束优化方法（如坐标轮换 法、单形替换法及鲍威尔法等）。,第四章 无约束优化方法,第二节 最速下降法,，,定义： 最速下降法就是采用使目标函数值下降得最快的负梯度方向作为探索方向，来求目标函数的极小值的方法，又称为梯度法。,最速下降法的迭代公式,第四章 无约束优化方法,第二节 最速下降法,，,最速下降法的迭代步骤：,第四章 无约束优化方法,第二节 最速下降法,，,第四章 无约束优化方法,第二节 最速下降法,，,
39、最速下降法的特点： 1）对初始搜索点无严格要求； 2）收敛速度不快； 3）相邻两次迭代搜索方向互相垂直，在远离极值点处收敛快，在靠近极值点处收敛慢； 4）收敛速度与目标函数值的性质有关，对等值线是同心圆的目标函数来说，经过一次迭代就可以达到极值点。,第四章 无约束优化方法,第三节 牛顿型法,，,牛顿型法的基本思想： 利用二次曲线来逐点近似原目标函数，以二次曲线的极 小点来近似原目标函数的极小点并逐渐逼近该点。,基本牛顿法的迭代公式：,第四章 无约束优化方法,第三节 牛顿型法,，,基本牛顿法的迭代公式：,第四章 无约束优化方法,第三节 牛顿型法,，,基本牛顿法的迭代公式：,阻尼牛顿法的迭代公式：,第四章 无约束优化方法,第三节 牛顿型法,，,
