罚函数法(SUMT法)课件

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

2、外点法迭代原理构造罚函数：基本思想：通过建立罚函数,将约束极值问题转化成一系列无约束极值问题去求解惩罚项罚因子罚函数的特点：f (X) + 很大的正数,设其最优解为 X*(M)，求解第5页，共42页。设 最优解为线性规划3-6一.外点法迭代原理证明：研究 X*(M) 与(NP)的最优解 X* 之间的关系10 若 (可行域)，则 X *(M) 是 (NP) 最优解。X*(M) 是(NP)的最优解。是 的最优解， 有：D第6页，共42页。设 最优解为线性规划3-6一.外点法迭代原理研究 X*(M) 与(NP)的最优解 X* 之间的关系10 若 (可行域)，则 X *(M) 是 (NP) 最优解。2

3、0 若 当M很大时， X *(M)也会相当靠近(NP) 可行域D的边界， 是(NP)的最优解X *的近似解(通常约束极值问题的最优解X *在可行域的边界上)第7页，共42页。20 若 当M很大时， X *(M)也会相当靠近(NP) 可行域D的边界， 是(NP)的最优解X *的近似解线性规划3-6一.外点法迭代原理证明：至少存在 i0 使是 的最优解，又是局部极小值当M很大时，会相当小。第8页，共42页。M越大， 越小，X*(M) 越靠近D的边界，即越靠近X*。 增大罚因子M的作用是将X*(M)拉向D的边界(即X*)。20 若 当M很大时， X *(M)也会相当靠近(NP) 可行域D的边界， 是

4、(NP)的最优解X *的近似解线性规划3-6一.外点法迭代原理证明：至少存在 i0 使当M很大时，有第9页，共42页。设 最优解为线性规划3-6一.外点法迭代原理研究 X*(M) 与(NP)的最优解 X* 之间的关系10 若 (可行域)，则 X *(M) 是 (NP) 最优解。20 若 当M很大时， X *(M)也会相当靠近(NP) 可行域D的边界， 是(NP)的最优解X *的近似解(通常约束极值问题的最优解X *在可行域的边界上)问题：如何取M，使得X*(M)是所需要的近似解？第10页，共42页。线性规划3-6一.外点法迭代原理收敛结论：通过建立罚函数,将约束极值问题转化成一系列无约束极值问

5、题去求解.通过迭代逐渐增大罚因子M：任意给定初始点X(0)，初始罚因子M1(=1)0则是(NP)的最优解. 否则M2=10M1则是(NP)的最优解. 否则M3=10M2则是(NP)的最优解. 否则Mk+1=10Mk(NP)的最优解若若若求解求解求解第11页，共42页。第三章 非线性规划一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举例外点法的优缺点 第12页，共42页。线性规划3-6二.外点法迭代步骤20 求 的最优解(用数值迭代的方法求解)10 给定X(0)，M1(=1)0， 30 若则迭代终止，否则取Mk+1=C Mk , 其中C = 510 令 k:= k+1 转20第13

6、页，共42页。第三章 非线性规划一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举例外点法的优缺点 第14页，共42页。线性规划3-6三.外点法举例例3-18解：外点法，第15页，共42页。线性规划3-6三.外点法举例例3-18解：(用解析法)解得：求解第16页，共42页。线性规划3-6三.外点法举例例3-18解：第17页，共42页。线性规划3-6一.外点法迭代原理第18页，共42页。线性规划3-6外点法也适用于一般情况:罚函数：因此在迭代算法中需加入收敛结论：等式约束的停机准则：设其最优解为 X (k) (Mk)(NP)的最优解求解第19页，共42页。线性规划3-6二.外点法迭代

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

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

9、可行域的边界时,障碍函数值迅速增大,从而使迭代点始终留在可行域的内部.障碍项第26页，共42页。线性规划3-6一.内点法迭代原理障碍函数：障碍函数的特点：f (X) + 有限的数值，X 接近D的边界的内部第27页，共42页。的内部设其最优解为 的内部线性规划3-6一.内点法迭代原理障碍函数：障碍函数的特点：收敛结论：通常(NP) 的最优解 X * 在D的边界上，为使当 且很快时，则求解f (X) + 有限的数值，当X接近D的边界第28页，共42页。第三章 非线性规划二.内点罚函数法(内点法)内点法迭代原理内点法迭代步骤内点法举例内点法的优缺点 第29页，共42页。线性规划3-6二.内点法迭代步

10、骤10 取r10(=1)， 20 取30 求 的最优解(用数值迭代的方法)40 检验 是否满足收敛准则，若满足，则迭代终止，否则取rk+1 = Crk ,其中C = 1/5或1/10。令k:=k+1转30当 且很快时，则第30页，共42页。当 且很快时，线性规划3-6二.内点法迭代步骤收敛准则：第31页，共42页。线性规划3-6二.内点法迭代步骤收敛准则：当k充分大时，X(k)在X*的 邻域内。第32页，共42页。线性规划3-6二.内点法迭代步骤10 取r10(=1)， 20 取30 求 的最优解(用数值迭代的方法)40 检验 是否满足收敛准则：若满足，则迭代终止，否则取rk+1 = Crk

11、,其中C = 1/5或1/10。令k:=k+1转30第33页，共42页。第三章 非线性规划二.内点罚函数法(内点法)内点法迭代原理内点法迭代步骤内点法举例内点法的优缺点 第34页，共42页。线性规划3-6三.内点法举例例3-18解：(解析法)求解解得：第35页，共42页。线性规划3-6三.内点法举例例3-18解：第36页，共42页。第三章 非线性规划二.内点罚函数法(内点法)内点法迭代原理内点法迭代步骤内点法举例内点法的优缺点 第37页，共42页。线性规划3-6四.内点法的优缺点优点： 由于迭代点总是在可行域内进行,每一个中间结果都是一个可行解,因此,中间停机的结果可作为近似解.缺点：1. 选取初始可行点困难；2. 只能求解不等式约束问题。第38页，共42页。第三章 非线性规划二.内点罚函数法(内点法)内点法迭代原理内点法迭代步骤内点法举例内点法的优缺点 第39页，共42页。第三章 非线性规划第六节 罚函数法(SUMT法)外点罚函数法(外点法)内点罚函数法(内点法)混合点罚函数法(混合点法) 第40页，共42页。线性规划3-6三.混合点法基本思想： 内点法只能求解不等式约束问题,而外点法可以求解