一非线规划问题的几种求解方法1罚函数法外点法市公开课一等奖百校联赛特等奖课件.pptx

第1页一、非线性规划问题几个求解方法一、非线性规划问题几个求解方法1.罚函数法（外点法）罚函数法（外点法）基本思想：基本思想：利用目标函数和约束函数结构辅助函数：利用目标函数和约束函数结构辅助函数：第2页要求结构函数要求结构函数含有这么性质：当点含有这么性质：当点x位于可行域以外时，位于可行域以外时，取值很大，而离取值很大，而离可行域越远则越大；当点在可行域内时，函可行域越远则越大；当点在可行域内时，函数数所以能够将前面有约束规划问题转换为以下所以能够将前面有约束规划问题转换为以下无约束规划模型：无约束规划模型：其中称为其中称为罚项，罚项，称为罚因子，称为罚因子，称为罚函数。称为罚函数。第3页定义普通以下：定义普通以下：函数函数普通定义以下：普通定义以下：第4页算法步骤算法步骤怎样怎样将此算法模块化将此算法模块化:第5页求解非线性规划模型例子求解非线性规划模型例子罚项函数：罚项函数：无约束规划目标函数：无约束规划目标函数：第6页global lamada%主程序主程序main2.m,罚函数方法罚函数方法x0=1 1;lamada=2;c=10;e=1e-5;k=1;while lamada*fun2p(x0)=ex0=fminsearch(fun2min,x0);lamada=c*lamada;k=k+1;end disp(最优解最优解),disp(x0)disp(k=),disp(k)程序程序1：主程序主程序main2.m第7页程序程序2：计算：计算函数函数fun2p.mfunction r=fun2p(x)%罚项函数罚项函数r=(x(1)-1)3-x(2)*x(2)2;第8页程序程序3：辅助函数程序：辅助函数程序fun2min.mfunction r=fun2min(x)%辅助函数辅助函数global lamadar=x(1)2+x(2)2+lamada*fun2p(x);第9页运行输出：运行输出：最优解最优解1.00012815099165-0.00000145071779k=33第10页练习题：练习题：1、用外点法求解以下模型、用外点法求解以下模型2、将例子程序改写为一个较为、将例子程序改写为一个较为通用罚函数法通用罚函数法程序程序。（考虑要提供哪些参数）。（考虑要提供哪些参数）第11页2.内点法（障碍函数法）内点法（障碍函数法）仅适合于仅适合于不等式约束最优化问题不等式约束最优化问题其中其中都是连续函数，将模型定义域记为都是连续函数，将模型定义域记为第12页结构辅助函数结构辅助函数为了保持迭代点含于可行域内部，我们定义为了保持迭代点含于可行域内部，我们定义障碍函数障碍函数第13页3.问题转化为一个无约束规划问题转化为一个无约束规划因为因为很小，则函数很小，则函数取值靠近于取值靠近于f(x)，所以原问题能够归结为以下规划问题近所以原问题能够归结为以下规划问题近似解：似解：第14页第15页练习题：练习题：请用内点法算法求解以下问题：请用内点法算法求解以下问题：第16页小结小结q讲解了两个讲解了两个求解有约束非线性最小化规划求解有约束非线性最小化规划特点：特点：q易于实现，方法简单；易于实现，方法简单；q没有用到目标函数导数没有用到目标函数导数q问题转化技巧（近似为一个无约束规划）问题转化技巧（近似为一个无约束规划）第17页4、其它求解算法、其它求解算法（1）间接法）间接法（2）直接法）直接法q直接搜索法直接搜索法q以梯度法为基础以梯度法为基础间接法间接法q无约束规划无约束规划Matlab求解函数求解函数q数学建模案例分析（数学建模案例分析（截断切割截断切割，飞机排队飞机排队）第18页（1）间接法）间接法在非线性最优化问题当中，假如目标函在非线性最优化问题当中，假如目标函数能以解析函数表示，可行域由不等式约束数能以解析函数表示，可行域由不等式约束确定，则能够利用目标函数和可行域已知性确定，则能够利用目标函数和可行域已知性质，在理论上推导出目标函数为最优值必要质，在理论上推导出目标函数为最优值必要条件，这种方法就称为条件，这种方法就称为间接法间接法（也称为（也称为解析解析法法）。普通要用到目标函数导数。普通要用到目标函数导数。第19页（2）直接法）直接法直接法直接法是一个数值方法是一个数值方法这种方法基本思想是这种方法基本思想是迭代迭代，经过迭代产生一，经过迭代产生一个点序列个点序列X(k)，使之逐步靠近最优点。使之逐步靠近最优点。只用到只用到目标函数目标函数。如黄金分割法、如黄金分割法、FibonacciFibonacci、随机搜索法。随机搜索法。第20页（3）迭代法普通步骤）迭代法普通步骤注意：注意：数值求解最优化问题计算效率取决于数值求解最优化问题计算效率取决于确定搜索方向确定搜索方向P(k)和步长和步长效率。效率。第21页最速下降法（最速下降法（steepestdescentmethod）由法国数学家由法国数学家Cauchy于于1847年首先提出。在年首先提出。在每次迭代中，沿最速下降方向（每次迭代中，沿最速下降方向（负梯度方向负梯度方向）进行搜索，每步沿负梯度方向取最优步长，进行搜索，每步沿负梯度方向取最优步长，所以这种方法称为所以这种方法称为最优梯度法最优梯度法。特点：特点：方方法法简简单单，只只以以一一阶阶梯梯度度信信息息确确定定下下一一步步搜搜索索方方向向，收敛速度慢；收敛速度慢；越是靠近极值点，收敛越慢；越是靠近极值点，收敛越慢；它是其它许多无约束、有约束最优化方法基础。它是其它许多无约束、有约束最优化方法基础。该法普通用于最优化开始几步搜索。该法普通用于最优化开始几步搜索。第22页以梯度法为基础最优化方法以梯度法为基础最优化方法求求f(x)在在En中极小点中极小点思想：思想：q方向导数是反应函数值沿某一方向改变率问题方向导数是反应函数值沿某一方向改变率问题q方向导数沿梯度方向取得最大值方向导数沿梯度方向取得最大值基础：方向导数、梯度基础：方向导数、梯度第23页q经过一系列一维搜索来实现。经过一系列一维搜索来实现。q本方法关键问题是选择搜索方向。本方法关键问题是选择搜索方向。q搜索方向不一样则形成不一样最优化方法。搜索方向不一样则形成不一样最优化方法。第24页最速下降法最速下降法算法：算法：第25页算法说明算法说明可经过可经过一维无约束搜索方法一维无约束搜索方法求解求解第26页例子：用最速下降法解以下问题例子：用最速下降法解以下问题分析：分析：1、编写一个梯度函数程序、编写一个梯度函数程序fun1gra.m2、求求(能够调用函数能够调用函数fminsearch)函函数数fungetlamada.m3、最速下降法主程序最速下降法主程序main1.m初始条件初始条件第27页第一步：计算梯度程序第一步：计算梯度程序fun1gra.mfunction r=fun1gra(x)%最速下降法求解示例最速下降法求解示例%函数函数f(x)=2*x12+x22梯度计算梯度计算%r(1)=4*x(1);r(2)=2*x(2);第28页第二步：求第二步：求最优目标函数最优目标函数function r=fungetlamada(lamada)%关于关于lamada一元函数，求最优步长一元函数，求最优步长global x0d=fun1gra(x0);r=2*(x0(1)-lamada*d(1)2+(x0(2)-lamada*d(2)2;%注意注意负负号表示是号表示是负负梯度梯度第29页第三步：主程序第三步：主程序main1.m%最速下降方法实现一个非线性最优化问题最速下降方法实现一个非线性最优化问题%min f(x)=2*x12+x22global x0 x0=1 1;yefi=0.0001;k=1;d=-fun1gra(x0);lamada=1;第30页主程序主程序main1.m（续）续）while sqrt(sum(d.2)=yefilamada=fminsearch(fungetlamada,lamada);%求最优步长求最优步长lamada x0=x0-lamada*fun1gra(x0);%计算计算x0 d=fun1gra(x0);%计算梯度计算梯度 k=k+1;%迭代次数迭代次数enddisp(x=),disp(x0),disp(k=),disp(k),disp(funobj=),disp(2*x0(1)2+x0(2)2)第31页三、三、Matlab求解有约束非线性规划求解有约束非线性规划第32页1.用用fmincon函数求解形以下面有约束非函数求解形以下面有约束非线性规划模型线性规划模型普通形式：普通形式：第33页用用Matlab求解有约束非线性最小化问题求解有约束非线性最小化问题求求解解非非线线性性规规划划问问题题Matlab函函数数为为：fmincon1.约束中能够有等式约束约束中能够有等式约束2.能够含线性、非线性约束均可能够含线性、非线性约束均可第34页输入输入参数语法：参数语法：x=fmincon(fun,x0,A,b)x=fmincon(fun,x0,A,b,Aeq,beq)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,.)第35页输入参数几点说明输入参数几点说明q模型中假如没有模型中假如没有A,b,Aeq,beq,lb,ub限制，则以空矩阵限制，则以空矩阵作为作为q参数传入；参数传入；qnonlcon：假如包含非线性等式或不等式约束，则将这些函数假如包含非线性等式或不等式约束，则将这些函数编写为一个编写为一个Matlab函数，函数，nonlcon就是定义这些函数程序文件名；就是定义这些函数程序文件名；不等式约束不等式约束c(x)=0c(x)2nargout 2%nonlcon%nonlcon 假如四个输出参数假如四个输出参数 GC=.GC=.%不等式约束梯度不等式约束梯度 GCeq=.GCeq=.%等式约束梯度等式约束梯度end end 第40页输出输出参数语法：参数语法：x,fval=fmincon(.)x,fval,exitflag=fmincon(.)x,fval,exitflag,output=fmincon(.)x,fval,exitflag,output,lambda=fmincon(.)x,fval,exitflag,output,lambda,grad=fmincon(.)x,fval,exitflag,output,lambda,grad,hessian=fmincon(.)利用步骤：利用步骤：将自己模型转化为上面形式将自己模型转化为上面形式写出对应参数写出对应参数调用函数调用函数第41页fmincon应用求解示例：应用求解示例：请问：请问：1、结合结合fmincon函数，需要提供哪些参数函数，需要提供哪些参数第42页第一步：编写一个第一步：编写一个M文件返回目标函数文件返回目标函数f在点在点x处值函数程序处值函数程序functionf=myfun(x)f=-x(1)*x(2)*x(3);函数函数myfun.m第43页第二步：为了调用第二步：为了调用MATLAB函数，必须将模函数，必须将模型中约束转化为以下形式型中约束转化为以下形式(=)。这里：这里：A=-1-2-2;122;b=072;这是这是2个线性约束，形如个线性约束，形如第44页第三步：提供一个搜索起点，然后调用对第三步：提供一个搜索起点，然后调用对应函数，程序以下：应函数，程序以下：%给一个初始搜索点给一个初始搜索点x0=10;10;10;x,fval=fmincon(myfun,x0,A,b)第45页主程序（整体）：主程序（整体）：A=-1-2-2;122;b=072;%给一个初始搜索点给一个初始搜索点x0=10;10;10;x,fval=fmincon(myfun,x0,A,b)第46页最终得到以下结果：最终得到以下结果：x=24.000012.000012.0000fval=-3.4560e+03第47页2.非负条件下非负条件下线性线性最小二乘最小二乘lsqnonneg适合以下模型：适合以下模型：注意：约束只有非负约束注意：约束只有非负约束第48页语法：语法：x=lsqnonneg(c,d)x=lsqnonneg(c,d,x0)x=lsqnonneg(c,d,x0,options)第49页3.有约束线性最小二乘有约束线性最小二乘lsqlin适合以下模型：适合以下模型：注意：约束有线性等式、不等式约束注意：约束有线性等式、不等式约束第50页语法：语法：x=lsqlin(C,d,A,b)x=lsqlin(C,d,A,b,Aeq,beq)x=lsqlin(C,d,A,b,Aeq,beq,lb,ub)x=lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0)x=lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options)x,resnorm=lsqlin(.)x,resnorm,residual=lsqlin(.)x,resnorm,residual,exitflag=lsqlin(.)x,resnorm,residual,exitflag,output=lsqlin(.)x,resnorm,residual,exitflag,output,lambda=lsqlin(.)第51页4.非线性最小二乘非线性最小二乘lsqnonlin适合模型：适合模型：第52页语法：语法：x=lsqnonlin(fun,x0)x=lsqnonlin(fun,x0,lb,ub)x=lsqnonlin(fun,x0,lb,ub,options)x=lsqnonlin(fun,x0,options,P1,P2,.)x,resnorm=lsqnonlin(.)x,resnorm,residual=lsqnonlin(.)x,resnorm,residual,exitflag=lsqnonlin(.)x,resnorm,residual,exitflag,output=lsqnonlin(.)x,resnorm,residual,exitflag,output,lambda=lsqnonlin(.)x,resnorm,residual,exitflag,output,lambda,jacobian=lsqnonlin(.)第53页例例1：求解：求解x，使得下式最小使得下式最小resnorm 等于等于 norm(C*x-d)2norm(C*x-d)2residual等于等于C*x-dC*x-d返回参数说明返回参数说明第54页第一步：编写第一步：编写M文件文件myfun.m计算向量计算向量FfunctionF=myfun(x)k=1:10;F=2+2*k-exp(k*x(1)-exp(k*x(2);第55页第二步：调用优化函数第二步：调用优化函数lsqnonlin%给定搜索起点给定搜索起点x0=0.30.4;%调用求解函数调用求解函数x,resnorm=lsqnonlin(myfun,x0)x=0.2578 0.2578resnorm%residual or sum of squaresresnorm=124.3622 第56页5.学习回顾学习回顾能力培养：能力培养：1、建模分析能力、建模分析能力2、应用数学能力、应用数学能力3、算法设计与程序设计、算法设计与程序设计第57页谢谢 谢！谢！第58页