优化决策理论与方法

优化决策理论与方法第一页，共八十八页，2022年，8月28日*-优化决策理论与方法确定性决策确定性决策：指未来状态是确定的（即只有一种状态）一类决策问题，每一个行动方案对应着一个确定的结果值，此时决策函数仅依赖于决策变量。特点：状态是确定的；决策问题变为优化问题。决策的已知变量：决策变量及其取值范围解决问题的主要理论方法：最优化理论与方法注：最优化理论与方法（数学规划）也可以求解不确定性决策问题、随机性决策问题第二页，共八十八页，2022年，8月28日*-优化决策理论与方法确定性决策优化决策方法的问题求解过程辨识目标C，确定优化的标准，如：利润、时间、能量等确定影响决策目标的决策变量x，形成目标函数C=f(x)明确决策变量的取值范围，形成约束函数设计求解算法，寻找决策目标在决策变量所受限制的范围内的极小化或极大化。最优化问题的一般形式为：第三页，共八十八页，2022年，8月28日*-优化决策理论与方法优化问题分类可行点与可行域：满足约束条件的x称为可行点，所有可行点的集合称为可行域，记为S；约束优化与无约束优化：当SRn时，称为约束优化；当S=Rn时，称为无约束优化；多目标优化：若f是多个目标函数构成的一个向量值函数，则称为多目标规划；线性规划与非线性规划：当f,g,h均为线性函数时称为线性规划，否则称为非线性规划。第四页，共八十八页，2022年，8月28日*-优化决策理论与方法优化问题分类整数规划：当决策变量的取值均为整数时称为整数规划；若某些变量取值为整数，而另一些变量取值为实数，则成为混合整数规划。动态规划与多层规划：若决策是分成多个阶段完成的，前后阶段之间相互影响，则称为动态规划；若决策是分成多个层次完成的，不同层次之间相互影响，则称为多层规划。第五页，共八十八页，2022年，8月28日*-优化决策理论与方法优化决策理论与方法1、线性规划2、非线性规划（约束和非约束）3、多目标规划4、组合优化与整数规划第六页，共八十八页，2022年，8月28日*-优化决策理论与方法线性规划—管理实例(食谱问题)假设市场上有n种不同的食物，第j种食物的单价为cj。人体正常活动过程中需要m种基本的营养成分，且每人每天至少需要摄入第i种营养成分bi个单位。已知第j种食物中包含第i种营养成分的量为aij个单位。问在满足人体基本营养需求的前提下什么样的配食方案最经济？设食谱中包含第j种食物的量为xj，则：第七页，共八十八页，2022年，8月28日*-优化决策理论与方法线性规划—标准型第八页，共八十八页，2022年，8月28日*-优化决策理论与方法线性规划—单纯形算法解空间分析可行域分析：n维空间；第一象限；m个超平面。最优解分析：在端点(或称为极点。极点向量中，至少有n-m个0分量)处取极值。单纯形算法的基本思想从某个极点开始获得一个可行解；判断该可行解是不是目标解。若是，算法结束；否则寻找下一个极点（确定入基变量和出基变量），直至找到目标解。第九页，共八十八页，2022年，8月28日*-优化决策理论与方法线性规划—内点算法1972年，V.Klee和G.L.Minty指出Dantzig的单纯形算法的迭代次数为O(2n)，是一个指数时间算法，不是优良算法。那么是否存在求解线性规划问题的多项式时间算法？1984年，N.Karmarkar提出了一种投影尺度算法，其计算效果能够同单纯形法相比较，掀起了线性规划内点算法的热潮。第十页，共八十八页，2022年，8月28日*-优化决策理论与方法线性规划—内点算法内点算法的思想已知线性规划问题的可行域是一个多面体，最优点在多面体的某个极点取到。在给定初始可行解后，沿着什么样的路径到达最优解呢？单纯形法是从某个基可行解开始，沿着多面体的边移动最终找到最优解。内点算法的思想是从可行域内的任意一点(任一可行解)出发，穿越可行域的内部达到最优解。N.Karmarkar的投影尺度算法就是一种典型的内点算法。第十一页，共八十八页，2022年，8月28日*-优化决策理论与方法线性规划—内点算法可行域内点初始基可行解基可行解目标函数目标函数最速下降方向第十二页，共八十八页，2022年，8月28日*-优化决策理论与方法线性规划—内点算法投影尺度算法如何穿过可行域的内部快速达到最优解呢？Karmarkar发现：(1)如果一个内点位于可行域(多胞形、多面体)的中心，那么目标函数的最速下降方向是比较好的方向；(2)存在一个适当的变换，能够将可行域中给定的内点置于变换后的可行域的中心。基于这两点，Karmarkar构造了一种称为投影尺度算法的内点算法。第十三页，共八十八页，2022年，8月28日*-优化决策理论与方法线性规划—内点算法X空间内点目标函数目标函数最速下降方向Y1空间中心点投影尺度变换1目标函数最速下降方向Y2空间中心点投影尺度变换2第十四页，共八十八页，2022年，8月28日*-优化决策理论与方法线性规划—Matlab函数应用OptimizationToolBoxMinfTxS.t.A·x≤bAeq·x=beqlb≤x≤ub其中：f,x,b,beq,lb和ub均为向量；A和Aeq为矩阵。[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)第十五页，共八十八页，2022年，8月28日*-优化决策理论与方法线性规划—Matlab函数应用例：maxz=x1+2x2S.t.x1+x2≤402x1+x2≤60x1≥0;x2≥0解：将max变为min，min–z=-x1-2x2则：f=[-1;-2];b=[40;60];lb=zeros(2,1);A=[11;21][x,fval]=linprog(f,A,b,[],[],lb)x=[0;40],fval=-80x1x2x1+x2=402x1+x2=60Z=x1+2x2第十六页，共八十八页，2022年，8月28日*-优化决策理论与方法优化决策理论与方法1、线性规划2、非线性规划（约束和非约束）3、多目标规划4、组合优化与整数规划第十七页，共八十八页，2022年，8月28日*-优化决策理论与方法无约束非线性规划—标准型Minf(x);xRn其中f：Rn→R是一个非线性连续函数。对于任意点x*Rn,它是函数f的最小点(或局部极小点)吗？例如：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)第十八页，共八十八页，2022年，8月28日*-优化决策理论与方法无约束非线性规划—极小值存在条件必要条件。设x*是f(x)的局部极小点，则当f(x)在x*点可微时，梯度f(x*)=0；当f(x)在x*点二阶可微时，Hesse矩阵▽2f(x*)是半正定的，即dRn，有dT2f(x*)d0。充分条件。设f(x)在x*点二阶可微，若梯度f(x*)=0且Hesse矩阵2f(x*)是正定的，则x*是f(x)的一个严格局部极小点。充要条件。设f(x)是可微凸函数，则x*是f(x)的全局最小点，当且仅当梯度f(x*)=0。第十九页，共八十八页，2022年，8月28日*-优化决策理论与方法无约束非线性规划—复习梯度矩阵Hesse矩阵Taylor展开第二十页，共八十八页，2022年，8月28日*-优化决策理论与方法无约束非线性规划—牛顿法基本思想：在一个点附近，用目标函数f(x)的二阶Taylor多项式近似f(x)，并用该Taylor多项式的最小点近似f(x)的最小点。如果近似误差比较大，那么可在近似最小点附近重新构造f(x)的二阶Taylor多项式(迭代)，据此寻找新的近似最小点，重复以上过程直到求得满足一定精度要求的迭代点。第二十一页，共八十八页，2022年，8月28日*-优化决策理论与方法无约束非线性规划—牛顿法设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)p由于k(p)的最小点满足g(xk)+G(xk)p=0，得p=x-xk=-G-1(xk)g(xk)因此，可近似得到迭代关系：xk+1=xk-G-1(xk)g(xk)第二十二页，共八十八页，2022年，8月28日*-优化决策理论与方法无约束非线性规划—牛顿法牛顿迭代法步骤初始化：给定一个初始点x0以及参数e>0；记k=0。收敛性检验：计算g(xk)，若||g(xk)||≤e，则算法终止；否则计算G(xk)。迭代改进：计算新的迭代点xk+1，即xk+1=xk-G-1(xk)g(xk)。k+1→k。返回收敛性检验。第二十三页，共八十八页，2022年，8月28日*-优化决策理论与方法无约束非线性规划—准牛顿法牛顿法算法的优点是收敛速度快(利用了Hesse矩阵)。但使用Hesse矩阵的不足之处是计算量大，Hesse矩阵可能非正定等，准牛顿法(Quasi-Newtonmethod)是对牛顿法的改进，目前被公认为是比较有效的无约束优化方法。基本思想：在迭代过程中只利用目标函数f(x)和梯度g(x)的信息，构造Hesse矩阵的近似矩阵，由此获得一个搜索方向，生产新的迭代点。具体内容请参考相关书籍。第二十四页，共八十八页，2022年，8月28日*-优化决策理论与方法无约束非线性规划—Matlab函数应用OptimizationToolBoxMinf(x)Matlab提供了两个求解无约束非线性规划的函数[x,fval]=fminunc(fun,x0)[x,fval]=fminsearch(fun,x0)用法相似，算法内部的搜索策略不同。fun为f(x)的函数形式，x0为初始解向量。第二十五页，共八十八页，2022年，8月28日*-优化决策理论与方法无约束非线性规划—Matlab函数应用用法创建一个matlab文件，如myfun.mfunctionf=myfun(x)f=f(x);然后调用fminunc或fminsearch并指定初始搜索点。x0=[x1,x2,…,xn][x,fval]=fminunc(@myfun,x0)或[x,fval]=fminsearch(@myfun,x0)第二十六页，共八十八页，2022年，8月28日*-优化决策理论与方法无约束非线性规划—Matlab函数应用例：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)解：创建一个matlab文件，如myfun.mfunctionf=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];%Startingguessoptions=optimset('LargeScale','off');[x,fval]=fminunc(@myfun,x0,options);或者[x,fval]=

