数学建模之非线性规划问题的算法幻灯片.ppt

《数学建模之非线性规划问题的算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《数学建模之非线性规划问题的算法幻灯片.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模课件之非线性规划问题的算法第1页，共58页，编辑于2022年，星期六一、非线性规划问题的几种求解方法一、非线性规划问题的几种求解方法1.罚函数法（外点法）罚函数法（外点法）基本思想：基本思想：利用目标函数和约束函数构造辅助函数：利用目标函数和约束函数构造辅助函数：第2页，共58页，编辑于2022年，星期六要求构造的函数要求构造的函数具有这样的性质：当点具有这样的性质：当点x位于可行域以外时，位于可行域以外时，取值很大，而离可行取值很大，而离可行域越远则越大；当点在可行域内时，函数域越远则越大；当点在可行域内时，函数因此可以将前面的有约束规划问题转换为下列无因此可以将前面的有约束规划问题

2、转换为下列无约束规划模型：约束规划模型：其中称为其中称为罚项，罚项，称为罚因子，称为罚因子，称为罚函数。称为罚函数。第3页，共58页，编辑于2022年，星期六的定义一般如下：的定义一般如下：函数函数一般定义如下：一般定义如下：第4页，共58页，编辑于2022年，星期六算法步骤算法步骤如何如何将此算法模块化将此算法模块化:第5页，共58页，编辑于2022年，星期六求解非线性规划模型例子求解非线性规划模型例子罚项函数：罚项函数：无约束规划目标函数：无约束规划目标函数：第6页，共58页，编辑于2022年，星期六global lamada%主程序主程序main2.m,罚函数方法罚函数方法x0=1 1;

3、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页，共58页，编辑于2022年，星期六程序程序2：计算：计算的函数的函数fun2p.mfunction r=fun2p(x)%罚项函数罚项函数r=(x(1)-1)3-x(2)*x(2)2;第8页，共58页，编辑于2022年，星期六程序程序3：辅助函数程序：辅助函数程序fun2min

4、.mfunction r=fun2min(x)%辅助函数辅助函数global lamadar=x(1)2+x(2)2+lamada*fun2p(x);第9页，共58页，编辑于2022年，星期六运行输出：运行输出：最优解最优解1.00012815099165-0.00000145071779k=33第10页，共58页，编辑于2022年，星期六练习题：练习题：1、用外点法求解下列模型、用外点法求解下列模型2、将例子程序改写为一个较为、将例子程序改写为一个较为通用的罚函数法通用的罚函数法程序程序。（考虑要提供哪些参数）。（考虑要提供哪些参数）第11页，共58页，编辑于2022年，星期六2.内点法（障

5、碍函数法）内点法（障碍函数法）仅适合于仅适合于不等式约束的最优化问题不等式约束的最优化问题其中其中都是连续函数，将模型的定义域记为都是连续函数，将模型的定义域记为第12页，共58页，编辑于2022年，星期六构造辅助函数构造辅助函数为了保持迭代点含于可行域内部，我们定义障碍为了保持迭代点含于可行域内部，我们定义障碍函数函数第13页，共58页，编辑于2022年，星期六3.问题转化为一个无约束规划问题转化为一个无约束规划由于由于很小，则函数很小，则函数取值接近于取值接近于f(x)，所，所以原问题可以归结为如下规划问题的近似解：以原问题可以归结为如下规划问题的近似解：第14页，共58页，编辑于2022

6、年，星期六第15页，共58页，编辑于2022年，星期六练习题：练习题：请用内点法算法求解下列问题：请用内点法算法求解下列问题：第16页，共58页，编辑于2022年，星期六小结小结q讲解了两个讲解了两个求解有约束非线性最小化规划求解有约束非线性最小化规划特点：特点：q易于实现，方法简单；易于实现，方法简单；q没有用到目标函数的导数没有用到目标函数的导数q问题的转化技巧（近似为一个无约束规划）问题的转化技巧（近似为一个无约束规划）第17页，共58页，编辑于2022年，星期六4、其它求解算法、其它求解算法（1）间接法）间接法（2）直接法）直接法q直接搜索法直接搜索法q以梯度法为基础的以梯度法为基础的

