非线性规划课件

数学建模与数学实验参考书目：赵静但琦－数学建模于数学实验，高等教育出版社，2005非线性规划

西安电子科技大学数学与统计学院李伟1例1：约束回归某大学希望为它的毕业生安排工作位置。为简单起见，假设每个毕业生接受政府部门、工业界或科学院中的一个位置。令：2最小，模型可表示为：3解设投资决策变量4

定义

目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题．非线性规划的基本概念

一般形式:

（1）其中，是定义在En上的实值函数，简记:

其它情况:

求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式．5

定义1

把满足问题（1）中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即问题(1)可简记为．定义2

对于问题(1)，设，若存在,使得对一切，且，都有，则称X*是f(X)在D上的局部极小值点（局部最优解）．特别地当时，若则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）．定义3对于问题(1),设,对任意的,都有则称X*是f(X)在D上的全局极小值点（全局最优解）．特别地当时，若，则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）．6非线性规划的基本解法SUTM外点法SUTM内点法（障碍罚函数法）1、罚函数法2、近似规划法7

罚函数法

罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解．这类方法称为序列无约束最小化方法．简称为SUMT法．其一为SUMT外点法，其二为SUMT内点法．8

其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当时，满足各，故罚项=0，不受惩罚．当时，必有的约束条件，故罚项>0，要受惩罚．SUTM外点法9

罚函数法的缺点是：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误．1、任意给定初始点X0，取M1>1，给定允许误差，令k=0；2、求无约束极值问题的最优解，设为Xk=X(Mk)，即；3、若存在使则取Mk+1>Mk()令k=k+1返回（2），否则，停止迭代．得最优解.SUTM外点法(罚函数法)的迭代步骤10SUTM内点法（障碍函数法）11

内点法的迭代步骤12

近似规划法的基本思想：将问题(1)中的目标函数和约束条件近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为(1)的解的近似．近似规划法每得到一个近似解后，都从这点出发，重复以上步骤．

这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。13

近似规划法的算法步骤如下1415Matlab求解有约束非线性规划1.用fmincon函数求解形如下面的有约束非线性规划模型一般形式：用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(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如下对照约束条件编写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)-80nonlcon的高级用法允许提供非线性约束条件中函数的梯度设置方法：options=optimset('GradConstr','on')

如果提供非线性约束条件中函数梯度，nonlcon的函数必须如下格式：参数nonlcon的函数一般格式如下function[c,ceq,GC,GCeq]=mycon(x)c=...

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

ceq=...

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

ifnargout>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(...)[x,fval,exitflag,output,lambda,grad,hessian]=fmincon(...)运用步骤：将自己的模型转化为上面的形式写出对应的参数调用函数fmincon应用求解示例：请问：1、结合fmincon函数，需要提供哪些参数第一步：编写一个M文件返回目标函数f在点x处的值函数程序functionf=myfun(x)f=-x(1)*x(2)*x(3);函数myfun.m第二步：为了调用MATLAB函数，必须将模型中的约束转化为如下形式(<=)。

这里：A=[-1-2-2;122];b=[072]’;这是2个线性约束，形如第三步：提供一个搜索起点，然后调用相应函数，程序如下：%给一个初始搜索点 x0=[10;10;10];[x,fval]=fmincon('m