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

1、第六讲 非线性规划问题的求解方法一、非线性规划问题的几种求解方法1. 罚函数法（外点法） 基本思想： 利用目标函数和约束函数构造辅助函数： 要求构造的函数 具有这样的性质：当点x位于可行域以外时， 取值很大，而离可行域越远则越大；当点在可行域内时，函数 因此可以将前面的有约束规划问题转换为下列无约束规划模型： 其中称为 罚项， 称为罚因子， 称为罚函数。 的定义一般如下：函数 一般定义如下：算法步骤如何将此算法模块化:求解非线性规划模型例子罚项函数：无约束规划目标函数：global lamada%主程序main2.m,罚函数方法x0=1 1; lamada=2;c=10; e=1e-5;k=1

2、;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程序2：计算 的函数fun2p.mfunction r=fun2p(x)%罚项函数r=(x(1)-1)3-x(2)*x(2)2; 程序3：辅助函数程序fun2min.mfunction r=fun2min(x)%辅助函数global lamadar=x(1)2+x(2)2+lamada*fun2p(x);运行输出：最优解 1.0001281

3、5099165 -0.00000145071779k=33 练习题： 1、用外点法求解下列模型 2、将例子程序改写为一个较为通用的罚函数法程序。（考虑要提供哪些参数） 2. 内点法（障碍函数法）仅适合于不等式约束的最优化问题其中都是连续函数，将模型的定义域记为构造辅助函数为了保持迭代点含于可行域内部，我们定义障碍函数 3. 问题转化为一个无约束规划由于 很小，则函数 取值接近于f(x)，所以原问题可以归结为如下规划问题的近似解： 练习题：请用内点法算法求解下列问题： 小结讲解了两个求解有约束非线性最小化规划特点：易于实现，方法简单；没有用到目标函数的导数问题的转化技巧（近似为一个无约束规划）4

4、、其它求解算法（1）间接法（2）直接法 直接搜索法以梯度法为基础的间接法无约束规划的Matlab求解函数数学建模案例分析（截断切割，飞机排队）（1）间接法在非线性最优化问题当中，如果目标函数能以解析函数表示，可行域由不等式约束确定，则可以利用目标函数和可行域的已知性质，在理论上推导出目标函数为最优值的必要条件，这种方法就称为间接法（也称为解析法） 。一般要用到目标函数的导数。（2）直接法直接法是一种数值方法这种方法的基本思想是迭代，通过迭代产生一个点序列 X(k) ，使之逐步接近最优点。 只用到目标函数。如黄金分割法、Fibonacci、随机搜索法。（3）迭代法一般步骤注意：数值求解最优化问题

5、的计算效率取决于确定搜索方向P (k)和步长 的效率。 最速下降法（steepest descent method）由法国数学家Cauchy于1847年首先提出。在每次迭代中，沿最速下降方向（负梯度方向）进行搜索，每步沿负梯度方向取最优步长，因此这种方法称为最优梯度法。 特点：方法简单，只以一阶梯度的信息确定下一步的搜索方向，收敛速度慢；越是接近极值点，收敛越慢；它是其它许多无约束、有约束最优化方法的基础。该法一般用于最优化开始的几步搜索。 以梯度法为基础的最优化方法求f(x)在En中的极小点 思想：方向导数是反映函数值沿某一方向的变化率问题 方向导数沿梯度方向取得最大值基础：方向导数、梯度通

6、过一系列一维搜索来实现。本方法的核心问题是选择搜索方向。搜索方向的不同则形成不同的最优化方法。最速下降法算法： 算法说明 可通过一维无约束搜索方法求解例子：用最速下降法解下列问题分析：1、编写一个梯度函数程序fun1gra.m2、求 (可以调用函数fminsearch )函数fungetlamada.m3、最速下降法主程序main1.m初始条件第一步：计算梯度程序 fun1gra.mfunction r=fun1gra(x)%最速下降法求解示例%函数f(x)=2*x12+x22的梯度的计算%r(1)=4*x(1);r(2)=2*x(2);第二步：求 最优的目标函数function r=fung

7、etlamada(lamada)%关于lamada的一元函数，求最优步长global x0d=fun1gra(x0);r=2*(x0(1)-lamada*d(1)2+(x0(2)-lamada*d(2)2; %注意负号表示是负梯度第三步：主程序main1.m%最速下降方法实现一个非线性最优化问题% min f(x)=2*x12+x22global x0 x0= 1 1 ;yefi=0.0001;k=1;d=-fun1gra(x0);lamada=1;主程序main1.m（续）while sqrt(sum(d.2)=yefilamada=fminsearch(fungetlamada,lamad

8、a);%求最优步长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)三、Matlab求解有约束非线性规划1. 用fmincon函数求解形如下面的有约束非线性规划模型一般形式：用Matlab求解有约束非线性最小化问题求解非线性规划问题的Matlab函数为： fmincon1.约束中可以有等式约束2.可以含线性、非线性约束均可输入参数语法：x = fmincon(fu

9、n,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, .) 输入参数的几点说明模型中如果没有A,b,Aeq,beq,lb,ub的限制，则以空矩阵 作为参数传入；nonlcon：如果包含

10、非线性等式或不等式约束，则将这些函数 编写为一个Matlab函数，nonlcon就是定义这些函数的程序文件名；不等式约束 c(x) 2% nonlcon 如果四个输出参数 GC = .% 不等式约束的梯度 GCeq = .% 等式约束的梯度end 输出参数语法：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(

11、.)x,fval,exitflag,output,lambda,grad,hessian = fmincon(.) 运用步骤：将自己的模型转化为上面的形式写出对应的参数调用函数fmincon应用求解示例：请问：1、结合fmincon函数，需要提供哪些参数第一步：编写一个M文件返回目标函数f在点x处的值函数程序 function f = myfun(x)f = -x(1) * x(2) * x(3); 函数myfun.m第二步：为了调用MATLAB函数，必须将模型中的约束转化为如下形式(=)。 这里：A=-1 -2 -2; 1 2 2 ;b=0 72;这是2个线性约束，形如第三步：提供一个搜索起

12、点，然后调用相应函数，程序如下：% 给一个初始搜索点x0 = 10; 10; 10; x,fval = fmincon(myfun,x0,A,b) 主程序（整体）：A=-1 -2 -2; 1 2 2 ;b=0 72;% 给一个初始搜索点x0 = 10; 10; 10; x,fval = fmincon(myfun,x0,A,b)最后得到如下结果：x = 24.0000 12.0000 12.0000fval = -3.4560e+032.非负条件下线性最小二乘 lsqnonneg 适合如下模型： 注意：约束只有非负约束语法：x =lsqnonneg(c,d)x =lsqnonneg(c,d,x

13、0)x =lsqnonneg(c,d,x0,options) 3.有约束线性最小二乘lsqlin 适合如下模型： 注意：约束有线性等式、不等式约束语法：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,resi

14、dual,exitflag = lsqlin(.)x,resnorm,residual,exitflag,output = lsqlin(.)x,resnorm,residual,exitflag,output,lambda = lsqlin(.)4.非线性最小二乘lsqnonlin 适合模型：语法：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,r

15、esnorm,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(.) 例1：求解x，使得下式最小 resnorm 等于 norm(C*x-d)2residual 等于C*x-d返回参数说明第一步：编写M文件myfun.m计算向量Ffunction F = myfun(x