fminsearch(@myfun,x0,options);第二十七页，共八十八页，2022年，8月28日*-优化决策理论与方法无约束非线性规划—Matlab函数应用fminunc结果：x=[0.5000-1.0000]fval=1.0983e-015iterations:8algorithm:'medium-scale:Quasi-Newtonlinesearch‘

fminsearch结果：x=[0.5000-1.0000]fval=5.1425e-010iterations:46algorithm:'Nelder-Meadsimplexdirectsearch'第二十八页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—标准型其中f(x)是目标函数，gi(x)和hj(x)为约束函数(约束条件)。S={x|gi(x)0hj(x)=0}为可行域。有约束非线性规划问题(COP)是指f(x),gi(x),hj(x)至少有一个是非线性的，且I或至少有一个为非空。第二十九页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—几个概念积极(active)约束：设x0是COP问题的一个可行解，则它必须满足所有约束条件。对于gi(x0)0，或者等号成立，或者大于号成立。称等号成立的约束为积极约束(有效约束)，此时，x0处于该约束条件形成的可行域边界上；称大于号成立的约束为非积极(inactive)约束(无效约束)，此时，x0不在该约束条件形成的可行域边界上。显然所有hj(x0)约束均是积极约束。记J={j|gj(x0)=0hj(x0)=0}，称为积极约束指标集。第三十页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—几个概念可行方向。设x0为COP问题的任一可行解，对某一方向d来说，若0>0使得对于任意[0,0]，均有x0+dS，称d为x0的一个可行方向。显然若d满足dTgi(x)0，dThj(x)=0，则d一定是可行方向。（可用一阶Taylor公式分析）。下降方向。设x0S，对某一方向d来说，若0>0使得对于任意[0,0]，均有f(x0+d)<f(x0)，则称d为x0点的一个下降方向。由f(x0+d)=f(x0)+(f(x0))Td+o()可知：若d满足dTf(x0)<0，有f(x0+d)<f(x0)，则d一定是下降方向。可行下降方向。若x0的某一方向d既是可行方向又是下降方向则称其为可行下降方向。这个方向就是我们从x0出发寻求最优解的搜索方向！第三十一页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—几个概念例：minf(x)=x1+x2S.t.g(x)=1-x12-x220图描述了该问题的相关概念。x1x2第三十二页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—极小值存在条件一阶必要条件几何特征：若x*是COP问题的局部极小点且函数f(x),gi(x),hj(x)在x*处可微，则dTf(x*)0。d为x*的任意可行方向。f(x*+d)=f(x*)+(f(x*))Td+o()代数特征(KKT定理)：若x*是COP问题的局部极小点且函数f(x),gi(x),hj(x)在x*处可微，则存在实数i0(iI),jR(j)，使得：f(x*)=igi(x*)i+jhj(x*)j；gi(x*)i=0；i0，iI若x*满足KKT条件，则称x*为COP问题的一个KKT点，i,j称为x*处的拉格朗日乘子。第三十三页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—极小值存在条件一阶充分条件设x*S，若函数f(x),gi(x),hj(x)在x*处可微，且对于x*的任意可行方向d，有dTf(x*)>0，则x*为COP问题的一个严格局部极小点。(凸规划问题)设f(x)为凸函数，gi(x)为凹函数，hj(x)为线性函数。对于x*S，若函数f(x),gi(x)在x*处可微，且KKT条件成立，则x*为COP问题的全局最小点。第三十四页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—极小值存在条件二阶必要条件设x*是COP问题的局部极小点且满足KKT条件。若函数f(x),gi(x),hj(x)在x*处二阶可微，则必有：dTxx2L(x*,*,*)d0

