第02讲 优化决策理论与方法.pptx

《第02讲 优化决策理论与方法.pptx》由会员分享，可在线阅读，更多相关《第02讲 优化决策理论与方法.pptx（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、决策理论与方法决策理论与方法(2)优化决策理论与方法优化决策理论与方法合肥工业大学管理学院合肥工业大学管理学院合肥工业大学管理学院合肥工业大学管理学院Saturday,April 1,2023Saturday,April 1,2023确定性决策确定性决策vv确定性决策确定性决策确定性决策确定性决策：指未来状态是确定的（即只有一种状：指未来状态是确定的（即只有一种状：指未来状态是确定的（即只有一种状：指未来状态是确定的（即只有一种状态）一类决策问题，每一个行动方案对应着一个确态）一类决策问题，每一个行动方案对应着一个确态）一类决策问题，每一个行动方案对应着一个确态）一类决策问题，每一个行动方案对

2、应着一个确定的结果值，此时决策函数仅依赖于决策变量。定的结果值，此时决策函数仅依赖于决策变量。定的结果值，此时决策函数仅依赖于决策变量。定的结果值，此时决策函数仅依赖于决策变量。vv特点特点特点特点：状态是确定的；决策问题变为优化问题。：状态是确定的；决策问题变为优化问题。：状态是确定的；决策问题变为优化问题。：状态是确定的；决策问题变为优化问题。vv决策的已知变量决策的已知变量决策的已知变量决策的已知变量：决策变量及其取值范围决策变量及其取值范围决策变量及其取值范围决策变量及其取值范围vv解决问题的主要理论方法解决问题的主要理论方法解决问题的主要理论方法解决问题的主要理论方法：最优化理论与方

3、法：最优化理论与方法：最优化理论与方法：最优化理论与方法vv注：注：注：注：最优化理论与方法（数学规划）也可以求解不最优化理论与方法（数学规划）也可以求解不最优化理论与方法（数学规划）也可以求解不最优化理论与方法（数学规划）也可以求解不确定性决策问题、随机性决策问题确定性决策问题、随机性决策问题确定性决策问题、随机性决策问题确定性决策问题、随机性决策问题决策理论与方法-优化决策理论与方法确定性决策确定性决策vv优化决策方法的问题求解过程优化决策方法的问题求解过程优化决策方法的问题求解过程优化决策方法的问题求解过程辨识目标辨识目标辨识目标辨识目标C C，确定优化的标准，如：利润、时间、能量等，确

4、定优化的标准，如：利润、时间、能量等，确定优化的标准，如：利润、时间、能量等，确定优化的标准，如：利润、时间、能量等确定影响决策目标的决策变量确定影响决策目标的决策变量确定影响决策目标的决策变量确定影响决策目标的决策变量x x，形成目标函数，形成目标函数，形成目标函数，形成目标函数C=C=f f(x x)明确决策变量的取值范围，形成约束函数明确决策变量的取值范围，形成约束函数明确决策变量的取值范围，形成约束函数明确决策变量的取值范围，形成约束函数设计求解算法，寻找决策目标在决策变量所受限制的范设计求解算法，寻找决策目标在决策变量所受限制的范设计求解算法，寻找决策目标在决策变量所受限制的范设计求

5、解算法，寻找决策目标在决策变量所受限制的范围内的极小化或极大化。围内的极小化或极大化。围内的极小化或极大化。围内的极小化或极大化。最优化问题的一般形式为：最优化问题的一般形式为：最优化问题的一般形式为：最优化问题的一般形式为：决策理论与方法-优化决策理论与方法优化问题分类优化问题分类vv可行点可行点可行点可行点与与与与可行域可行域可行域可行域：满足约束条件的：满足约束条件的：满足约束条件的：满足约束条件的x x称为可行点，所称为可行点，所称为可行点，所称为可行点，所有可行点的集合称为可行域，记为有可行点的集合称为可行域，记为有可行点的集合称为可行域，记为有可行点的集合称为可行域，记为S S；v

