数学建模课件之非线性规划问题的算法

数学建模课件之非线性规划问题的算法第1页，共58页，2023年，2月20日，星期六一、非线性规划问题的几种求解方法

1.罚函数法（外点法）

基本思想：利用目标函数和约束函数构造辅助函数：第2页，共58页，2023年，2月20日，星期六要求构造的函数具有这样的性质：当点x位于可行域以外时，取值很大，而离可行域越远则越大；当点在可行域内时，函数因此可以将前面的有约束规划问题转换为下列无约束规划模型：其中称为罚项，称为罚因子，称为罚函数。第3页，共58页，2023年，2月20日，星期六的定义一般如下：函数一般定义如下：第4页，共58页，2023年，2月20日，星期六算法步骤如何将此算法模块化:第5页，共58页，2023年，2月20日，星期六求解非线性规划模型例子罚项函数：无约束规划目标函数：第6页，共58页，2023年，2月20日，星期六globallamada%主程序main2.m,罚函数方法x0=[11];lamada=2;c=10;e=1e-5;k=1;whilelamada*fun2p(x0)>=e x0=fminsearch('fun2min',x0);lamada=c*lamada;k=k+1;enddisp(‘最优解’),disp(x0)disp('k='),disp(k)

程序1：主程序main2.m第7页，共58页，2023年，2月20日，星期六程序2：计算的函数fun2p.mfunctionr=fun2p(x)%罚项函数r=((x(1)-1)^3-x(2)*x(2))^2;

第8页，共58页，2023年，2月20日，星期六程序3：辅助函数程序fun2min.mfunctionr=fun2min(x)%辅助函数globallamadar=x(1)^2+x(2)^2+lamada*fun2p(x);第9页，共58页，2023年，2月20日，星期六运行输出：最优解1.00012815099165-0.00000145071779

k=33第10页，共58页，2023年，2月20日，星期六练习题：

1、用外点法求解下列模型2、将例子程序改写为一个较为通用的罚函数法程序。（考虑要提供哪些参数）第11页，共58页，2023年，2月20日，星期六2.内点法（障碍函数法）仅适合于不等式约束的最优化问题其中都是连续函数，将模型的定义域记为第12页，共58页，2023年，2月20日，星期六构造辅助函数为了保持迭代点含于可行域内部，我们定义障碍函数第13页，共58页，2023年，2月20日，星期六3.问题转化为一个无约束规划由于很小，则函数取值接近于f(x)，所以原问题可以归结为如下规划问题的近似解：第14页，共58页，2023年，2月20日，星期六第15页，共58页，2023年，2月20日，星期六练习题：

请用内点法算法求解下列问题：

第16页，共58页，2023年，2月20日，星期六小结讲解了两个求解有约束非线性最小化规划特点：易于实现，方法简单；没有用到目标函数的导数问题的转化技巧（近似为一个无约束规划）第17页，共58页，2023年，2月20日，星期六4、其它求解算法

（1）间接法

（2）直接法

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

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

(k)和步长的效率。第21页，共58页，2023年，2月20日，星期六最速下降法（steepestdescentmethod）由法国数学家Cauchy于1847年首先提出。在每次迭代中，沿最速下降方向（负梯度方向）进行搜索，每步沿负梯度方向取最优步长，因此这种方法称为最优梯度法。特点：方法简单，只以一阶梯度的信息确定下一步的搜索方向，收敛速度慢；越是接近极值点，收敛越慢；它是其它许多无约束、有约束最优化方法的基础。该法一般用于最优化开始的几步搜索。第22页，共58页，2023年，2月20日，星期六以梯度法为基础的最优化方法求f(x)在En中的极小点思想：方向导数是反映函数值沿某一方向的变化率问题方向导数沿梯度方向取得最大值基础：方向导数、梯度第23页，共58页，2023年，2月20日，星期六通过一系列一维搜索来实现。本方法的核心问题是选择搜索方向。搜索方向的不同则形成不同的最优化方法。第24页，共58页，2023年，2月20日，星期六最速下降法算法：

第25页，共58页，2023年，2月20日，星期六算法说明可通过一维无约束搜索方法求解第26页，共58页，2023年，2月20日，星期六例子：用最速下降法解下列问题分析：1、编写一个梯度函数程序fun1gra.m2、求(可以调用函数fminsearch)函数fungetlamada.m3、最速下降法主程序main1.m初始条件第27页，共58页，2023年，2月20日，星期六第一步：计算梯度程序fun1gra.mfunctionr=fun1gra(x)%最速下降法求解示例%函数f(x)=2*x1^2+x2^2的梯度的计算%r(1)=4*x(1);r(2)=2*x(2);第28页，共58页，2023年，2月20日，星期六第二步：求最优的目标函数functionr=fungetlamada(lamada)%关于lamada的一元函数，求最优步长globalx0d=fun1gra(x0);r=2*(x0(1)-lamada*d(1))^2+(x0(2)-lamada*d(2))^2;%注意负号表示是负梯度第29页，共58页，2023年，2月20日，星期六第三步：主程序main1.m%最速下降方法实现一个非线性最优化问题%minf(x)=2*x1^2+x2^2globalx0x0=[11];yefi=0.0001;k=1;d=-fun1gra(x0);lamada=1;第30页，共58页，2023年，2月20日，星期六主程序main1.m（续）whilesqrt(sum(d.^2))>=yefilamada=fminsearch(‘fungetlamada’,lamada);%求最优步长lamadax0=x0-lamada*fun1gra(x0);%计算x0d=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页，2023年，2月20日，星期六三、Matlab求解有约束非线性规划第32页，共58页，2023年，2月20日，星期六1.用fmincon函数求解形如下面的有约束非线性规划模型一般形式：第33页，共58页，2023年，2月20日，星期六用Matlab求解有约束非线性最小化问题求解非线性规划问题的Matlab函数为：fmincon

