一非线规划问题的几种求解方法1罚函数法外点法.ppt

《一非线规划问题的几种求解方法1罚函数法外点法.ppt》由会员分享，可在线阅读，更多相关《一非线规划问题的几种求解方法1罚函数法外点法.ppt（58页珍藏版）》请在三一文库上搜索。

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

2、 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,程序2：计算 的函数fun2p.m,function r=fun2p(x) %罚项函数 r=(x(1)-1)3-x(2)*x(2)2;,程序3：辅助函数程序fun2min.m,function r=fun2min(x) %辅助函数 global lamada r=x(1)2+x(2)2+lamada*fun2

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

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

5、到目标函数。 如黄金分割法、Fibonacci、随机搜索法。,（3）迭代法一般步骤,注意：数值求解最优化问题的计算效率取决于确定搜索方向P (k)和步长 的效率。,最速下降法（steepest descent method） 由法国数学家Cauchy于1847年首先提出。在每次迭代中，沿最速下降方向（负梯度方向）进行搜索，每步沿负梯度方向取最优步长，因此这种方法称为最优梯度法。 特点： 方法简单，只以一阶梯度的信息确定下一步的搜索方向，收敛速度慢； 越是接近极值点，收敛越慢； 它是其它许多无约束、有约束最优化方法的基础。 该法一般用于最优化开始的几步搜索。,以梯度法为基础的最优化方法,求f(x

6、)在En中的极小点,思想： 方向导数是反映函数值沿某一方向的变化率问题 方向导数沿梯度方向取得最大值,基础：方向导数、梯度,通过一系列一维搜索来实现。 本方法的核心问题是选择搜索方向。 搜索方向的不同则形成不同的最优化方法。,最速下降法算法：,算法说明,可通过一维无约束搜索方法求解,例子：用最速下降法解下列问题,分析： 1、编写一个梯度函数程序fun1gra.m 2、求 (可以调用函数fminsearch )函数fungetlamada.m 3、最速下降法主程序main1.m,初始条件,第一步：计算梯度程序 fun1gra.m,function r=fun1gra(x) %最速下降法求解示例

7、%函数f(x)=2*x12+x22的梯度的计算 % r(1)=4*x(1); r(2)=2*x(2);,第二步：求 最优的目标函数,function r=fungetlamada(lamada) %关于lamada的一元函数，求最优步长 global x0 d=fun1gra(x0); r=2*(x0(1)-lamada*d(1)2+(x0(2)-lamada*d(2)2; %注意负号表示是负梯度,第三步：主程序main1.m,%最速下降方法实现一个非线性最优化问题 % min f(x)=2*x12+x22 global x0 x0= 1 1 ; yefi=0.0001; k=1; d=-fu

8、n1gra(x0); lamada=1;,主程序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),三、Matlab求解有约束非线性规划,1. 用fmincon函数求解形如下面的有约束非线性规划模型,

9、一般形式：,用Matlab求解有约束非线性最小化问题 求解非线性规划问题的Matlab函数为： fmincon 1.约束中可以有等式约束 2.可以含线性、非线性约束均可,输入参数语法：,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(f

10、un,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2, .),输入参数的几点说明,模型中如果没有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 = . %计算机非线性等

11、式约束在点x处的函数值,对参数nonlcon的进一步示例,2个不等式约束， 2个等式约束 3个决策变量x1，x2，x3 如果nonlcon以mycon1作为参数值，则程序mycon1.m如下,对照约束条件编写myfun1.m,function c,ceq = mycon1(x) c(1) = x(1)*x(1)+x(2)*x(2)+x(3)*x(3)-100 c(2) = 60 - x(1)*x(1) + 10*x(3)*x(3) ceq(1) = x(1) + x(2)*x(2) + x(3) - 80 ceq(2) = x(1)3 + x(2)*x(2) + x(3) - 80,nonlc

12、on的高级用法,允许提供非线性约束条件中函数的梯度 设置方法： options = optimset(GradConstr, on) 如果提供非线性约束条件中函数梯度， nonlcon的函数必须如下格式：,参数nonlcon的函数一般格式如下,function c,ceq,GC,GCeq = mycon(x) c = . % 计算非线性不等式约束在点x处的函数值 ceq = . %计算机非线性等式约束在点x处的函数值 if nargout 2 % nonlcon 如果四个输出参数 GC = . % 不等式约束的梯度 GCeq = . % 等式约束的梯度 end,输出参数语法：,x,fval =

13、 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(.) 运用步骤： 将自己的模型转化为上面的形式 写出对应的参数 调用函数,fmincon应用求解示例：,请问： 1、结合fmincon函数，需要提供哪些参数,

14、第一步：编写一个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个线性约束，形如,第三步：提供一个搜索起点，然后调用相应函数，程序如下：,% 给一个初始搜索点 x0 = 10; 10; 10; x,fval = fmincon(myfun,x0,A,b),主程序（整体）：,A=-1 -2 -2; 1 2 2 ; b=0 72; % 给一个初始搜

15、索点 x0 = 10; 10; 10; x,fval = fmincon(myfun,x0,A,b),最后得到如下结果：,x = 24.0000 12.0000 12.0000 fval = -3.4560e+03,2.非负条件下线性最小二乘 lsqnonneg,适合如下模型：,注意：约束只有非负约束,语法：,x =lsqnonneg(c,d) x =lsqnonneg(c,d,x0) x =lsqnonneg(c,d,x0,options),3.有约束线性最小二乘lsqlin,适合如下模型：,注意：约束有线性等式、不等式约束,语法：,x = lsqlin(C,d,A,b) x = lsqli

16、n(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,exitfl

17、ag,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,resnorm,residual = lsqnonlin(.) x,resnorm,residual,exitflag = lsqnonlin(.) x,resnorm,resi

18、dual,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)2 residual 等于C*x-d,返回参数说明,第一步：编写M文件myfun.m计算向量F,function F = myfun(x) k = 1:10; F = 2 + 2*k-exp(k*x(1)-exp(k*x(2);,第二步：调用优化函数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,5.学习回顾,能力培养： 1、建模分析能力 2、应用数学能力 3、算法设计与程序设计,谢 谢！,