6、v约束优化约束优化约束优化约束优化与与与与无约束优化无约束优化无约束优化无约束优化：当：当：当：当S S R Rn n时，称为约束优时，称为约束优时，称为约束优时，称为约束优化；当化；当化；当化；当S=RS=Rn n时，称为无约束优化；时，称为无约束优化；时，称为无约束优化；时，称为无约束优化；vv多目标优化多目标优化多目标优化多目标优化：若：若：若：若f f是多个目标函数构成的一个向量值是多个目标函数构成的一个向量值是多个目标函数构成的一个向量值是多个目标函数构成的一个向量值函数，则称为多目标规划；函数，则称为多目标规划；函数，则称为多目标规划；函数，则称为多目标规划；vv线性规划线性规划线

7、性规划线性规划与与与与非线性规划非线性规划非线性规划非线性规划：当：当：当：当f f,g g,h h均为线性函数时称均为线性函数时称均为线性函数时称均为线性函数时称为线性规划，否则称为非线性规划。为线性规划，否则称为非线性规划。为线性规划，否则称为非线性规划。为线性规划，否则称为非线性规划。决策理论与方法-优化决策理论与方法优化问题分类优化问题分类vv整数规划整数规划整数规划整数规划：当决策变量的取值均为整数时称为整数：当决策变量的取值均为整数时称为整数：当决策变量的取值均为整数时称为整数：当决策变量的取值均为整数时称为整数规划；若某些变量取值为整数，而另一些变量取值规划；若某些变量取值为整数

8、，而另一些变量取值规划；若某些变量取值为整数，而另一些变量取值规划；若某些变量取值为整数，而另一些变量取值为实数，则成为混合整数规划。为实数，则成为混合整数规划。为实数，则成为混合整数规划。为实数，则成为混合整数规划。vv动态规划动态规划动态规划动态规划与与与与多层规划多层规划多层规划多层规划：若决策是分成多个阶段完成：若决策是分成多个阶段完成：若决策是分成多个阶段完成：若决策是分成多个阶段完成的，前后阶段之间相互影响，则称为动态规划；若的，前后阶段之间相互影响，则称为动态规划；若的，前后阶段之间相互影响，则称为动态规划；若的，前后阶段之间相互影响，则称为动态规划；若决策是分成多个层次完成的，

9、不同层次之间相互影决策是分成多个层次完成的，不同层次之间相互影决策是分成多个层次完成的，不同层次之间相互影决策是分成多个层次完成的，不同层次之间相互影响，则称为多层规划。响，则称为多层规划。响，则称为多层规划。响，则称为多层规划。决策理论与方法-优化决策理论与方法优化决策理论与方法优化决策理论与方法1 1、线性规划、线性规划、线性规划、线性规划2 2、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）3 3、多目标规划、多目标规划、多目标规划、多目标规划4 4、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划、组合优化与整数

10、规划决策理论与方法-优化决策理论与方法线性规划线性规划管理实例管理实例vv(食谱问题食谱问题食谱问题食谱问题)假设市场上有假设市场上有假设市场上有假设市场上有n n种不同的食物，第种不同的食物，第种不同的食物，第种不同的食物，第j j种食物的单价种食物的单价种食物的单价种食物的单价为为为为c cj j。人体正常活动过程中需要。人体正常活动过程中需要。人体正常活动过程中需要。人体正常活动过程中需要mm种基本的营养成分，且每种基本的营养成分，且每种基本的营养成分，且每种基本的营养成分，且每人每天至少需要摄入第人每天至少需要摄入第人每天至少需要摄入第人每天至少需要摄入第i i种营养成分种营养成分种营

11、养成分种营养成分b bi i个单位。已知第个单位。已知第个单位。已知第个单位。已知第j j种食物种食物种食物种食物中包含第中包含第中包含第中包含第i i种营养成分的量为种营养成分的量为种营养成分的量为种营养成分的量为a aij ij个单位。问在满足人体基本营个单位。问在满足人体基本营个单位。问在满足人体基本营个单位。问在满足人体基本营养需求的前提下什么样的配食方案最经济？养需求的前提下什么样的配食方案最经济？养需求的前提下什么样的配食方案最经济？养需求的前提下什么样的配食方案最经济？vv设食谱中包含第设食谱中包含第设食谱中包含第设食谱中包含第j j种食物的量为种食物的量为种食物的量为种食物的量

