建模仿真与优化设计2010.ppt

《建模仿真与优化设计2010.ppt》由会员分享，可在线阅读，更多相关《建模仿真与优化设计2010.ppt（138页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、建模仿真建模仿真与与优化设计优化设计第一部分第一部分中北大学中北大学 张保成张保成1.掌握优化问题的数学描述方法；掌握优化问题的数学描述方法；2.熟练掌握常用优化算法。熟练掌握常用优化算法。一一 优化模型的一般意义优化模型的一般意义 二二 非线性规划建模非线性规划建模无约束最优化无约束最优化 三三 非线性规划建模非线性规划建模有约束有约束非线性规划非线性规划 四四 连续结构体建模与优化设计连续结构体建模与优化设计学学习习内内容容目目的的（一）优化模型的数学描述（一）优化模型的数学描述下的最大值或最小值，其中下的最大值或最小值，其中设计变量（决策变量）设计变量（决策变量）目标函数目标函数将一个优

2、化问题用数学式子来描述，即求函数将一个优化问题用数学式子来描述，即求函数在约束条件在约束条件和和可行域可行域一一 优化模型的一般意义优化模型的一般意义“受约束于”之意（二）优化模型的分类（二）优化模型的分类1.1.根据是否存在约束条件根据是否存在约束条件 有约束问题和无约束问题。有约束问题和无约束问题。2.2.根据设计变量的性质根据设计变量的性质 静态问题和动态问题。静态问题和动态问题。3.3.根据目标函数和约束条件表达式的性质根据目标函数和约束条件表达式的性质 线性规划，非线性规划，二次规划，多目标规划等。线性规划，非线性规划，二次规划，多目标规划等。（1）非线性规划）非线性规划目标函数和约

3、束条件中，至少有一个非线性函数。目标函数和约束条件中，至少有一个非线性函数。（2）线性规划（）线性规划（LP）目标函数和所有的约束条件都是设计变量目标函数和所有的约束条件都是设计变量的线性函数。的线性函数。（3）二次规划问题）二次规划问题目标函数为二次函数，约束条件为线性约束目标函数为二次函数，约束条件为线性约束5.根据变量具有确定值还是随机值根据变量具有确定值还是随机值 确定规划和随机规划。确定规划和随机规划。4.4.根据设计变量的允许值根据设计变量的允许值整数规划（整数规划（0-1规划）和实数规划。规划）和实数规划。（三）建立优化模型的一般步骤（三）建立优化模型的一般步骤1.确定设计变量和

4、目标变量；确定设计变量和目标变量；2.确定目标函数的表达式；确定目标函数的表达式；3.寻找约束条件。寻找约束条件。二、优化求解的数学基础二、优化求解的数学基础函数的梯度函数的梯度泰勒展开泰勒展开二阶导数矩阵二阶导数矩阵矢量的概念、运算和点积矢量的概念、运算和点积矩阵的运算和逆矩阵矩阵的运算和逆矩阵（一）方向导数（一）方向导数 和和 分别是分别是 函函数数 f(x1,x2)在在x0点处沿点处沿坐标轴坐标轴x1和和x2方向的变方向的变化率化率 故函数故函数 f(x1,x2)在在x0(x10,x20)点点处沿某一方向处沿某一方向S的变化率为：的变化率为：称为该函数沿此方向的方向导数称为该函数沿此方向

5、的方向导数 偏导数可以看作是函数沿坐标轴偏导数可以看作是函数沿坐标轴方向的方向导数，并有方向的方向导数，并有（二）梯度（二）梯度 二元函数在点二元函数在点x0的梯度是由函数在该点的各一阶偏导数组的梯度是由函数在该点的各一阶偏导数组成的向量。即成的向量。即:S d x2 x1x0 2 1x10 x20 x2x1X二、优化求解的数学基础二、优化求解的数学基础 设设S方向单位向量方向单位向量 则有则有 函数的梯度具有以下性质：函数的梯度具有以下性质：（1）函数在一点的梯度是一个向量。梯度的方向是该点函数）函数在一点的梯度是一个向量。梯度的方向是该点函数值上升最快的方向，与梯度相反的方向是该点函数值下