其中，L(x,,)=f(x)-g(x)T-h(x)T,g(x),h(x)分别为由gi(x)和hj(x)构成的向量值函数，,分别为对应于g(x)和h(x)的拉格朗日乘子向量。二阶充分条件设x*是COP问题的KKT点。*,*分别为对应于g(x)和h(x)的拉格朗日乘子向量，且函数f(x),gi(x),hj(x)在x*处二阶可微，若dTxx2L(x*,*,*)d>0,则x*为COP问题的一个严格局部极小点。第三十五页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—极小值存在条件例：minf(x)=x12+x22S.t.x1+x24x1,x20解：g1(x)=x1+x2-40;g2(x)=x10;g3(x)=x20f(x)=[2x1,2x2]T,g1(x)=[1,1]T,g2(x)=[1,0]T,g3(x)=[0,1]T,得到：2x1=1+22x2=1+3又(x1+x2-4)1=0；x12=0；x23=0；i0若1=0，则x1=x2=0，与题意不符；若1>0，则x1+x2-4=0，x1>0,x2>0。因此有2=3=0，所以x1=x2=1/2，得x1=x2=2，x*=[2,2]T为该问题的唯一KKT点。根据凸规划充分条件知x*为全局最小点。第三十六页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—可行方向法上面例题介绍了通过求解KKT方程获得问题解的方法，但KKT方程并不总是很好求解。下面介绍几种约束优化的求解方法：可行方向法、序列无约束化法和SQP法。可行方向法的应用条件：要求所有约束均为线性约束（称为线性约束的优化问题，LCO）。可行方向法的基本思想：当某个可行方向同时也是目标函数的下降方向时，沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值。第三十七页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—可行方向法x1x2第三十八页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—可行方向法LCO问题：