12、为x xj j，则：，则：，则：，则：决策理论与方法-优化决策理论与方法线性规划线性规划标准型标准型决策理论与方法-优化决策理论与方法线性规划线性规划单纯形算法单纯形算法vv解空间分析解空间分析解空间分析解空间分析可行域分析可行域分析可行域分析可行域分析：n n维空间；第一象限；维空间；第一象限；维空间；第一象限；维空间；第一象限；mm个超平面。个超平面。个超平面。个超平面。最优解分析最优解分析最优解分析最优解分析：在端点：在端点：在端点：在端点(或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有n n-mm个个个个0 0分

13、量分量分量分量)处取极值。处取极值。处取极值。处取极值。vv单纯形算法的基本思想单纯形算法的基本思想单纯形算法的基本思想单纯形算法的基本思想从某个极点开始获得一个可行解；从某个极点开始获得一个可行解；从某个极点开始获得一个可行解；从某个极点开始获得一个可行解；判断该可行解是不是目标解。若是，算法结束；否则寻判断该可行解是不是目标解。若是，算法结束；否则寻判断该可行解是不是目标解。若是，算法结束；否则寻判断该可行解是不是目标解。若是，算法结束；否则寻找下一个极点（确定找下一个极点（确定找下一个极点（确定找下一个极点（确定入基变量入基变量入基变量入基变量和和和和出基变量出基变量出基变量出基变量），

14、直至找到），直至找到），直至找到），直至找到目标解。目标解。目标解。目标解。决策理论与方法-优化决策理论与方法线性规划线性规划内点算法内点算法vv19721972年，年，年，年，V.KleeV.Klee和和和和G.L.MintyG.L.Minty指出指出指出指出DantzigDantzig的单纯的单纯的单纯的单纯形算法的迭代次数为形算法的迭代次数为形算法的迭代次数为形算法的迭代次数为O(2O(2n n)，是一个指数时间算法，是一个指数时间算法，是一个指数时间算法，是一个指数时间算法，不是优良算法。那么是否存在求解线性规划问题的不是优良算法。那么是否存在求解线性规划问题的不是优良算法。那么是否存

15、在求解线性规划问题的不是优良算法。那么是否存在求解线性规划问题的多项式时间算法？多项式时间算法？多项式时间算法？多项式时间算法？vv19841984年，年，年，年，N.KarmarkarN.Karmarkar提出了一种提出了一种提出了一种提出了一种投影尺度算法投影尺度算法投影尺度算法投影尺度算法，其计算效果能够同单纯形法相比较，掀起了线性规其计算效果能够同单纯形法相比较，掀起了线性规其计算效果能够同单纯形法相比较，掀起了线性规其计算效果能够同单纯形法相比较，掀起了线性规划划划划内点算法内点算法内点算法内点算法的热潮。的热潮。的热潮。的热潮。决策理论与方法-优化决策理论与方法线性规划线性规划内点

16、算法内点算法vv内点算法的思想内点算法的思想内点算法的思想内点算法的思想已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题的可行域是一个多面体，最优点在多面体的某个极点取到。在给定初始可行解后，沿着什么面体的某个极点取到。在给定初始可行解后，沿着什么面体的某个极点取到。在给定初始可行解后，沿着什么面体的某个极点取到。在给定初始可行解后，沿着什么样的路径到达最优解呢？样的路径到达最优解呢？样的路径到达最优解呢？样的路径到达最优解呢？单纯形法是从某个基可行解开始，沿着多面体的边移动单纯形法

17、是从某个基可行解开始，沿着多面体的边移动单纯形法是从某个基可行解开始，沿着多面体的边移动单纯形法是从某个基可行解开始，沿着多面体的边移动最终找到最优解。最终找到最优解。最终找到最优解。最终找到最优解。内点算法的思想是从可行域内的任意一点内点算法的思想是从可行域内的任意一点内点算法的思想是从可行域内的任意一点内点算法的思想是从可行域内的任意一点(任一可行解任一可行解任一可行解任一可行解)出发，穿越可行域的内部达到最优解。出发，穿越可行域的内部达到最优解。出发，穿越可行域的内部达到最优解。出发，穿越可行域的内部达到最优解。N.Karmarkar N.Karmarkar的的的的投影尺度算法投影尺度算

18、法投影尺度算法投影尺度算法就是一种典型的内点算法。就是一种典型的内点算法。就是一种典型的内点算法。就是一种典型的内点算法。决策理论与方法-优化决策理论与方法线性规划线性规划内点算法内点算法可行域可行域内点内点初始基可行解初始基可行解基可行解基可行解目标函数目标函数目标函数最速下降方向目标函数最速下降方向决策理论与方法-优化决策理论与方法线性规划线性规划内点算法内点算法vv投影尺度算法投影尺度算法投影尺度算法投影尺度算法如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？KarmarkarKarm

19、arkar发现：发现：发现：发现：(1)(1)如果一个内点位于可行域如果一个内点位于可行域如果一个内点位于可行域如果一个内点位于可行域(多胞形、多面体多胞形、多面体多胞形、多面体多胞形、多面体)的的的的中心，那么目标函数的最速下降方向是比较好的方向；中心，那么目标函数的最速下降方向是比较好的方向；中心，那么目标函数的最速下降方向是比较好的方向；中心，那么目标函数的最速下降方向是比较好的方向；(2)(2)存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置于变换后的

20、可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，KarmarkarKarmarkar构构构构造了一种称为造了一种称为造了一种称为造了一种称为投影尺度算法投影尺度算法投影尺度算法投影尺度算法的内点算法。的内点算法。的内点算法。的内点算法。决策理论与方法-优化决策理论与方法线性规划线性规划内点算法内点算法X空间空间内点内点目标函数目标函数目标函数最目标函数最速下降方向速下降方向Y1空间空间中心点中心点投影尺度变换投影尺度变换1目标函数最目标函数最速下降方向速下降方向Y2空间空间中心点中心点投影尺度变换投影尺度变换

21、2决策理论与方法-优化决策理论与方法线性规划线性规划Matlab函数应用函数应用vvOptimization ToolBoxOptimization ToolBoxMin Min f fT Tx xS.t.S.t.AxbAxbAeqAeqx x=beq=beqlblbx xubub其中：其中：其中：其中：f f,x x,b b,beq,lb,beq,lb和和和和ubub均为向量；均为向量；均为向量；均为向量；A A和和和和AeqAeq为矩阵。为矩阵。为矩阵。为矩阵。x x,f fval=val=linproglinprog(f f,A,A,b b,Aeq,beq,lb,ub),Aeq,beq,

22、lb,ub)决策理论与方法-优化决策理论与方法线性规划线性规划Matlab函数应用函数应用vv例：例：例：例：max z=x1+2x2max z=x1+2x2S.t.S.t.x1+x2x1+x240402x1+x2602x1+x260 x1x10;x200;x20解解解解：将：将：将：将maxmax变为变为变为变为minmin，min z=-x1-2x2min z=-x1-2x2则：则：则：则：f f=-1;-2;=-1;-2;b b=40;60;lb=zeros(2,1);A=1 1;2 1=40;60;lb=zeros(2,1);A=1 1;2 1 x x,f fval=val=linpr