6、降值上升最快的方向，与梯度相反的方向是该点函数值下降的最快的方向，梯度的大小就是它的模长。的最快的方向，梯度的大小就是它的模长。（2）一点的梯度方向是与过该点的等值线或等值面的切线或）一点的梯度方向是与过该点的等值线或等值面的切线或切平面相垂直的方向，或者说是该点等值线或等值面的法切平面相垂直的方向，或者说是该点等值线或等值面的法线方向。线方向。（3）梯度是函数在一点邻域内局部形态的描述。在一点上升）梯度是函数在一点邻域内局部形态的描述。在一点上升得快的方向，离开该领域后就不一定上升得快，甚至可能得快的方向，离开该领域后就不一定上升得快，甚至可能下降。下降。二、优化求解的数学基础二、优化求解的

7、数学基础（三）泰勒展开（三）泰勒展开 为了便于数学问题的分析和求解，往往需要将一个为了便于数学问题的分析和求解，往往需要将一个复杂的非线性函数简化成线性函数或二次函数。简化的复杂的非线性函数简化成线性函数或二次函数。简化的方法可以采用泰勒展开式。方法可以采用泰勒展开式。由高等数学可知，一元函数由高等数学可知，一元函数 f(x)若在点若在点x0的邻域内的邻域内n阶可导，则函数可在该点邻域内作泰勒展开：阶可导，则函数可在该点邻域内作泰勒展开：二元函数二元函数 f(x)在点在点x0(x10,x20)也可以作泰勒展开，展也可以作泰勒展开，展开式一般取前三项，即：开式一般取前三项，即：二、优化求解的数学

8、基础二、优化求解的数学基础将上式写为矩阵形式将上式写为矩阵形式 其中，其中，G(x0)称为函数称为函数 f(x1,x2)在点在点x0处处的的二阶导数矩阵或海赛矩阵。二阶导数矩阵或海赛矩阵。二、优化求解的数学基础二、优化求解的数学基础 在优化计算中，当某点附近的函数值采用泰勒展开在优化计算中，当某点附近的函数值采用泰勒展开式作近似表达时，研究该点邻域的极值问题需要分析式作近似表达时，研究该点邻域的极值问题需要分析二次型函数是否正定。当对任何非零向量二次型函数是否正定。当对任何非零向量x使使 则二次型函数正定，则二次型函数正定，G为正定矩阵为正定矩阵二、优化求解的数学基础二、优化求解的数学基础（四

9、）二次函数（四）二次函数 当将函数的泰勒展开式取到二次项时得到二当将函数的泰勒展开式取到二次项时得到二次函数形式。优化计算经常把目标函数表示为二次次函数形式。优化计算经常把目标函数表示为二次函数以使问题分析得以简化。在线性代数中将二次函数以使问题分析得以简化。在线性代数中将二次齐次函数称作二次型，其矩阵形式齐次函数称作二次型，其矩阵形式 在优化计算中，当某点附近的函数值采用泰在优化计算中，当某点附近的函数值采用泰勒展开式作近似表达时，研究该点邻域的极值问题勒展开式作近似表达时，研究该点邻域的极值问题需要分析二次型函数是否正定。当对任何非零向量需要分析二次型函数是否正定。当对任何非零向量x使使

10、则二次型函数正定，则二次型函数正定，G为正定矩阵为正定矩阵二、优化求解的数学基础二、优化求解的数学基础 对于一般二次函数对于一般二次函数 矩阵有正定和负定之分。对于所有非零向量：矩阵有正定和负定之分。对于所有非零向量：（1）若有）若有 ，则称矩阵是正定的；，则称矩阵是正定的；（2）若有）若有 ，则称矩阵是半正定的；，则称矩阵是半正定的；（3）若有）若有 ，则称矩阵是负定的；，则称矩阵是负定的；（4）若有）若有 ，则称矩阵是半负定的；，则称矩阵是半负定的；（5）若有）若有 ，则称矩阵是不定的，则称矩阵是不定的二、优化求解的数学基础二、优化求解的数学基础 可以证明，正定二次函数具有以下性质：可以证