Minf(x)S.t.aiTxbi,iI

ajTx=bj,j设x0是LCO的一个可行解，若d是可行域在x0点的可行方向，则d满足AI(x0)d0(I(x0)={i|aiTx0=bi,iI})，Ad=0。设x0是LCO的一个可行解，若d是可行域在x0点的下降方向，则d满足dTf(x0)<0。第三十九页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—可行方向法Zoutendijk可行方向法：其核心思想是通过求解下列线性规划问题，在可行方向的某个范围内获得目标函数的最速下降方向。MindTf(x0)S.t.AI(x0)d0,I(x0)={i|aiTx0=bi,iI}Ad=0||d||∞1可以证明：当x0取得KKT点时当且仅当dTf(x0)的最优值为零。第四十页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—序列无约束化法求解约束优化的一类重要方法是用一个无约束优化问题的序列逼近约束优化问题，通过无约束优化问题的最优解序列逼近约束优化问题的最优解。基本思想：将约束条件通过某种转换与目标函数合并形成一个无约束优化问题。这种转换隐含着某种惩罚，即x偏离约束条件越远，受到的惩罚越大。因此也将此类方法称为罚函数法，所形成的无约束优化函数成为罚函数。第四十一页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—序列无约束化法二次罚函数法：罚函数：其中(gi)-=max{0,-gi}，称为罚参数，且当→0时，Q(x,)的极小值趋于f(x)的极小值。第四十二页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—序列无约束化法例：minf=x1+x2S.t.x1-x22=0解：对于>0，定义二次罚函数MinQ(x,)=x1+x2+(2)-1(x1-x22)2Q’x1=1+(x1-x22)/=0Q’x2=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第四十三页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—序列无约束化法对数障碍函数法：障碍函数：其中称为障碍参数，且当→0时，P(x,)的极小值趋于f(x)的极小值。该方法的适用性：COP问题仅包含不等式约束函数，且可行域存在内点。即S0={x|g(x)>0}≠第四十四页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—序列无约束化法例：min{f=x/2|x1}解：构造对数障碍函数P(x,)=x/2-ln(x-1)P’x=1/2-/(x-1)=0，得x*=1+2，P*=1/2+-ln2当→0时得x*=1，f*=1/2第四十五页，共八十八页，2022年，8月28日*-优化决策理论与方法二次规划—标准型若有约束非线性规划的目标函数是决策变量x的二次函数且所有约束均为线性约束，称此类非线性规划问题为二次规划(QuadraticProgramming,QP)问题。其标准型为：第四十六页，共八十八页，2022年，8月28日*-优化决策理论与方法二次规划—标准型其中Q=QTRn×n（n阶对称方阵）；以aiT(iI)为行向量的矩阵记为AIRI×n；以ajT(j)为行向量的矩阵记为AR×n；对应的向量记为bI,b。若目标函数的Hesse矩阵Q是半正定(或正定)的，则QP问题为(严格)凸二次规划(CQP)。我们仅讨论凸二次规划问题，因为非凸二次规划的Q存在负特征根，求解很困难。第四十七页，共八十八页，2022年，8月28日*-优化决策理论与方法二次规划—极小点存在条件充要条件可行点x*是QP问题的局部极小点当且仅当x*为一个KKT点且对于任意非零可行方向d，有dTQd0。对于凸二次规划，x*为全局极小点当且仅当x*为局部极小点，当且仅当x*为KKT点。二次规划的KKT定理形式为：Qx*+c=AIT*+AT*(AIx*-bI)*=0二次规划的求解本质上就是求解上述KKT方程。第四十八页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—SQP法对于非线性约束优化(COP)问题，若x*是COP问题的一个局部最优解，则它对应一个纯等式约束优化问题第四十九页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—SQP法因此如果事先知道积极约束指标集，那么带有不等式约束优化问题就可以转化为纯等式约束优化问题，并可用准牛顿法求解，这就是逐次二次规划(SequentialQuadraticProgramming，SQP)法。基本思想：在迭代点处构造一个二次规划子问题，近似原来的约束优化问题；然后通过求解该二次规划子问题获得约束优化问题的一个改进迭代点；不断重复此过程，直到求出满足一定要求的迭代点。第五十页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—SQP法对于等式约束优化问题Minf(x)S.t.h(x)=0拉格朗日函数记为L(x,)=f(x)-Th(x)则L(x,)=(f(x)-h(x),-h(x))T=0，显然问题的最优解(x*,*)满足此式。设(xk,k)是第k次迭代结果，根据牛顿法，有：第五十一页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—SQP法上述迭代过程等价于如下的二次规划的迭代。设给定迭代点(xk,k)，则第五十二页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—Matlab函数应用OptimizationToolBoxMinf(x)s.t.c(x)0ceq(x)=0A·xbAeq·x=beqlbxub[x,fval]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)fun定义目标函数,x0定义初始可行解，nonlcon定义c(x)和ceq(x)。第五十三页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—Matlab函数应用用法创建一个matlab文件，如myfun.mfunctionf=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)第五十四页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—Matlab函数应用例：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)S.t.x1x2-x1-x2-1.5x1x2-10解：创建一个matlab文件，如myfun.mfunctionf=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=[];第五十五页，共八十八页，2022年，8月28日*-优化决策理论与方法约束非线性规划—Matlab函数应用调用有约束非线性规划函数x0=[-1,1];%Startingguessoptions=optimset('LargeScale','off');[x,fval]=fmincon(@objfun,x0,[],[],[],[],[],[],@confun,options)运行结果：x=[-9.54741.0474]fval=0.0236iterations:8algorithm:'medium-scale:SQP,Quasi-Newton,line-search'第五十六页，共八十八页，2022年，8月28日*-优化决策理论与方法二次规划—Matlab函数应用OptimizationToolBoxMin0.5xTHx+fTxs.t.A·xbAeq·x=beqlbxub[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)x0定义初始可行解(可选)第五十七页，共八十八页，2022年，8月28日*-优化决策理论与方法二次规划—Matlab函数应用用法首先要将目标函数转换成二次规划标准型，从而得到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)第五十八页，共八十八页，2022年，8月28日*-优化决策理论与方法二次规划—Matlab函数应用例：minf(x)=1/2x12+x22-x1x2-2x1-6x2)S.t.x1+x22