23、oglinprog(f f,A,A,b b,lb),lb)x x=0;40,=0;40,f fval=-80val=-80 x1x2x1+x2=402x1+x2=60Z=x1+2x2决策理论与方法-优化决策理论与方法优化决策理论与方法优化决策理论与方法1 1、线性规划、线性规划、线性规划、线性规划2 2、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）3 3、多目标规划、多目标规划、多目标规划、多目标规划4 4、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划决策理论与方法-优化决策理论与方法无约束非线

24、性规划无约束非线性规划标准型标准型vvMin Min f f(x x););x x R Rn nvv其中其中其中其中f f：R Rn nRR是一个非线性连续函数。对于任意点是一个非线性连续函数。对于任意点是一个非线性连续函数。对于任意点是一个非线性连续函数。对于任意点x x*R Rn n,它是函数它是函数它是函数它是函数f f的最小点的最小点的最小点的最小点(或局部极小点或局部极小点或局部极小点或局部极小点)吗？吗？吗？吗？vv例如：例如：例如：例如：min min f f(x x)=e)=ex x1 1(4(4x x1 12 2+2+2x x2 22 2+4+4x x1 1x x2 2+2+

25、2x x2 2+1)+1)决策理论与方法-优化决策理论与方法无约束非线性规划无约束非线性规划极小值存在条件极小值存在条件vv必要条件必要条件必要条件必要条件。设。设。设。设x x*是是是是f f(x x)的局部极小点，则的局部极小点，则的局部极小点，则的局部极小点，则当当当当f f(x x)在在在在x x*点可微时，梯度点可微时，梯度点可微时，梯度点可微时，梯度 f f(x x*)=0)=0；当当当当f f(x x)在在在在x x*点二阶可微时，点二阶可微时，点二阶可微时，点二阶可微时，HesseHesse矩阵矩阵矩阵矩阵2 2f f(x x*)是半正定是半正定是半正定是半正定 的，的，的，的

