优化决策理论与方法课件

路漫漫其悠远路漫漫其悠远少壮不努力，老大徒悲伤少壮不努力，老大徒悲伤少壮不努力，老大徒悲伤少壮不努力，老大徒悲伤2024/5/25优化决策理论与方法优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂确定性决策确定性决策v确定性决策确定性决策：指未来状态是确定的（即只有一种状：指未来状态是确定的（即只有一种状态）一类决策问题，每一个行动方案对应着一个确态）一类决策问题，每一个行动方案对应着一个确定的结果值，此时决策函数仅依赖于决策变量。定的结果值，此时决策函数仅依赖于决策变量。v特点特点：状态是确定的；决策问题变为优化问题。：状态是确定的；决策问题变为优化问题。v决策的已知变量决策的已知变量：决策变量及其取值范围决策变量及其取值范围v解决问题的主要理论方法解决问题的主要理论方法：最优化理论与方法：最优化理论与方法v注：注：最优化理论与方法（数学规划）也可以求解不最优化理论与方法（数学规划）也可以求解不确定性决策问题、随机性决策问题确定性决策问题、随机性决策问题决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂确定性决策确定性决策v优化决策方法的问题求解过程优化决策方法的问题求解过程辨识目标辨识目标C，确定优化的标准，如：利润、时间、能量等，确定优化的标准，如：利润、时间、能量等确定影响决策目标的决策变量确定影响决策目标的决策变量x，形成目标函数，形成目标函数C=f(x)明确决策变量的取值范围，形成约束函数明确决策变量的取值范围，形成约束函数设计求解算法，寻找决策目标在决策变量所受限制的范设计求解算法，寻找决策目标在决策变量所受限制的范围内的极小化或极大化。围内的极小化或极大化。最优化问题的一般形式为：最优化问题的一般形式为：决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂优化问题分类优化问题分类v可行点可行点与与可行域可行域：满足约束条件的：满足约束条件的x称为可行点，所称为可行点，所有可行点的集合称为可行域，记为有可行点的集合称为可行域，记为S；v约束优化约束优化与与无约束优化无约束优化：当：当S Rn时，称为约束优时，称为约束优化；当化；当S=Rn时，称为无约束优化；时，称为无约束优化；v多目标优化多目标优化：若：若f是多个目标函数构成的一个向量值是多个目标函数构成的一个向量值函数，则称为多目标规划；函数，则称为多目标规划；v线性规划线性规划与与非线性规划非线性规划：当：当f,g,h均为线性函数时称均为线性函数时称为线性规划，否则称为非线性规划。为线性规划，否则称为非线性规划。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂优化问题分类优化问题分类v整数规划整数规划：当决策变量的取值均为整数时称为整数：当决策变量的取值均为整数时称为整数规划；若某些变量取值为整数，而另一些变量取值规划；若某些变量取值为整数，而另一些变量取值为实数，则成为混合整数规划。为实数，则成为混合整数规划。v动态规划动态规划与与多层规划多层规划：若决策是分成多个阶段完成：若决策是分成多个阶段完成的，前后阶段之间相互影响，则称为动态规划；若的，前后阶段之间相互影响，则称为动态规划；若决策是分成多个层次完成的，不同层次之间相互影决策是分成多个层次完成的，不同层次之间相互影响，则称为多层规划。响，则称为多层规划。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂优化决策理论与方法优化决策理论与方法1、线性规划、线性规划2 2、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）3 3、多目标规划、多目标规划、多目标规划、多目标规划4 4、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂线性规划线性规划管理实例管理实例v(食谱问题食谱问题)假设市场上有假设市场上有n种不同的食物，第种不同的食物，第j种食物的单价种食物的单价为为cj。人体正常活动过程中需要。人体正常活动过程中需要m种基本的营养成分，且每种基本的营养成分，且每人每天至少需要摄入第人每天至少需要摄入第i种营养成分种营养成分bi个单位。已知第个单位。已知第j种食物种食物中包含第中包含第i种营养成分的量为种营养成分的量为aij个单位。问在满足人体基本营个单位。问在满足人体基本营养需求的前提下什么样的配食方案最经济？养需求的前提下什么样的配食方案最经济？v设食谱中包含第设食谱中包含第j种食物的量为种食物的量为xj，则：，则：决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂线性规划线性规划标准型标准型决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂线性规划线性规划单纯形算法单纯形算法v解空间分析解空间分析可行域分析可行域分析：n n维空间；第一象限；维空间；第一象限；维空间；第一象限；维空间；第一象限；mm个超平面。个超平面。个超平面。个超平面。最优解分析最优解分析：在端点：在端点：在端点：在端点(或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有n-m个个个个0 0分量分量分量分量)处取极值。处取极值。处取极值。处取极值。v单纯形算法的基本思想单纯形算法的基本思想从某个极点开始获得一个可行解；从某个极点开始获得一个可行解；从某个极点开始获得一个可行解；从某个极点开始获得一个可行解；判断该可行解是不是目标解。若是，算法结束；否则寻判断该可行解是不是目标解。若是，算法结束；否则寻判断该可行解是不是目标解。若是，算法结束；否则寻判断该可行解是不是目标解。若是，算法结束；否则寻找下一个极点（确定找下一个极点（确定找下一个极点（确定找下一个极点（确定入基变量入基变量和和和和出基变量出基变量），直至找到），直至找到），直至找到），直至找到目标解。目标解。目标解。目标解。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂线性规划线性规划内点算法内点算法vv19721972年，年，年，年，V.KleeV.Klee和和和和G.L.MintyG.L.Minty指出指出指出指出DantzigDantzig的单纯的单纯的单纯的单纯形算法的迭代次数为形算法的迭代次数为形算法的迭代次数为形算法的迭代次数为O(2O(2n)，是一个指数时间算法，是一个指数时间算法，是一个指数时间算法，是一个指数时间算法，不是优良算法。那么是否存在求解线性规划问题的不是优良算法。那么是否存在求解线性规划问题的不是优良算法。那么是否存在求解线性规划问题的不是优良算法。那么是否存在求解线性规划问题的多项式时间算法？多项式时间算法？多项式时间算法？多项式时间算法？vv19841984年，年，年，年，N.KarmarkarN.Karmarkar提出了一种提出了一种提出了一种提出了一种投影尺度算法投影尺度算法，其计算效果能够同单纯形法相比较，掀起了线性规其计算效果能够同单纯形法相比较，掀起了线性规其计算效果能够同单纯形法相比较，掀起了线性规其计算效果能够同单纯形法相比较，掀起了线性规划划划划内点算法内点算法的热潮。的热潮。的热潮。的热潮。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂线性规划线性规划内点算法内点算法v内点算法的思想内点算法的思想已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题的可行域是一个多面体，最优点在多面体的某个极点取到。在给定初始可行解后，沿着什么面体的某个极点取到。在给定初始可行解后，沿着什么面体的某个极点取到。在给定初始可行解后，沿着什么面体的某个极点取到。在给定初始可行解后，沿着什么样的路径到达最优解呢？样的路径到达最优解呢？样的路径到达最优解呢？样的路径到达最优解呢？单纯形法是从某个基可行解开始，沿着多面体的边移动单纯形法是从某个基可行解开始，沿着多面体的边移动单纯形法是从某个基可行解开始，沿着多面体的边移动单纯形法是从某个基可行解开始，沿着多面体的边移动最终找到最优解。最终找到最优解。最终找到最优解。最终找到最优解。内点算法的思想是从可行域内的任意一点内点算法的思想是从可行域内的任意一点内点算法的思想是从可行域内的任意一点内点算法的思想是从可行域内的任意一点(任一可行解任一可行解任一可行解任一可行解)出出出出发，穿越可行域的内部达到最优解。发，穿越可行域的内部达到最优解。发，穿越可行域的内部达到最优解。发，穿越可行域的内部达到最优解。N.Karmarkar N.Karmarkar的的的的投投影尺度算法影尺度算法就是一种典型的内点算法。就是一种典型的内点算法。就是一种典型的内点算法。就是一种典型的内点算法。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂线性规划线性规划内点算法内点算法可行域可行域内点内点初始基可行解初始基可行解基可行解基可行解目标函数目标函数目标函数最速下降方向目标函数最速下降方向决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂线性规划线性规划内点算法内点算法v投影尺度算法投影尺度算法如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？KarmarkarKarmarkar发现：发现：发现：发现：(1)(1)如果一个内点位于可行域如果一个内点位于可行域如果一个内点位于可行域如果一个内点位于可行域(多胞形、多面体多胞形、多面体多胞形、多面体多胞形、多面体)的的的的中心，那么目标函数的最速下降方向是比较好的方向；中心，那么目标函数的最速下降方向是比较好的方向；中心，那么目标函数的最速下降方向是比较好的方向；中心，那么目标函数的最速下降方向是比较好的方向；(2)(2)存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置于变换后的可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，KarmarkarKarmarkar构构构构造了一种称为造了一种称为造了一种称为造了一种称为投影尺度算法投影尺度算法的内点算法。的内点算法。的内点算法。的内点算法。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂线性规划线性规划内点算法内点算法X空间空间内点内点目标函数目标函数目标函数最目标函数最速下降方向速下降方向Y1空间空间中心点中心点投影尺度变换投影尺度变换1目标函数最目标函数最速下降方向速下降方向Y2空间空间中心点中心点投影尺度变换投影尺度变换2决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂线性规划线性规划Matlab函数应用函数应用vOptimization ToolBoxMin fTxS.t.AxbAeqx=beqlbxub其中：其中：f,x,b,beq,lb和和ub均为向量；均为向量；A和和Aeq为矩阵。为矩阵。x,fval=linprog(f,A,b,Aeq,beq,lb,ub)决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂线性规划线性规划Matlab函数应用函数应用vv例：例：例：例：max z=x1+2x2max z=x1+2x2S.t.S.t.x1+x2x1+x2402x1+x260 x10;x200;x20解解：将：将max变为变为min，min z=-x1-2x2则：则：f=-1;-2;b=40;60;lb=zeros(2,1);A=1 1;2 1 x,fval=linprog(f,A,b,lb)x=0;40,fval=-80 x1x2x1+x2=402x1+x2=60Z=x1+2x2决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂优化决策理论与方法优化决策理论与方法1 1、线性规划、线性规划、线性规划、线性规划2、非线性规划（约束和非约束）、非线性规划（约束和非约束）3 3、多目标规划、多目标规划、多目标规划、多目标规划4 4、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂无约束非线性规划无约束非线性规划标准型标准型vMin f(x);x Rnv其中其中f：RnR是一个非线性连续函数。对于任意点是一个非线性连续函数。对于任意点x*Rn,它是函数它是函数f的最小点的最小点(或局部极小点或局部极小点)吗？吗？v例如：例如：min f(x)=ex1(4x12+2x22+4x1x2+2x2+1)决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂无约束非线性规划无约束非线性规划极小值存在条件极小值存在条件v必要条件必要条件。设。设x*是是f(x)的局部极小点，则的局部极小点，则当当f(x)在在x*点可微时，梯度点可微时，梯度 f(x*)=0；当当f(x)在在x*点二阶可微时，点二阶可微时，Hesse矩阵矩阵2f(x*)是半正定是半正定 的，的，即即d Rn，有，有dT 2f(x*)d 0。v充分条件充分条件。设设f(x)在在x*点二阶可微，若梯度点二阶可微，若梯度 f(x*)=0且且Hesse矩阵矩阵 2f(x*)是正定是正定 的，则的，则x*是是f(x)的一个严的一个严格局部极小点。格局部极小点。v充要条件充要条件。设。设f(x)是可微凸函数，则是可微凸函数，则x*是是f(x)的全局的全局最小点，当且仅当梯度最小点，当且仅当梯度 f(x*)=0。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂无约束非线性规划无约束非线性规划复习复习vv梯度矩阵梯度矩阵梯度矩阵梯度矩阵vvHesseHesse矩阵矩阵矩阵矩阵vvTaylorTaylor展开展开展开展开决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂无约束非线性规划无约束非线性规划牛顿法牛顿法v基本思想基本思想：在一个点附近，用目标函数：在一个点附近，用目标函数f(x)的二阶的二阶Taylor多项式近似多项式近似f(x)，并用该，并用该Taylor多项式的最小多项式的最小点近似点近似f(x)的最小点。如果近似误差比较大，那么可的最小点。如果近似误差比较大，那么可在近似最小点附近重新构造在近似最小点附近重新构造f(x)的二阶的二阶Taylor多项式多项式(迭代迭代)，据此寻找新的近似最小点，重复以上过程，据此寻找新的近似最小点，重复以上过程直到求得满足一定精度要求的迭代点。直到求得满足一定精度要求的迭代点。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂无约束非线性规划无约束非线性规划牛顿法牛顿法v设设xk是第是第k次迭代结果，记次迭代结果，记gk=g(xk)=f(xk)；Gk=G(xk)=2f(xk)。则。则f(x)=f(xk+p)k(p)=f(xk)+g(xk)Tp+1/2pTG(xk)pv由于由于 k(p)的最小点满足的最小点满足g(xk)+G(xk)p=0，得，得p=x-xk=-G-1(xk)g(xk)v因此，可近似得到迭代关系：因此，可近似得到迭代关系：xk+1=xk-G-1(xk)g(xk)决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂无约束非线性规划无约束非线性规划牛顿法牛顿法v牛顿迭代法步骤牛顿迭代法步骤初始化初始化：给定一个初始点：给定一个初始点x0以及参数以及参数e0；记；记k=0。收敛性检验收敛性检验：计算：计算g(xk)，若，若|g(xk)|e，则算法终止；否则，则算法终止；否则计算计算G(xk)。迭代改进迭代改进：计算新的迭代点：计算新的迭代点xk+1，即，即xk+1=xk-G-1(xk)g(xk)。k+1k。返回收敛性检验。返回收敛性检验。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂无约束非线性规划无约束非线性规划准牛顿法准牛顿法vv牛顿法算法的优点是收敛速度快牛顿法算法的优点是收敛速度快牛顿法算法的优点是收敛速度快牛顿法算法的优点是收敛速度快(利用了利用了利用了利用了HesseHesse矩阵矩阵矩阵矩阵)。但使用。但使用。但使用。但使用HesseHesse矩阵的不足之处是计算量大，矩阵的不足之处是计算量大，矩阵的不足之处是计算量大，矩阵的不足之处是计算量大，HesseHesse矩阵可能非正定等，准牛顿法矩阵可能非正定等，准牛顿法矩阵可能非正定等，准牛顿法矩阵可能非正定等，准牛顿法(Quasi-(Quasi-Newton method)Newton method)是对牛顿法的改进，目前被公认是对牛顿法的改进，目前被公认是对牛顿法的改进，目前被公认是对牛顿法的改进，目前被公认为是比较有效的无约束优化方法。为是比较有效的无约束优化方法。为是比较有效的无约束优化方法。为是比较有效的无约束优化方法。v基本思想基本思想：在迭代过程中只利用目标函数：在迭代过程中只利用目标函数：在迭代过程中只利用目标函数：在迭代过程中只利用目标函数f(x)f(x)和梯度和梯度和梯度和梯度g(x)g(x)的信息，构造的信息，构造的信息，构造的信息，构造HesseHesse矩阵的近似矩阵，由此获矩阵的近似矩阵，由此获矩阵的近似矩阵，由此获矩阵的近似矩阵，由此获得一个搜索方向，生产新的迭代点。具体内容请参得一个搜索方向，生产新的迭代点。具体内容请参得一个搜索方向，生产新的迭代点。具体内容请参得一个搜索方向，生产新的迭代点。具体内容请参考相关书籍。考相关书籍。考相关书籍。考相关书籍。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂无约束非线性规划无约束非线性规划Matlab函数应用函数应用vOptimization ToolBoxMin f(x)vMatlab提供了两个求解无约束非线性规划的函数提供了两个求解无约束非线性规划的函数x,fval=x,fval=fminunc(fun,x0)(fun,x0)x,fval=x,fval=fminsearch(fun,x0)(fun,x0)vv用法相似，算法内部的搜索策略不同。用法相似，算法内部的搜索策略不同。用法相似，算法内部的搜索策略不同。用法相似，算法内部的搜索策略不同。funfun为为为为f(x)f(x)的的的的函数形式，函数形式，函数形式，函数形式，x0 x0为初始解向量。为初始解向量。为初始解向量。为初始解向量。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂无约束非线性规划无约束非线性规划Matlab函数应用函数应用v用法用法创建一个创建一个matlab文件，如文件，如myfun.mfunction f=myfun(x)f=f(x);然后调用然后调用fminunc或或fminsearch并指定初始搜索点。并指定初始搜索点。x0=x1,x2,xn x,fval=fminunc(myfun,x0)或或 x,fval=fminsearch(myfun,x0)决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂无约束非线性规划无约束非线性规划Matlab函数应用函数应用v例例：min f(x)=ex1(4x12+2x22+4x1x2+2x2+1)v解解：创建一个创建一个matlab文件，如文件，如myfun.mfunction f=myfun(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);调用无约束非线性规划函数调用无约束非线性规划函数调用无约束非线性规划函数调用无约束非线性规划函数 x0=-1,1;%Starting guess x0=-1,1;%Starting guess options=optimset(LargeScale,off);options=optimset(LargeScale,off);x,fval=x,fval=fminunc(myfun,x0,options);(myfun,x0,options);或者或者或者或者x,fval=x,fval=fminsearch(myfun,x0,options);(myfun,x0,options);决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂无约束非线性规划无约束非线性规划Matlab函数应用函数应用v 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 searchsearchv fminsearch结果：结果：x=0.5000 -1.0000 x=0.5000 -1.0000fval=5.1425e-010fval=5.1425e-010iterations:46iterations:46algorithm:Nelder-Mead simplex direct searchalgorithm:Nelder-Mead simplex direct search决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划标准型标准型v其中其中f(x)是目标函数，是目标函数，gi(x)和和hj(x)为约束函数为约束函数(约束约束条件条件)。S=x|gi(x)0 hj(x)=0为可行域。为可行域。v有约束非线性规划问题有约束非线性规划问题(COP)是指是指f(x),gi(x),hj(x)至少至少有一个是非线性的，且有一个是非线性的，且I或或 至少有一个为非空。至少有一个为非空。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划几个概念几个概念v积极积极(active)约束约束：设：设x0是是COP问题的一个可行解，问题的一个可行解，则它必须满足所有约束条件。对于则它必须满足所有约束条件。对于gi(x0)0，或者，或者等号成立，或者大于号成立。称等号成立的约束为等号成立，或者大于号成立。称等号成立的约束为积极约束积极约束(有效约束有效约束)，此时，此时，x0处于该约束条件形成处于该约束条件形成的可行域边界上；称大于号成立的约束为非积极的可行域边界上；称大于号成立的约束为非积极(inactive)约束约束(无效约束无效约束)，此时，此时，x0不在该约束条件不在该约束条件形成的可行域边界上。显然所有形成的可行域边界上。显然所有hj(x0)约束均是积极约束均是积极约束。记约束。记J=j|gj(x0)=0 hj(x0)=0，称为积极约束指，称为积极约束指标集。标集。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划几个概念几个概念v可行方向可行方向。设。设x0为为COP问题的任一可行解，对某一方向问题的任一可行解，对某一方向d来来说，若说，若00使得对于任意使得对于任意0,0，均有，均有x0+d S，称，称d为为x0的一个可行方向。显然若的一个可行方向。显然若d满足满足dT gi(x)0，dT hj(x)=0，则则d一定是可行方向。（可用一阶一定是可行方向。（可用一阶Taylor公式分析）。公式分析）。v下降方向下降方向。设设x0 S，对某一方向，对某一方向d来说，若来说，若00使得对于任使得对于任意意0,0，均有，均有f(x0+d)f(x0)，则称，则称d为为x0点的一个下降方点的一个下降方向。由向。由f(x0+d)=f(x0)+(f(x0)Td+o()可知：若可知：若d满足满足dT f(x0)0，有，有f(x0+d)0，则，则x*为为COP问题的一个问题的一个严格局部极小点。严格局部极小点。(凸规划问题凸规划问题)设设f(x)为凸函数，为凸函数，gi(x)为凹函数，为凹函数，hj(x)为线性为线性函数。对于函数。对于x*S，若，若函数函数f(x),gi(x)在在x*处可微，且处可微，且KKT条件成立，则条件成立，则x*为为COP问题的全局最小点。问题的全局最小点。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划极小值存在条件极小值存在条件v二阶必要条件二阶必要条件设设设设x*是是COP问题的局部极小点且满足问题的局部极小点且满足KKT条件。若函数条件。若函数f(x),gi(x),hj(x)在在x*处二阶可微，则必有：处二阶可微，则必有：dT xx2L(x*,*,*)d 0 其中，其中，L(x,)=f(x)-g(x)T-h(x)T,g(x),h(x)分别为由分别为由gi(x)和和hj(x)构成的向量值函数，构成的向量值函数，,分别为对应于分别为对应于g(x)和和h(x)的拉格朗日乘子向量。的拉格朗日乘子向量。v二阶充分条件二阶充分条件设设设设x*是是COP问题的问题的KKT点。点。*,*分别为对应于分别为对应于g(x)和和h(x)的拉格朗日乘子向量，且的拉格朗日乘子向量，且函数函数f(x),gi(x),hj(x)在在x*处二处二阶可微，若阶可微，若dT xx2L(x*,*,*)d0,则则x*为为COP问题的一个问题的一个严格局部极小点。严格局部极小点。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划极小值存在条件极小值存在条件v例：例：min f(x)=x12+x22 S.t.x1+x2 4 x1,x2 0v解：解：g1(x)=x1+x2-4 0;g2(x)=x1 0;g3(x)=x2 0 f(x)=2x1,2x2T,g1(x)=1,1T,g2(x)=1,0T,g3(x)=0,1T,得得到：到：2x1=1+22x2=1+3又又(x1+x2-4)1=0；x1 2=0；x2 3=0；i 0v若若 1=0，则，则x1=x2=0，与题意不符；，与题意不符；v若若 10，则，则x1+x2-4=0，x10,x20。因此有。因此有 2=3=0，所以，所以x1=x2=1/2，得，得x1=x2=2，x*=2,2T为该问题的唯一为该问题的唯一KKT点。点。v根据凸规划充分条件知根据凸规划充分条件知x*为全局最小点。为全局最小点。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划可行方向法可行方向法vv上面例题介绍了通过求解上面例题介绍了通过求解上面例题介绍了通过求解上面例题介绍了通过求解KKTKKT方程获得问题解的方方程获得问题解的方方程获得问题解的方方程获得问题解的方法，但法，但法，但法，但KKTKKT方程并不总是很好求解。下面介绍几种方程并不总是很好求解。下面介绍几种方程并不总是很好求解。下面介绍几种方程并不总是很好求解。下面介绍几种约束优化的求解方法：可行方向法、序列无约束化约束优化的求解方法：可行方向法、序列无约束化约束优化的求解方法：可行方向法、序列无约束化约束优化的求解方法：可行方向法、序列无约束化法和法和法和法和SQPSQP法。法。法。法。v可行方向法的应用条件可行方向法的应用条件：要求所有约束均为线性约：要求所有约束均为线性约：要求所有约束均为线性约：要求所有约束均为线性约束（称为线性约束的优化问题，束（称为线性约束的优化问题，束（称为线性约束的优化问题，束（称为线性约束的优化问题，LCOLCO）。）。）。）。v可行方向法的基本思想可行方向法的基本思想：当某个可行方向同时也是：当某个可行方向同时也是：当某个可行方向同时也是：当某个可行方向同时也是目标函数的下降方向时，沿此方向移动一定会在满目标函数的下降方向时，沿此方向移动一定会在满目标函数的下降方向时，沿此方向移动一定会在满目标函数的下降方向时，沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值。足可行性的情况下改进迭代点的目标函数值。足可行性的情况下改进迭代点的目标函数值。足可行性的情况下改进迭代点的目标函数值。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划可行方向法可行方向法x1x2决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划可行方向法可行方向法vLCO问题：问题：Min f(x)S.t.aiTx bi,i I ajTx=bj,jv设设x0是是LCO的一个可行解，若的一个可行解，若d是可行域在是可行域在x0点的点的可可行方向行方向，则，则d满足满足AI(x0)d 0(I(x0)=i|aiTx0=bi,i I)，A d=0。v设设x0是是LCO的一个可行解，若的一个可行解，若d是可行域在是可行域在x0点的点的下下降方向降方向，则，则d满足满足dT f(x0)0，定义二次罚函数，定义二次罚函数Min Q(x,)=x1+x2+(2)-1(x1-x22)2Qx1=1+(x1-x22)/=0Qx2=1-2x2(x1-x22)/=0解得：解得：x*=(1/4-,-1/2)T,Q*=-1/4-/2当当 0时得，时得，x*=(1/4,-1/2)T,f*=-1/4决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划序列无约束化法序列无约束化法v对数障碍函数法对数障碍函数法：障碍函数：障碍函数：其中其中 称为障碍参数，且当称为障碍参数，且当 0时，时，P(x,)的极小值趋于的极小值趋于f(x)的极小值。的极小值。该方法的适用性：该方法的适用性：COP问题仅包含不等式约束函数，且问题仅包含不等式约束函数，且可行域存在内点。即可行域存在内点。即S0=x|g(x)0 决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划序列无约束化法序列无约束化法v例例：minf=x/2|x 1v解：构造对数障碍函数解：构造对数障碍函数P(x,)=x/2-ln(x-1)Px=1/2-/(x-1)=0，得，得x*=1+2，P*=1/2+-ln2 当当 0时得时得x*=1，f*=1/2决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂二次规划二次规划标准型标准型v若有约束非线性规划的目标函数是决策变量若有约束非线性规划的目标函数是决策变量x的二次的二次函数且所有约束均为线性约束，称此类非线性规划函数且所有约束均为线性约束，称此类非线性规划问题为二次规划问题为二次规划(Quadratic Programming,QP)问题。问题。其标准型为：其标准型为：决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂二次规划二次规划标准型标准型v其中其中Q=QT Rnn（n阶对称方阵）；以阶对称方阵）；以aiT(i I)为行为行向量的矩阵记为向量的矩阵记为AI RIn；以；以ajT(j)为行向量的为行向量的矩阵记为矩阵记为A R n；对应的向量记为；对应的向量记为bI,b。若目标函。若目标函数的数的Hesse矩阵矩阵Q是半正定是半正定(或正定或正定)的，则的，则QP问题为问题为(严格严格)凸二次规划凸二次规划(CQP)。我们仅讨论凸二次规划问。我们仅讨论凸二次规划问题，因为非凸二次规划的题，因为非凸二次规划的Q存在负特征根，求解很存在负特征根，求解很困难。困难。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂二次规划二次规划极小点存在条件极小点存在条件v充要条件充要条件可行点可行点x*是是QP问题的局部极小点当且仅当问题的局部极小点当且仅当x*为一个为一个KKT点且对于任意非零可行方向点且对于任意非零可行方向d，有，有dTQd 0。对于凸二次规划，对于凸二次规划，x*为全局极小点当且仅当为全局极小点当且仅当x*为局部极小为局部极小点，当且仅当点，当且仅当x*为为KKT点。点。二次规划的二次规划的KKT定理形式为：定理形式为：Qx*+c=AIT*+A T*(AIx*-bI)*=0v二次规划的求解本质上就是求解上述二次规划的求解本质上就是求解上述KKT方程。方程。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划SQP法法vv对于非线性约束优化对于非线性约束优化对于非线性约束优化对于非线性约束优化(COP)(COP)问题，问题，问题，问题，vv若若若若x*是是是是COPCOP问题的一个局部最优解，则它对应一个问题的一个局部最优解，则它对应一个问题的一个局部最优解，则它对应一个问题的一个局部最优解，则它对应一个纯等式约束优化问题纯等式约束优化问题纯等式约束优化问题纯等式约束优化问题决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划SQP法法vv因此如果事先知道积极约束指标集，那么带有不等因此如果事先知道积极约束指标集，那么带有不等因此如果事先知道积极约束指标集，那么带有不等因此如果事先知道积极约束指标集，那么带有不等式约束优化问题就可以转化为纯等式约束优化问题，式约束优化问题就可以转化为纯等式约束优化问题，式约束优化问题就可以转化为纯等式约束优化问题，式约束优化问题就可以转化为纯等式约束优化问题，并可用准牛顿法求解，这就是逐次二次规划并可用准牛顿法求解，这就是逐次二次规划并可用准牛顿法求解，这就是逐次二次规划并可用准牛顿法求解，这就是逐次二次规划(Sequential Quadratic Programming(Sequential Quadratic Programming，SQP)SQP)法。法。法。法。v基本思想基本思想：在迭代点处构造一个二次规划子问题，：在迭代点处构造一个二次规划子问题，：在迭代点处构造一个二次规划子问题，：在迭代点处构造一个二次规划子问题，近似原来的约束优化问题；然后通过求解该二次规近似原来的约束优化问题；然后通过求解该二次规近似原来的约束优化问题；然后通过求解该二次规近似原来的约束优化问题；然后通过求解该二次规划子问题获得约束优化问题的一个改进迭代点；不划子问题获得约束优化问题的一个改进迭代点；不划子问题获得约束优化问题的一个改进迭代点；不划子问题获得约束优化问题的一个改进迭代点；不断重复此过程，直到求出满足一定要求的迭代点。断重复此过程，直到求出满足一定要求的迭代点。断重复此过程，直到求出满足一定要求的迭代点。断重复此过程，直到求出满足一定要求的迭代点。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划SQP法法v对于等式约束优化问题对于等式约束优化问题Min f(x)S.t.h(x)=0v拉格朗日函数记为拉格朗日函数记为L(x,)=f(x)-Th(x)v则则 L(x,)=(f(x)-h(x),-h(x)T=0，显然问题的最优解，显然问题的最优解(x*,*)满足此式。满足此式。v设设(xk,k)是第是第k次迭代结果，根据牛顿法，有：次迭代结果，根据牛顿法，有：决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划SQP法法v上述迭代过程等价于如下的二次规划的迭代。设给定迭代点上述迭代过程等价于如下的二次规划的迭代。设给定迭代点(xk,k)，则，则决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划Matlab函数应用函数应用vOptimization ToolBoxMin f(x)s.t.c(x)0 ceq(x)=0 A x b Aeq x=beq lb x ubvx,fval=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)vfun定义目标函数定义目标函数,x0定义初始可行解，定义初始可行解，nonlcon定义定义c(x)和和ceq(x)。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划Matlab函数应用函数应用v用法用法创建一个创建一个matlab文件，如文件，如myfun.mfunction f=myfun(x)f=f(x);创建另一个创建另一个matlab文件，如文件，如confun.mfunction c,ceq=confun(x)c=c(x);ceq=ceq(x);调用调用fmincon并指定初始搜索点以及其他向量、矩阵。并指定初始搜索点以及其他向量、矩阵。x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;x,fval=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,confun)决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划Matlab函数应用函数应用v例例：min f(x)=ex1(4x12+2x22+4x1x2+2x2+1)S.t.x1x2-x1-x2-1.5 x1x2-10v解解：创建一个创建一个matlab文件，如文件，如myfun.mfunction f=myfun(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);创建另一个创建另一个matlab文件，如文件，如confun.mfunction c,ceq=confun(x)c=1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;ceq=;决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂约束非线性规划约束非线性规划Matlab函数应用函数应用调用有约束非线性规划函数调用有约束非线性规划函数x0=-1,1;%Starting guessoptions=optimset(LargeScale,off);x,fval=fmincon(objfun,x0,confun,options)运行结果运行结果：x=-9.5474 1.0474x=-9.5474 1.0474fval=0.0236fval=0.0236iterations:8iterations:8algorithm:medium-scale:SQP,Quasi-Newton,line-algorithm:medium-scale:SQP,Quasi-Newton,line-searchsearch决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂二次规划二次规划Matlab函数应用函数应用vOptimization ToolBoxMin 0.5xTHx+fTxs.t.Ax b Aeqx=beq lb x ubvvx,fval=x,fval=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)(H,f,A,b,Aeq,beq,lb,ub,x0)vvx0 x0定义初始可行解定义初始可行解定义初始可行解定义初始可行解(可选可选可选可选)决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂二次规划二次规划Matlab函数应用函数应用v用法用法首先要将目标函数转换成二次规划标准型，从而得到首先要将目标函数转换成二次规划标准型，从而得到H和和f两个矩阵。两个矩阵。调用调用quadprog并根据需要指定初始搜索点以及其他向量、并根据需要指定初始搜索点以及其他向量、矩阵。矩阵。x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;x,fval=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)(H,f,A,b,Aeq,beq,lb,ub,x0)决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂二次规划二次规划Matlab函数应用函数应用v例例：min f(x)=1/2x12+x22-x1x2-2x1-6x2)S.t.x1+x2 2 -x1+2x2 2 2x1+x2 3 x1,x2 0v解解：改写改写f(x)=1/2(x12+2x22-x1x2-x1x2)-2x1-6x2得：得：H=1-1;-1 2,f=-2;-6,x=x1;x2;表示其它矩阵或向量表示其它矩阵或向量A=1 1;-1 2;2 1;b=2;2;3;lb=0;0;Aeq=;beq=;ub=。不指派初始解。不指派初始解。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂二次规划二次规划Matlab函数应用函数应用调用二次规划函数调用二次规划函数x,fval=quadprog(H,f,A,b,lb)(H,f,A,b,lb)运行结果运行结果：x=0.6667;1.3333x=0.6667;1.3333fval=-8.2222fval=-8.2222iterations:3iterations:3algorithm:medium-scale:active-set(algorithm:medium-scale:active-set(积极约束集方法积极约束集方法积极约束集方法积极约束集方法)决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂优化决策理论与方法优化决策理论与方法1 1、线性规划、线性规划、线性规划、线性规划2 2、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）3、多目标规划、多目标规划4 4、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂多目标规划多目标规划管理实例管理实例v(物资调度物资调度)假设物资调度部门计划将某种物资从若干个存储假设物资调度部门计划将某种物资从若干个存储仓库调运到若干个销售网点销售。考虑到物资的时效性和销仓库调运到若干个销售网点销售。考虑到物资的时效性和销售效益，调度部门希望物资在运输过程中尽可能快地到达目售效益，调度部门希望物资在运输过程中尽可能快地到达目的地；同时，考虑到运输成本，调度部门还希望物资的总运的地；同时，考虑到运输成本，调度部门还希望物资的总运输费用最小。试建立描述物资调运过程的数学模型。输费用最小。试建立描述物资调运过程的数学模型。v解解：设共有：设共有m个仓库，第个仓库，第i个仓库的物资库存量为个仓库的物资库存量为ai吨；有吨；有n个个销售网点，第销售网点，第j个销售网点的销售量为个销售网点的销售量为bj吨。第吨。第i个仓库到第个仓库到第j个销售网点的距离为个销售网点的距离为dij，单位物资的运费为，单位物资的运费为cij。设从第。设从第i个仓个仓库运到第库运到第j个销售网点的物资量为个销售网点的物资量为xij。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂多目标规划多目标规划管理实例管理实例v决策目标：决策目标：运输速度最快，可用吨公里数（运输速度最快，可用吨公里数（可观测变量可观测变量）最小描述。）最小描述。总吨公里数为总吨公里数为 i jdijxij；运输费用最小。总运输费用为运输费用最小。总运输费用为 i jcijxij；v约束条件约束条件每个仓库的运出量不超过仓库的库存量：每个仓库的运出量不超过仓库的库存量：jxij ai；运到每个销售网点的量与其销售能力相匹配：运到每个销售网点的量与其销售能力相匹配：ixij=bj；每个仓库的运出量非负：每个仓库的运出量非负：xij 0。决策理论与方法-优化决策理论与方法路漫漫其悠远路漫漫其悠远锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂锲而不舍，金石可镂多目标规划多目标规划管理实例