11、明，正定二次函数具有以下性质：（1）正定二次函数的等值线或等值面是一簇同心圆）正定二次函数的等值线或等值面是一簇同心圆或同心椭球。椭圆簇或椭球簇的中心就是该二次函或同心椭球。椭圆簇或椭球簇的中心就是该二次函数的极小点。数的极小点。（2）非正定二次函数在极小点附近的等值线或等值）非正定二次函数在极小点附近的等值线或等值面近似于椭圆或椭球。面近似于椭圆或椭球。二、优化求解的数学基础二、优化求解的数学基础（五）无约束优化问题的极值条件（五）无约束优化问题的极值条件 二次函数二次函数 f(x1,x2)在在x0取得极值的必要条件取得极值的必要条件为为 充分条件为：该点处海赛矩阵正定，即充分条件为：该点处

12、海赛矩阵正定，即二、优化求解的数学基础二、优化求解的数学基础正定：各阶主子式正定：各阶主子式均大于零。均大于零。现代设计方法概论课程教案（六）（六）下降迭代算法及其收敛性下降迭代算法及其收敛性无约束最优化问题求优过程的无约束最优化问题求优过程的求解方法大致分为两类。求解方法大致分为两类。（1）解析法）解析法Hessian矩阵正定矩阵正定极小值点极小值点Hessian矩阵负定矩阵负定极大值点极大值点二、优化求解的数学基础二、优化求解的数学基础现代设计方法概论课程教案（2）数值迭代计算）数值迭代计算（六）（六）下降迭代算法及其收敛性下降迭代算法及其收敛性二、优化求解的数学基础二、优化求解的数学基础

13、三、优化设计的迭代计算三、优化设计的迭代计算三、优化设计的迭代计算三、优化设计的迭代计算 （一）优化问题的求解方法（一）优化问题的求解方法 1、优化问题的本质、优化问题的本质优化问题的本质求极值的数学问题。优化问题的本质求极值的数学问题。2、优化问题的求解方法、优化问题的求解方法理论上理论上解析法解析法数值计算法数值计算法即应用极值理论求解即应用极值理论求解能求解吗能求解吗？由于实际由于实际优化数学优化数学模型的目模型的目标函数及标函数及约束函数约束函数往往是非往往是非线性的线性的解析法求解析法求解非常困解非常困难，甚至难，甚至无法实现无法实现（二）数值计算法的迭代方法（二）数值计算法的迭代方

14、法1、数值计算法的数学基础、数值计算法的数学基础计算方法计算方法2、数值计算法的迭代方法、数值计算法的迭代方法数值计算法可以数值计算法可以较好地解决这类较好地解决这类问题问题三、优化设计的迭代计算三、优化设计的迭代计算三、优化设计的迭代计算三、优化设计的迭代计算 从目标函数出发从目标函数出发构造一种使目标函数值逐次下降的数值计算方法构造一种使目标函数值逐次下降的数值计算方法利用计算机进行反复迭代运算利用计算机进行反复迭代运算一步步搜索、调优逐步逼近函数极值点或最优点一步步搜索、调优逐步逼近函数极值点或最优点直到满足一定的精度时终止迭代计算直到满足一定的精度时终止迭代计算最后所逼近的设计点即最优

15、点，所得最后所逼近的设计点即最优点，所得到的解即一定精度下的近似解到的解即一定精度下的近似解三、优化设计的迭代计算三、优化设计的迭代计算三、优化设计的迭代计算三、优化设计的迭代计算（三）迭代计算的迭代过程（三）迭代计算的迭代过程由选定的初始点由选定的初始点x(0)出发出发使使满足满足由于各设计点的函数值依由于各设计点的函数值依次下降，可见迭代点不断次下降，可见迭代点不断向理论最优点逼近，最后向理论最优点逼近，最后可得到一定精度下的近似可得到一定精度下的近似最优点，记作最优点，记作x*。适当的步长适当的步长(0)某种优化方法所规某种优化方法所规定的搜索方向定的搜索方向S(0)三、优化设计的迭代计

