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

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