26、，即即即即d d R Rn n，有，有，有，有d dT T 2 2f f(x x*)d d 0 0。vv充分条件充分条件充分条件充分条件。设设设设f f(x x)在在在在x x*点二阶可微，若梯度点二阶可微，若梯度点二阶可微，若梯度点二阶可微，若梯度 f f(x x*)=0)=0且且且且HesseHesse矩阵矩阵矩阵矩阵 2 2f f(x x*)是正定是正定是正定是正定 的，则的，则的，则的，则x x*是是是是f f(x x)的一个严的一个严的一个严的一个严格局部极小点。格局部极小点。格局部极小点。格局部极小点。vv充要条件充要条件充要条件充要条件。设。设。设。设f f(x x)是可微凸函数

27、，则是可微凸函数，则是可微凸函数，则是可微凸函数，则x x*是是是是f f(x x)的全局的全局的全局的全局最小点，当且仅当梯度最小点，当且仅当梯度最小点，当且仅当梯度最小点，当且仅当梯度 f f(x x*)=0)=0。决策理论与方法-优化决策理论与方法无约束非线性规划无约束非线性规划复习复习vv梯度矩阵梯度矩阵梯度矩阵梯度矩阵vvHesseHesse矩阵矩阵矩阵矩阵vvTaylorTaylor展开展开展开展开决策理论与方法-优化决策理论与方法无约束非线性规划无约束非线性规划牛顿法牛顿法vv基本思想基本思想基本思想基本思想：在一个点附近，用目标函数：在一个点附近，用目标函数：在一个点附近，用目

28、标函数：在一个点附近，用目标函数f f(x x)的二阶的二阶的二阶的二阶TaylorTaylor多项式近似多项式近似多项式近似多项式近似f f(x x)，并用该，并用该，并用该，并用该TaylorTaylor多项式的最小多项式的最小多项式的最小多项式的最小点近似点近似点近似点近似f f(x x)的最小点。如果近似误差比较大，那么可的最小点。如果近似误差比较大，那么可的最小点。如果近似误差比较大，那么可的最小点。如果近似误差比较大，那么可在近似最小点附近重新构造在近似最小点附近重新构造在近似最小点附近重新构造在近似最小点附近重新构造f f(x x)的二阶的二阶的二阶的二阶TaylorTaylor

29、多项式多项式多项式多项式(迭代迭代迭代迭代)，据此寻找新的近似最小点，重复以上过程，据此寻找新的近似最小点，重复以上过程，据此寻找新的近似最小点，重复以上过程，据此寻找新的近似最小点，重复以上过程直到求得满足一定精度要求的迭代点。直到求得满足一定精度要求的迭代点。直到求得满足一定精度要求的迭代点。直到求得满足一定精度要求的迭代点。决策理论与方法-优化决策理论与方法无约束非线性规划无约束非线性规划牛顿法牛顿法vv设设设设x xk k是第是第是第是第k k次迭代结果，记次迭代结果，记次迭代结果，记次迭代结果，记g gk k=g g(x xk k)=)=f f(x xk k)；GGk k=G=G(x

30、 xk k)=)=2 2f f(x xk k)。则。则。则。则f f(x x)=)=f f(x xk k+p p)k k(p p)=)=f f(x xk k)+)+g g(x xk k)T Tp p+1/2+1/2p pT TG(G(x xk k)p pvv由于由于由于由于 k k(p p)的最小点满足的最小点满足的最小点满足的最小点满足g g(x xk k)+G()+G(x xk k)p p=0=0，得，得，得，得p p=x x-x xk k=-G=-G-1-1(x xk k)g g(x xk k)vv因此，可近似得到迭代关系：因此，可近似得到迭代关系：因此，可近似得到迭代关系：因此，可近似

31、得到迭代关系：x xk k+1+1=x xk k-G-G-1-1(x xk k)g g(x xk k)决策理论与方法-优化决策理论与方法无约束非线性规划无约束非线性规划牛顿法牛顿法vv牛顿迭代法步骤牛顿迭代法步骤牛顿迭代法步骤牛顿迭代法步骤初始化初始化初始化初始化：给定一个初始点：给定一个初始点：给定一个初始点：给定一个初始点x x0 0以及参数以及参数以及参数以及参数e0e0；记；记；记；记k k=0=0。收敛性检验收敛性检验收敛性检验收敛性检验：计算：计算：计算：计算g g(x xk k)，若，若，若，若|g g(x xk k)|e)|e，则算法终止；，则算法终止；，则算法终止；，则算法终

