机械优化设计方法PPT课件

1、1机械优化设计方法Optimization of Machine Design 大连交通大学机械工程学院2序论 什么是优化技术第一章 优化设计的基本概念 1.1 优化问题的数学模型 1.2 优化问题的基本解法第二章 优化设计的数学基础 1.1 矢量 1.2 矩阵 1.3 多元函数的方向导数与梯度 1.4 多元函数的泰勒展开 1.5 无约束优化问题的极值条件 1.6 凸规划 1.7 等式约束优化问题极值条件 1.8 不等式约束优化问题极值条件 第三章 一维优化问题 3.1 单峰函数目 录3目 录 3.2 黄金分割法 3.3 对分法 3.4 二次插值法 第四章 无约束优化问题 4.1 梯度法（最速

2、下降法） 4.2 坐标轮换法 4.3 鲍威尔法 4.4 牛顿法 4.5 DFP变尺度法 4.6 共轭梯度法 4.7 单纯形法 第五章 线性规划单纯形法 第六章 约束优化问题 6.1 约束随机方向法 6.2 网格法 4目 录 6.3 罚函数法 6.4 增广拉格朗日（Lagrange）乘子法 6.6 复合形法 6.7 可行方向法 第七章 多目标及离散变量优化问题 7.1 多目标优化问题及方法 7.2 离散变量优化问题及方法第八章 机械优化设计示例 8.1 优化应用技巧 8.2 示例5产 地有用成份含量（%）单价（元/T）K1K3一62926二34520三41310例：例： 某公司出口某矿石，合同规

3、定，矿石上三种有用成份某公司出口某矿石，合同规定，矿石上三种有用成份K1不低于不低于4%，K2不低于不低于1.9%, K3不低于不低于5%。而生产这种矿石的产地很多，可以在所有产地中的一个矿而生产这种矿石的产地很多，可以在所有产地中的一个矿井采购出口，也可以从多个矿井采购，混合后再出口，方案井采购出口，也可以从多个矿井采购，混合后再出口，方案多个，现经过综合考虑，决定仅从三个矿井进货，混合后满多个，现经过综合考虑，决定仅从三个矿井进货，混合后满足合同的要求。三个产地矿井的有用成份含量及价格如下表足合同的要求。三个产地矿井的有用成份含量及价格如下表什么是优化技术？什么是优化技术？序论6要求确定三

4、个产地矿石按什么比例混合，既能满足外销合同的要要求确定三个产地矿石按什么比例混合，既能满足外销合同的要求，而成本又最低。这就是一个在既定的方案中，定量地确定最优求，而成本又最低。这就是一个在既定的方案中，定量地确定最优比例的优化设计问题。比例的优化设计问题。分析：分析：设从一号产地供应的原矿石占混合出口矿石的设从一号产地供应的原矿石占混合出口矿石的X1份，产地二占份，产地二占X2份，份，则产地三占（则产地三占（1X1X2）份）份显然，出口公司只能从三个产地矿进货或不进货，显然，出口公司只能从三个产地矿进货或不进货，而不能向产地返销，所以有：而不能向产地返销，所以有： X10 (1-1) X20

5、 (1-2)1X1X20 (1-3)设计变量设计变量7按合同中有用成份含量的要求，有按合同中有用成份含量的要求，有0.06 X1+0.03 X2+0.04 (1X1X2) 0.040.02 X1+0.04 X2+0.01 (1X1X2) 0.0190.09 X1+0.05 X2+0.03 (1X1X2) 0.05将上三式整理后得将上三式整理后得 2 X1 X2 0 (1-4)X1 + 3 X2 0.90 (1-5) 3X1 +2X2 10 (1-6)则从三个产地各按则从三个产地各按X1：X2：（：（1X1X2）的比例进货成本最低，即）的比例进货成本最低，即F =26X1+20 X2+10(1X

6、1X2)=16X1+10 X2+10 =min (1-7)约束条件约束条件目标函数目标函数8可行域可行域等值线等值线最优点最优点9DesignSpaceFeasibleDesignSpace例：悬臂梁减重优化确定性优化 设计变量:10 高度 80 mm10 宽度 50 mm 约束:Stress 16 MPa 目标:质量最小1080105020 30 40 50 60 70203040Beam Height, mmFlange Width, mmStress= 16Loads at free endFlangeWidthBeamHeightArea = 400Area = 300最优解最优解:高