16、算三、优化设计的迭代计算三、优化设计的迭代计算三、优化设计的迭代计算 迭代过程图示：迭代过程图示：X(0)X(1)X(k)s(0)a(0)X(2)x*三、优化设计的迭代计算三、优化设计的迭代计算三、优化设计的迭代计算三、优化设计的迭代计算（四）迭代计算的终止准则（四）迭代计算的终止准则 由于数值迭代是逐步逼近最优点而获得近似解的，由于数值迭代是逐步逼近最优点而获得近似解的，所以要考虑优化问题解的收敛性及迭代过程的终止条件。所以要考虑优化问题解的收敛性及迭代过程的终止条件。1、迭代的收敛性、迭代的收敛性 指某种迭代程序产生的序列指某种迭代程序产生的序列xk (k=0,1,2,)收敛于收敛于2、通

17、常采用的终止准则、通常采用的终止准则（1）点距准则）点距准则|xk+1-xk|1相邻两个设计点相邻两个设计点的距离已达到充的距离已达到充分小分小或或两迭代点的坐标分两迭代点的坐标分量之差量之差三、优化设计的迭代计算三、优化设计的迭代计算三、优化设计的迭代计算三、优化设计的迭代计算 （2）函数下降量准则）函数下降量准则相邻迭代点的函数值下降相邻迭代点的函数值下降量达到充分小量达到充分小或或相邻迭代点的函数值的相相邻迭代点的函数值的相对值达到充分小对值达到充分小（3）梯度准则）梯度准则无约束最优化无约束最优化非线性规划建模非线性规划建模教学目的教学目的教学内容教学内容2、掌握用数学软件包求解无约束

18、最优化问题。、掌握用数学软件包求解无约束最优化问题。1、了解无约束最优化基本算法。、了解无约束最优化基本算法。1.1.无约束优化基本思想及基本算法无约束优化基本思想及基本算法。3.用用MATLAB求解无约束优化问题。求解无约束优化问题。2.MATLAB优化工具箱简介优化工具箱简介 无约束最优化问题无约束最优化问题求解无约束最优化问题的的基本思想求解无约束最优化问题的的基本思想*无约束最优化问题的基本算法无约束最优化问题的基本算法标准形式：标准形式：求解无约束最优化问题的基本思想求解无约束最优化问题的基本思想求解的基本思想求解的基本思想 (以二元函数为例)531连续可微多局部极小 唯一极小(全局

19、极小)搜索过程搜索过程最优点 (1 1)初始点 (-1 1)-114.00-0.790.583.39-0.530.232.60-0.180.001.500.09-0.030.980.370.110.470.590.330.200.800.630.050.950.900.0030.990.991E-40.9990.9981E-50.9997 0.9998 1E-8坐标轮换法坐标轮换法坐标轮换法坐标轮换法一、坐标轮换法的迭代过程一、坐标轮换法的迭代过程 如图，以二次函数为例。如图，以二次函数为例。x2x0 x01x02 x21x11x12x1x21坐标轮换法坐标轮换法坐标轮换法坐标轮换法 任取一初

20、始点任取一初始点x0作为第一轮的始点作为第一轮的始点x01,先沿第先沿第一坐标轴的方向一坐标轴的方向e1作一维搜索，用一维优化方法确作一维搜索，用一维优化方法确定最优步长定最优步长 11，得第一轮的第一个迭代点，得第一轮的第一个迭代点x11=x01+11 e1，然后以然后以x11为新起点，沿第二坐为新起点，沿第二坐标轴的方向标轴的方向e2作作一维搜索，确定步长一维搜索，确定步长 21，得第一，得第一轮的第二个迭代点轮的第二个迭代点x21=x11+11 e2 第二轮第二轮迭代，需要迭代，需要 x11x01 x12 x02+12 e1 x22=x12+22 e2 依次依次类推，不断迭代，目标函数值

21、不断下降，类推，不断迭代，目标函数值不断下降，最后逼近该目标函数的最优点。最后逼近该目标函数的最优点。坐标轮换法坐标轮换法坐标轮换法坐标轮换法 二、终止准则二、终止准则 可以采用点距准则或者其它准则。可以采用点距准则或者其它准则。注意：注意：若采用点距准则或函数值准则，其中采用的若采用点距准则或函数值准则，其中采用的点应该是一轮迭代的始点和终点，而不是某搜索方点应该是一轮迭代的始点和终点，而不是某搜索方向的前后迭代点。向的前后迭代点。坐标轮换法坐标轮换法坐标轮换法坐标轮换法 三、坐标轮换法的流程图三、坐标轮换法的流程图入口入口给定：给定：x0，K=1i=1Xik=x0沿沿ei方向一维搜索求方向