7、间接法间接法q无约束规划的无约束规划的Matlab求解函数求解函数q数学建模案例分析（数学建模案例分析（截断切割截断切割，飞机排队飞机排队）第18页，共58页，编辑于2022年，星期六（1）间接法）间接法在非线性最优化问题当中，如果目标函在非线性最优化问题当中，如果目标函数能以解析函数表示，可行域由不等式约束确数能以解析函数表示，可行域由不等式约束确定，则可以利用目标函数和可行域的已知性质，定，则可以利用目标函数和可行域的已知性质，在理论上推导出目标函数为最优值的必要条件，在理论上推导出目标函数为最优值的必要条件，这种方法就称为这种方法就称为间接法间接法（也称为（也称为解析法解析法）。一般要用

8、到目标函数的导数。一般要用到目标函数的导数。第19页，共58页，编辑于2022年，星期六（2）直接法）直接法直接法直接法是一种数值方法是一种数值方法这种方法的基本思想是这种方法的基本思想是迭代迭代，通过迭代产生一个点，通过迭代产生一个点序列序列X(k)，使之逐步接近最优点。，使之逐步接近最优点。只用到只用到目标函数目标函数。如黄金分割法、如黄金分割法、FibonacciFibonacci、随机搜索法。、随机搜索法。第20页，共58页，编辑于2022年，星期六（3）迭代法一般步骤）迭代法一般步骤注意：注意：数值求解最优化问题的计算效率取决于确数值求解最优化问题的计算效率取决于确定搜索方向定搜索方

9、向P(k)和步长和步长的效率。的效率。第21页，共58页，编辑于2022年，星期六最速下降法（最速下降法（steepestdescentmethod）由法国数学家由法国数学家Cauchy于于1847年首先提出。在每次迭年首先提出。在每次迭代中，沿最速下降方向（代中，沿最速下降方向（负梯度方向负梯度方向）进行搜索，）进行搜索，每步沿负梯度方向取最优步长，因此这种方法称为每步沿负梯度方向取最优步长，因此这种方法称为最优梯度法最优梯度法。特点：特点：方方法法简简单单，只只以以一一阶阶梯梯度度的的信信息息确确定定下下一一步步的的搜搜索索方方向向，收敛速度慢；收敛速度慢；越是接近极值点，收敛越慢；越是接

10、近极值点，收敛越慢；它是其它许多无约束、有约束最优化方法的基础。它是其它许多无约束、有约束最优化方法的基础。该法一般用于最优化开始的几步搜索。该法一般用于最优化开始的几步搜索。第22页，共58页，编辑于2022年，星期六以梯度法为基础的最优化方法以梯度法为基础的最优化方法求求f(x)在在En中的极小点中的极小点思想：思想：q方向导数是反映函数值沿某一方向的变化率问题方向导数是反映函数值沿某一方向的变化率问题q方向导数沿梯度方向取得最大值方向导数沿梯度方向取得最大值基础：方向导数、梯度基础：方向导数、梯度第23页，共58页，编辑于2022年，星期六q通过一系列一维搜索来实现。通过一系列一维搜索来

11、实现。q本方法的核心问题是选择搜索方向。本方法的核心问题是选择搜索方向。q搜索方向的不同则形成不同的最优化方法。搜索方向的不同则形成不同的最优化方法。第24页，共58页，编辑于2022年，星期六最速下降法最速下降法算法：算法：第25页，共58页，编辑于2022年，星期六算法说明算法说明可通过可通过一维无约束搜索方法一维无约束搜索方法求解求解第26页，共58页，编辑于2022年，星期六例子：用最速下降法解下列问题例子：用最速下降法解下列问题分析：分析：1、编写一个梯度函数程序、编写一个梯度函数程序fun1gra.m2、求、求(可以调用函数可以调用函数fminsearch)函数函数fungetla