-x1+2x22

2x1+x23x1,x20解：改写f(x)=1/2(x12+2x22-x1x2-x1x2)-2x1-6x2得：H=[1-1;-12],f=[-2;-6],x=[x1;x2];表示其它矩阵或向量A=[11;-12;21];b=[2;2;3];lb=[0;0];Aeq=[];beq=[];ub=[]。不指派初始解。第五十九页，共八十八页，2022年，8月28日*-优化决策理论与方法二次规划—Matlab函数应用调用二次规划函数[x,fval]=quadprog(H,f,A,b,[],[],lb)运行结果：x=[0.6667;1.3333]fval=-8.2222iterations:3algorithm:‘medium-scale:active-set(积极约束集方法)'第六十页，共八十八页，2022年，8月28日*-优化决策理论与方法优化决策理论与方法1、线性规划2、非线性规划（约束和非约束）3、多目标规划4、组合优化与整数规划第六十一页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—管理实例(物资调度)假设物资调度部门计划将某种物资从若干个存储仓库调运到若干个销售网点销售。考虑到物资的时效性和销售效益，调度部门希望物资在运输过程中尽可能快地到达目的地；同时，考虑到运输成本，调度部门还希望物资的总运输费用最小。试建立描述物资调运过程的数学模型。解：设共有m个仓库，第i个仓库的物资库存量为ai吨；有n个销售网点，第j个销售网点的销售量为bj吨。第i个仓库到第j个销售网点的距离为dij，单位物资的运费为cij。设从第i个仓库运到第j个销售网点的物资量为xij。第六十二页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—管理实例决策目标：运输速度最快，可用吨公里数（可观测变量）最小描述。总吨公里数为ijdijxij；运输费用最小。总运输费用为ijcijxij；约束条件每个仓库的运出量不超过仓库的库存量：jxijai；运到每个销售网点的量与其销售能力相匹配：ixij=bj；每个仓库的运出量非负：xij0。第六十三页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—管理实例最后得到模型：模型包含2个目标；mn个决策变量；mn+m+n个约束。第六十四页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—标准型多目标规划(multi-ObjectiveProgramming,MOP)就是指在决策变量满足给定约束的条件下研究多个可数值化的目标函数同时极小化(或极大化)的问题。其一般形式如下：Minf(x)=(f1(x),f2(x),…,fp(x))T，S.t.gi(x)0;iIhj(x)=0;j。第六十五页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—Pareto最优解设x*是可行域S上的一个点，对于xS，均有：fi(x*)fi(x)(i=1,…,p)，称x*为MOP问题的绝对最优解；若不存在xS，使得fi(x)fi(x*)(或fi(x)<fi(x*))(i=1,…,p)，则称x*为MOP问题的有效解(或弱有效解)。有效解通常也称为Pareto最优解。Sx1x2f(S)f(S)f2f2f1f1绝对最优解有效解弱有效解第六十六页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—Pareto最优解存在条件(必要条件)假设向量值函数f=[f1(x),…,fp(x)]T,g=[g1(x),…,g|I|(x)]T,h=[h1(x),…,h||(x)]T在x*S处可微，若x*是MOP问题的有效解或弱有效解，则存在向量R+p，R+|I|，R+||，使得(,,)≠0，且f(x*)=g(x*)+h(x*)Tg(x*)=0。第六十七页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—求解方法直接求解多目标规划问题的有效解集是NP-难问题。下面介绍多目标规划问题的间接解法，基本思路都是将多目标规划问题转化为一个或多个单目标优化问题。基于一个单目标问题的方法：将原来的多目标规划问题转化成一个单目标优化问题，然后利用非线性优化算法求解该单目标问题，所得解作为MOP问题的最优解。关键问题在于：保证所构造的单目标问题的最优解是MOP问题的有效解或弱有效解。第六十八页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—求解方法线性加权和法：MinTf(x)=kkfk(x)，S.t.gi(x)0;iIhj(x)=0;j权重设置要求：kk=1,k0(k=1,2,…,p)。主要目标法：Minf(x)=f1(x)，(不妨设f1(x)为主要目标)S.t.gi(x)0;iIhj(x)=0;jfk(x)uk,k=2,…,puk为专家经验值。第六十九页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—求解方法极小化极大法：在目标函数f(x)的p个分量中，极小化f(x)的最大分量，即minxSmax1jpfj(x)理想点法：分别求出f(x)中每个分量fj(x)的极小点fj0，得到理想点f0=(f10,…,fp0)T；然后求解单目标优化问题：minxS||f(x)-f0||。为范数的阶，可取1，2，∞。第七十页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—求解方法基于多个单目标问题的方法：将原来的多目标规划问题转化成具有一定次序的多个单目标优化问题，然后依次求解这些单目标优化问题，并把最后一个单目标优化问题的解作为MOP问题的最优解。关键问题在于：保证最后一个单目标优化问题的最优解是MOP问题的有效解或弱有效解。分层排序法：将目标函数按重要度依次排序，然后在前一个目标函数的最优解集中寻找下一个目标的最优解集，并把最后一个目标的最优解作为MOP问题的最优解。第七十一页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—求解方法minf1(x)，xS（不妨设f1(x)为第一层目标），得到最优解集S1;第j层：minfj(x),xSj-1，j=2,…,p最后将Sp中的点作为多目标问题的最优解。第七十二页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—Matlab函数应用OptimizationToolBoxMinmax{fi(x)}s.t.c(x)0ceq(x)=0A·xbAeq·x=beqlbxub[x,fval]=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)Fun定义目标函数；x0定义初始可行解；nonlcon定义c(x)和ceq(x)。第七十三页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—Matlab函数应用用法创建一个matlab文件，如myfun.mfunctionf=myfun(x)f(1)=f1(x);f(2)=f2(x);…;f(p)=fp(x)创建另一个matlab文件，如confun.mfunction[c,ceq]=confun(x)c=c(x);ceq=ceq(x);调用fminimax并指定初始搜索点以及其他向量、矩阵。x0=[x1,x2,…,xn];A;b;Aeq;beq;lb;ub;[x,fval]=fminimax(@myfun,x0,A,b,Aeq,beq,lb,ub,@confun)第七十四页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—Matlab函数应用OptimizationToolBoxMinx,