7、度高度= 38.4宽度宽度= 22.7应力应力= 16面积面积= 233.410ADM第一章第一章 优化设计的基本概念优化设计的基本概念1. 设计变量设计变量设计过程中，其数值可以改变的能够描述结构特性的独设计过程中，其数值可以改变的能够描述结构特性的独立变量。传动比，尺寸。立变量。传动比，尺寸。2. 目标函数目标函数目标函数是比较和选择各种不同设计方案的量化指标，目标函数是比较和选择各种不同设计方案的量化指标，是设计变量的函数。质量，成本，利润，速度。是设计变量的函数。质量，成本，利润，速度。,.,21nxxxX )(XF 1.1 优化问题的数学模型优化问题的数学模型11ADM第一章第一章

8、优化设计的基本概念优化设计的基本概念目标函数目标函数 1）目标函数必须包含全部或部分设计变量；）目标函数必须包含全部或部分设计变量； 2）当必须采用多目标优化时，可选择其中一个主要的目标作单目标）当必须采用多目标优化时，可选择其中一个主要的目标作单目标 优化，其它目标按满足一定值要求的约束处理，优化后在选另一优化，其它目标按满足一定值要求的约束处理，优化后在选另一 目标优化；目标优化； 3）近似目标函数）近似目标函数借助实验数据处理建立目标函数；借助实验数据处理建立目标函数； 4）转移或替代目标函数，如以中心距作为减速器重量的替代目标函）转移或替代目标函数，如以中心距作为减速器重量的替代目标函

9、 数；数； 5）单体设计对象的多目标评价）单体设计对象的多目标评价设计变量和约束条件不变，建立设计变量和约束条件不变，建立 多个不同的目标函数并分别优化，得到一组优化方案，优中择优；多个不同的目标函数并分别优化，得到一组优化方案，优中择优； 6）目标函数的规一化）目标函数的规一化minF(X)12ADM第一章第一章 优化设计的基本概念优化设计的基本概念3. 约束条件约束条件 对设计变量取值范围的约束。强度，刚度，固有频率。对设计变量取值范围的约束。强度，刚度，固有频率。4. 设计空间和可行域设计空间和可行域设计空间：由设计变量构成的设计空间：由设计变量构成的n维实空间维实空间可行域：设计空间内

10、，满足约束条件的子空间可行域：设计空间内，满足约束条件的子空间5. 数学描述优化设计数学描述优化设计iiiiibxaXhXg0)(0)(不等式约束不等式约束等式约束等式约束变量取值范围约束变量取值范围约束,.,2, 1, 0)(;,.2 , 1, 0)(|)(minpmmjXhmjXgXDRDXXFjjn13ADM第一章第一章 优化设计的基本概念优化设计的基本概念6 数学模型的分类数学模型的分类 1）按数学关系分：代数模型、微分方程模型、概率统计模型、）按数学关系分：代数模型、微分方程模型、概率统计模型、逻辑模型、混合模型。逻辑模型、混合模型。 2）按模型的确定性分：确定性模型、不确定性模型（

11、包括随即）按模型的确定性分：确定性模型、不确定性模型（包括随即模型和模糊模型）模型和模糊模型） 。 3）按优化规模分：小型）按优化规模分：小型n10、中型中型10n50。 4）按变量取值特点分：整数规划、实数规划。按变量取值特点分：整数规划、实数规划。 5）目标函数数目：单目标优化、多目标优化。）目标函数数目：单目标优化、多目标优化。 6）按目标函数和约束函数特性分：线性规划、非线性规划、几）按目标函数和约束函数特性分：线性规划、非线性规划、几何规划（多项式规划）。何规划（多项式规划）。14ADM第一章第一章 优化设计的基本概念优化设计的基本概念7. 例例0)(0)(01)(02)(44)(m

12、in2413221221112221xXgxXgxxXgxxXgxxxXFX*X*F(X)等值等值线线g1(X)g2(X)x1x2可行域可行域158. 注意事项注意事项 设计变量设计变量 1）以主要影响因素作为设计变量；）以主要影响因素作为设计变量； 2）根据优化问题的特殊性选择设计变量；）根据优化问题的特殊性选择设计变量； 3）注意独立变量和相关变量，尽量不包括相关变量；）注意独立变量和相关变量，尽量不包括相关变量； 4）变量群转换，减少变量数目，如变量在目标函数中以）变量群转换，减少变量数目，如变量在目标函数中以x1x2形式存形式存 在，可令在，可令y= x1x2 ； 5）必须的设计变量不

13、能遗漏；）必须的设计变量不能遗漏； 6）冗余变量）冗余变量相关变量，齿轮设计变量为相关变量，齿轮设计变量为i,z,m,b，齿轮孔径为冗齿轮孔径为冗 余变量。余变量。ADM第一章第一章 优化设计的基本概念优化设计的基本概念16ADM第一章第一章 优化设计的基本概念优化设计的基本概念约束函数约束函数 1）不能矛盾；）不能矛盾； 2）可行域不能无界；）可行域不能无界； 3）避免多余约束；）避免多余约束； 4） 尽量给定设计变量取值上下界，缩小可行域；尽量给定设计变量取值上下界，缩小可行域； 5）谨慎对待等式约束；）谨慎对待等式约束； 6）近似约束）近似约束不能用精确数学表达式描述的约束的处理；不能用

14、精确数学表达式描述的约束的处理； 7）不能遗漏必要的约束，如压簧优化设计忽略了工作状态下，相邻）不能遗漏必要的约束，如压簧优化设计忽略了工作状态下，相邻 圈间间隙值约束；圈间间隙值约束； 8）全部设计变量必须包含在约束函数集中。）全部设计变量必须包含在约束函数集中。17第一章第一章 优化设计的基本概念优化设计的基本概念 KKkkdXX11.2 优化问题的基本解法优化问题的基本解法1、解析方法、解析方法2、数值方法、数值方法 搜索法搜索法,迭代公式：迭代公式：)()2()1()0(,.,nXXXX）（nk., 3 , 2 , 1 , 018第一章第一章 优化设计的基本概念优化设计的基本概念 kS

15、 kd 直接搜索法直接搜索法的方法不同，这些方法，大致可分为两类：的方法不同，这些方法，大致可分为两类：这种方法只需要进行函数值的计算与比较来确定优化的方向这种方法只需要进行函数值的计算与比较来确定优化的方向和步长。例如一维搜索中的黄金分割法（和步长。例如一维搜索中的黄金分割法（0.6180.618法）、二次插法）、二次插值法等，多维问题中的随机方向搜索法，共轭方向法（值法等，多维问题中的随机方向搜索法，共轭方向法（PowellPowell法）、复合形法等。法）、复合形法等。 间接法间接法这种方法需要利用函数的一阶或二阶偏导数矩阵来确定优化这种方法需要利用函数的一阶或二阶偏导数矩阵来确定优化方

16、向和步长，如梯度法以负数梯度矢量方向为优化方向，这方向和步长，如梯度法以负数梯度矢量方向为优化方向，这就需要计算一阶偏导数矩阵。就需要计算一阶偏导数矩阵。确定确定 的方法不同，大致可分为两类：的方法不同，大致可分为两类：19第一章第一章 优化设计的基本概念优化设计的基本概念优化计算的终止判别优化计算的终止判别（1）相邻两次迭代点之间的距已达到充分小时）相邻两次迭代点之间的距已达到充分小时11-kkxx（2）当目标函灵数值的下降量已充分小时）当目标函灵数值的下降量已充分小时 21kkXFXF（3）当迭代点的目标函数梯度达到充分小）当迭代点的目标函数梯度达到充分小3kxf20ADM第二章第二章 优

17、化设计的数学基础优化设计的数学基础1.1 矢量矢量 Vector定义：有大小和方向的量二维矢量x2x1P(x1,x2)P(x1,x2)OTxxOPX,21TxxOPX,21TxxxxPP,2121n维矢量 TnxxxOPX,.,2121ADM第二章第二章 优化设计的数学基础优化设计的数学基础1.2 矩阵矩阵由一组数按一定次序排列成的具有m行n列的表mnmmnnaaaaaaaaaA.21222211121122ADM第二章第二章 优化设计的数学基础优化设计的数学基础l逆矩阵逆矩阵 Lattice 若 则B为A的逆矩阵 逆矩阵的求法EBAAB1 ABAAA*1A*为A的伴随矩阵23ADM第二章第二

18、章 优化设计的数学基础优化设计的数学基础l矩阵的正定与负定矩阵的正定与负定 二次型 对 若133132232112233222211321222),(321xxaxxaxxaxaxaxaxxxFAXXT 0XanyXFXFXFXFXF)(0)(0)(0)(0)(A为正定；A为半正定；A为负定；A为半负定不定24ADM第二章第二章 优化设计的数学基础优化设计的数学基础矩阵正、负定的判定 对称矩阵A正定的充要条件：其行列式各阶主子式之值均大于0; 对称矩阵A负定的充要条件：各阶主子式的值，应负、正交替地变化符号 。1.3 多元函数的方向导数与梯度多元函数的方向导数与梯度1.3.1 方向导数：函数在

19、任意方向上的变化规律方向导数：函数在任意方向上的变化规律 2201100coscosxXFxXFSXF25第二章第二章 优化设计的数学基础优化设计的数学基础1. 3.2 梯度：函数增加最快的方向梯度：函数增加最快的方向nixFXFTi,.,2, 1,)(1.3.3 多元函数的二阶偏导与海赛矩阵多元函数的二阶偏导与海赛矩阵njixxFHji,.,2 , 1,2 22221222222122122122122nnnnnxXFxxXFxxXFxxXFxXFxxXFxxXFxxXFxXFXF26ADM第二章第二章 优化设计的数学基础优化设计的数学基础1.4 多元函数的泰勒级数展开多元函数的泰勒级数展开

20、 XXHXXFXXFXFFXXXHXXXFXXXFXFTTTT)(21)()()()()(21)()()()(000000000 nnnRxxxFnxxxFxxxFxFxF 00200000!121一元函数泰勒展开式一元函数泰勒展开式：多元函数泰勒展开式多元函数泰勒展开式：27ADM第二章第二章 优化设计的数学基础优化设计的数学基础1.5 无约束优化问题的极值条件无约束优化问题的极值条件 极值定义：在X0点的某邻域 内，若)(0X)()()()(00XFXFXFXFX0为严格极大值点；为严格极大值点；X0为严格极小值点；为严格极小值点；极值存在的必要条件：梯度为0T向量 0)(0XF极值存在的

21、充分条件：XXHXXXHXXFXFTTT)(21)(21)(000H(X0)正定，正定， F(X0)为极小值；为极小值；H(X0)负定，负定， F(X0)为极大值。为极大值。凸函数凸函数： 212111XFaXaFXaaXF28第二章第二章 优化设计的数学基础优化设计的数学基础1.6 凸规划凸规划凸集：凸集：29第一章第一章 优化设计的基本概念优化设计的基本概念凸规划凸规划： XFmin 0Xgjmj, 2 , 1 s.t凸规划凸规划的的性质性质：（1）若给定一点）若给定一点， 0 x，则集合，则集合0XFXFXR为凸集为凸集 。（2）可行域）可行域 mjxgjXR,2, 10为凸集。为凸集。

22、（3）凸规划的局部最优解就是全局最优解。凸规划的局部最优解就是全局最优解。30第一章第一章 优化设计的基本概念优化设计的基本概念1.7 等式约束优化问题的极值等式约束优化问题的极值（1）消元法（降维法）消元法（降维法）（2）拉格朗日乘子法（升维法）拉格朗日乘子法（升维法） lkXhk,3 , 2 , 10 XFmin lkkkXhXFXL1,构造拉格朗日函数构造拉格朗日函数转化为无约束问题转化为无约束问题31ADM1.8 目标函数的约束极值问题目标函数的约束极值问题 目标函数的约束极值约束极值，又称为条件极值条件极值。与前面所讨论的无约束条件下函数的极值问题的区别在于它是带有约束的条件下的函数

23、极值问题。在约束条件下所求得的函数极值点，称为约束极值点约束极值点。 对于带有约束条件的目标函数，其求最优解的过程可归结为，寻求一组设计变量,在满足约束方程的条件下，使目标函数值最小，这样求得的最优点X*，称为约束最优点约束最优点。 两者重合 两者不重合 自然极值点与约束最优点的相互关系第二章第二章 优化设计的数学基础优化设计的数学基础32 （a） （b）可行域形状对约束最优解的影响（a）可行域为凸集（b）可行域为非凸集ADM第二章第二章 优化设计的数学基础优化设计的数学基础33ADM 目标函数或约束函数的非凸性使约束极值点增多情况 Kuhn-Tucker最优胜条件最优胜条件简称为Kuhn-T

24、ucker条件或K-T条件，可有效地用于对约束极值点存在条件的分析、检验。K-T条件如下：设X*为非线性规划问题 pmmjhmjgtsFjjn, 2, 10)(, 2 , 10)(. .)(minXXEXX第二章第二章 优化设计的数学基础优化设计的数学基础34ADM的约束极值点，且在全部等式约束及不等式约束条件中共有q个约束条件为起作用约束，即 , (ij，i+j = 1,2,q p)。如果在X*处诸起作用约束的梯度向量 、 (i+j = 1,2,q 0为步长，为步长， 若若 f(xk-2 )0 或或 f(xk-2 )0, f(xk)=2 则则 xk-2 , xk或或xk xk-2 为单峰区为

25、单峰区间间xk-2 xk-1 xk h 2hf046ADM第三章第三章 一维优化问题一维优化问题3.2 黄金分割法黄金分割法3.2.1 区间缩小求解极值点的基本思路区间缩小求解极值点的基本思路 按一定规则在按一定规则在a,b内取两个点内取两个点x1,x2a x1 x2 b a x1 x2 b a x1 x2 b (a) (b) (c) f(x1)f(x2) f(x1)=f(x2)a,b a,x2 a,b x1,b a,b a,x2 或或x1,b 47ADM第三章第三章 一维优化问题一维优化问题3.2.2 取点规则取点规则黄金分割法黄金分割法(0.618法，均匀缩短率对称取点法，均匀缩短率对称取

26、点) 黄金分割：将一线段分割成两段，使得整段长度黄金分割：将一线段分割成两段，使得整段长度L与较长段与较长段x 的的比值等于较长段比值等于较长段x与较短段与较短段L-x 的比值的比值L a x1 x2 b LLxLxLLxL)1 (LL)1 (LL)1 (618. 0215012LL)1 ()(618. 0),(382. 021abaxabax48ADM第三章第三章 一维优化问题一维优化问题3.2.3 区间收缩区间收缩 参见参见 3.2 1618. 0lnlnlnln)(ababNabN49ADM第三章第三章 一维优化问题一维优化问题3.2.4 收敛判据收敛判据 常用判据常用判据 1） 2）

27、3） 4） 判据的使用判据的使用 1)、3)或或2)、4)组合使用，并从组合使用，并从a, b, (a+b)/2中选最优者中选最优者4321)(/)()()()(/bfbfafbfafbbabaff a b a b50ADM第三章第三章 一维优化问题一维优化问题3.3 对分法对分法3.3.1 中心对分法（可微中心对分法（可微） 比较比较的符号，将区间的符号，将区间a,b缩短一半。缩短一半。3.3.2 两点对分法（可不可微两点对分法（可不可微） 2),( ),( bafbfaf a (a+b)/2 b0)( af0)2( baf0)( bf2,baabaa x1 x2 b f1 f2 有明显的差

28、异。的选取应使21221,)(ffxabaxfxf(a+b)/22251ADM第三章第三章 一维优化问题一维优化问题3.4 二次插值法二次插值法 二次插值：二次多项式逼近二次插值：二次多项式逼近3.4.1 方法原理方法原理 二次多项式逼近目标函数，以二次多项式的极小值点作为目标函数的二次多项式逼近目标函数，以二次多项式的极小值点作为目标函数的近似最优点。近似最优点。3.4.2 二次多项式构造二次多项式构造 单峰区间单峰区间x1,x3内存在极小值点，内存在极小值点，在在x1,x3内取点内取点x2，则则过过x1,x2,x3构造构造其极小值点为其极小值点为x* 321xfxfxf2)(cxbxaxp

29、 x1 x2 x* x* x3 32132,*,*,xxxxxxf(x)p(x)52ADM第三章第三章 一维优化问题一维优化问题3.4.3 区间缩小原理区间缩小原理 比较比较f(x*)和和f(x2)，以其中较小者对应的点为新的以其中较小者对应的点为新的x2点，新点，新 x2左右相邻左右相邻的点分别为新的点分别为新x1 ，新，新 x3 。3.4.4 收敛判据收敛判据见黄金分割法见黄金分割法习题习题初始区间初始区间 a,b = -0.5,1.5，绝对精度绝对精度分别用解析法、黄金分割法、中心对分法、两点对分法求解。分别用解析法、黄金分割法、中心对分法、两点对分法求解。) 1(5)(min1xexf

30、x15. 053ADM第四章第四章 无约束优化问题无约束优化问题nRXXF)(min分类：分类：1）直接法（不需计算导数）直接法（不需计算导数） 2）间接法（需计算导数）间接法（需计算导数）)()()()1()()()()(minkkkkkkkSXXSXF54ADM4.1 最速下降法（梯度法）最速下降法（梯度法）4.1.1 方法原理方法原理 将将n维优化问题转化为沿负梯度方向的一维搜索求优。维优化问题转化为沿负梯度方向的一维搜索求优。 1） 搜索方向、最优步长及迭代公式搜索方向、最优步长及迭代公式 2）收敛判据）收敛判据 ( )( )( )( )( )( )(1)( )( )( )()()mi

31、n()kkkkkkkkkkF XSF XF XSXXS 方向：步长：)(0)(kXFF极值条件：第四章第四章 无约束优化问题无约束优化问题55ADM4.1.2 梯度法的特点梯度法的特点 1）对初始点没有要求，可任选对初始点没有要求，可任选 2）相邻两点的搜索方向正交，）相邻两点的搜索方向正交， 亦即，梯度法迭代路径为绕道逼近极小点。负梯度方向仅是局部下亦即，梯度法迭代路径为绕道逼近极小点。负梯度方向仅是局部下降最快，不是最好的下降方向。梯度法不是最有效的算法。降最快，不是最好的下降方向。梯度法不是最有效的算法。0)()()()(0)( )()()()1()()()()()()(kTkkTkkk

32、kkXFXFXFXFXFfXFXFf第四章第四章 无约束优化问题无约束优化问题56ADM第四章第四章 多维无约束优化问题多维无约束优化问题4.2 坐标轮换法（坐标方向为搜索方向）坐标轮换法（坐标方向为搜索方向）4.2.1 原理原理 将将n维问题转化为依次沿维问题转化为依次沿n个坐标方向轮回进行一维搜索。个坐标方向轮回进行一维搜索。57ADM第四章第四章 无约束优化问题无约束优化问题4.2.2 算法算法 1）任选初始点任选初始点 设定初始步长设定初始步长 置搜索方向置搜索方向 2）以）以 为初始点，沿为初始点，沿 方向作试探，步长方向作试探，步长 计算计算 ，若，若 说明试探成功；否则，说明试探

33、成功；否则， 若若 ，置，置 ，若，若 ，TnxxxX,.,)0()0(2)0(1)0(0)01. 0(0TnTTieeeS 1,.,0 , 0 , 0.0,.,0 , 1 , 00,.,0 , 0 , 1 21)0(X1e01)0(eXX)()()0(XFXF和)()()0(XFXF)()()0(XFXF0)()()0(XFXF58ADM第四章第四章 无约束优化问题无约束优化问题 则作一维搜索求最优步长和优化点则作一维搜索求最优步长和优化点 若沿坐标轴正负方向试探均失败，则迭代点不变若沿坐标轴正负方向试探均失败，则迭代点不变 3）以）以 为起点，按为起点，按1）沿）沿 方向搜索，得方向搜索，

34、得 沿沿n个坐标方向进行完一轮一维搜索后，得个坐标方向进行完一轮一维搜索后，得 4）以）以 作第二轮得起始点作第二轮得起始点 ，重复，重复2）、）、3）得第二轮搜索）得第二轮搜索终点终点 。 5）如果从某轮起始点出发，依次沿）如果从某轮起始点出发，依次沿n个坐标轴的正负方向试探均失败，个坐标轴的正负方向试探均失败，则缩短试探步长（如减半），返回则缩短试探步长（如减半），返回2）。当探索步长足够小，满足收敛判）。当探索步长足够小，满足收敛判据据 时，终止迭代，所得点即为优化结果时，终止迭代，所得点即为优化结果X*。SXXSXF)0()1()0(1)(min)0()1(1XX)1(1X2e)1(2

35、X)1(nX)1(nX)1()2(0nXX)2(nXmin59ADM第四章第四章 无约束优化问题无约束优化问题4.2.3 讨论讨论 1）计算量小，程序简单，计算效率低，适合变量）计算量小，程序简单，计算效率低，适合变量n10的情况。的情况。 2）若目标函数具有脊线，算法将出现病态：沿两个坐标方向均不能使）若目标函数具有脊线，算法将出现病态：沿两个坐标方向均不能使函数数值下降，误认为最优点。函数数值下降，误认为最优点。脊线脊线60ADM第四章第四章 无约束优化问题无约束优化问题4.3 鲍威尔法（共轭方向为搜索方向）鲍威尔法（共轭方向为搜索方向）4.3.1 共轭方向共轭方向 1）定义）定义 A为为

36、n阶正定矩阵，若两个阶正定矩阵，若两个n维矢量满足维矢量满足 则称则称S1和和S2对矩阵对矩阵A共轭，共轭矢量方向为共轭方向。共轭，共轭矢量方向为共轭方向。 对于对于n个个n维矢量维矢量Si，i=1,2,n(Si不为不为0)，若满足，若满足则称则称n个个n维矢量维矢量Si，i=1,2,n为对矩阵为对矩阵A共轭。共轭。 2）共轭方向与函数的极小值点关系）共轭方向与函数的极小值点关系 考察正定二次函数考察正定二次函数 其等值线为同心椭圆族其等值线为同心椭圆族021ASST1S2SAST1AST2jiASSjiASSjTijTi, 0, 0AXXXbaXFTT21)(61ADM第四章第四章 无约束优

37、化问题无约束优化问题S2S1S1X1X2X1(0)X2(0)x1x2 从从X1(0)出发沿出发沿S1方向作一维搜索，方向作一维搜索，得最优点得最优点X1 （与椭圆相切）；从（与椭圆相切）；从X2(0)出发沿出发沿S1方向作一维搜索，得最优点方向作一维搜索，得最优点X2；连接；连接X1 、 X2得矢量得矢量S2 ， S2过椭过椭圆族中心，即目标函数极小值点圆族中心，即目标函数极小值点X*，且且S1、S2对对A正交，正交，沿沿S1 的共轭方向的共轭方向S2可搜索到正定二元可搜索到正定二元二次函数极值点二次函数极值点。X*00)(0)(1112121211112ASSASXXSAXbSXFSAXbS

38、XFTTTT二式相减1()F X62ADM第四章第四章 无约束优化问题无约束优化问题4.3.2 原始鲍威尔法原始鲍威尔法 S1 、S2、 S3为共、轭为共、轭方向（方向（参见前页参见前页） 搜索方向搜索方向: x1x3x2e1e2e3X0(1)S1e2e3S1X1(1)X2(1)X3(1)X0(2)X1(2)X2(2)X3(2)X0(3)S2e3S1S2S3X1(3)X2(3)X3(3)X0(4)第第1轮轮第第2轮轮第第3轮轮)()()()1()()()()(minkkkkkkkSXXSXF)4(0)4(34321)3(0)3(33213)2(0)2(32132)1(0)1(31321,4,3

39、,2,1XXSSSSXXSSSeXXSSeeXXSeee轮：第轮：第轮：第轮：第63ADM第四章第四章 无约束优化问题无约束优化问题 原始鲍威尔法的严重缺陷：当某一轮方向组中的矢量系出现线性相关时原始鲍威尔法的严重缺陷：当某一轮方向组中的矢量系出现线性相关时（特别是接近（特别是接近X*时），会出现退化，无法获得极小值点。时），会出现退化，无法获得极小值点。4.3.3 改进鲍威尔法改进鲍威尔法 与原始鲍威尔法的区别：每构造一个新方向，根据判别条件决定是否替与原始鲍威尔法的区别：每构造一个新方向，根据判别条件决定是否替换原来的某个方向。构造换原来的某个方向。构造k+1轮方向组时，是否淘汰前一轮的某

40、一个方向轮方向组时，是否淘汰前一轮的某一个方向Sm(k) ，根据下面二个条件判断：根据下面二个条件判断：31221231213( )10( )2( )( )30( )( )1).).222maxkknkknkkmmaFFbFFFFFFFFF XFF XFFXXF XF X 第第k轮初始点函数值；轮初始点函数值；第第k轮最后一个方向搜索终点函数值；轮最后一个方向搜索终点函数值；X0(k)对对Xn(k) 映射点映射点Xn1(k)的函数值；的函数值；一维搜索中函数值下降最大者，其方一维搜索中函数值下降最大者，其方向为向为Sm(k) 64ADM 条件式条件式a)、b)同时或两者之同时或两者之一成立：第

