罚函数法(SUMT法)(ppt文档).ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,第三章 非线性规划,第六节 罚函数法,(,SUMT,法,),外点罚函数法,(,外点法,),内点罚函数法,(,内点法,),混合点罚函数法,(,混合点法,),第三章 非线性规划,一,.,外点罚函数法,(,外点法,),外点法迭代原理,外点法迭代步骤,外点法举例,外点法的优缺点,线性规划,3-6,一,.,外点法迭代原理,线性规划,3-6,一,.,外点法迭代原理,构造罚函数：,基本思想：,通过建立罚函数,将约束极值问题转化成一系列无约束极值问题去求解,.,惩罚项,罚因子,罚函数的特点：,f,(,X,)+,很大的正数,(,当,M,取值很大时,),惩罚项,可行域,D,研究,X,*,(,M,),与,(,NP,),的最优解,X,*,之间的关系,线性规划,3-6,一,.,外点法迭代原理,构造罚函数：,基本思想：,通过建立罚函数,将约束极值问题转化成一系列无约束极值问题去求解,惩罚项,罚因子,罚函数的特点：,f,(,X,)+,很大的正数,设其最优解为,X,*,(,M,),，,求解,设 最优解为,线性规划,3-6,一,.,外点法迭代原理,证明：,研究,X,*,(,M,),与NP,),的最优解,X,*,之间的关系,1,0,若,(,可行域,),，则,X,*,(,M,),是,(,NP,),最优解。,X,*,(,M,),是,(,NP,),的,最优解。,是 的最优解，有：,D,设 最优解为,线性规划,3-6,一,.,外点法迭代原理,研究,X,*,(,M,),与,(,NP,),的最优解,X,*,之间的关系,1,0,若,(,可行域,),，则,X,*,(,M,),是,(,NP,),最优解。,2,0,若,当,M,很大时，,X,*,(,M,),也会相当靠近,(,NP,),可行域,D,的边界，是,(,NP,),的最优解,X,*,的近似解,(,通常约束极值问题的最优解,X,*,在可行域的边界上,),2,0,若,当,M,很大时，,X,*,(,M,),也会相当靠近,(,NP,),可行域,D,的边界，是,(,NP,),的最优解,X,*,的近似解,线性规划,3-6,一,.,外点法迭代原理,证明：,至少存在,i,0,使,是 的最优解，,又,是局部极小值,当,M,很大时，,会相当小。,M,越大，越小，,X,*,(,M,),越靠近,D,的边界，即越靠近,X,*,。增大罚因子,M,的作用,是将,X,*,(,M,),拉向,D,的边界,(,即,X,*,),。,2,0,若,当,M,很大时，,X,*,(,M,),也会相当靠近,(,NP,),可行域,D,的边界，是,(,NP,),的最优解,X,的近似解,线性规划,3-6,一,.,外点法迭代原理,证明：,至少存在,i,0,使,当,M,很大时，有,设 最优解为,线性规划,3-6,一,.,外点法迭代原理,研究,X,*,(,M,),与,(,NP,),的最优解,X,*,之间的关系,1,0,若,(,可行域,),，则,X,*,(,M,),是,(,NP,),最优解。,2,0,若,当,M,很大时，,X,*,(,M,),也会相当靠近,(,NP,),可行域,D,的边界，是,(,NP,),的最优解,X,*,的近似解,(,通常约束极值问题的最优解,X,*,在可行域的边界上,),问题：,如何取,M,，使得,X,*,(,M,),是所需要的近似解？,线性规划,3-6,一,.,外点法迭代原理,收敛结论：,通过建立罚函数,将约束极值问题转化成,一系列,无约束极值问题去求解,.,通过迭代逐渐增大罚因子,M,：,任意给定初始点,X,(0),，初始罚因子,M,1,(=1)0,则是,(,NP,),的最优解,.,否则,M,2,=10,M,1,则是,(,NP,),的最优解,.,否则,M,3,=10,M,2,则是,(,NP,),的最优解,.,否则,M,k,+1,=10,M,k,(,NP,),的最优解,若,若,若,求解,求解,求解,第三章 非线性规划,一,.,外点罚函数法,(,外点法,),外点法迭代原理,外点法迭代步骤,外点法举例,外点法的优缺点,线性规划,3-6,二外点法迭代步骤,2,0,求 的最优解,(,用数值迭代的方法求解,),1,0,给定,X,(0),，,M,1,(=1)0,，,3,0,若,则迭代终止，,否则取,M,k,+1,=,C,M,k,其中,C,=510,令,k,:=,k,+1,转,2,0,第三章 非线性规划,一,.,外点罚函数法,(,外点法,),外点法迭代原理,外点法迭代步骤,外点法举例,外点法的优缺点,线性规划,3-6,三,.,外点法举例,例,3-18,解：,外点法，,线性规划,3-6,三,.,外点法举例,例,3-18,解：,(,用解析法,),解得：,求解,线性规划,3-6,三,.,外点法举例,例,3-18,解：,线性规划,3-6,一,.,外点法迭代原理,线性规划,3-6,外点法也适用于一般情况,:,罚函数：,因此在迭代算法中需加入,收敛结论：,等式约束的停机准则：,设其最优解为,X,(,k,),(,M,k,),(,NP,),的最优解,求解,线性规划,3-6,二,.,外点法迭代步骤,2,0,求 的最优解,(,用数值迭代的方法求解,),1,0,给定,X,(0),，,M,1,(=1)0,，,3,0,若,则迭代终止，,否则取,M,k,+1,=,C,M,k,其中,C,=510,令,k,:=,k,+1,转,2,0,第三章 非线性规划,一,.,外点罚函数法,(,外点法,),外点法迭代原理,外点法迭代步骤,外点法举例,外点法的优缺点,线性规划,3-6,四,.,外点法的优缺点,优点：,1.,方法简单,计算方便,.,2.,初始点选择容易,它可以在整个,n,维空间中选取,.,缺点：,1.,当 接近最优解 时，即罚因子,M,k,很大时，,罚函数 的性质变坏,这就使得求解,非常困难。,2.,外点法的中间结果不是可行解，不能作为近似最优,解。只有迭代到最后才能得到最优解的近似解。,第三章 非线性规划,一,.,外点罚函数法,(,外点法,),外点法迭代原理,外点法迭代步骤,外点法举例,外点法的优缺点,第三章 非线性规划,第六节 罚函数法,(SUMT,法,),外点罚函数法,(,外点法,),内点罚函数法,(,内点法,),混合点罚函数法,(,混合点法,),第三章 非线性规划,二,.,内点罚函数法,(,内点法,),内点法迭代原理,内点法迭代步骤,内点法举例,内点法的优缺点,线性规划,3-6,一,.,内点法迭代原理,构造障碍函数：,基本思想：,障碍项,障碍因子,内点法要求迭代过程始终在可行域内进行,.,为此,把初始点取在可行域内,并在可行域的边界上设置一道,“障碍”,使迭代点靠近可行域的边界时,障碍函数值迅速增大,从而使迭代点始终留在可行域的内部,.,障碍项,线性规划,3-6,一,.,内点法迭代原理,障碍函数：,障碍函数的特点：,f,(,X,)+,有限的数值，,X,接近,D,的边界,的内部,的内部,设其最优解为 的内部,线性规划,3-6一,.,内点法迭代原理,障碍函数：,障碍函数的特点：,收敛结论：,通常,(,NP,),的最优解,X,*,在,D,的边界上，为使,当 且很快时，则,求解,f,(,X,)+,有限的数值，,当,X,接近,D,的边界,第三章 非线性规划,二,.,内点罚函数法,(,内点法,),内点法迭代原理,内点法迭代步骤,内点法举例,内点法的优缺点,线性规划,3-6,二,.,内点法迭代步骤,1,0,取,r,1,0(=1),，,2,0,取,3,0,求 的最优解,(,用数值迭代的方法,),4,0,检验 是否满足收敛准则，,若满足，则迭代终止，,否则取,r,k+,1,=Cr,k,其中,C=,1/5,或,1/10,。令,kk+,1,转,3,0,当 且很快时，则,当 且很快时，,线性规划,3-6,二,.,内点法迭代步骤,收敛准则：,线性规划,3-6,二,.,内点法迭代步骤,收敛准则：,当,k,充分大时，,X,(,k,),在,X,*,的 邻域内。,线性规划,3-6,二,.,内点法迭代步骤,1,0,取,r,1,0(=1),，,2,0,取,3,0,求 的最优解,(,用数值迭代的方法,),4,0,检验 是否满足收敛准则：,若满足，则迭代终止，,否则取,r,k+,1,=Cr,k,其中,C=,1/5,或,1/10,。令,k:=k+,1,转,3,0,第三章 非线性规划,二,.,内点罚函数法,(,内点法,),内点法迭代原理,内点法迭代步骤,内点法举例,内点法的优缺点,线性规划,3-6,三,.,内点法举例,例,3-18,解：,(,解析法,),求解,解得：,线性规划,3-6,三,.,内点法举例,例,3-18,解：,第三章 非线性规划,二,.,内点罚函数法,(,内点法,),内点法迭代原理,内点法迭代步骤,内点法举例,内点法的优缺点,线性规划,3-6,四,.,内点法的优缺点,优点：,由于迭代点总是在可行域内进行,每一个中间结果都是一个可行解,因此,中间停机的结果可作为近似解,.,缺点：,1.,选取初始可行点困难；,2.,只能求解不等式约束问题。,第三章 非线性规划,二,.,内点罚函数法,(,内点法,),内点法迭代原理,内点法迭代步骤,内点法举例,内点法的优缺点,第三章 非线性规划,第六节 罚函数法,(SUMT,法,),外点罚函数法,(,外点法,),内点罚函数法,(,内点法,),混合点罚函数法,(,混合点法,),线性规划,3-6,三,.,混合点法,基本思想：,内点法只能求解不等式约束问题,而外点法可以求解等式约束问题,.,混合点法是用内点法来处理不等式约束,用外点法来处理等式约束的一种罚函数法,.,构造罚函数：,收敛结论：,求解,的最优解,在迭代中，令,第三章 非线性规划,第六节 罚函数法,(SUMT,法,),外点罚函数法,(,外点法,),内点罚函数法,(,内点法,),混合点罚函数法,(,混合点法,),作业：,P246 22(2)23(2),作业：,P203 3(2)4(2),