罚函数法(SUMT法).ppt

《罚函数法(SUMT法).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章非线性规划第六节罚函数法(SUMT法)外点罚函数法(外点法)内点罚函数法(内点法)混合点罚函数法(混合点法)第三章非线性规划一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举例外点法的优缺点线性规划3-6一.外点法迭代原理线性规划3-6一.外点法迭代原理构造罚函数：基本思想：通过建立罚函数,将约束极值问题转化成一系列无约束极值问题去求解.惩罚项罚因子罚函数的特点：f(X)+很大的正数,(当M取值很大时)惩罚项可行域D研究X*(M)与(NP)的最优解X*之间的关系线性规划3-6一.外点法迭代原理构造罚函数：基本思想：通过建立罚函数,将约束极值问题转化成一系列无约束极

2、值问题去求解惩罚项罚因子罚函数的特点：f(X)+很大的正数,设其最优解为X*(M)，求解设最优解为线性规划3-6一.外点法迭代原理证明：研究X*(M)与(NP)的最优解X*之间的关系10若(可行域)，则X*(M)是(NP)最优解。X*(M)是(NP)的最优解。是的最优解，有：D设最优解为线性规划3-6一.外点法迭代原理研究X*(M)与(NP)的最优解X*之间的关系10若(可行域)，则X*(M)是(NP)最优解。20若当M很大时，X*(M)也会相当靠近(NP)可行域D的边界，是(NP)的最优解X*的近似解(通常约束极值问题的最优解X*在可行域的边界上)20若当M很大时，X*(M)也会

3、相当靠近(NP)可行域D的边界，是(NP)的最优解X*的近似解线性规划3-6一.外点法迭代原理证明：至少存在i0使是的最优解，又是局部极小值当M很大时，会相当小。M越大，越小，X*(M)越靠近D的边界，即越靠近X*。增大罚因子M的作用是将X*(M)拉向D的边界(即X*)。20若当M很大时，X*(M)也会相当靠近(NP)可行域D的边界，是(NP)的最优解X*的近似解线性规划3-6一.外点法迭代原理证明：至少存在i0使当M很大时，有设最优解为线性规划3-6一.外点法迭代原理研究X*(M)与(NP)的最优解X*之间的关系10若(可行域)，则X*(M)是(NP)最优解。20若当M很大时，X

4、*(M)也会相当靠近(NP)可行域D的边界，是(NP)的最优解X*的近似解(通常约束极值问题的最优解X*在可行域的边界上)问题：如何取M，使得X*(M)是所需要的近似解？线性规划3-6一.外点法迭代原理收敛结论：通过建立罚函数,将约束极值问题转化成一系列无约束极值问题去求解.通过迭代逐渐增大罚因子M：任意给定初始点X(0)，初始罚因子M1(=1)>0则是(NP)的最优解.否则M2=10M1则是(NP)的最优解.否则M3=10M2则是(NP)的最优解.否则Mk+1=10Mk(NP)的最优解若若若求解求解求解第三章非线性规划一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举

5、例外点法的优缺点线性规划3-6二.外点法迭代步骤20求的最优解(用数值迭代的方法求解)10给定X(0)，M1(=1)>0，30若则迭代终止，否则取Mk+1=CMk,其中C=5~10令k:=k+1转20第三章非线性规划一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举例外点法的优缺点线性规划3-6三.外点法举例例3-18解：外点法，线性规划3-6三.外点法举例例3-18解：(用解析法)解得：求解线性规划3-6三.外点法举例例3-18解：线性规划3-6一.外点法迭代原理线性规划3-6外点法也适用于一般情况:罚函数：因此在迭代算法中需加入收敛结论：等式约束的停机准则：设其最优

6、解为X(k)(Mk)(NP)的最优解求解线性规划3-6二.外点法迭代步骤20求的最优解(用数值迭代的方法求解)10给定X(0)，M1(=1)>0，30若则迭代终止，否则取Mk+1=CMk,其中C=5~10令k:=k+1转20第三章非线性规划一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举例外点法的优缺点线性规划3-6四.外点法的优缺点优点：1.方法简单,计算方便.2.初始点选择容易,它可以在整个n维空间中选取.缺点：1.当接近最优解时，即罚因子Mk很大时，罚函数的性质变坏,这就使得求解非常困难。2.外点法的中间结果不是可行解，不能作为近似最优解。只有迭代到最后才能得到

7、最优解的近似解。第三章非线性规划一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举例外点法的优缺点第三章非线性规划第六节罚函数法(SUMT法)外点罚函数法(外点法)内点罚函数法(内点法)混合点罚函数法(混合点法)第三章非线性规划二.内点罚函数法(内点法)内点法迭代原理内点法迭代步骤内点法举例内点法的优缺点线性规划3-6一.内点法迭代原理构造障碍函数：基本思想：障碍项障碍因子内点法要求迭代过程始终在可行域内进行.为此,把初始点取在可行域内,并在可行域的边界上