41、一成立：第k+1轮仍沿用第轮仍沿用第k轮的轮的方向组，取方向组，取Xn(k)（ F2 F3）或映）或映射点射点Xn1(k)（ F3 F(X(k)。不是严格的下降算法。原因：不是严格的下降算法。原因： X(k+1)是近似二次式在牛是近似二次式在牛顿方向上的极小点，而非顿方向上的极小点，而非F(X)在牛顿方向上的极小点。在牛顿方向上的极小点。 2）对牛顿法的修正）对牛顿法的修正阻尼牛顿法阻尼牛顿法 修正方法：在牛顿方向上作一维搜索求最优步长。修正方法：在牛顿方向上作一维搜索求最优步长。 当当F(X)的海赛矩阵的海赛矩阵Hk在迭代点处在迭代点处正定正定情况下，阻尼牛顿法可以保证每次迭情况下，阻尼牛顿

42、法可以保证每次迭代，迭代点的函数值都代，迭代点的函数值都下降；下降； Hk在迭代点处在迭代点处不定不定情况下，函数值不会上升，但情况下，函数值不会上升，但不一定下降；不一定下降； Hk在迭代点处在迭代点处奇异奇异情况下，不能求逆，无法构造牛顿方向；要求情况下，不能求逆，无法构造牛顿方向；要求F(X)二阶可微，需计算梯度、海赛矩阵及其逆矩阵，计算量大二阶可微，需计算梯度、海赛矩阵及其逆矩阵，计算量大。4.4.3 收敛判据收敛判据 同梯度法。同梯度法。kkkkkkkkgHXXSXF1)()()1()()()()(min步长：第四章第四章 无约束优化问题无约束优化问题68ADM第四章第四章 无约束优

43、化问题无约束优化问题69ADM4.5 DFP变尺度法变尺度法拟牛顿法，基于牛顿法的思想进行了重要改进。拟牛顿法，基于牛顿法的思想进行了重要改进。4.5.1 基本思想基本思想 综合梯度法和牛顿法的优有点，克服梯度法收敛速度慢和牛顿法收敛综合梯度法和牛顿法的优有点，克服梯度法收敛速度慢和牛顿法收敛快但稳定性差且计算量大的缺点。快但稳定性差且计算量大的缺点。 比较梯度法和牛顿法，比较梯度法和牛顿法，)()()()()()1(1)()()1()()()()()()1()(:kkkkkkkkkkkkkkkkkkkSXgAXXDFPgHXXgXXFXXk：变尺度法迭代公式将二者统一为牛顿法：梯度法第四章第

44、四章 无约束优化问题无约束优化问题70ADM Ak为为nn对称矩阵，对称矩阵， Ak为单位矩阵时，上式为梯度法；为单位矩阵时，上式为梯度法； AkHk-1时，时，上式为阻尼牛顿法。上式为阻尼牛顿法。 拟牛顿法的基本思想：用某种方法，人为构造一拟牛顿法的基本思想：用某种方法，人为构造一n阶对称矩阵阶对称矩阵 AkA(X(k)，近似替代牛顿法的近似替代牛顿法的Hk-1。通过迭代不断修正。通过迭代不断修正Ak， 使使Ak Hk-1。 由于是不断变化的，它使搜索方向不断向牛顿方向逼近，故可把看由于是不断变化的，它使搜索方向不断向牛顿方向逼近，故可把看作是变化的尺度矩阵，这就是变尺度法叫法的由来。梯度法

45、和牛顿作是变化的尺度矩阵，这就是变尺度法叫法的由来。梯度法和牛顿法也属于变尺度法的范畴。法也属于变尺度法的范畴。 Ak应满足的条件应满足的条件： 1. 正定正定 保证迭代过程中函数值始终下降，要求保证迭代过程中函数值始终下降，要求S(k)与与gk夹角为锐角，即夹角为锐角，即0)(kTkgS第四章第四章 无约束优化问题无约束优化问题712. 拟牛顿条件拟牛顿条件使使Ak Hk-1，Ak1可以由第可以由第k步的信息递推构造步的信息递推构造由由得得即即 ADM第四章第四章 无约束优化问题无约束优化问题 00kkTkkTkkgAgggAXHXXgFXFkTTkk21)()()1(1)()(kkkkkk

46、kXHgXFgXHgXFg)(1kkkkkXHgggkkkkkkgAXgHX1)(1)(72ADM第四章第四章 无约束优化问题无约束优化问题.;min.1)()()()()1()(1)1(1)()()1()()(0010kkkkkTkkTkkkkTkTkkkkkkkkkkkkkkkkkkkkAAAgAgAggAgXXXAXXXgggXFggAXXgAXFAAAEA4.5.2 Ak序列的生成（序列的生成（DFP递推公式）递推公式）73ADM第四章第四章 无约束优化问题无约束优化问题4.5.3 算法算法 1）任选初始点）任选初始点X(0)，收敛精度收敛精度 2）置置k=0，Ak=E（单位矩阵）；单

47、位矩阵）； 3）沿）沿 4） 5）用）用DFP公式求公式求Ak+1； 6）置置 。若。若kn（变量数目），转到变量数目），转到3），否则返回到），否则返回到2）开）开始下一轮（从负梯度法重开始，有利于收敛）；始下一轮（从负梯度法重开始，有利于收敛）； 7）输出结果）输出结果X*，F(X*)，结束。结束。），否则进行下一步；转到，若点的梯度。计算700)0(ggX)(min)(,)()()()()()()(kkkkkkkkkSXFSXFgAS使优步长方向作一维搜索，求最），否则继续；，转到。若，7)(1)1(1)()()()1(kkkkkkkgXFgSXX1 kk74ADM第四章第四章 无约束优

48、化问题无约束优化问题4.6共轭梯度法共轭梯度法 将梯度法和共轭方向法结合起来，每一轮搜索的第一步沿负梯度方向将梯度法和共轭方向法结合起来，每一轮搜索的第一步沿负梯度方向搜索，后续各步沿上一步的共轭方向搜索，具有二次收敛速度，每一搜索，后续各步沿上一步的共轭方向搜索，具有二次收敛速度，每一轮搜索轮搜索n步。步。第一步的搜索方向第一步的搜索方向负梯度方向负梯度方向 以后各步的搜索方向以后各步的搜索方向共轭方向共轭方向的确定的确定应使应使n n维实空间中的两个非维实空间中的两个非0 0向量向量S(k)和和S(k1)关于矩阵关于矩阵A共轭，共轭，即应使即应使 对于正定二次函数对于正定二次函数有有)(1

49、)()1()1()(kkkkkSgSXFS0SS(k)1)(kATAXXXbaXFTT21)()1()1(1)()()()(kkkkkkAXbXFgAXbXFg75ADM第四章第四章 无约束优化问题无约束优化问题二式相减二式相减 而而则则可得可得即即因因 为一正交系，为一正交系，故有故有则则 )()1(1kkkkXXAgg)()()()1(kkkkSXX)()(1kkkkSAgg01SSS)(11)(k(k)1)(kkkkTTggA0SSS1)(111)(k(k)1)(kkkTkkkkTTggSgggA01.gggkk，00)(11kTkkTkSggg或011kTkkTkgggg22111kk

50、kTkkTkgggggg76ADM第四章第四章 无约束优化问题无约束优化问题77ADM第四章第四章 无约束优化问题无约束优化问题算法算法l任选初始点任选初始点X(0)，给定收敛精度给定收敛精度和维数和维数n n；2令令 ，求迭代初始点，求迭代初始点X(0)的梯度的梯度g0取第一次搜索的方向取第一次搜索的方向S(0)为初始点的负梯度为初始点的负梯度3 3进行一维搜索，求最优步长进行一维搜索，求最优步长( (k k) )并求出新点并求出新点 4 4计算计算X(k+1)点的梯度点的梯度5收敛检查。满足条件收敛检查。满足条件则，计算结束；否则继续下一步；则，计算结束；否则继续下一步；6判断判断k+1是

51、否等于是否等于n，若若k+1n，则令则令X(0)= =X(k+1)转步骤转步骤2；若；若k+1 n，则继续下一步；则继续下一步；7 7计算计算 0k)()(kkXFgkkgS)(2)1()(kXF)()()()1()()()()(minkkkkkkkSXXSXF)()1(1kkXFg78ADM第四章第四章 无约束优化问题无约束优化问题8确定下一步的搜索方向确定下一步的搜索方向 令令 ，返回步骤，返回步骤3。讨论讨论共轭梯度法具有超线性收敛速度（共轭梯度法具有超线性收敛速度（11收敛速度阶数收敛速度阶数2n因为当m=n时约束方程只有一个唯一的解，不存在可供选择的其它解，不存在优化问题。当mn时，

52、约束方程有无穷多组解，线性规划就是要从这无穷多组解中寻找一个使目标函数极小化的最优解。线性规划的数学模型中，约束条件主要是等式约束，不等式约束仅限于变量的非负约束。对于其它形式的不等式约束的话，可以通过引人松弛变量的方法将其转化为等式约束。例如，对于约束条件可通过引入松弛变量x30，变换为如果原来问题中的某些变量并不要求非负，则可将其变换为两个非负变量之差0, 00222121xxxx0, 0, 022321321xxxxxx0, 0 kkkkkxxxxx92例：例：某车间生产甲、乙两种产品。生产甲种产而每件需要材料9kg、3个工时、4kW电，可获利60元。生产乙种产品每件需用材料4kg、10

53、个工时、5kW电，可获利120元。若每天能供应材料360kg，有300个工时，能供200kW电，则每天生产甲、乙两种产品各多少件，才能够获得最大的利润。设每天生产的甲、乙两种产品分别为x1、x2件，则此问题的数学模型如下引入松弛变量x3、x4、x5将其转换为标准形式)(0, 0)(20054)(300103)(36049. .)(12060),()(max212121212121非负约束电力约束工时约束材料约束最大利润xxxxxxxxtsxxxxFF X0, 0, 0, 0, 02000054300001033600049. .12060)(min5432154321543215432121x

54、xxxxxxxxxxxxxxxxxxxtsxxF XADM第五章第五章 线性规划线性规划93ADM第五章第五章 线性规划线性规划二维线性规划问题的图解法94ADM第五章第五章 线性规划线性规划在约束方程中，若令n-m个变量为0，就可求得另外m个不全为0的解。于是这m个不全为0的解和n-m个为0的解共同组成一个解向量，称为线性规划问题的基本解。其中m个不全为0的变量称基本变量，其余n-m个为0的变量称非基本变量。若构成基本解的基本变量均为非负值，则称这样的基本解为基本可行解。可见，基本可行解是同时满足约束方程和变量非负约束的基本解。因此，线性规划问题的求解可归结为从所有基本可行解中找出使目标函数

55、取极小值的最优解。在系数矩阵中，任取m列可以构成一个基本解。可知，一个线性规划问题的基本解的个数等于排列组合数)!( !mnmnCmn95ADM第五章第五章 线性规划线性规划由图示的线性规划的图解法可以看出，线性规划的约束边界为一组直线或平面，由这些直线和平面构成的可行域是一个封闭的凸多边形或凸多面体。这个凸多边形或凸多面体的每一个顶点对应该线性规划问题的一个基本可行解。因此线性规划问题的最优解必定在这些顶点上取得。实际上，线性规划解法就是一种关于基本可行解的迭代算法，或者说一种可行域顶点转换的算法。 二、基本可行解及其转换二、基本可行解及其转换既然线性规划问题的最优解必定在约束条件所围成的凸

56、多边形或凸多面体的顶点上取得，而每一个顶点都是线性规划问题的一个基本可行解，则线性规划问题的求解可归结为找出目标函数值下降的基本可行解的过程。这样，求解线性规划问题须解决以下两个问题：1）基本可行解的求解；2）新的基本可行解应使目标函数应有较大的下降。1基本解及其的转换基本解及其的转换（1）基本解的产生根据基本解的定义，对由系数矩阵和常数向量组成的如下增广矩阵96ADM第五章第五章 线性规划线性规划 进行一系列初等变换，将其中系数矩阵的m列依次变为基向量时，满足约束方程的一个基本解便产生了。若经m次主元变换后，将增广矩阵的前m列变为如下单位子矩阵mmnmmnnbbbaaaaaaaaa.2121

57、222211121121, 2, 1, 2, 11,1, 21, 1.1.00.0.100.01mnmnnkmkkmmmmbbbaaaaaaaaa97ADM第五章第五章 线性规划线性规划约束方程变换为如下的正则方程 则，对应的基本解为 21121, 2, 1, 2, 11,1, 21, 1.1.00.0.100.01mnkmmsnmnnkmkkmmmmbbbxxxxxxxaaaaaaaaaTmbbb0.0.21X98其中，前m个变量为基本变量，后n-m个变量为非基本变量。若变换后的常数项均为非负，即 ，则此基本解是一个基本可行解。可见，得到一个基本解或基本可行解的方法，都是对增广矩阵进行高斯消

58、元变换。消元变换的基本公式为 上式表明了对转轴变量转轴变量xk以为转轴元素转轴元素的转轴变换转轴变换（Pivot operation）或消元消元变换变换,上标表示变换的次数。0ibADM第五章第五章 线性规划线性规划()()(1,2,.,;1,2,., )()()ljljlkljijijiklklllkiiiiklkaailaaaaailaim jnbbilabbbaila99ADM第五章第五章 线性规划线性规划（2）解的转换在增广矩阵中，将某一非基本变量xm+s对应的任意一个系数作为转轴变换的转轴元素，进行另一次消元变换，又可得到一个新的增广矩阵和相应的基本解。这种变换实际上是一种非基变量和

59、基本变量的转换，也是从一组基本解向另一组基本解的转换。但是这样的变换并不能保证变换后的常数向量为非负。也就是说，如果原来的解是一个基本可行解，不能保证变换后的解也是一个基本可行解。 2基本可行解的转换基本可行解的转换规则规则（选择转轴行）要使变换后所得的基本解为可行解，还要研究这样的方法，即如何使某个选定的变量xk（k=m+1,m+2,n）进入基本变量，来替换另一个现在还在基本变量中的xs（k=1,2,m），形成新的基本可行解。当已经得到一组可行解，即，若要求把xk选进基本变量的下一组基本解是可行解的话，则在系数矩阵第k列所有系数中不能取任何负值的作为转轴元素否则将使转轴变换后的对应元素为负值

60、，结果对应的xk必将是负的，它就不是可行解的一个元素。 100ADM第五章第五章 线性规划线性规划因此，第一个要求是，若 都是非负的，则必须 才可选做转轴元素进行转轴运算，用xk去代替xs。这个过程是：反复进行转轴运算，直到xs从某个正值变成0，而xk则从0变成某个正值为止。根据原来的正则形式方程组式，由于要求xk由非基本变量变成基本变量，其值将由0变成某一正值，这将引起原来各基本变量取值的变化 如果上式是可行解，且 又是其中的一个基本变量，则在中必然有一个(假定它是，sm)是0，其余皆为正。当然这个变量 就应从基本变量中排除出去。lb0lka2222211111.mkmkmkmmlklklk