s.t.F(x)-weight·goalc(x)0ceq(x)=0A·xbAeq·x=beqlbxub[x,fval]=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)Fun定义目标函数；goal为理想点；x0定义初始可行解；nonlcon定义c(x)和ceq(x)。weight为各目标的权重向量。第七十五页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—Matlab函数应用用法创建一个matlab文件，如myfun.mfunctionf=myfun(x)f(1)=f1(x);f(2)=f2(x);…;f(p)=fp(x)创建另一个matlab文件，如confun.mfunction[c,ceq]=confun(x)c=c(x);ceq=ceq(x);调用fgoalattain并设定理想点、权重向量，指定初始搜索点以及其他向量、矩阵。x0=[x1,x2,…,xn];A;b;Aeq;beq;lb;ub;goal;weight[x,fval]=fgoalattain(@myfun,x0,goal,weight,A,b,Aeq,beq,lb,ub,@confun)第七十六页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—Matlab函数应用例：min{f1,f2,f3,f4,f5}f(1)=2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304;f(2)=-x(1)^2-3*x(2)^2;f(3)=x(1)+3*x(2)-18;f(4)=-x(1)-x(2);f(5)=x(1)+x(2)-8;无约束。第七十七页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—Matlab函数应用解(1)：用fminimax求解。定义myfun.m指定初始搜索点：x0=[0.1;0.1]调用[x,fval]=fminimax(@myfun,x0)结果：x=[4.00004.0000]fval=[0.0000-64.0000-2.0000-8.0000-0.0000]iterations:7algorithm:'minimaxSQP,Quasi-Newton,line_search‘第七十八页，共八十八页，2022年，8月28日*-优化决策理论与方法多目标规划—Matlab函数应用解(2)：用fgoalattain求解。定义myfun.m指定初始搜索点：x0=[0.1;0.1]指定理想点：goal=[1-60-5-10-1]指定权重：weight=abs(goal)调用[x,fval]=fgoalattain(@myfun,x0,goal,weight)结果：x=[3.97983.9596]fval=[1.9395-62.8754-2.1412-7.9395-0.0605]iterations:7algorithm:'goalattainmentSQP,Quasi-Newton,line_search'第七十九页，共八十八页，2022年，8月28日*-优化决策理论与方法优化决策理论与方法1、线性规划2、非线性规划（约束和非约束）3、多目标规划4、组合优化与整数规划第八十页，共八十八页，2022年，8月28日*-优化决策理论与方法组合优化