12、mada.m3、最速下降法主程序、最速下降法主程序main1.m初始条件初始条件第27页，共58页，编辑于2022年，星期六第一步：计算梯度程序第一步：计算梯度程序fun1gra.mfunction r=fun1gra(x)%最速下降法求解示例最速下降法求解示例%函数函数f(x)=2*x12+x22的梯度的计算的梯度的计算%r(1)=4*x(1);r(2)=2*x(2);第28页，共58页，编辑于2022年，星期六第二步：求第二步：求最优的目标函数最优的目标函数function r=fungetlamada(lamada)%关于关于lamada的一元函数，求最优步长的一元函数，求最优步长glo

13、bal x0d=fun1gra(x0);r=2*(x0(1)-lamada*d(1)2+(x0(2)-lamada*d(2)2;%注意注意负负号表示是号表示是负负梯度梯度第29页，共58页，编辑于2022年，星期六第三步：主程序第三步：主程序main1.m%最速下降方法实现一个非线性最优化问题最速下降方法实现一个非线性最优化问题%min f(x)=2*x12+x22global x0 x0=1 1;yefi=0.0001;k=1;d=-fun1gra(x0);lamada=1;第30页，共58页，编辑于2022年，星期六主程序主程序main1.m（续）（续）while sqrt(sum(d.2

14、)=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页，共58页，编辑于2022年，星期六三、三、Matlab求解有约束非线性规划求解有约束非线性规划第32页，共58页，编辑于2022年，星期六1.用用fmincon函数求解形如下

15、面的有约束非函数求解形如下面的有约束非线性规划模型线性规划模型一般形式：一般形式：第33页，共58页，编辑于2022年，星期六用用Matlab求解有约束非线性最小化问题求解有约束非线性最小化问题求求解解非非线线性性规规划划问问题题的的Matlab函函数数为为：fmincon1.约束中可以有等式约束约束中可以有等式约束2.可以含线性、非线性约束均可可以含线性、非线性约束均可第34页，共58页，编辑于2022年，星期六输入输入参数语法：参数语法：x=fmincon(fun,x0,A,b)x=fmincon(fun,x0,A,b,Aeq,beq)x=fmincon(fun,x0,A,b,Aeq,be

16、q,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页，共58页，编辑于2022年，星期六输入参数的几点说明输入参数的几点说明q模型中如果没有模型中如果没有A,b,Aeq,beq,lb,ub的限制，则以空矩阵的限制，则以空矩阵作为作为q参数传入；参数传入；qnonlcon：如果包含非线性等式或不等式约束，则将这些函数：如果

17、包含非线性等式或不等式约束，则将这些函数编写为一个编写为一个Matlab函数，函数，nonlcon就是定义这些函数的程序文件名；就是定义这些函数的程序文件名；不等式约束不等式约束c(x)=0c(x)2nargout 2%nonlcon%nonlcon 如果四个输出参数如果四个输出参数 GC=.GC=.%不等式约束的梯度不等式约束的梯度 GCeq=.GCeq=.%等式约束的梯度等式约束的梯度end end 第40页，共58页，编辑于2022年，星期六输出输出参数语法：参数语法：x,fval=fmincon(.)x,fval,exitflag=fmincon(.)x,fval,exitflag,o

18、utput=fmincon(.)x,fval,exitflag,output,lambda=fmincon(.)x,fval,exitflag,output,lambda,grad=fmincon(.)x,fval,exitflag,output,lambda,grad,hessian=fmincon(.)运用步骤：运用步骤：将自己的模型转化为上面的形式将自己的模型转化为上面的形式写出对应的参数写出对应的参数调用函数调用函数第41页，共58页，编辑于2022年，星期六fmincon应用求解示例：应用求解示例：请问：请问：1、结合结合fmincon函数，需要提供哪些参数函数，需要提供哪些参数第4

19、2页，共58页，编辑于2022年，星期六第一步：编写一个第一步：编写一个M文件返回目标函数文件返回目标函数f在点在点x处处的值函数程序的值函数程序functionf=myfun(x)f=-x(1)*x(2)*x(3);函数函数myfun.m第43页，共58页，编辑于2022年，星期六第二步：为了调用第二步：为了调用MATLAB函数，必须将模型中函数，必须将模型中的约束转化为如下形式的约束转化为如下形式(=)。这里：这里：A=-1-2-2;122;b=072;这是这是2个线性约束，形如个线性约束，形如第44页，共58页，编辑于2022年，星期六第三步：提供一个搜索起点，然后调用相应函第三步：提供

20、一个搜索起点，然后调用相应函数，程序如下：数，程序如下：%给一个初始搜索点给一个初始搜索点x0=10;10;10;x,fval=fmincon(myfun,x0,A,b)第45页，共58页，编辑于2022年，星期六主程序（整体）：主程序（整体）：A=-1-2-2;122;b=072;%给一个初始搜索点给一个初始搜索点x0=10;10;10;x,fval=fmincon(myfun,x0,A,b)第46页，共58页，编辑于2022年，星期六最后得到如下结果：最后得到如下结果：x=24.000012.000012.0000fval=-3.4560e+03第47页，共58页，编辑于2022年，星期六

21、2.非负条件下非负条件下线性线性最小二乘最小二乘lsqnonneg适合如下模型：适合如下模型：注意：约束只有非负约束注意：约束只有非负约束第48页，共58页，编辑于2022年，星期六语法：语法：x=lsqnonneg(c,d)x=lsqnonneg(c,d,x0)x=lsqnonneg(c,d,x0,options)第49页，共58页，编辑于2022年，星期六3.有约束线性最小二乘有约束线性最小二乘lsqlin适合如下模型：适合如下模型：注意：约束有线性等式、不等式约束注意：约束有线性等式、不等式约束第50页，共58页，编辑于2022年，星期六语法：语法：x=lsqlin(C,d,A,b)x=

22、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=

23、lsqlin(.)第51页，共58页，编辑于2022年，星期六4.非线性最小二乘非线性最小二乘lsqnonlin适合模型：适合模型：第52页，共58页，编辑于2022年，星期六语法：语法：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

24、,resnorm,residual,exitflag,output=lsqnonlin(.)x,resnorm,residual,exitflag,output,lambda=lsqnonlin(.)x,resnorm,residual,exitflag,output,lambda,jacobian=lsqnonlin(.)第53页，共58页，编辑于2022年，星期六例例1：求解：求解x，使得下式最小，使得下式最小resnorm 等于等于 norm(C*x-d)2norm(C*x-d)2residual等于等于C*x-dC*x-d返回参数说明返回参数说明第54页，共58页，编辑于2022年，星

25、期六第一步：编写第一步：编写M文件文件myfun.m计算向量计算向量FfunctionF=myfun(x)k=1:10;F=2+2*k-exp(k*x(1)-exp(k*x(2);第55页，共58页，编辑于2022年，星期六第二步：调用优化函数第二步：调用优化函数lsqnonlin%给定搜索起点给定搜索起点x0=0.30.4;%调用求解函数调用求解函数x,resnorm=lsqnonlin(myfun,x0)x=0.2578 0.2578resnorm%residual or sum of squaresresnorm=124.3622 第56页，共58页，编辑于2022年，星期六5.学习回顾学习回顾能力培养：能力培养：1、建模分析能力、建模分析能力2、应用数学能力、应用数学能力3、算法设计与程序设计、算法设计与程序设计第57页，共58页，编辑于2022年，星期六谢谢 谢！谢！第58页，共58页，编辑于2022年，星期六