22、一维搜索求 ixik=xi-1k+ikeix=xk f=f(x)i=n?|xnk-x0k|?x*=xf*=f(x*)出口出口i=i+1x0=x0kk=k+1NYNY坐标轮换法坐标轮换法坐标轮换法坐标轮换法四、例题四、例题五、小结五、小结 坐标轮换法程序简单，易于掌握。但是计算效率比较坐标轮换法程序简单，易于掌握。但是计算效率比较低，尤其是当优化问题的维数较高时更为严重。一般把此低，尤其是当优化问题的维数较高时更为严重。一般把此种方法应用于维数小于种方法应用于维数小于10的低维优化问题。的低维优化问题。对于目标函数存在对于目标函数存在“脊线脊线”的情况，在脊线的情况，在脊线的尖点处没有一个坐标方

23、的尖点处没有一个坐标方向可以使函数值下降，只向可以使函数值下降，只有在锐角所包含的范围搜有在锐角所包含的范围搜索才可以达到函数值下降索才可以达到函数值下降的目的，故坐标轮换法对的目的，故坐标轮换法对此类函数会失效。此类函数会失效。x2x1 脊线脊线鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法方向加速法方向加速法方向加速法方向加速法 鲍威尔方法是直接利用函数值来构造共轭方向鲍威尔方法是直接利用函数值来构造共轭方向的一种共轭方向法。这种方法是在研究具有正定矩阵的一种共轭方向法。这种方法是在研究具有正定矩阵G的二次函数的二次函数 的极小化问题时形成的。其基本思想是在不用导数的的极小化问题时形成的。其基本

24、思想是在不用导数的前提下，在迭代中逐次构造前提下，在迭代中逐次构造G的共轭方向。的共轭方向。一、共轭方向的概念一、共轭方向的概念 设设G为一正定对称矩阵，若有一组非零向量为一正定对称矩阵，若有一组非零向量S1，S2，Sn满足满足 SiTGSj=0 (i j)，则称这组向量关则称这组向量关于矩阵于矩阵G共轭。共轭。共轭方向对于构造一种有效的算法是很重要的。共轭方向对于构造一种有效的算法是很重要的。以正定二元二次函数为例，我们进行探讨。以正定二元二次函数为例，我们进行探讨。鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法 正定的二元二次函数的等值线为一组椭圆，任选正定的二元二次函数的等值线为一组椭圆，任选

25、初始点初始点x0沿某个下降方向沿某个下降方向S0作一维搜索，得作一维搜索，得x1 x1=x0+0S0此时，点此时，点x1的梯度必然与方向的梯度必然与方向S0垂直，即有垂直，即有 f(x1)TS0=0S0与某一等值线相切于与某一等值线相切于x1点。点。下一次的迭代，若选择负梯下一次的迭代，若选择负梯度方向为搜索方向，将产生度方向为搜索方向，将产生锯齿现象。为避免锯齿的产锯齿现象。为避免锯齿的产生，我们取迭代方向生，我们取迭代方向S1直指直指极小点极小点x*，如图所示。如图所示。x0 x*x1 1S1-f(x1)S1 0S0鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法 若选定这样的方向，则对于二元二次

26、函数只需进若选定这样的方向，则对于二元二次函数只需进行行S0 和和S1两次搜索就可以求得极小点两次搜索就可以求得极小点x*，即，即 x*=x1+1S1由于由于 f(x1)=Gx1+b，当，当x1 x*时时 1S1 0，由于由于x*是是f（x）的极小点，应满足极值必要条件，故的极小点，应满足极值必要条件，故 f(x*)=Gx*+b=0，即即 f(x*)=G（x1+1S1）+b=f(x1)+1GS1=0 等式等式两端同乘以两端同乘以(S0)T,得得（S0）TGS1=0，故两个向故两个向量量S0、S1是是G的共轭向量。的共轭向量。因此，若要使第二个迭代点成为正定二元二次因此，若要使第二个迭代点成为正

