4 非线性规划

《4 非线性规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、非线性规划东北大学数学系王琪wangqimath@hotmail.com优化问题•优化问题一般形式：minf(x)s.t.h(x)£0,j=1,,qjg(x)=0,i=1,,piT其中，，x=[x1xn]f(x)称为目标函数，h(x)≤0称为不等式约束，g(x)=0称ji为等式约束。优化问题的分类•根据目标函数和约束条件的函数的类型，优化问题可以分为：线性规划问题、非线性规划问题。Ø线性规划问题：目标函数和约束条件中所有函数均为线性（即变量的次数不超过1）Ø非线性规划问题：目标函数或约束条件中至少有一个非线性函数（在

2、非线性规划问题中，将一类特殊的规划问题——目标函数为二次函数的优化问题命名为二次规划）。优化问题的分类•根据有无约束条件，分为无约束最优化问题和有约束最优化问题。•根据自变量的类型，分为：一般最优化问题、整数规划问题、混合整数规划问题、0-1规划问题。•根据目标函数的多少，分为：单目标优化问题和多目标优化问题。非线性规划问题的基本解法•1、罚函数法ØSUTM外点法ØSUTM内点法（障碍罚函数法）•2、近似规划法罚函数法•罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解．这

3、类方法称为序列无约束最小化方法．简称为SUMT法．•其一为SUMT外点法，其二为SUMT内点法．SUTM外点法对一般的非线性规划：minf(X)ìgi()X³0i=1,2,...,m;s.t.í(1)h()X=0j=1,2,...,l.îjml22可设：T(X,M)=f(X)+M[]min()0,g()X+M[]h()X(2)åiåji=1j=1将问题（1）转化为无约束问题：minT(X,M)(3)nXÎE其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当时XÎD，满

4、足各gi(X)³0,hi(X)=0，故罚项=0，不受惩罚．当时XÏD，必有gi(X)<0或hi(X)¹0的约束条件，故罚项>0，要受惩罚．SUTM外点法(罚函数法)的迭代步骤1、任意给定初始点X0，取M>1，给定允许误差e>0，令k=1；12、求无约束极值问题minT(X,M)的最优解，设为Xk=X(M)，即nkXÎEkminT(X,M)=T(X,Mk)；nXÎEk3、若存在，i(1£i£m)使-gi(X)>e，则取M>M()Mk+1=aM,a=10k令k=k+1返回（2），否则，停止迭代．得最优解*k.X»Xm-g(Xk

5、)>e2计算时也可将收敛性判别准则改i为Må[]min()0,gi()X£0.i=1罚函数法的缺点是：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着M的增k大，可能导致错误。SUTM内点法（障碍函数法）ìminf(X)考虑问题：í()(1)îs.t.giX³0i=1,2,...,m0{()}0设集合D=X

6、giX>0,i=1,2,,m¹f，D是可行域中所有严格内点的集合。构造障碍函数mm1I(X,r)：I(X,r)=f(X)+råln

7、gi()X或I(X,r)=f(X)+råi=1i=1gi()Xmm1其中称rålngi()X或rå为障碍项，r为障碍因子i=1i=1gi()X这样问题（1）就转化为求一系列极值问题：()kminIX,r得X（r）kk0XÎDSUTM内点法的迭代步骤(1)给定允许误差e>0，取r>0,0

8、iki=1i=1g()Xi*k足，停止迭代，X»X；否则取r=br，令k=k+1，k+1k返回(3）．近似规划法近似规划法的基本思想：将问题(3)中的目标函数f(X)g(X)³0(i=1,...,m);h(X)=0(j=1,,l)和约束条件ij近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为(3)的解的近似．每得到一个近似解后，都从这点出发，重复以上步骤．这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往

9、收敛于非线性规划问题的解。近似规划法的算法步骤如下(1)给定初始可行点1{111}1X=x,x,,x，步长限制d(j=1,,n)，12nj步长缩小系数bÎ()0,1，允许误差e，令k=1；k(2)在点X处，将f(X)，g(X),h(X)按泰勒级数展开并ij取一阶近似，得到近似线性规划问题：kkTkm