非线性规划的基本解法 SUTM外点法 1、罚函数法 SUTM内点法(障碍罚函数法 2、近似规划法 返回
6 非线性规划的基本解法 SUTM外点法 SUTM内点法（障碍罚函数法） 1、罚函数法 2、近似规划法 返回
罚函数法 罚函数法基本思想是通过构造罚函数把 约束问题转化为一系列无约束最优化问题, 进而用无约東最优化方法去求解.这类方法 称为序列无约束最小化方法.简称为SUMT 法 其一为SUMT外点法,其二为SUMT内点 法
7 罚函数法 罚函数法基本思想是通过构造罚函数把 约束问题转化为一系列无约束最优化问题， 进而用无约束最优化方法去求解．这类方法 称为序列无约束最小化方法．简称为SUMT 法． 其一为SUMT外点法，其二为SUMT内点 法．
SUTM外点法 对一般的非线性规划:minf(X) g(x)≥0i s t X)=0 可设:(x,M)=f(x)+M∑[m(0g()+M∑(x)(2) 将问题①)转化为无约束间题:mnT(X,M) (3) X∈E 其中T(X,M)称为罚函数,M称为罚因子,带M的项称为罚项,这 里的罚函数只对不满足约束条件的点实行惩罚:X∈D时,满 足g:(X)≥02(X)=0,故罚项=0,不受惩罰.X≠D时, 8(X)<0或h(X)≠0的约束条件,故罚项>0,要受惩罚
8 ( , ) ( ) min (0, ( )) ( ) (2) 1 2 1 2 = = = + + l j j m i 可设：T X M f X M gi X M h X 1 min T(X,M ) (3) n XE 将问题（）转化为无约束问题： 其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这 里的罚函数只对不满足约束条件的点实行惩罚：当 时，满 足各 ，故罚项=0，不受惩罚．当 时， 必有 的约束条件，故罚项>0，要受惩罚． X D gi (X) 0,hi (X) = 0 X D gi (X ) 0或hi (X ) 0 SUTM外点法 ( ) ( ) ( ) (1) 0 1,2,..., . 0 1,2,..., m; . . min = = = h X j l g X i st f X j i 对一般的非线性规划：
STM外点法(罚函数法)的迭代步骤 、任意给定初始点X0,取M》1,给定允许误差ε>0,令k=1 2、求无约束极值问题mn(x4)的最优解,设为x=XM),即 min T(X, M)=T(Xk, MK) X∈En 3、若存在≤≤m,使-8(x)>,则取M>M(M41=aM=10) 令k-k+1返回(2),否则,停止迭代.得最优解x*≈xk 计算时也可将收敛性判别准则-8(x)>6改为M>m(0g(x)0 罚函数法的缺点是:每个近似最优解Ⅹ往往不是容许解, 而只能近似满足约束,在实际问题中这种结果可能不能使用; 在解一系列无约束问题中,计算量太大,特别是随着M的增大, 可能导致错误
9 罚函数法的缺点是：每个近似最优解X k往往不是容许解， 而只能近似满足约束，在实际问题中这种结果可能不能使用； 在解一系列无约束问题中，计算量太大，特别是随着Mk的增大， 可能导致错误． 1、任意给定初始点X 0，取M1>1，给定允许误差 ，令k=1； 2、求无约束极值问题 的最优解，设为X k=X(Mk)，即 ； 3、若存在 ，使 ，则取Mk>M( ) 令k=k+1返回（2），否则，停止迭代．得最优解 . 计算时也可将收敛性判别准则 改为 . 0 T(X M ) n X E min , min ( , ) ( , ) k k X E T X M T X M n = i(1 i m) − ( ) k gi X Mk+1 = M, =10 min(0, ( )) 0 1 2 = m i M gi X k X X * − ( ) k gi X SUTM外点法(罚函数法)的迭代步骤
SUTM内点法(障碍函数法) 考虑问题: min 8:(X)≥0i=1,2.,m() 设集合D={X|g(X)>0,i=1,2,…,m}≠如,D是可行域中 所有严格内点的集 构造障碍函数 I(X,T)(x,r)=f(X)+∑ng(x)或1(X,r)=f(X)+∑ 8 其中称∑ng(X)或戊。1为障碍项,r为障碍因子 g 这样问题(1)就转化为求一系列极值问题: min(Xk)得X(nk) X∈D
10 ( ) ( ) (1) . . 0 1,2,..., min i st g X = m f X i 考虑问题： ( ) 所有严格内点的集合。 设集合D 0 = X | gi X 0,i =1,2,,m ，D 0 是可行域中 ( ) ( ) ( ) ( ) ( ) ( ) ( ) 其中称 或 为障碍项， 为障碍因子 ： 或 构造障碍函数 r g X r g X r g X I X r I X r f X r g X I X r f X r m i i m i i m i i m i i = = = = = + = + 1 1 1 1 1 ln 1 , , ln ( , ) ( ) ( ) 得 （ ） 这样问题（）就转化为求一系列极 值问题： k k k X D I X r X r min , 1 0 SUTM内点法（障碍函数法）