1.约束中可以有等式约束 2.可以含线性、非线性约束均可第34页，共58页，2023年，2月20日，星期六输入参数语法：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页，共58页，2023年，2月20日，星期六输入参数的几点说明模型中如果没有A,b,Aeq,beq,lb,ub的限制，则以空矩阵[]作为参数传入；nonlcon：如果包含非线性等式或不等式约束，则将这些函数

编写为一个Matlab函数，nonlcon就是定义这些函数的程序文件名；不等式约束c(x)<=0等式约束ceq(x)=0.如果nonlcon=‘mycon’;则myfun.m定义如下function[c,ceq]=mycon(x)c=...

%计算非线性不等式约束在点x处的函数值ceq=...

%计算机非线性等式约束在点x处的函数值

第36页，共58页，2023年，2月20日，星期六对参数nonlcon的进一步示例2个不等式约束，2个等式约束3个决策变量x1，x2，x3如果nonlcon以‘mycon1’作为参数值，则程序mycon1.m如下第37页，共58页，2023年，2月20日，星期六对照约束条件编写myfun1.mfunction[c,ceq]=mycon1(x)c(1)=x(1)*x(1)+x(2)*x(2)+x(3)*x(3)-100c(2)=60-x(1)*x(1)+10*x(3)*x(3)ceq(1)=x(1)+x(2)*x(2)+x(3)-80ceq(2)=x(1)^3+x(2)*x(2)+x(3)-80第38页，共58页，2023年，2月20日，星期六nonlcon的高级用法允许提供非线性约束条件中函数的梯度设置方法：options=optimset('GradConstr','on')

如果提供非线性约束条件中函数梯度，nonlcon的函数必须如下格式：第39页，共58页，2023年，2月20日，星期六参数nonlcon的函数一般格式如下function[c,ceq,GC,GCeq]=mycon(x)c=...

%计算非线性不等式约束在点x处的函数值

ceq=...

%计算机非线性等式约束在点x处的函数值

ifnargout>2

%nonlcon如果四个输出参数

GC=...

%不等式约束的梯度

GCeq=...

%等式约束的梯度end第40页，共58页，2023年，2月20日，星期六输出参数语法：[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页，共58页，2023年，2月20日，星期六fmincon应用求解示例：请问：1、结合fmincon函数，需要提供哪些参数第42页，共58页，2023年，2月20日，星期六第一步：编写一个M文件返回目标函数f在点x处的值函数程序functionf=myfun(x)f=-x(1)*x(2)*x(3);函数myfun.m第43页，共58页，2023年，2月20日，星期六第二步：为了调用MATLAB函数，必须将模型中的约束转化为如下形式(<=)。

这里：A=[-1-2-2;122];b=[072]’;这是2个线性约束，形如第44页，共58页，2023年，2月20日，星期六第三步：提供一个搜索起点，然后调用相应函数，程序如下：%给一个初始搜索点 x0=[10;10;10];[x,fval]=fmincon('myfun',x0,A,b)第45页，共58页，2023年，2月20日，星期六主程序（整体）：A=[-1-2-2;122];b=[072]’;%给一个初始搜索点 x0=[10;10;10];[x,fval]=fmincon('myfun',x0,A,b)第46页，共58页，2023年，2月20日，星期六最后得到如下结果：

x=24.000012.000012.0000

fval=-3.4560e+03第47页，共58页，2023年，2月20日，星期六2.非负条件下线性最小二乘lsqnonneg

适合如下模型：

注意：约束只有非负约束第48页，共58页，2023年，2月20日，星期六语法：x=lsqnonneg(c,d)x=lsqnonneg(c,d,x0)x=lsqnonneg(c,d,x0,options)

第49页，共58页，2023年，2月20日，星期六3.有约束线性最小二乘lsqlin

适合如下模型：注意：约束有线性等式、不等式约束第50页，共58页，2023年，2月20日，星期六语法：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页，共58页，2023年，2月20日，星期六4.非线性最小二乘lsqnonlin

适合模型：第52页，共58页，2023年，2月20日，星期六语法：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