求解非线性规划

1、非线性规划的实例与定义如果目标函数或约束条件中包含非线性函数， 就称这种规划问题为非线性规 划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象 线性规划有单纯形法这一通用方法， 非线性规划目前还没有适于各种问题的一般 算法，各个方法都有自己特定的适用范围。1.2 线性规划与非线性规划的区别如果线性规划的最优解存在， 其最优解只能在其可行域的边界上到达 特别 是可行域的顶点上到达 ；而非线性规划的最优解如果最优解存在那么可能在 其可行域的任意一点到达。1.3 非线性规划的 Matlab 解法Matlab 中非线性规划的数学模型写成以下形式min f (x)Ax BAeq x

2、BeqC(x) 0Ceq( x ) 0其中f(x)是标量函数，A,B,Aeq,Beq是相应维数的矩阵和向量，C(x),Ceq(x)是 非线性向量函数。Matlab 中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)它的返回值是向量x，其中FUN是用M文件定义的函数f(x) ；X0是x的初始值;A,B,Aeq,Beq 定义了线性约束 A* X B,Aeq*X Beq ，如果没有等式约束，那么 A=,B=,Aeq=,Beq=; LB和UB是变量x的下界和上界，如果上界和下界没有约束，那么LB=，UB=，如果x无下界，那么LB=-inf，

3、如果x无上界，那么UB=inf;NONLCO是用 M文件定义的非线性向量函数 C(x),Ceq(x) ； OPTION定义了优化参数，可以使用 Matlab 缺省的参数设置 例 2 求以下非线性规划问题22min f(x) x1x28x12 x2 02x1 x22 0x1,x2 0.i丨编写M文件function f=fun1(x);f=x(12+x (2)八2+8;和M文件function g,h=fun2(x);g=-x(1)A2+x(2);h=-x(1)-x (2)A2+2; %等式约束 ii 在 Matlab 的命令窗口依次输入options=optimset;x,y=fmincon(

4、 'fun1' ,rand(2,1),zeros(2,1),.'fun2' , options)就可以求得当 x11,x21时，最小值 y 10。1.4 求解非线性规划的根本迭代格式记NP的可行域为K 0假设 x* K ，并且f(x*)f(x), x K那么称x*是NP的整体最优解，f(x*)是(NP)的整体最优值。如果有f (x* ) f (x), x K,x x*那么称x*是NP的严格整体最优解，f(x*)是(NP)的严格整体最优值。假设x* K，并且存在x*的邻域N (x*)，使f (x*)f(x), x N (x*) K , * *那么称x是NP的局部最

5、优解，f(x )是(NP)的局部最优值。如果有f (x*) f (x), x N (x*) K那么称x*是NP的严格局部最优解，f(x*)是(NP)的严格局部最优值。由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是整个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一局部 可行域上的极值点，但并不一定是整个可行域上的全局最优解。对于非线性规划模型(NP)，可以采用迭代方法求它的最优解。迭代方法的根本 思想是：从一个选定的初始点 x Rn出发，按照某一特定的迭代规那么产生一个 点列xk，使得当xk是有穷点列时，其最后一个点是(NP)的最优解；当xk是 无穷点列时，

6、它有极限点，并且其极限点是(NP)的最优解。设xk Rn是某迭代方法的第k轮迭代点，xk 1 Rn是第k 1轮迭代点，记xk 1 xk tkpk 1这里tk R1,pk Rn, Pk 1，显然pk是由点xk与点xk 1确定的方向。式1 就是求解非线性规划模型(NP)的根本迭代格式。通常，我们把根本迭代格式1中的pk称为第k轮搜索方向，tk为沿pk方向 的步长，使用迭代方法求解(NP)的关键在于，如何构造每一轮的搜索方向和确定 适当的步长。设x Rn,p 0，假设存在0，使f (x tp) f (x), t (0,)，称向量p是f在点x处的下降方向。设x Rn, p 0，假设存在t 0，使x t

7、p K，称向量p是点x处关于K的可行方向一个向量p，假设既是函数f在点x处的下降方向，又是该点关于区域 K的可 行方向，那么称之为函数f在点X处关于K的可行下降方向。现在，我们给出用根本迭代格式1求解(NP)的一般步骤如下：0选取初始点x0，令k: 0。1构造搜索方向，依照一定规那么，构造f在点xk处关于K的可行下降方向作为搜索方向pk。2寻求搜索步长。以xk为起点沿搜索方向pk寻求适当的步长tk，使目标函数 值有某种意义的下降。3求出下一个迭代点。按迭代格式1求出k 1k丄kX X tkP。假设xk 1已满足某种终止条件，停止迭代4 以xk 1代替xk，回到1步。1.5 凸函数、凸规划设f(x)为定义在n维欧氏空间E(n)中某个凸集R上的函数，假设对任何实数(01)以及R中的任意两点x和X(2)，恒有f ( x(1) x(2)f(x)(1)f (x(2)那么称f (x)为定义在R上的凸函数。假设对每一个(01)和xx(2) R恒有f ( X(1) x(2) f(x)(1)f(x)那么称f(x)为定义在R上的严格凸函数。考虑非线性规划mxiRn f(x)R x|gj(x) 0, j 1,2, ,l假定其中f (x)为凸函数，gj(x)( j 1,2,1)为凸函数，这样的非线性规划称