一非线性规划问题的几种求解方法1-罚函数法(外点法)

一、非线性规划问题的几种求解方法1.罚函数法（外点法）基本思想：利用目标函数和约束函数构造辅助函数：),,2,1(0)(),,2,1(0)(..)(minljxhmixgtsxfji)()(),(xPxfxF要求构造的函数具有这样的性质：当点x位于可行域以外时，取值很大，而离可行域越远则越大；当点在可行域内时，函数因此可以将前面的有约束规划问题转换为下列无约束规划模型：其中称为罚项，称为罚因子，称为罚函数。),(xF),(xF)(),(xfxF)()(),(minxPxfxF)(xP),(xF的定义一般如下：)(xPljjmiixhxgxP11))(())(()(其中)(),(yy是满足如下条件的连续函数：当0y时，0)(y；当0y时，0)(y；当0y时，0)(y；当0y时，0)(y；函数一般定义如下：)(),(yyaixg)}](,0[max{，bjxh|)(|，1,1ba，a,b为常数，通常取a=b=2。算法步骤（1）给定初始点x(0)，初始罚因子)1(，放大系数c1；允许误差e0,设置k=1；（2）以x(k-1)作为搜索初始点，求解无约束规划问题)()(minxPxf，令x(k)为所求极小点。（3）当exPk)()(，则停止计算，得到点x(k)；否则，令)()1(kkc，返回（2）执行。如何将此算法模块化:求解非线性规划模型例子罚项函数：无约束规划目标函数：0)1(..)min(22312221xxtsxx)()(xPxf)()(kxPgloballamada%主程序main2.m,罚函数方法x0=[11];lamada=2;c=10;e=1e-5;k=1;whilelamada*fun2p(x0)=ex0=fminsearch('fun2min',x0);lamada=c*lamada;k=k+1;enddisp(‘最优解’),disp(x0)disp('k='),disp(k)程序1：主程序main2.m程序2：计算的函数fun2p.mfunctionr=fun2p(x)%罚项函数r=((x(1)-1)^3-x(2)*x(2))^2;)()(kxP程序3：辅助函数程序fun2min.mfunctionr=fun2min(x)%辅助函数globallamadar=x(1)^2+x(2)^2+lamada*fun2p(x);运行输出：最优解1.00012815099165-0.00000145071779k=33练习题：1、用外点法求解下列模型2、将例子程序改写为一个较为通用的罚函数法程序。（考虑要提供哪些参数）1..)2min(212221xxtsxx2.内点法（障碍函数法）仅适合于不等式约束的最优化问题其中都是连续函数，将模型的定义域记为mixgtsxfi,,2,1,0)(..)(min),,2,1)((),(mixgxfi},,2,1,0)(|{mixgxSi构造辅助函数为了保持迭代点含于可行域内部，我们定义障碍函数)()(),(xBxfxF其中)(xB是连续函数，当点x趋于可行域边界时，)(xB，B(x)可以取如下形式：miixgxB1)(1)(或)(log)(1xgxBimi在这里是个很小的正数，那么当x趋于边界时，),(xF。3.问题转化为一个无约束规划由于很小，则函数取值接近于f(x)，所以原问题可以归结为如下规划问题的近似解：),(xFSxtsxF..),(min算法：（1）给定初始内点Sx)0(，允许误差e0，障碍参数)1(，缩小系数)1,0(b，置k=1；（2）以)1(kx为初始点，求解下列规划问题：SxtsxBxfk..)()(min)(，令)(kx为所求极小点（3）如果exBkk)()()(，则停止计算，得到结果)(kx，（4）否则令)()1(kkb，置k=k+1，返回（2）。练习题：请用内点法算法求解下列问题：10..45)(min21221xxtsxxxf小结讲解了两个求解有约束非线性最小化规划特点：易于实现，方法简单；没有用到目标函数的导数问题的转化技巧（近似为一个无约束规划）4、其它求解算法（1）间接法（2）直接法直接搜索法以梯度法为基础的间接法无约束规划的Matlab求解函数数学建模案例分析（截断切割，飞机排队）（1）间接法在非线性最优化问题当中，如果目标函数能以解析函数表示，可行域由不等式约束确定，则可以利用目标函数和可行域的已知性质，在理论上推导出目标函数为最优值的必要条件，这种方法就称为间接法（也称为解析法）。一般要用到目标函数的导数。（2）直接法直接法是一种数值方法这种方法的基本思想是迭代，通过迭代产生一个点序列{X(k)}，使之逐步接近最优点。只用到目标函数。如黄金分割法、Fibonacci、随机搜索法。（3）迭代法一般步骤注意：数值求解最优化问题的计算效率取决于确定搜索方向P(k)和步长的效率。（1）选定初始点X(0)，k=0（2）寻找一个合适的方向P(k)，k=0，1，2，…P(k)为第k+1步的搜索方向。（3）求出沿P(k)方向前进的步长)(k（4）得到新的点X(k+1)，)()()()1(kkkkPXX检验X(k+1)是否最优，如果是最优，则迭代结束，否则1kk，转到（2）执行。)(k最速下降法（steepestdescentmethod）由法国数学家Cauchy于1847年首先提出。在每次迭代中，沿最速下降方向（负梯度方向）进行搜索，每步沿负梯度方向取最优步长，因此这种方法称为最优梯度法。特点：方法简单，只以一阶梯度的信息确定下一步的搜索方向，收敛速度慢；越是接近极值点，收敛越慢；它是其它许多无约束、有约束最优化方法的基础。该法一般用于最优化开始的几步搜索。以梯度法为基础的最优化方法求f(x)在En中的极小点nExxf),(min思想：方向导数是反映函数值沿某一方向的变化率问题方向导数沿梯度方向取得最大值基础：方向导数、梯度通过一系列一维搜索来实现。本方法的核心问题是选择搜索方向。搜索方向的不同则形成不同的最优化方法。最速下降法算法：1.给定初始点Exn)1(，给定误差0，令k=1；2.计算搜索方向xdkkf)()(；3.如果dk)(，则迭代终止，否则通过下列一维搜索求)(k：dxkkf)()(0min4.令dxxkkkk)()()()1(，置k=k+1，转（2）步执行。算法说明可通过一维无约束搜索方法求解dxxkkkk)()()()1()()()(xdkkf)(k：为dxkkf)()(0min的解)(k例子：用最速下降法解下列问题分析：1、编写一个梯度函数程序fun1gra.m2、求(可以调用函数fminsearch)函数fungetlamada.m3、最速下降法主程序main1.m22212)(minxxxf0001.0,]1,1[)1(Tx初始条件)(k第一步：计算梯度程序fun1gra.mfunctionr=fun1gra(x)%最速下降法求解示例%函数f(x)=2*x1^2+x2^2的梯度的计算%r(1)=4*x(1);r(2)=2*x(2);第二步：求最优的目标函数functionr=fungetlamada(lamada)%关于lamada的一元函数，求最优步长globalx0d=fun1gra(x0);r=2*(x0(1)-lamada*d(1))^2+(x0(2)-lamada*d(2))^2;%注意负号表示是负梯度)(k第三步：主程序main1.m%最速下降方法实现一个非线性最优化问题%minf(x)=2*x1^2+x2^2globalx0x0=[11];yefi=0.0001;k=1;d=-fun1gra(x0);lamada=1;主程序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)三、Matlab求解有约束非线性规划1.用fmincon函数求解形如下面的有约束非线性规划模型一般形式：0)(0)(..)(minXcXcuXlbXAbAXtsXfeqeqeq用Matlab求解有约束非线性最小化问题求解非线性规划问题的Matlab函数为：fmincon1.约束中可以有等式约束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(fun,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=...%计算机非线性等式约束在点x处的函数值对参数nonlcon的进一步示例2个不等式约束，2个等式约束3个决策变量x1，x2，x3如果nonlcon以‘mycon1’作为参数值，则程序mycon1.m如下808060101003223132212321232221xxxxxxxxxxx对照约束条件编写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)-80808060101003223132212321232221xxxxxxxxxxxnonlcon的高级用法允许提供非线性约束条件中函数的梯度设置方法：options=optimset('GradConstr','on')如果提供非线性约束条件中函数梯度，nonlcon的函数必须如下格式：参数nonlcon的函数一般格式如下function[c,ceq,GC,GCeq]=mycon(x)c=...%计算非线性不等式约束在点x处的函数值ceq=...%计算机非线性等式约束在点x处的函数值ifnargout2%nonlcon如果四个输出参数GC=...%不等式约束的梯度GCeq=...%等式约束的梯度end输出参数语法：[x,fval]=fmincon(...)[x,fval,exitflag]=fmincon(...)[x,fval,exitflag,output]=fmincon(...)[x,fval,exitflag,output,lambda]=fmin