27、定二元二次函数的极小点，只要使两次一维搜索的方向函数的极小点，只要使两次一维搜索的方向S0、S1关关于函数的二阶导数矩阵于函数的二阶导数矩阵G共轭就可以了。共轭就可以了。鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法 二、共轭二、共轭 方向的生成方向的生成 设设xk、xk+1为从不同点出发，沿同一方向为从不同点出发，沿同一方向Sj 进行进行一维搜索得到的两个极小点，如图所示。根据梯度和一维搜索得到的两个极小点，如图所示。根据梯度和等值面的性质，等值面的性质，Sj 和和xk、xk+1两点处的梯度两点处的梯度gk、gk+1之间存在如下关系之间存在如下关系 (Sj)Tgk=0 (Sj)Tgk+1=0又因为

28、又因为xk、xk+1两点处的梯度两点处的梯度 可表示为可表示为 gk=Gxk+b gk+1=Gxk+1+b 两式相减，得两式相减，得 gk+1-gk=G(xk+1-xK)gkgk+1SjSjSkxk+1xK鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法 因此有因此有 (Sj)T(gk+1-gk)=(Sj)T G(xk+1-xK)=0 若取方向若取方向Sk=xk+1-xK，则，则Sk和和Sj对对G共轭。这说共轭。这说明只要沿方向明只要沿方向Sj 分别对函数作两次一维搜索，得到两分别对函数作两次一维搜索，得到两个极小点，则这两点的连线方向就是与个极小点，则这两点的连线方向就是与Sj 共轭的方向。共轭的方

29、向。gkgk+1SjSjSkxk+1xK鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法三、鲍威尔基本算法三、鲍威尔基本算法 如图所示，以三维二次目标函数的无约束优化问如图所示，以三维二次目标函数的无约束优化问题为例。题为例。x1x3x2e1e2e3e2e3e3x01x11x21x31x1x12x22x32x13x23x33x2x3S3-S1S2S2S1鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法 鲍威尔基本算法的步骤：鲍威尔基本算法的步骤：第一环基本方向组取单位坐标矢量系第一环基本方向组取单位坐标矢量系e1、e2、e3、en，沿这些方向依次作一维搜索，然后将始，沿这些方向依次作一维搜索，然后将始末两点相

30、连作为新生方向，再沿新生方向作一维搜索，末两点相连作为新生方向，再沿新生方向作一维搜索，完成第一环的迭代。以后每环的基本方向组是将上环完成第一环的迭代。以后每环的基本方向组是将上环的第一个方向淘汰，上环的新生方向补入本环的最后的第一个方向淘汰，上环的新生方向补入本环的最后而构成。而构成。n维目标函数完成维目标函数完成n环的迭代过程称为一轮。环的迭代过程称为一轮。从这一轮的终点出发沿新生方向搜索所得到的极小点，从这一轮的终点出发沿新生方向搜索所得到的极小点，作为下一轮迭代的始点。这样就形成了算法的循环。作为下一轮迭代的始点。这样就形成了算法的循环。鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法 鲍威尔

31、基本算法的缺陷：鲍威尔基本算法的缺陷：可能在某一环迭代中出现基本方向组为线性可能在某一环迭代中出现基本方向组为线性相关的矢量系的情况。如第相关的矢量系的情况。如第k环中，产生新的方向：环中，产生新的方向：Sk=xnk-x0k=1kS1k+2kS2k+nkSnk 式中，式中，S1k、S2k、Snk为第为第k环基本环基本方向组矢量，方向组矢量，1k、2k、nk为个方向为个方向的最优步长。的最优步长。若在第若在第k环的优化搜索过程中出现环的优化搜索过程中出现 1k=0，则，则方向方向Sk表示为表示为S2k、S3k、Snk的线性组合，的线性组合，以后的各次搜索将在降维的空间进行，无法得到以后的各次搜索

