《第02讲优化决策理论与方法.ppt》由会员分享，可在线阅读，更多相关《第02讲优化决策理论与方法.ppt（86页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第02讲优化决策理论与方法讲优化决策理论与方法现在学习的是第1页，共86页确定性决策确定性决策vv确定性决策确定性决策：指未来状态是确定的（即只有一种状：指未来状态是确定的（即只有一种状态）一类决策问题，每一个行动方案对应着一个确态）一类决策问题，每一个行动方案对应着一个确定的结果值，此时决策函数仅依赖于决策变量。定的结果值，此时决策函数仅依赖于决策变量。vv特点特点：状态是确定的；决策问题变为优化问题。：状态是确定的；决策问题变为优化问题。vv决策的已知变量决策的已知变量：决策变量及其取值范围决策变量及其取值范围决策变量及其取值范围决策变量及其取值范围vv解决问题的主要理论方法解决问题的主
2、要理论方法：最优化理论与方法：最优化理论与方法vv注：注：最优化理论与方法（数学规划）也可以求解不最优化理论与方法（数学规划）也可以求解不确定性决策问题、随机性决策问题确定性决策问题、随机性决策问题现在学习的是第2页，共86页确定性决策确定性决策vv优化决策方法的问题求解过程优化决策方法的问题求解过程辨识目标辨识目标辨识目标辨识目标C C，确定优化的标准，如：利润、时间、能量等，确定优化的标准，如：利润、时间、能量等，确定优化的标准，如：利润、时间、能量等，确定优化的标准，如：利润、时间、能量等确定影响决策目标的决策变量确定影响决策目标的决策变量确定影响决策目标的决策变量确定影响决策目标的决策
3、变量x x，形成目标函数，形成目标函数，形成目标函数，形成目标函数C=C=f f(x x)明确决策变量的取值范围，形成约束函数明确决策变量的取值范围，形成约束函数明确决策变量的取值范围，形成约束函数明确决策变量的取值范围，形成约束函数设计求解算法，寻找决策目标在决策变量所受限制的范设计求解算法，寻找决策目标在决策变量所受限制的范设计求解算法，寻找决策目标在决策变量所受限制的范设计求解算法，寻找决策目标在决策变量所受限制的范围内的极小化或极大化。围内的极小化或极大化。围内的极小化或极大化。围内的极小化或极大化。最优化问题的一般形式为：最优化问题的一般形式为：最优化问题的一般形式为：最优化问题的一
4、般形式为：现在学习的是第3页，共86页优化问题分类优化问题分类vv可行点可行点与与可行域可行域：满足约束条件的：满足约束条件的x称为可行点，所称为可行点，所有可行点的集合称为可行域，记为有可行点的集合称为可行域，记为S；vv约束优化约束优化与与无约束优化无约束优化：当：当S Rn时，称为约束优时，称为约束优化；当化；当S=Rn时，称为无约束优化；时，称为无约束优化；vv多目标优化多目标优化：若：若f是多个目标函数构成的一个向量值是多个目标函数构成的一个向量值函数，则称为多目标规划；函数，则称为多目标规划；vv线性规划线性规划与与非线性规划非线性规划：当：当f,g,h均为线性函数时称均为线性函数
5、时称为线性规划，否则称为非线性规划。为线性规划，否则称为非线性规划。现在学习的是第4页，共86页优化问题分类优化问题分类vv整数规划整数规划：当决策变量的取值均为整数时称为整数：当决策变量的取值均为整数时称为整数规划；若某些变量取值为整数，而另一些变量取值规划；若某些变量取值为整数，而另一些变量取值为实数，则成为混合整数规划。为实数，则成为混合整数规划。vv动态规划动态规划与与多层规划多层规划：若决策是分成多个阶段完成：若决策是分成多个阶段完成的，前后阶段之间相互影响，则称为动态规划；若的，前后阶段之间相互影响，则称为动态规划；若决策是分成多个层次完成的，不同层次之间相互影决策是分成多个层次完
6、成的，不同层次之间相互影响，则称为多层规划。响，则称为多层规划。现在学习的是第5页，共86页优化决策理论与方法优化决策理论与方法1、线性规划、线性规划2、非线性规划（约束和非约束）、非线性规划（约束和非约束）3、多目标规划、多目标规划4、组合优化与整数规划、组合优化与整数规划现在学习的是第6页，共86页线性规划线性规划管理实例管理实例vv(食谱问题食谱问题食谱问题食谱问题)假设市场上有假设市场上有假设市场上有假设市场上有n n种不同的食物，第种不同的食物，第种不同的食物，第种不同的食物，第j j种食物的单价为种食物的单价为种食物的单价为种食物的单价为c cj j。人体正常活动过程中需要人体正常
7、活动过程中需要人体正常活动过程中需要人体正常活动过程中需要mm种基本的营养成分，且每人每天至少需种基本的营养成分，且每人每天至少需种基本的营养成分，且每人每天至少需种基本的营养成分，且每人每天至少需要摄入第要摄入第要摄入第要摄入第i i种营养成分种营养成分种营养成分种营养成分b bi i个单位。已知第个单位。已知第个单位。已知第个单位。已知第j j种食物中包含第种食物中包含第种食物中包含第种食物中包含第i i种营养种营养种营养种营养成分的量为成分的量为成分的量为成分的量为a aij ij个单位。问在满足人体基本营养需求的前提下什么样的个单位。问在满足人体基本营养需求的前提下什么样的个单位。问在
8、满足人体基本营养需求的前提下什么样的个单位。问在满足人体基本营养需求的前提下什么样的配食方案最经济？配食方案最经济？配食方案最经济？配食方案最经济？vv设食谱中包含第设食谱中包含第设食谱中包含第设食谱中包含第j j种食物的量为种食物的量为种食物的量为种食物的量为x xj j，则：，则：，则：，则：现在学习的是第7页，共86页线性规划线性规划标准型标准型现在学习的是第8页，共86页线性规划线性规划单纯形算法单纯形算法vv解空间分析解空间分析可行域分析可行域分析可行域分析可行域分析：n n维空间；第一象限；维空间；第一象限；维空间；第一象限；维空间；第一象限；mm个超平面。个超平面。个超平面。个超
9、平面。最优解分析最优解分析最优解分析最优解分析：在端点：在端点：在端点：在端点(或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有n n-mm个个个个0 0分量分量分量分量)处取极值。处取极值。处取极值。处取极值。vv单纯形算法的基本思想单纯形算法的基本思想从某个极点开始获得一个可行解；从某个极点开始获得一个可行解；从某个极点开始获得一个可行解；从某个极点开始获得一个可行解；判断该可行解是不是目标解。若是，算法结束；否则寻判断该可行解是不是目标解。若是，算法结束；否则寻判断该可行解是不是目标解。若是，算法结束；否则寻判断该可
10、行解是不是目标解。若是，算法结束；否则寻找下一个极点（确定找下一个极点（确定找下一个极点（确定找下一个极点（确定入基变量入基变量入基变量入基变量和和和和出基变量出基变量出基变量出基变量），直至找到目），直至找到目），直至找到目），直至找到目标解。标解。标解。标解。现在学习的是第9页，共86页线性规划线性规划内点算法内点算法vv1972年，年，V.Klee和和G.L.Minty指出指出Dantzig的单纯的单纯形算法的迭代次数为形算法的迭代次数为O(2n)，是一个指数时间算法，是一个指数时间算法，不是优良算法。那么是否存在求解线性规划问题的不是优良算法。那么是否存在求解线性规划问题的多项式时间算
11、法？多项式时间算法？vv1984年，年，N.Karmarkar提出了一种提出了一种投影尺度算法投影尺度算法，其计算效果能够同单纯形法相比较，掀起了线性规其计算效果能够同单纯形法相比较，掀起了线性规划划内点算法内点算法的热潮。的热潮。现在学习的是第10页，共86页线性规划线性规划内点算法内点算法vv内点算法的思想内点算法的思想已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题的可行域是一个多面体，最优点在多面体的某个极点取到。在给定初始可行解后，沿着什么样面体的某个极点取到。在给定初始可
12、行解后，沿着什么样面体的某个极点取到。在给定初始可行解后，沿着什么样面体的某个极点取到。在给定初始可行解后，沿着什么样的路径到达最优解呢？的路径到达最优解呢？的路径到达最优解呢？的路径到达最优解呢？单纯形法是从某个基可行解开始，沿着多面体的边移动单纯形法是从某个基可行解开始，沿着多面体的边移动单纯形法是从某个基可行解开始，沿着多面体的边移动单纯形法是从某个基可行解开始，沿着多面体的边移动最终找到最优解。最终找到最优解。最终找到最优解。最终找到最优解。内点算法的思想是从可行域内的任意一点内点算法的思想是从可行域内的任意一点内点算法的思想是从可行域内的任意一点内点算法的思想是从可行域内的任意一点(
13、任一可行解任一可行解任一可行解任一可行解)出出出出发，穿越可行域的内部达到最优解。发，穿越可行域的内部达到最优解。发，穿越可行域的内部达到最优解。发，穿越可行域的内部达到最优解。N.KarmarkarN.Karmarkar的的的的投投投投影尺度算法影尺度算法影尺度算法影尺度算法就是一种典型的内点算法。就是一种典型的内点算法。就是一种典型的内点算法。就是一种典型的内点算法。现在学习的是第11页，共86页线性规划线性规划内点算法内点算法可行域可行域内点内点初始基可行解初始基可行解基可行解基可行解目标函数目标函数目标函数最速下降方向目标函数最速下降方向现在学习的是第12页，共86页线性规划线性规划内
14、点算法内点算法vv投影尺度算法投影尺度算法如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？KarmarkarKarmarkar发现：发现：发现：发现：(1)(1)如果一个内点位于可行域如果一个内点位于可行域如果一个内点位于可行域如果一个内点位于可行域(多胞形、多面体多胞形、多面体多胞形、多面体多胞形、多面体)的的的的中心，那么目标函数的最速下降方向是比较好的方向；中心，那么目标函数的最速下降方向是比较好的方向；中心，那么目标函数的最速下降方向是比较好的方向；中心，那么目标函数的最速下降方向是
15、比较好的方向；(2)(2)存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置于变换后的可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，KarmarkarKarmarkar构造构造构造构造了一种称为了一种称为了一种称为了一种称为投影尺度算法投影尺度算法投影尺度算法投影尺度算法的内点算法。的内点算法。的内点算法。的内点算法。现在学习的是第13页，共86页线性规划线性规划内点算法内点
16、算法X空间空间内点内点目标函数目标函数目标函数最速目标函数最速下降方向下降方向Y1空间空间中心点中心点投影尺度变换投影尺度变换1目标函数最速目标函数最速下降方向下降方向Y2空间空间中心点中心点投影尺度变换投影尺度变换2现在学习的是第14页，共86页线性规划线性规划Matlab函数应用函数应用vvOptimization 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和和和和A
17、eqAeq为矩阵。为矩阵。为矩阵。为矩阵。x x,f fval=val=linproglinprog(f f,A,A,b b,Aeq,beq,lb,ub),Aeq,beq,lb,ub)现在学习的是第15页，共86页线性规划线性规划Matlab函数应用函数应用vv例：例：max z=x1+2x2S.t.x x1 1+x+x2 240402x2x1 1+x+x2 26060 x x1 10;x0;x2 200解解：将：将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,l
18、b)x=0;40,fval=-80 x1x2x1+x2=402x1+x2=60Z=x1+2x2现在学习的是第16页，共86页优化决策理论与方法优化决策理论与方法1、线性规划、线性规划2、非线性规划（约束和非约束）、非线性规划（约束和非约束）3、多目标规划、多目标规划4、组合优化与整数规划、组合优化与整数规划现在学习的是第17页，共86页无约束非线性规划无约束非线性规划标准型标准型vvMin f(x);x Rnvv其中其中f：RnR是一个非线性连续函数。对于任意点是一个非线性连续函数。对于任意点x*Rn,它是函数它是函数f的最小点的最小点(或局部极小点或局部极小点)吗？吗？vv例如：例如：min
19、 f(x)=ex1(4x12+2x22+4x1x2+2x2+1)现在学习的是第18页，共86页无约束非线性规划无约束非线性规划复习复习vv梯度向量梯度向量梯度向量梯度向量vvHesse矩阵矩阵vvTaylorTaylor展开展开展开展开现在学习的是第19页，共86页无约束非线性规划无约束非线性规划极小值存在条件极小值存在条件vv必要条件必要条件。设。设x*是是f(x)的局部极小点，则的局部极小点，则当当当当f f(x x)在在在在x x*点可微时，梯度点可微时，梯度点可微时，梯度点可微时，梯度 f f(x x*)=0)=0；当当当当f f(x x)在在在在x x*点二阶可微时，点二阶可微时，点
20、二阶可微时，点二阶可微时，HesseHesse矩阵矩阵矩阵矩阵2 2f f(x x*)是半正定是半正定是半正定是半正定 的，的，的，的，即即即即d d R Rn n，有，有，有，有d dT T 2 2f f(x x*)d d 0 0。vv充分条件充分条件。设设f(x)在在x*点二阶可微，若梯度点二阶可微，若梯度 f(x*)=0且且Hesse矩阵矩阵 2f(x*)是正定是正定 的，则的，则x*是是f(x)的一个严的一个严格局部极小点。格局部极小点。vv充要条件充要条件。设。设f(x)是可微凸函数，则是可微凸函数，则x*是是f(x)的全局的全局最小点，当且仅当梯度最小点，当且仅当梯度 f(x*)=
21、0。现在学习的是第20页，共86页无约束非线性规划无约束非线性规划牛顿法牛顿法vv基本思想基本思想：在一个点附近，用目标函数：在一个点附近，用目标函数f(x)的二阶的二阶Taylor多项式近似多项式近似f(x)，并用该，并用该Taylor多项式的最小多项式的最小点近似点近似f(x)的最小点。如果近似误差比较大，那么可的最小点。如果近似误差比较大，那么可在近似最小点附近重新构造在近似最小点附近重新构造f(x)的二阶的二阶Taylor多项式多项式(迭代迭代)，据此寻找新的近似最小点，重复以上过程，据此寻找新的近似最小点，重复以上过程直到求得满足一定精度要求的迭代点。直到求得满足一定精度要求的迭代点
22、。现在学习的是第21页，共86页无约束非线性规划无约束非线性规划牛顿法牛顿法vv设设xk是第是第k次迭代结果，记次迭代结果，记gk=g(xk)=f(xk)；Gk=G(xk)=2f(xk)。则。则f(x)=f(xk+p)f(xk)+g(xk)Tp+1/2pTG(xk)p=k(p)vv由于由于 k(p)的最小点满足的最小点满足g(xk)+G(xk)p=0，得，得p=x-xk=-G-1(xk)g(xk)vv因此，可近似得到迭代关系：因此，可近似得到迭代关系：xk+1=xk-G-1(xk)g(xk)现在学习的是第22页，共86页无约束非线性规划无约束非线性规划牛顿法牛顿法vv牛顿迭代法步骤牛顿迭代法步
23、骤初始化初始化初始化初始化：给定一个初始点：给定一个初始点：给定一个初始点：给定一个初始点x x0 0以及参数以及参数以及参数以及参数e0e0；记；记；记；记k k=0=0。收敛性检验收敛性检验收敛性检验收敛性检验：计算：计算：计算：计算g g(x xk k)，若，若，若，若|g g(x xk k)|e)|e，则算法终止；否则，则算法终止；否则，则算法终止；否则，则算法终止；否则计算计算计算计算G(G(x xk k)。迭代改进迭代改进迭代改进迭代改进：计算新的迭代点：计算新的迭代点：计算新的迭代点：计算新的迭代点x xk k+1+1，即，即，即，即x xk k+1+1=x xk k-G-G-1
24、-1(x xk k)g g(x xk k)。k k+1+1k k。返回收敛性检验。返回收敛性检验。返回收敛性检验。返回收敛性检验。现在学习的是第23页，共86页无约束非线性规划无约束非线性规划准牛顿法准牛顿法vv牛顿法算法的优点是收敛速度快牛顿法算法的优点是收敛速度快(利用了利用了Hesse矩阵矩阵)。但使用。但使用Hesse矩阵的不足之处是计算量大，矩阵的不足之处是计算量大，Hesse矩阵可能非正定等，准牛顿法矩阵可能非正定等，准牛顿法(Quasi-Newton method)是对牛顿法的改进，目前被公认是对牛顿法的改进，目前被公认为是比较有效的无约束优化方法。为是比较有效的无约束优化方法。
25、vv基本思想基本思想：在迭代过程中只利用目标函数：在迭代过程中只利用目标函数f(x)和梯度和梯度g(x)的信息，构造的信息，构造Hesse矩阵的近似矩阵，由此获矩阵的近似矩阵，由此获得一个搜索方向，生产新的迭代点。具体内容请参得一个搜索方向，生产新的迭代点。具体内容请参考相关书籍。考相关书籍。现在学习的是第24页，共86页无约束非线性规划无约束非线性规划Matlab函数应用函数应用vvOptimization ToolBoxMin Min f f(x x)vvMatlab提供了两个求解无约束非线性规划的函数提供了两个求解无约束非线性规划的函数x,fval=x,fval=fminuncfminu
26、nc(fun,x0)(fun,x0)x,fval=x,fval=fminsearchfminsearch(fun,x0)(fun,x0)vv用法相似，算法内部的搜索策略不同。用法相似，算法内部的搜索策略不同。fun为为f(x)的的函数形式，函数形式，x0为初始解向量。为初始解向量。现在学习的是第25页，共86页无约束非线性规划无约束非线性规划Matlab函数应用函数应用vv用法用法创建一个创建一个创建一个创建一个matlabmatlab文件，如文件，如文件，如文件，如myfun.mmyfun.mfunction f=myfun(x)function f=myfun(x)f=f(x);f=f(x
27、);然后调用然后调用然后调用然后调用fminuncfminunc或或或或fminsearchfminsearch并指定初始搜索点。并指定初始搜索点。并指定初始搜索点。并指定初始搜索点。x0=x1,x2,xnx0=x1,x2,xn x,fval=x,fval=fminuncfminunc(myfun,x0)(myfun,x0)或或或或 x,fval=x,fval=fminsearchfminsearch(myfun,x0)(myfun,x0)现在学习的是第26页，共86页无约束非线性规划无约束非线性规划Matlab函数应用函数应用vv例例：min f(x)=ex1(4x12+2x22+4x1x2
28、+2x2+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);调用无约束非线性规划函数调用无约束非线性规划函数调用无约束非线性规划函数调用无约束非线性规划函数 x0=-1,1;%Starting guessx0=-1,1;%Starting gu
29、ess 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);现在学习的是第27页，共86页无约束非线性规划无约束非线性规划Matlab函数应用函数应用vv fminunc结果：结果：x=0.5000 -1.0000 x=0.5
30、000 -1.0000fval=1.0983e-015fval=1.0983e-015iterations:8iterations:8algorithm:medium-scale:Quasi-Newton line algorithm:medium-scale:Quasi-Newton line searchsearchvv fminsearch结果：结果：x=0.5000 -1.0000 x=0.5000 -1.0000fval=5.1425e-010fval=5.1425e-010iterations:46iterations:46algorithm:Nelder-Mead simplex
31、 direct searchalgorithm:Nelder-Mead simplex direct search现在学习的是第28页，共86页约束非线性规划约束非线性规划标准型标准型vv其中其中f(x)是目标函数，是目标函数，gi(x)和和hj(x)为约束函数为约束函数(约束条约束条件件)。S=x|gi(x)0 hj(x)=0为可行域。为可行域。vv有约束非线性规划问题有约束非线性规划问题(COP)是指是指f(x),gi(x),hj(x)至少至少有一个是非线性的，且有一个是非线性的，且I或或 至少有一个为非空。至少有一个为非空。现在学习的是第29页，共86页约束非线性规划约束非线性规划几个概
32、念几个概念vv积极积极(active)约束约束：设：设x0是是COP问题的一个可行解，问题的一个可行解，则它必须满足所有约束条件。对于则它必须满足所有约束条件。对于gi(x0)0，或者，或者等号成立，或者大于号成立。称等号成立的约束为等号成立，或者大于号成立。称等号成立的约束为积极约束积极约束(有效约束有效约束)，此时，此时，x0处于该约束条件形成处于该约束条件形成的可行域边界上；称大于号成立的约束为非积极的可行域边界上；称大于号成立的约束为非积极(inactive)约束约束(无效约束无效约束)，此时，此时，x0不在该约束条件不在该约束条件形成的可行域边界上。显然所有形成的可行域边界上。显然所
33、有hj(x0)约束均是积极约束均是积极约束。记约束。记J=j|gj(x0)=0 hj(x0)=0，称为积极约束指，称为积极约束指标集。标集。现在学习的是第30页，共86页约束非线性规划约束非线性规划几个概念几个概念vv可行方向可行方向可行方向可行方向。设。设。设。设x x0 0为为为为COPCOP问题的任一可行解，对某一方向问题的任一可行解，对某一方向问题的任一可行解，对某一方向问题的任一可行解，对某一方向d d来说，若来说，若来说，若来说，若0 000使得对于任意使得对于任意使得对于任意使得对于任意0,0,0 0，均有，均有，均有，均有x x0 0+d d S S，称，称，称，称d d为为为
34、为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，对某一方向，对某一方向，对某一方向，对某一方向d d来说，若来说，若来说，若来说，若0 000使得对于任意使得对于任意使
35、得对于任意使得对于任意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，则，则，则，则x x*为为为为COPCOP问题的一个问题的一个问题的一个问题的一个严格局部极小
36、点。严格局部极小点。严格局部极小点。严格局部极小点。(凸规划问题凸规划问题凸规划问题凸规划问题)设设设设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条件成立，则条件成立，则条件成立，则条件成立，则x x*为为为为COPCOP问题的全局最小点。问题的全局最小点。问题的全局最小点。问题
37、的全局最小点。现在学习的是第34页，共86页约束非线性规划约束非线性规划极小值存在条件极小值存在条件vv二阶必要条件二阶必要条件二阶必要条件二阶必要条件设设设设x x*是是是是COPCOP问题的局部极小点且满足问题的局部极小点且满足问题的局部极小点且满足问题的局部极小点且满足KKTKKT条件。若函数条件。若函数条件。若函数条件。若函数f f(x x),),g gi i(x x),),h hj j(x x)在在在在x x*处二阶可微，则必有：处二阶可微，则必有：处二阶可微，则必有：处二阶可微，则必有：d dT T xxxx2 2L(L(x x*,*,*)d d 0 0 其中，其中，其中，其中，L
38、(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二阶充分条件二阶充分条件二阶充分条件二阶充分条件设设设设x x*是是是是COPCOP问题的问题的问题的问题的KKTKKT点。点。点。点。
39、*,*分别为对应于分别为对应于分别为对应于分别为对应于g g(x x)和和和和h h(x x)的拉格朗日乘子向量，且的拉格朗日乘子向量，且的拉格朗日乘子向量，且的拉格朗日乘子向量，且函数函数函数函数f f(x x),),g gi i(x x),),h hj j(x x)在在在在x x*处二处二处二处二阶可微，若阶可微，若阶可微，若阶可微，若d dT T xxxx2 2L(L(x x*,*,*)d d0,0,则则则则x x*为为为为COPCOP问题的一个问题的一个问题的一个问题的一个严格局部极小点。严格局部极小点。严格局部极小点。严格局部极小点。现在学习的是第35页，共86页约束非线性规划约束非
40、线性规划极小值存在条件极小值存在条件vv例：例：例：例：min f(x)=xmin f(x)=x1 12 2+x+x2 22 2 S.t.x S.t.x1 1+x+x2 2 4 4 x x1 1,x,x2 2 0 0vv解：解：解：解：g g1 1(x)=x(x)=x1 1+x+x2 2-4-4 0;g0;g2 2(x)=x(x)=x1 1 0;g0;g3 3(x)=x(x)=x2 2 0 0 f(x)=2xf(x)=2x1 1,2x,2x2 2 T T,g g1 1(x)=1,1(x)=1,1T T,g g2 2(x)=1,0(x)=1,0T T,g g3 3(x)=0,1(x)=0,1T
41、T,得到：得到：得到：得到：2x2x1 1=1 1+2 22x2x2 2=1 1+3 3又又又又(x(x1 1+x+x2 2-4)-4)1 1=0=0；x x1 1 2 2=0=0；x x2 2 3 3=0=0；i i 0 0vv若若若若 1 1=0=0，则，则，则，则x x1 1=x=x2 2=0=0，与题意不符；，与题意不符；，与题意不符；，与题意不符；vv若若若若 1 100，则，则，则，则x1+x2-4=0 x1+x2-4=0，x10,x20 x10,x20。因此有。因此有。因此有。因此有 2 2=3 3=0=0，所以，所以，所以，所以x1=x2=x1=x2=1 1/2/2，得，得，得
42、，得x1=x2=2x1=x2=2，x*=2,2x*=2,2T T为该问题的唯一为该问题的唯一为该问题的唯一为该问题的唯一KKTKKT点。点。点。点。vv根据凸规划充分条件知根据凸规划充分条件知根据凸规划充分条件知根据凸规划充分条件知x*x*为全局最小点。为全局最小点。为全局最小点。为全局最小点。现在学习的是第36页，共86页约束非线性规划约束非线性规划可行方向法可行方向法vv上面例题介绍了通过求解上面例题介绍了通过求解KKT方程获得问题解的方方程获得问题解的方法，但法，但KKT方程并不总是很好求解。下面介绍几种方程并不总是很好求解。下面介绍几种约束优化的求解方法：可行方向法、序列无约束化约束优
43、化的求解方法：可行方向法、序列无约束化法和法和SQP法。法。vv可行方向法的应用条件可行方向法的应用条件：要求所有约束均为线性约：要求所有约束均为线性约束（称为线性约束的优化问题，束（称为线性约束的优化问题，LCO）。）。vv可行方向法的基本思想可行方向法的基本思想：当某个可行方向同时也是：当某个可行方向同时也是目标函数的下降方向时，沿此方向移动一定会在满目标函数的下降方向时，沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值。足可行性的情况下改进迭代点的目标函数值。现在学习的是第37页，共86页约束非线性规划约束非线性规划可行方向法可行方向法x1x2现在学习的是第38页，共86页约
44、束非线性规划约束非线性规划可行方向法可行方向法vvLCO问题：问题：Min f(x)S.t.aiTx bi,i I ajTx=bj,jvv设设x0是是LCO的一个可行解，若的一个可行解，若d是可行域在是可行域在x0点的点的可可行方向行方向，则，则d满足满足AI(x0)d 0(I(x0)=i|aiTx0=bi,i I)，A d=0。vv设设x0是是LCO的一个可行解，若的一个可行解，若d是可行域在是可行域在x0点的点的下下降方向降方向，则，则d满足满足dT f(x0)0，定义二次罚函数，定义二次罚函数Min Q(Min Q(x x,)=)=x x1 1+x x2 2+(2+(2 )-1-1(x
45、x1 1-x x2 22 2)2 2QQx1x1=1+(=1+(x x1 1-x x2 22 2)/)/=0=0QQx2x2=1-2=1-2x x2 2(x x1 1-x x2 22 2)/)/=0=0解得：解得：解得：解得：x x *=(1/4-=(1/4-,-1/2),-1/2)T T,Q,Q*=-1/4-=-1/4-/2/2当当当当 0 0时得，时得，时得，时得，x x*=(1/4,-1/2)=(1/4,-1/2)T T,f f*=-1/4=-1/4现在学习的是第43页，共86页约束非线性规划约束非线性规划序列无约束化法序列无约束化法vv对数障碍函数法对数障碍函数法：障碍函数：障碍函数：
46、障碍函数：障碍函数：其中其中其中其中 称为障碍参数，且当称为障碍参数，且当称为障碍参数，且当称为障碍参数，且当 0 0时，时，时，时，P(P(x x,)的极小值趋于的极小值趋于的极小值趋于的极小值趋于f f(x x)的极小值。的极小值。的极小值。的极小值。该方法的适用性：该方法的适用性：该方法的适用性：该方法的适用性：COPCOP问题仅包含不等式约束函数，且问题仅包含不等式约束函数，且问题仅包含不等式约束函数，且问题仅包含不等式约束函数，且可行域存在内点。即可行域存在内点。即可行域存在内点。即可行域存在内点。即S S0 0=x x|g g(x x)0)0 现在学习的是第44页，共86页约束非线
47、性规划约束非线性规划序列无约束化法序列无约束化法vv例例：minf=x/2|x 1vv解：构造对数障碍函数解：构造对数障碍函数P(x,)=x/2-ln(x-1)PPx x=1/2-=1/2-/(/(x x-1)=0-1)=0，得，得，得，得x x *=1+2=1+2 ，P*=1/2+P*=1/2+-ln2ln2 当当当当 0 0时得时得时得时得x x*=1=1，f f*=1/2*=1/2现在学习的是第45页，共86页二次规划二次规划标准型标准型vv若有约束非线性规划的目标函数是决策变量若有约束非线性规划的目标函数是决策变量x的二次的二次函数且所有约束均为线性约束，称此类非线性规划函数且所有约束
48、均为线性约束，称此类非线性规划问题为二次规划问题为二次规划(Quadratic Programming,QP)问题。问题。其标准型为：其标准型为：现在学习的是第46页，共86页二次规划二次规划标准型标准型vv其中其中Q=QT Rnn（n阶对称方阵）；以阶对称方阵）；以aiT(i I)为行为行向量的矩阵记为向量的矩阵记为AI RIn；以；以ajT(j)为行向量的矩为行向量的矩阵记为阵记为A R n；对应的向量记为；对应的向量记为bI,b。若目标函数。若目标函数的的Hesse矩阵矩阵Q是半正定是半正定(或正定或正定)的，则的，则QP问题为问题为(严格严格)凸二次规划凸二次规划(CQP)。我们仅讨论
49、凸二次规划问。我们仅讨论凸二次规划问题，因为非凸二次规划的题，因为非凸二次规划的Q存在负特征根，求解很存在负特征根，求解很困难。困难。现在学习的是第47页，共86页二次规划二次规划极小点存在条件极小点存在条件vv充要条件充要条件可行点可行点可行点可行点x x*是是是是QPQP问题的局部极小点当且仅当问题的局部极小点当且仅当问题的局部极小点当且仅当问题的局部极小点当且仅当x x*为一个为一个为一个为一个KKTKKT点且对于任意非零可行方向点且对于任意非零可行方向点且对于任意非零可行方向点且对于任意非零可行方向d d，有，有，有，有d dT TQQd d 0 0。对于凸二次规划，对于凸二次规划，对
50、于凸二次规划，对于凸二次规划，x x*为全局极小点当且仅当为全局极小点当且仅当为全局极小点当且仅当为全局极小点当且仅当x x*为局部极小为局部极小为局部极小为局部极小点，当且仅当点，当且仅当点，当且仅当点，当且仅当x x*为为为为KKTKKT点。点。点。点。二次规划的二次规划的二次规划的二次规划的KKTKKT定理形式为：定理形式为：定理形式为：定理形式为：QQx x*+c=A+c=AI IT T *+A+A T T *(A(AI Ix x*-b bI I)*=0=0vv二次规划的求解本质上就是求解上述二次规划的求解本质上就是求解上述KKT方程。方程。现在学习的是第48页，共86页约束非线性规划