32、止；否则计算否则计算否则计算否则计算G(G(x xk k)。迭代改进迭代改进迭代改进迭代改进：计算新的迭代点：计算新的迭代点：计算新的迭代点：计算新的迭代点x xk k+1+1，即，即，即，即x xk k+1+1=x xk k-G-G-1-1(x xk k)g g(x xk k)。k+1kk+1k。返回收敛性检验。返回收敛性检验。返回收敛性检验。返回收敛性检验。决策理论与方法-优化决策理论与方法无约束非线性规划无约束非线性规划准牛顿法准牛顿法vv牛顿法算法的优点是收敛速度快牛顿法算法的优点是收敛速度快牛顿法算法的优点是收敛速度快牛顿法算法的优点是收敛速度快(利用了利用了利用了利用了HesseH

33、esse矩阵矩阵矩阵矩阵)。但使用。但使用。但使用。但使用HesseHesse矩阵的不足之处是计算量大，矩阵的不足之处是计算量大，矩阵的不足之处是计算量大，矩阵的不足之处是计算量大，HesseHesse矩阵可能非正定等，准牛顿法矩阵可能非正定等，准牛顿法矩阵可能非正定等，准牛顿法矩阵可能非正定等，准牛顿法(Quasi-(Quasi-Newton method)Newton method)是对牛顿法的改进，目前被公认是对牛顿法的改进，目前被公认是对牛顿法的改进，目前被公认是对牛顿法的改进，目前被公认为是比较有效的无约束优化方法。为是比较有效的无约束优化方法。为是比较有效的无约束优化方法。为是比较

34、有效的无约束优化方法。vv基本思想基本思想基本思想基本思想：在迭代过程中只利用目标函数：在迭代过程中只利用目标函数：在迭代过程中只利用目标函数：在迭代过程中只利用目标函数f(x)f(x)和梯度和梯度和梯度和梯度g(x)g(x)的信息，构造的信息，构造的信息，构造的信息，构造HesseHesse矩阵的近似矩阵，由此获矩阵的近似矩阵，由此获矩阵的近似矩阵，由此获矩阵的近似矩阵，由此获得一个搜索方向，生产新的迭代点。具体内容请参得一个搜索方向，生产新的迭代点。具体内容请参得一个搜索方向，生产新的迭代点。具体内容请参得一个搜索方向，生产新的迭代点。具体内容请参考相关书籍。考相关书籍。考相关书籍。考相关

35、书籍。决策理论与方法-优化决策理论与方法无约束非线性规划无约束非线性规划Matlab函数应用函数应用vvOptimization ToolBoxOptimization ToolBoxMin Min f f(x x)vvMatlabMatlab提供了两个求解无约束非线性规划的函数提供了两个求解无约束非线性规划的函数提供了两个求解无约束非线性规划的函数提供了两个求解无约束非线性规划的函数x,fval=x,fval=fminuncfminunc(fun,x0)(fun,x0)x,fval=x,fval=fminsearchfminsearch(fun,x0)(fun,x0)vv用法相似，算法内部的

36、搜索策略不同。用法相似，算法内部的搜索策略不同。用法相似，算法内部的搜索策略不同。用法相似，算法内部的搜索策略不同。funfun为为为为f(x)f(x)的的的的函数形式，函数形式，函数形式，函数形式，x0 x0为初始解向量。为初始解向量。为初始解向量。为初始解向量。决策理论与方法-优化决策理论与方法无约束非线性规划无约束非线性规划Matlab函数应用函数应用vv用法用法用法用法创建一个创建一个创建一个创建一个matlabmatlab文件，如文件，如文件，如文件，如myfun.mmyfun.mfunction f=myfun(x)function f=myfun(x)f=f(x);f=f(x);

37、然后调用然后调用然后调用然后调用fminuncfminunc或或或或fminsearchfminsearch并指定初始搜索点。并指定初始搜索点。并指定初始搜索点。并指定初始搜索点。x0=x1,x2,xn x0=x1,x2,xn x,fval=x,fval=fminuncfminunc(myfun,x0)(myfun,x0)或或或或 x,fval=x,fval=fminsearchfminsearch(myfun,x0)(myfun,x0)决策理论与方法-优化决策理论与方法无约束非线性规划无约束非线性规划Matlab函数应用函数应用vv例例例例：min min f f(x x)=e)=ex x1