32、将在降维的空间进行，无法得到n维空间的函数极小值，计算将失败。维空间的函数极小值，计算将失败。鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法 鲍威尔基本算法的退化鲍威尔基本算法的退化x1x2x3 1=0 1e2 3e3S1如图所示为一个三维优化如图所示为一个三维优化问题的示例，设第一环中问题的示例，设第一环中 1=0，则新生方向与，则新生方向与e2、e3共面，随后的各共面，随后的各环方向组中，各矢量必在环方向组中，各矢量必在该平面内，使搜索局限于该平面内，使搜索局限于二维空间，不能得到最优二维空间，不能得到最优解。解。鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法四、鲍威尔修正算法四、鲍威尔修正算法 在某

33、环已经取得的在某环已经取得的n+1各方向中，选取各方向中，选取n个线性无关的个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组。并且共轭程度尽可能高的方向作为下一环的基本方向组。鲍威尔修正算法的搜索方向的构造：鲍威尔修正算法的搜索方向的构造：在第在第k环的搜索中，环的搜索中，x0k 为初始点，搜索方向为为初始点，搜索方向为S1k、S2k、Snk，产生的新方向为产生的新方向为Sk，此方向的极小点，此方向的极小点为为xk。点点 xn+1k=2xnk-x0k，为为x0k对对xnk的映射点。的映射点。计算计算x0k、x1k、xnk、xk、x n+1k 各点的函数值，记作：各点的函数值，记作：

34、F1=F(x0k)F2=F(xnk)F3=F(xn+1k)=F(xmk)-F(xm-1k)是第是第k环方向组中，依次沿各方向搜索函数值下降最环方向组中，依次沿各方向搜索函数值下降最大值，即大值，即Smk方向函数下降最大。方向函数下降最大。鲍威尔方法鲍威尔方法鲍威尔方法鲍威尔方法 为了构造第为了构造第k+1环基本方向组，采用如下判别式：环基本方向组，采用如下判别式：按照一下两种情况处理：按照一下两种情况处理：1、上式中至少一个不等式成立，则第、上式中至少一个不等式成立，则第k+1环的基本方向仍环的基本方向仍用老方向组用老方向组S1k、S2k、Snk。k+1的环初始点取的环初始点取 x0k+1=x

35、nk F2 f(xk)，而使计算失败。而使计算失败。阻尼牛顿法阻尼牛顿法阻尼牛顿法阻尼牛顿法一、对原始牛顿法的改进一、对原始牛顿法的改进 为解决原始牛顿法的不足，加入搜索步长为解决原始牛顿法的不足，加入搜索步长(k)因此，因此，迭代公式变为：迭代公式变为：xk+1=xk-(k)G(xk)-1 f(xk)这就是阻尼牛顿法的迭代公式，最优步长这就是阻尼牛顿法的迭代公式，最优步长(k)也称为阻也称为阻尼因子，是沿牛顿方向一维搜索得到的最优步长。尼因子，是沿牛顿方向一维搜索得到的最优步长。二、阻尼牛顿法的迭代步骤二、阻尼牛顿法的迭代步骤 （1）给定初始点和收敛精度）给定初始点和收敛精度 （2）计算）计

36、算 f(xk)、G(xk)、G(xk)-1 （3）求）求xk+1=xk-(k)G(xk)-1 f(xk)（4）检查收敛精度，若检查收敛精度，若|xk+1-xk 0，要受惩罚SUTMSUTM外点法外点法 罚函数法的缺点缺点是：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误1、任意给定初始点X0，取M11，给定允许误差 ，令k=1；2、求无约束极值问题 的最优解，设为Xk=X(Mk)，即 ；3、若存在 ，使 ，则取MkM()令k=k+1返回（2），否则，停止迭代得最优解 .计算时也可将收

37、敛性判别准则 改为 .SUTMSUTM外点法外点法(罚函数法)的迭代步骤迭代步骤SUTMSUTM内点法（障碍函数法）内点法（障碍函数法）内点法的迭代步骤内点法的迭代步骤 近似规划法的基本思想近似规划法的基本思想：将问题(3)中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题,再用单纯形法求解之，把其符合原始条件的最优解作为(3)的解的近似近似规划法近似规划法每得到一个近似解后，都从这点出发，重复以上步骤 这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。近似规划法的算法步骤如下

38、近似规划法的算法步骤如下用MATLAB软件求解,其输入格式输入格式如下:1.x=quadprog(H,C,A,b);2.x=quadprog(H,C,A,b,Aeq,beq);3.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);4.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6.x,fval=quaprog(.);7.x,fval,exitflag=quaprog(.);8.x,fval,exitflag,output=quaprog(.)

