机械优化设计总复习.ppt

1,机械优化设计总复习,2012年6月7日,2,题型,一、名词解释(每小题4分，共12分)二、选择题(每空2分,共30分)三、简答题(每小题6分,共12分)四、建模题(8分)五、计算填表题(8分)六、计算题(30分),3,一 设计变量 在优化设计过程中，要优化选择的设计参数。设计变量必须是独立变量，即：在一个优化设计问题中，任意两个设计变量之间没有函数关系。按照产品设计变量的取值特点，设计变量可分为连续变量（例如轴径、轮廓尺寸等）和离散变量（例如各种标准规格等）。小型设计问题：一般含有210个设计变量；中型设计问题：1050个设计变量；大型设计问题：50个以上的设计变量。,第二章 优化设计的基本要素和数学模型,4,二 设计空间 在一个优化设计问题中，所有可能的设计方案构成了一个向量集合。可以证明，这个向量集合是一个向量空间，并且是一个欧氏空间。一个优化设计问题中，设计变量的个数，就是它的设计空间的维数。三 目标函数 优化设计中要优化的某个或某几个设计指标，这些指标是设计变量的函数，称为目标函数。在构造目标函数时，应注意目标函数必须包含全部设计变量，所有的设计变量必须包含在约束函数中。,5,四 设计约束 优化设计中设计变量必须满足的条件，这些条件是设计变量的函数。,约束条件的分类（1）根据约束的性质分 边界约束 直接限定设计变量的取值范围的约束条件，即,性能约束 由方案的某种性能或设计要求，推导出来的约束条件。,i 1,2,，n,6,u=1,2,，m,v=1，2，p n,（2）根据约束条件的形式分不等式约束,一个 n 维的优化设计问题中，等式约束的个数必须少于 n。,显式约束 隐式约束,等式约束,7,约束条件可以用数学等式或不等式来表示。等式约束对设计变量的约束严格，起着降低设计自由度的作用，要求：设计点落在约束面上，pn,其形式为,等式约束降低了设计空间的维数。有一个独立的等式约束，就可用代入法消去一个设计变量，使优化问题降低1维。因此，等式约束的数目应当小于设计变量的数目。如果相等，成了既定系统，就没法优化了。等式约束hv(x)=0可看成是同时满足：hv(x)0和hv(x)0这两个不等式约束。对于等式约束来说，设计变量x所代表的设计点必须在式(2-3)所表示的面(或线)上这种约束又称为起作用约束或紧约束,*等式约束的个数 p 设计变量的数目 n,8,在机械最优化设计中不等式约束更为普遍，不等式约束的形式为,要求:设计点落在约束面的一侧。不等式约束在设计空间内划分出可行区域与不可行区域，但不降低设计空间的维数。,9,设计点的集台构成设计空间，n维设计问题属于n维欧氏空间，如对设计点的取值不加以限制，则设计空间是无限的，凡属这类的优化设计问题称为无约束优化问题。但在实际问题中设计变量的取值范围是有限制的或必须满足一定条件，在优化设计中。这种对设计变量取值的限制条件，称为约束条件或设计约束。约束的形式，可能是对某个或某组设计变量的直接限制(例如，若应力为设计变量，则应力值应不大于其许用值，构成直接限制)，这时称为显约束；也可能是对某个或某组设计变量的间接限制(例如，若结构应力又是某些设计变量如力和截面积的函数时，则这些设计变量间接地受到许用应力的限制,或例中的复杂结构的性能约束函数（变形、应力、频率等），需要通过有限元等方法计算求得。)，这时称为隐约束。,10,*五 可行域 可行域:在设计空间中，满足所有约束条件的所构成的空间。,满足两项约束条件g1（X）=-x12-x22+16 0g2（X）x22 0的二维设计问题的可行域D,11,约束（曲）面：对于某一个不等式约束 gu(x)0 中，满足 gu(x)=0的 x 点的集合构成一个曲面，称为约束（曲）面。,它将设计空间分成两部分：满足约束条件 gu(x)0 的部分和不满足约束条件gu(x)0 的部分。,设计可行域（简称为可行域）对于一个优化问题，所有不等式约束的约束面将组成一个复合的约束曲面，包围了设计空间中满足所有不等式约束的区域，称为设计可行域。,记作 D=,g u(x)0 u=1,2,mh v(x)=0 v=1,2,p,问题：等式约束与约束曲面是什么关系？,D,12,可行设计点（内点）：在可行域内任意一点称为可行设计点，代表一个可行方案。即位于由gu(x)0构成的约束曲面之内的设计点,极限设计点（边界点）：在约束面上(或边界线)的点称为极限设计点。边界点是允许的极限设计方案。,若讨论的设计点 x(k)点使得 gu(x(k)=0，则gu(x(k)0 称为适时约束或起作用约束。,非可行设计点（外点）：在可行域外的点称为非可行设计点，代表不可采用的设计方案。,问题：极限设计点是否代表可行设计方案？什么约束一定是适时约束？可行域是否一定封闭？,13,六 优化设计的数学模型,14,八 优化分类及机械优化设计的特点,机械优化设计基本上是非线性的、有约束的最优化问题。,15,其数学表达式：,等值线（面）：具有相同目标函数值的点集在设计 空间形成的曲线和曲面,在极值处，函数的等值线聚成一点，并位于等值线 族的中心。当该中心为极小值时，离中心线愈远，函数值愈大。当目标函数值的变化范围一定时，等值线越稀疏，说明函数值的变化愈平缓 函数的等值面（线）是用来描述、研究函数的整体性质的。,总结：(2维问题3维、n维）,第三章 优化设计的数学基础,16,17,等值线的分布情况，反映了目标函数值的变化情况；等值线越向里，目标函数值越小；等值线越密的地方，其目标函数值的变化率也越大；,对于有心的等值线族来说，等值线族的中心就是一个相对极小点。不同值的等值线不相交；除极值点外，等值线在设计空间内不会中断；,18,1.无约束最优解,若在整个设计空间内所得点，使：,则称：,2.约束最优解,则称：,若设计空间内点，使：,二、约束最优解和无约束最优解,19,无约束优化设计问题最优解：,约束优化设计问题最优解：,不受约束条件限制，使目标函数达到最小值的一组设计变量，即最优点 x*=x1*,x2*,x n*和最优值 f(x*)构成无约束问题最优解。,满足约束条件，使目标函数达到最小值的一组设计变量，即最优点 x*=x1*,x2*,x n*和最优值 f(x*)构成约束问题最优解。,20,情况a):,情况b):,对于无约束优化问题:当目标函数不是单峰函数时，则会有多个极值点，如图：有两个极值点：和，它们称为局部最优点。,对于约束优化问题:极值点不仅与目标函数的性质有关，还与约束集合的性质有关。如图：目标函数是凸函数，约束集合为非凸集，则有点：、，称为局部最优点,整个可行域内的最小点称为全域最优点。,三、局部最优点和全域最优点,21,二、极值点存在的条件,一元函数 在点 取极值的条件为（对于连续可微的一元函数）,必要条件：,充分条件：,当 时取极小值当 时取极大值,（一）一元函数（即单变量函数）的情况：（1）极值点存在的必要条件,3.2 无约束目标函数的极值点存在条件,22,梯度,1、梯度的定义,n维函数的梯度是函数各维一阶偏导数组成的向量,梯度的模是函数各维一阶偏导数平方和的开方,梯度与它的模的比值称为梯度的单位向量,23,2、函数梯度的性质：,1、函数的梯度 是函数在点 的最速上升方向，而负梯度 是函数在点 的最快下降方向。函数的梯度随着点 在设计空间的位置不同而异，这只是反映了函数在点 邻域内函数的局部性质，仅在该点附近具有这种性质。由于梯度的模因点而异，即函数在不同点的最大增加率是不同的。故，函数在某点的梯度向量只是指出了在该点极小领域内函数的最速上升方向，是函数的一种局部性质。,24,2、函数梯度的模 是在点 处函数变化率的最大值。,3、函数的梯度 与在点 的函数等值面正交（函数在任意点处的梯度向量与过该点的等值线的切线正交。即，任意点的梯度方向是等值线在该点的法线方向）。与点 的函数等值面相切方向的函数变化率为零。,4、当梯度 与方向 之间的夹角介于090之间时，该区域内的任意方向都是使函数值增大的方向，即函数上升方向；当梯度 与方向 之间的夹角介于90180之间时，该区域内的任意方向都是使函数值减小的方向，即函数下降方向。,25,5、函数f（x1，x2）的梯度是一个向量，它在坐标轴x1、x2的分量是f/x1、f/x2，梯度的符号是：f(X)f(x1，x2)，或gradf(X)grad f(x1，x2)6、函数的方向导数函数的梯度与方向S的单位向量的标量积7、梯度方向是函数具有最大变化率的方向。即：函数值沿正梯度方向增加最快，沿负梯度方向下降最快。8、梯度的模就是函数的最大变化率。9、对于优化设计问题，为了尽快取得最优解，希望每一次迭代的搜索方向S等于或者接近于目标函数的负梯度方向。这样才能使得函数值的下降速度最快，尽快收敛于最优点。,26,10、函数在给定点 的梯度方向是函数等值线或等值面 在该点的法线方向。,上升方向,下降方向,27,例3 求二元函数在x0=0 0T处函数变化率最大的方向和数值。,解：由于函数变化率最大的方向是梯度方向，这里用单位向量p表示，函数变化率最大的数值是梯度的模f(x0)。求f(x1,x2)在x0点处的梯度方向和数值，如下,28,解：,则函数在 处的最速下降方向为,29,该方向上的单位向量为,新点,该点函数值,30,梯度 模：,函数的梯度方向与函数等值面相垂直，也就是和等值面上过x0的一切曲线相垂直。,由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。,31,即，n维函数的二阶Taylor展开式可写成：,其中：,就称为Hesse 矩阵，是一个实对称方阵。,32,例 5 求二元函数f(x1,x2)x12+x22-4x1-2x2+5 在X02,2处的海赛二阶泰勒展开式。,解：,33,解：因为,则,又因为：,故Hesse阵为：,34,1、正定的概念 设有二次型，若对于任意不为“0”的矢量，恒有，则相应的系数对称矩阵A称为正定矩阵,相应的函数 为“正定二次型函数”,类似地，若对于任何矢量,总有，则称A为负定矩阵。相应的函数 为“负定二次型函数”,二、正定矩阵及其判别法,35,2、正定性的判别（1）若对称矩阵 正定，其充要条件是矩阵行列式 的各阶主子式值均大于0,（2）、若矩阵A负定，其充要条件是矩阵行列式 的各阶主子式值负、正相间。即：,36,37,38,四 函数的凸性1.凸集2.凸函数 如果HESSEN矩阵正定，为凸函数；二次函数,3.凸规划,凸规划问题中的任何局部最优解都是全局最优解；,39,凸规划,对于约束优化问题,式中若F（X）、均为凸函数，则称此问题为凸规划。,40,几个常用的梯度公式：,41,*五、优化问题的极值条件,1、无约束优化问题的极值条件,1）F(x)在 处取得极值，其必要条件是:,即在极值点处函数的梯度为n维零向量。,42,2）处取得极值充分条件,海色（Hessian）矩阵 正定，即各阶主子式均大于零，则X*为极小点。,海色（Hessian）矩阵 负定，即各阶主子式负、正相间，则X*为极大点。,43,1）约束优化设计的最优点在可行域 D 中 最优点是一个内点，其最优解条件与无约束优化设计的最优解条件相同；,2、约束优化问题的极值条件,2）约束优化设计的最优点在可行域 D 的边界上 设 X(k)点有适时约束,44,45,K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。,对于目标函数和约束函数都是凸函数的情况，符合K-T条件的点一定是全局最优点。这种情况K-T条件即为多元函数取得约束极值的充分必要条件。,46,K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。,47,48,49,一维搜索也称直线搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。（搜索步长求解）,一维搜索方法数值解法分类,第四章 一维搜索的最优化方法,50,只有一个变量的搜索求优，称为一维最优化方法，也称为单变量优化。,对于多维优化问题求极值，就可以处理成：将一个多维优化问题转化成了一个一维优化问题。,该问题就变成了一个从已知点 出发，沿着给定方向 求最优步长 使 为最小的一系列一维优化问题。,：一维搜索的最优步长因子。,51,1、一维搜索是多维求优问题的基础；2、一维搜索的好坏直接影响到优化问题的求解速度。,意义：,1、解析解法：,步骤：,在点 处沿着方向 展开成二阶 Taylor展开式；,最优步长 的求解方法：,52,1、单谷(峰）区间 在给定区间内仅有一个谷值的函数称为单谷数，其区间称为单谷区间。,确定搜索区间的外推法,函数值：“大小大”图形：“高低高”,53,二、确定初始单谷区间的外推法,基本思想：对f(x)任选一个初始点a1及初始步长h，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高低高”形态。,步骤：,（1）选定初始点a1,初始步长hh0 0，计算 y1f(a1)，y2f(a1h)。（2）比较y1和y2。（a）如y1y2,向右前进；加大步长 h2 h，转（3）向前；（b）如y1y2,向左后退；h h0，将a1与a2，y1与y2的 值互换。转（3）向后探测；（c）如y1y2，极小点在a1和a1h之间。,54,(3）产生新的探测点a3，y3f(a3);(4)比较函数值 y2与y3：（b）如y2y3,加大步长 h2 h(也可不变)，a1=a2,a2=a3,转（3）继续探测。（a）如y2y3,则初始区间得到：a=mina1,a3，b=maxa3,a1，函数最小值所在的区间为a，b。,55,56,一、序列消去法基本原理,逐步缩小搜索区间，直至最小点存在的范围达到允许的误差范围。,57,58,59,黄金分割法要求插入两点：,黄金分割法区间消去示意：,掌握该方法的关键在于：一，确定黄金分割点；二，清楚区间的取舍原则，,黄金分割法程序简单，可靠性好，但搜索速度慢，计算量较大。适用于维数不多的优化问题中作为一维搜索方法。,60,例 1 用黄金分割法求函数f(x)=3x3-4x+2的极小点，给定 x0=0,h=1,=0.2。,解：1）确定初始区间x1=x0=0,f1=f(x1)=2x2=x0+h=0+1=1,f2=f(x2)=1由于f1f2,应加大步长继续向前探测。,x3=x0+2h=0+2=2,f3=f(x3)=18由于f2f3,可知初始区间已找到，即a,b=x1,x2=0,2,2）用黄金分割法缩小区间 第一次缩小区间：x1=0+0.382X(2-0)=0.764,f1=0.282 x2=0+0.618 X(2-0)=1.236,f2=2.72 f10.2,61,第二次缩小区间：令 x2=x1=0.764,f2=f1=0.282 x1=0+0.382X(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,应继续缩小区间。,第三次缩小区间：令 x1=x2=0.764,f1=f2=0.282 x2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747由于f10.2,应继续缩小区间。,62,第四次缩小区间：令 x2=x1=0.764,f2=f1=0.282 x1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223由于f10.2,应继续缩小区间。,第五次缩小区间：令 x2=x1=0.652,f2=f1=0.223 x1=0.472+0.382X(0.764-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.5X(0.584+0.764)=0.674,f(x*)=0.222,63,64,65,66,67,68,4.4 多项式近似法二次插值法(微分法),（一）基本思想,对形式复杂的函数，数学运算时不方便,复杂函数 f(x),极小点x*,函数近似，最优点也应近似,一次多项式二次多项式三次多项式,?如何构造符合要求的多项式?,69,一、基本原理,它是属于曲线拟合方法的范畴，是利用一个多项式来逼近原函数的一种近似方法。,即，构造一个低次插值函数 来逼近原函数，用 的最优点 来近似 的最优点。,若插值函数 为二次多项式：称为二次插值法；若插值函数 为三次多项式：称为三次插值法；,二次插值法又称抛物线法，它是以目标函数的二次插值函数的极小点作为新的中间插入点，进行区间缩小的一维搜索算法。,70,情况分析：,）,即：,71,）,情况分析：,即：,即：,72,73,74,75,76,77,目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。,（1）间接法要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。（2）直接法不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。,无约束优化问题是：,求n维设计变量,使目标函数,第 五 章 无约束最优化方法,搜索方向的构成问题乃是无约束优化方法的关键。,78,本章应掌握内容：1）梯度法的特点 2）无约束优化方法有几种 3）各种无约束方法由哪些特点：4）用DFP变尺度法求算目标函数的极值,79,无约束优化方法的基本步骤 1选择初始点。2确定迭代方向（搜索方向）目标函数值的下降方向。3确定迭代步长，使得迭代点的函数值具有下降性。如何确定迭代方向？是各种无约束优化方法之根本。各无约束优化方法的区别，主要在于迭代方向的不同。可以把初始点、搜索方向、迭代步长 称为优化方法算法的三要素。其中以搜索方向 更为突出和重要，它从根本上决定若一个算法的成败、收敛速率的快慢等。所以一个算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向 是研究优化方法的最根本的任务之一。各种无约束优化方法的区别就在于确定其搜索方向 的方法不同,80,*一、梯度法,负梯度方向 是函数最速下降方向。梯度法就是以负梯度方向作为一维搜索的方向，即 k=1,2,n,基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。,81,在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。,图4-2 最速下降法的搜索路径,*会证明：,82,方法特点（1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。,83,二、牛顿法及其改进,84,牛顿法的迭代公式 阻尼牛顿法的迭代公式牛顿方向,85,方法特点（1）初始点应选在X*附近，有一定难度；（2）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；（3）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。,86,87,88,2 坐标轮换法,坐标轮换法的基本思想：是将一个n维优化问题转化为依次沿n个坐标方向反复进行一维搜索问题。这种方法的实质是把n维问题的求优过程转化为对每个变量逐次进行一维求优的循环过程。每次一维搜索时，只允许n个变量的一次改动，其余(n-1)个变量固定不变。该方法是将一个多维无约束优化问题转化成了一系列的一维问题来求解，因此该方法也称为“变量轮换法”或“降维法”。,89,90,91,92,若：，则有。若：，也可认为向量 通过矩阵A进行线性变换后与 正交。共轭是正交的推广，正交是共轭的特例,一、共轭方向,1.定义：,设A为 的实对称正定阵，而 中两个非零 维列向量，如果满足：，则称向量关于实对称正定阵A是共轭的。简称为 关于A共轭。,举例：,判断、是否关于矩阵A共轭。,三、共轭方向法,93,“共轭方向”定义推广为：,如果非零的n维向量组，且这个向量组中的任意两个向量关于A矩阵共轭，即满足：，则称向量组 关于矩阵A共轭。,1.定义：,*注意：n维空间中，相互共轭的非零向量的个数不超过维数n。,举例：,即对于矩阵A来说，和 不是唯一的。,；,94,正定二元二次函数：,共轭方向的几何意义,95,连接两切点构成的矢量：,96,2 二次收敛性定义：对于一个 n 维的二次函数若应用某种优化方法，经过有限次（一般不超过 n 次）一维搜索，就能找到极小点，则称该优化方法具有二次收敛性质。定理：共轭方向法具有二次收敛性。,97,1.基本原理：,由于共轭方向法中新一轮的搜索方向组是：,不论方向 的“好、坏”，都将被舍去，因此可能造成新的方向组线性相关或近似相关。,Powell法对这点进行了改进：有选择性地去掉第k轮中的某个方向，或者不更换原方向，以避免产生线性相关性。,98,方向 为：与 相对应的搜索方向，即函数值下降最大的方向。,是否用方向 替换第k轮中的某一方向，形成新的方向组，通过判别条件：,其中：,99,如果这两个条件有一个成立：则第k1轮的搜索方向仍用第k轮的基本方向组：,1.基本原理：,如果这两个条件均不成立：则去掉第k轮方向组中的 函数值下降最大的方向，再将新生成的方向 补在最后，构成第k1轮的基本方向组：,第k+1轮迭代初始点 取第k轮方向 上的一维极小点。,第k+1轮迭代初始点 取第k轮中 和 中函数值小的点。,100,101,102,2、变尺度法的基本思想,1.基本思想：,它是通过构造一个对称正定阵，在迭代过程中不断修正改变，逐渐逼近，一旦达到极值点附近，就可望达到牛顿法的收敛速度。,它既可以通过初始的梯度方向来产生一个较好的迭代点；又可以避免计算二阶导数及其逆矩阵，而在极值点附近又具有牛顿法收敛快的特点。,当：，该迭代公式变成了牛顿法的迭代公式。,当：，该迭代公式变成了梯度法的迭代公式。,：称为变尺度矩阵。,103,Ak 是需要构造nn的一个对称方阵，,如Ak=I,则得到梯度法；,变尺度法的关键在于尺度矩阵Ak的产生。,搜索方向：,104,105,106,107,108,109,110,有约束优化方法,随机方向法复合形法惩罚函数法,111,第六章 约束优化方法 机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为：,112,（1）直接法 直接法包括：网格法、复合形法、随机试验法、随机方向法、可变容差法和可行方向法。（2）间接法 间接法包括：罚函数法、内点罚函数法、外点罚函数法、混合罚函数法、广义乘子法、广义简约梯度法和约束变尺度法等。约束优化问题间接解法的基本迭代过程,根据求解方式的不同，约束优化设计问题可分为:直接解法、间接解法。,113,约束最优化间题有解的条件为：(1）目标函数和约束函数为连续、可微函数，且存在一个有界的可行域；(2）可行域，应是一个非空集，即存在满足约束条件的点列：约束问题最优解的求解过程，可归结为：寻求一组设计变量在满足约束方程：的条件下，使目标函数最小，即使：,114,62 约束随机方向搜索法,一、基本原理,约束随机方向搜索法是解决小型约束最优化问题的一种较为有效的直接求解方法。基本思想：利用计算机产生的随机数所构成的随机方向进行搜索，产生的新点必须在可行域内，即满足直接法的特性。随机方向法，一种数值迭代解法，是约束最优化问题的一种常用的直接求解方法。它和随机梯度法、GaussSeidel法等都属于约束随机法。其基本思想可用二维最优化问题来进行说明,115,1、基本思想 1）从可行域内某一点出发，沿某一给定步长，并随机产生搜索方向，直到该方向同时满足可行性和下降性要求，沿着这个方向以该步长继续搜索，直到不满足可行性及下降性条件为止。2）把上述满足要求的终点作为新的起点，重新产生随机方向，如果能够找到一个合适的方向，同时满足条件，则沿该方向以原步长继续搜索；如若找不到适合的方向，则将步长减半，仍以该点为起点随机搜索，如果能找到新的方向，则沿该方向继续，如果不能，步长再减半。直到找不到新的搜索方向，且步长满足精度要求，则以该起点为最优点。,116,117,118,119,120,在可行域中选取K个设计点(n+1K2n)作为初始复合形的顶点。比较各顶点目标函数值的大小，去掉目标函数值最大的顶点(称最坏点)，以坏点以外其余各点的中心为映射中心，用坏点的映射点替换该点，构成新的复合形顶点。反复迭代计算，使复合形不断向最优点移动和收缩，直至收缩到复合形的顶点与形心非常接近，且满足迭代精度要求为止。由于复合形的形状不必保持规则的图形，对目标函数和约束函数无特殊要求，因此这种方法适应性强，在机械优化设计中应用广泛。,一、复合形法的基本原理,121,1）在可行域内取顶点 k=4,构成初始复合形,3、基本原理（以二维问题为例）,2）求出 作为映射中心,122,3）找到最坏点 的映射点,的映射点 的迭代公式,4）若 满足可行性和适用性要求，则以 代 替 组成新的复合形,这就完成了“一轮”迭代,123,124,125,126,二、初始复合形的产生,127,128,129,130,131,这种方法可保证移动后的点一定会在可行域内，且不会与原来的可行点重合。,132,133,134,135,136,137,138,139,例 用外点法求解约束优化问题,解：,（2）用极值条件求解：,在可行域内，因：所以在可行域内无极值点。,140,在可行域外令：,联立求解得：,可以看出：,所以：,141,142,143,144,145,三、内点法,内点法是另一种惩罚函数法。其构成形式与外点法相同，这种方法将新目标函数定义于可行域内，序列迭代点在可行域内逐步逼近约束边界上的最优点。内点法只能用来求解具有不等式约束的优化问题,对于不等式约束：，满足上述要求的复合函数有以下两种：,构造惩罚函数：,146,147,此时，惩罚因子是一递减的正数序列：,由于内点法的迭代过程在可行域内进行，“障碍项”的作用是阻止迭代点越出可行域。由“障碍项”的函数形式可知，当迭代点靠近某一约束边界时，其值趋近于0，而“障碍项”的值陡然增加，并趋近于无穷大，好像在可行域的边界上筑起了一道“高墙”，使迭代点始终不能越出可行域。显然，只有当惩罚因子时，才能求得在约束边界上的最优解。罚因子的作用是：由于内点法只能在可行域内迭代，而最优解很可能在可行域内靠近边界处或就在边界上，此时尽管泛函的值很大，但罚因子是不断递减的正值，经多次迭代，接近最优解时，惩罚项已是很小的正值。,148,此时，惩罚因子是一递减的正数序列：,性质：（1）内点罚函数的有效区域是约束函数的可行域，而且目标函数在可行域内各点上都受到惩罚，越靠近约束边界惩罚越多。（2）不同的惩罚因子对应不同的惩罚函数，惩罚因子越小，惩罚函数的极小点越靠近约束边界。（3）当惩罚因子趋进于零时，惩罚函数的极小点就是原约束问题的极小点。（4）内点法只适用于不等式约束。,