38、 1(4(4x x1 12 2+2+2x x2 22 2+4+4x x1 1x x2 2+2+2x x2 2+1)+1)vv解解解解：创建一个创建一个创建一个创建一个matlabmatlab文件，如文件，如文件，如文件，如myfun.mmyfun.mfunction f=myfun(x)function f=myfun(x)f=ef=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);xp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);调用无约束非线性规划函数调用无约束非线性规划函数调用无约束非线性规划函数调

39、用无约束非线性规划函数 x0=-1,1;%Starting guess x0=-1,1;%Starting guess options=optimset(LargeScale,off);options=optimset(LargeScale,off);x,fval=x,fval=fminunc fminunc(myfun,x0,options);(myfun,x0,options);或者或者或者或者x,fval=x,fval=fminsearchfminsearch(myfun,x0,options);(myfun,x0,options);决策理论与方法-优化决策理论与方法无约束非线性规划无约

40、束非线性规划Matlab函数应用函数应用vv fminunc fminunc结果：结果：结果：结果：x=0.5000 -1.0000 x=0.5000 -1.0000fval=1.0983e-015fval=1.0983e-015iterations:8iterations:8algorithm:medium-scale:Quasi-Newton line algorithm:medium-scale:Quasi-Newton line searchsearchvv fminsearchfminsearch结果：结果：结果：结果：x=0.5000 -1.0000 x=0.5000 -1.000

41、0fval=5.1425e-010fval=5.1425e-010iterations:46iterations:46algorithm:Nelder-Mead simplex direct searchalgorithm:Nelder-Mead simplex direct search决策理论与方法-优化决策理论与方法约束非线性规划约束非线性规划标准型标准型vv其中其中其中其中f f(x x)是目标函数，是目标函数，是目标函数，是目标函数，g gi i(x x)和和和和h hj j(x x)为约束函数为约束函数为约束函数为约束函数(约束约束约束约束条件条件条件条件)。S=S=x x|g g

42、i i(x x)0 0 h hj j(x x)=0)=0 为可行域。为可行域。为可行域。为可行域。vv有约束非线性规划问题有约束非线性规划问题有约束非线性规划问题有约束非线性规划问题(COP)(COP)是指是指是指是指f f(x x),),g gi i(x x),),h hj j(x x)至至至至少有一个是非线性的，且少有一个是非线性的，且少有一个是非线性的，且少有一个是非线性的，且I I或或或或 至少有一个为非空。至少有一个为非空。至少有一个为非空。至少有一个为非空。决策理论与方法-优化决策理论与方法约束非线性规划约束非线性规划几个概念几个概念vv积极积极积极积极(active)(activ

43、e)约束约束约束约束：设：设：设：设x x0 0是是是是COPCOP问题的一个可行解，问题的一个可行解，问题的一个可行解，问题的一个可行解，则它必须满足所有约束条件。对于则它必须满足所有约束条件。对于则它必须满足所有约束条件。对于则它必须满足所有约束条件。对于g gi i(x x0 0)0 0，或者，或者，或者，或者等号成立，或者大于号成立。称等号成立的约束为等号成立，或者大于号成立。称等号成立的约束为等号成立，或者大于号成立。称等号成立的约束为等号成立，或者大于号成立。称等号成立的约束为积极约束积极约束积极约束积极约束(有效约束有效约束有效约束有效约束)，此时，此时，此时，此时，x x0 0