39、;1、二次规划、二次规划例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t.x1+x22 -x1+2x22 x10,x20 1、写成标准形式写成标准形式：2、输入命令输入命令：H=1-1;-1 2;c=-2;-6;A=1 1;-1 2;b=2;2;Aeq=;beq=;VLB=0;0;VUB=;x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3、运算结果运算结果为：x=0.6667 1.3333 z=-8.2222s.t.1.首先建立M文件fun.m,定义目标函数F（X）:function f=fun(X);f=F(X);2、一

40、般非线性规划、一般非线性规划 其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：3.建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下：(1)x=fmincon(fun,X0,A,b)(2)x=fmincon(fun,X0,A,b,Aeq,beq)(3)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB)(4)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fmincon(fun,X0,A,b,Ae

41、q,beq,VLB,VUB,nonlcon,options)(6)x,fval=fmincon(.)(7)x,fval,exitflag=fmincon(.)(8)x,fval,exitflag,output=fmincon(.)输出极值点M文件迭代的初值参数说明变量上下限注意：注意：1 fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。2 fmincon函数的中型算法使用的是序列二次规划法。在每一

42、步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关。1、写成标准形式写成标准形式：s.t.2x1+3x2 6 s.t x1+4x2 5 x1,x2 0例例22、先建立先建立M-文件文件 fun3.m:function f=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)23、再建立主程序youh2.m：x0=1;1;A=2 3;1 4;b=6;5;Aeq=;beq=;VLB=0;0;VUB=;x,fval=fmincon(fun3,x0,A,b,Aeq,beq,V

43、LB,VUB)4、运算结果为：运算结果为：x=0.7647 1.0588 fval=-2.02941先建立先建立M文件文件 fun4.m,定义目标函数定义目标函数:function f=fun4(x);f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);x1+x2=0 s.t.1.5+x1x2-x1-x2 0 -x1x2 10 0例例32再建立再建立M文件文件mycon.m定义非线性约束：定义非线性约束：function g,ceq=mycon(x)g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10

44、;3主程序主程序youh3.m为为:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon)3.运算结果为运算结果为：x=-1.2250 1.2250 fval=1.8951 例4 1先建立先建立M-文件文件fun.m定义目标函数定义目标函数:function f=fun(x);f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2.m定义非线性约束：定义非线性约束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2

45、)2-7;3.主程序主程序fxx.m为为:x0=3;2.5;VLB=0 0;VUB=5 10;x,fval,exitflag,output =fmincon(fun,x0,VLB,VUB,mycon2)4.运算结果为运算结果为:x=4.0000 3.0000fval=-11.0000exitflag=1output=iterations:4 funcCount:17 stepsize:1 algorithm:1x44 char firstorderopt:cgiterations:应用实例：应用实例：供应与选址供应与选址 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离

46、单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？（一）、建立模型（一）、建立模型 记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为di，i=1,6;料场位置为料场位置为(xj，yj)，日储量为，日储量为ej，j=1,2；从料场；从料场j向工地向工地i的运送量为的运

47、送量为Xij。当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。（二）使用临时料场的情形（二）使用临时料场的情形 使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划模型为：设X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 编写程序gying1.m计算结果为：计算结果为：x=3.0000 5

48、.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval=136.2275（三）改建两个新料场的情形（三）改建两个新料场的情形 改建两个新料场,要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小.这是非线性规划问题。非线性规划模型为：设 X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6 X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 x1=X13,y1=X14,x2=

49、X15,y2=X16 （1）先编写M文件liaoch.m定义目标函数。(2)取初值为线性规划的计算结果及临时料场的坐标:x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;编写主程序gying2.m.(3)计算结果为：x=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867fval=105.4626exitflag=1(4)若修改主程序gying2.m,取初值为上面的计算结果:x0=3.0000 5.0000 0.0707 7.0000 0 0

50、.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867得结果为:x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852fval=103.4760exitflag=1总的吨千米数比上面结果略优.(5)若再取刚得出的结果为初值,却计算不出最优解.(6)若取初值为:x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499,则计算结果为:x