44、处于该约束条件形处于该约束条件形处于该约束条件形处于该约束条件形成的可行域边界上；称大于号成立的约束为非积极成的可行域边界上；称大于号成立的约束为非积极成的可行域边界上；称大于号成立的约束为非积极成的可行域边界上；称大于号成立的约束为非积极(inactive)(inactive)约束约束约束约束(无效约束无效约束无效约束无效约束)，此时，此时，此时，此时，x x0 0不在该约束不在该约束不在该约束不在该约束条件形成的可行域边界上。显然所有条件形成的可行域边界上。显然所有条件形成的可行域边界上。显然所有条件形成的可行域边界上。显然所有h hj j(x(x0 0)约束均约束均约束均约束均是积极约束

45、。记是积极约束。记是积极约束。记是积极约束。记J=J=j j|g gj j(x x0 0)=0)=0 h hj j(x x0 0)=0)=0，称为积极，称为积极，称为积极，称为积极约束指标集。约束指标集。约束指标集。约束指标集。决策理论与方法-优化决策理论与方法约束非线性规划约束非线性规划几个概念几个概念vv可行方向可行方向可行方向可行方向。设。设。设。设x x0 0为为为为COPCOP问题的任一可行解，对某一方向问题的任一可行解，对某一方向问题的任一可行解，对某一方向问题的任一可行解，对某一方向d d来来来来说，若说，若说，若说，若0 000使得对于任意使得对于任意使得对于任意使得对于任意0

46、,0,0 0，均有，均有，均有，均有x x0 0+d d S S，称，称，称，称d d为为为为x x0 0的一个可行方向。显然若的一个可行方向。显然若的一个可行方向。显然若的一个可行方向。显然若d d满足满足满足满足d dT T g gi i(x x)0 0，d dT T h hj j(x x)=0)=0，则，则，则，则d d一定是可行方向。（可用一阶一定是可行方向。（可用一阶一定是可行方向。（可用一阶一定是可行方向。（可用一阶TaylorTaylor公式分公式分公式分公式分析）。析）。析）。析）。vv下降方向下降方向下降方向下降方向。设设设设x x0 0 S S，对某一方向，对某一方向，对某

47、一方向，对某一方向d d来说，若来说，若来说，若来说，若0 000使得对于任使得对于任使得对于任使得对于任意意意意0,0,0 0，均有，均有，均有，均有f f(x x0 0+d d)f f(x x0 0)，则称，则称，则称，则称d d为为为为x x0 0点的一个下降点的一个下降点的一个下降点的一个下降方向。由方向。由方向。由方向。由f f(x x0 0+d d)=)=f f(x x0 0)+)+(f f(x x0 0)T Td d+o(+o()可知：若可知：若可知：若可知：若d d满足满足满足满足d dT T f f(x x0 0)0)0，有，有，有，有f f(x x0 0+d d)0)0，则

48、，则，则，则x x*为为为为COPCOP问题的一问题的一问题的一问题的一个严格局部极小点。个严格局部极小点。个严格局部极小点。个严格局部极小点。(凸规划问题凸规划问题凸规划问题凸规划问题)设设设设f f(x x)为凸函数，为凸函数，为凸函数，为凸函数，g gi i(x x)为凹函数，为凹函数，为凹函数，为凹函数，h hj j(x x)为线为线为线为线性函数。对于性函数。对于性函数。对于性函数。对于x x*S S，若，若，若，若函数函数函数函数f f(x x),),g gi i(x x)在在在在x x*处可微，且处可微，且处可微，且处可微，且KKTKKT条件成立，则条件成立，则条件成立，则条件成

49、立，则x x*为为为为COPCOP问题的全局最小点。问题的全局最小点。问题的全局最小点。问题的全局最小点。决策理论与方法-优化决策理论与方法约束非线性规划约束非线性规划极小值存在条件极小值存在条件vv二阶必要条件二阶必要条件二阶必要条件二阶必要条件设设设设x x*是是是是COPCOP问题的局部极小点且满足问题的局部极小点且满足问题的局部极小点且满足问题的局部极小点且满足KKTKKT条件。若函数条件。若函数条件。若函数条件。若函数f f(x x),),g gi i(x x),),h hj j(x x)在在在在x x*处二阶可微，则必有：处二阶可微，则必有：处二阶可微，则必有：处二阶可微，则必有：

50、d dT T xxxx2 2L(L(x x*,*,*)d d 0 0 其中，其中，其中，其中，L(L(x x,)=)=f f(x x)-)-g g(x x)T T -h h(x x)T T ,g g(x x),),h h(x x)分别为由分别为由分别为由分别为由g gi i(x x)和和和和h hj j(x x)构成的向量值函数，构成的向量值函数，构成的向量值函数，构成的向量值函数，,分别为对应于分别为对应于分别为对应于分别为对应于g g(x x)和和和和h h(x x)的拉格朗日乘子向量。的拉格朗日乘子向量。的拉格朗日乘子向量。的拉格朗日乘子向量。vv二阶充分条件二阶充分条件二阶充分条件二阶