约束优化方法ppt课件.ppt

《约束优化方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《约束优化方法ppt课件.ppt（150页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、有约束的优化方法有约束的优化方法 5-1 5-1 约束最优解及其一阶必要条件约束最优解及其一阶必要条件 5-25-2 随机方向法随机方向法 5-35-3 复合形法复合形法 5-4-15-4-1 内惩罚函数法内惩罚函数法 5-4-25-4-2 外惩罚函数法外惩罚函数法 5-4-3 5-4-3 混合惩罚函数法混合惩罚函数法第五章第五章 约束优化方法约束优化方法约束最优解（约束最优解（a）5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件约束最优解（约束最优解（b）5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件约束最优解（约束最优解（c）5-1 5-1 约束最优解及其必要条件

2、约束最优解及其必要条件5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件约束优化问题的最优性条件：在满足等式和不等式约束约束优化问题的最优性条件：在满足等式和不等式约束条件下，其目标函数值最小的点所必需满足的条件。条件下，其目标函数值最小的点所必需满足的条件。 （局部最优解）（局部最优解）最优点可能出现的情况：最优点可能出现的情况：1）在可行域内部）在可行域内部2）在约束边界上）在约束边界上约束最优解约束最优解5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件约束最优解的搜索路线约束最优解的搜索路线 约束优化问题的最优性条件：在满足等式和不等式约束约束优化问题的最优性条件：

3、在满足等式和不等式约束条件下，其目标函数值最小的点所必需满足的条件。条件下，其目标函数值最小的点所必需满足的条件。约束优化设计问题数学模型为约束优化设计问题数学模型为: :min( ),. .( )01,2,( )01,2,njkfRst gjmhklxxxx5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件x(k)不是约束最优点不是约束最优点单起作用约束条件极小点的必要条件单起作用约束条件极小点的必要条件x(k)是约束最优点是约束最优点)()(kxg5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件因而得出单约束条件极小点的必要条件可以因而得出单约束条件极小点的必要条件可

4、以表示成：表示成：)()()()(xxgf05-1 5-1 约束最优解及其必要条件约束最优解及其必要条件)(k5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件两个起作用约束条件极小点的必要条件两个起作用约束条件极小点的必要条件x(k)不是约束最优点不是约束最优点x(k)是约束最优点是约束最优点x)()(kxf)()(1kg x)()(2kgx)()(1kgx)()(2kgx)()(kxf5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件若若x(k)为约束最优点为约束最优点x*，约束条件极小点的必要条件，约束条件极小点的必要条件可以表示成：可以表示成：0, 0)()()(2

5、1)(22)(11)(xxxggf它的几何意义：如果它的几何意义：如果x*是一个局部极小点，则该点是一个局部极小点，则该点的目标函数梯度应落在该点的目标函数梯度应落在该点起作用约束的梯度起作用约束的梯度所组成所组成的锥角之内。的锥角之内。几何意义：如果几何意义：如果x(k)是一个局部极小点，则该点的目是一个局部极小点，则该点的目标函数梯度应落在该点标函数梯度应落在该点起作用约束起作用约束的梯度所组成的锥的梯度所组成的锥角之内。角之内。x(k)不是约束最优点不是约束最优点x(k)是约束最优点是约束最优点5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件推广到推广到n维设计空间的具有维设

6、计空间的具有m个不等式约束的问题，个不等式约束的问题，即为检验约束优化问题局部最优点的著名的即为检验约束优化问题局部最优点的著名的K-T条件：条件：JugfuJukuuk, 2 , 10)()(1)()(xxJuxxgxxfuJuikuuik, 2 , 10)()(1)()(或：或：即只有当即只有当u u为非负乘子时，为非负乘子时， x x(k(k) )才是约束最优点才是约束最优点x x* *。5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件K-T条件对于约束问题的重要性在于：条件对于约束问题的重要性在于：1）检验某点是否

7、为约束最优点；）检验某点是否为约束最优点；2）检验一种搜索方法是否可行。）检验一种搜索方法是否可行。例例1 1：判断：判断x x(k(k) )=1 0=1 0T T是否为下列约束优化问题最优点：是否为下列约束优化问题最优点：01),(0),(0),(. .)2(),(min22121322121211222121xxxxgxxxgxxxgtsxxxxf5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件01),(0),(0),(. .)2(),(min22121322121211222121xxxxgxxxgxxxgtsxxxxf解：解：1）判断）判断该点起作用约束：该点起作用约束：0

8、1),(211xxg0),(212xxg0),(213xxg2）计算目标函数及）计算目标函数及起作用起作用约束在该点梯度：约束在该点梯度：022)2(2)()(21)(kxkxxf x10)()(2kgx1212)()(1)(3kxgkxx5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件2）计算目标函数及）计算目标函数及起作起作用约束在该点梯度：用约束在该点梯度：022)2(2)()(21)(kxkxxf x10)()(2kgx1212)()(1)(3kxgkxx3）代入）代入K-T条件，求乘子条件，求乘子：)()()()(33)(22)(kkkggfxxx12100232解得解得

9、：1, 132因此判断该点是约束最优点。因此判断该点是约束最优点。5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件01),(0),(0),(. .) 2(),(min22121322121211222121xxxxgxxxgxxxgt sxxxxf5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件0)1 (),(0),(0),(. .) 2(),(min31221322121211222121xxxxgxxxgxxxgt sxxxxf练习：练习：判断判断x(k)=1 0T是否为下列约束优化问题的最优点：是否为下列约束优化问题的最优点：答案：乘子无解，故非最优点。答案：乘子

10、无解，故非最优点。5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件对于仅有等式约束的优化设计问题，以一个对于仅有等式约束的优化设计问题，以一个等式约束为例：等式约束为例：)()()(xxxhhf0)(xh可以写成：可以写成：0)(0)(xxhh从而得出等式约束问题的从而得出等式约束问题的K-TK-T条件：条件：)()(xxhf即：即：5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件从而得出多个等式约束问题从而得出多个等式约束问题pvvvhf1)()(xxpvhv, 10)(xK-TK-T条件：条件：5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件因此，容易得

11、出对于具有等式约束和不因此，容易得出对于具有等式约束和不等式约束的优化设计问题，其约束最优等式约束的优化设计问题，其约束最优点的一阶必要条件：点的一阶必要条件：JuJughgfuupvvvJuuu00)()()()(11xxxx 是多元函数取得约束极值的是多元函数取得约束极值的, ,以用来作为约束极值的判断条件。以用来作为约束极值的判断条件。 这种这种情况情况K-TK-T条件即为多元函数取得约束极值的充分条件即为多元函数取得约束极值的充分必要条件。必要条件。5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件（1 1）直接法）直接法 直接法是在满足不等式约束的可行设计区域内直直接法是在

12、满足不等式约束的可行设计区域内直接搜索问题的最优解接搜索问题的最优解x x* *和和f f( (x x* *) )。 （2 2）间接法）间接法 间接法是将优化问题转化为一系列无约束优化问间接法是将优化问题转化为一系列无约束优化问题来求解。题来求解。 约束优化设计问题求解方式约束优化设计问题求解方式: : 直接解法思路直接解法思路: :1(0,1,2,)kkkkdkxxkkd步长步长 可行搜索方向可行搜索方向 可行可行搜索方向搜索方向:当设计点沿该方向作微量移动时，当设计点沿该方向作微量移动时，目标函数值将下降，且目标函数值将下降，且不会越出可行域不会越出可行域。 5-2 5-2 随机方向法随机

13、方向法 随机方向法基本原理随机方向法基本原理1 1 初始点的选择初始点的选择 1) 人为确定；人为确定； 2) 随机选择：随机选择：(1(1) )输入设计变量的下限值和上限值，即输入设计变量的下限值和上限值，即 aixibi (i=1,2,n)(2)(2)产生产生n n个随机数个随机数qi. （ 0 qi 1）(3)(3)计算随机点计算随机点x x的各分量：的各分量： xi=ai+qi(bi-ai)(4)(4)判别随机点判别随机点x x是否可行，若随机点是否可行，若随机点x x为可行点，则取初始为可行点，则取初始点点 x x0 0=x=x；若随机点；若随机点x x为非可行点，则转步骤为非可行点

14、，则转步骤2)2)重新计算，直重新计算，直到到 产生的随机点是可行点为止。产生的随机点是可行点为止。1) 在在-1,1区间内产生随机数区间内产生随机数ri (i=1,2,n)12iir 计算随机单位向量计算随机单位向量snniirrrr21121e2)取一试验步长取一试验步长，按下式计算，按下式计算k个随机点个随机点: ), 2 , 1(0kjxxjje2 2 随机方向的产生随机方向的产生同样方法计算出同样方法计算出k个随机单位向量（个随机单位向量（kn）5-2 5-2 随机方向法随机方向法3)检验检验k个随机点的个随机点的可行性可行性，比较其大小，选，比较其大小，选出目标函数值最小的点出目标

15、函数值最小的点xL。4)比较两点比较两点xL和和x0的目标函数值的目标函数值(适用性适用性)：0 xxLd则将步长缩小，转步骤则将步长缩小，转步骤2)重新计算重新计算 )()()0(xxffL若若则则若若)()()0(xxffL1)选择一个可行的初始点选择一个可行的初始点x0。2)产生产生k个个n维随机单位向量。维随机单位向量。3)取试验步长，计算出取试验步长，计算出k个随机点。个随机点。4)在在k个随机点中，根据可行性和适用性，找出可行个随机点中，根据可行性和适用性，找出可行搜索方向。搜索方向。5)从初始点从初始点x0出发，沿可行搜索方向出发，沿可行搜索方向d以以步长步长进行迭进行迭代计算，

16、直到搜索到一个满足全部约束条件，且目标代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点函数值不再下降的新点x。随机方向法的计算步骤：随机方向法的计算步骤：5)从初始点从初始点x0出发，沿可行搜索方向出发，沿可行搜索方向d以以步长步长进行迭进行迭代计算，直到搜索到一个满足全部约束条件，且目标代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点函数值不再下降的新点x。满足，迭代终止。约束最优解为满足，迭代终止。约束最优解为x*x，否则，否则，x0=x，转到步骤转到步骤2。 6)若收敛条件若收敛条件随机方向法的计算步骤：随机方向法的计算步骤：例：用随机方向法求解下面问

17、题的约束最优解：例：用随机方向法求解下面问题的约束最优解： 04),(0),(01),(. .)3(),(min22121322121211222121xxxxgxxxgxxxgtsxxxxf解：解：1）确定初始点）确定初始点：2）产生）产生k个随机方向（个随机方向（k=3）：8 . 06 . 04 . 03 . 04 . 0)3 . 0(1221e65. 076. 06 . 07 . 07 . 0)6 . 0(1222e0105 . 005 . 01223e9)(00)0()0(xfxT3）计算）计算k个随机点个随机点：8 . 06 . 01)0(1exx65. 076. 02)0(2exx

18、013)0(3exx4）判断）判断k个随机点的可行性个随机点的可行性：1x3x5）判断可行搜索方向）判断可行搜索方向：40)31 (223f6 .138 . 0)36 . 0(221f)()0(3xffT01 )0(3xxd6）从可行点沿着可行方向前进）从可行点沿着可行方向前进：02010130dxdxx 验证其可行性和适用性验证其可行性和适用性：10)32()(22xf3)(ffx7）从可行点沿着可行方向前进）从可行点沿着可行方向前进：0301020dxdxx 验证其可行性和适用性验证其可行性和适用性：不可行性不可行性8）产生）产生k个随机方向（个随机方向（k=3）计算各随机点）计算各随机点

19、：12. 099. 01 . 08 . 01 . 0)8 . 0(1221e95. 032. 06 . 02 . 02 . 0)6 . 0(1222e6 . 08 . 03 . 04 . 03 . 04 . 01223e12. 099. 2101exx95. 032. 2202exx6 . 02 . 1303exx9）判断可行性与适用性）判断可行性与适用性： 均不可行均不可行10）步长减半计算各随机点）步长减半计算各随机点：06. 049. 2101exx48. 016. 2202exx3 . 06 . 1303exx11）判断可行性与适用性）判断可行性与适用性： 均不可行均不可行12）步长再

20、减半计算各随机点，直到步长很小依然找不）步长再减半计算各随机点，直到步长很小依然找不到一个可行点，则此时的到一个可行点，则此时的x0即为即为 x*=2 0T, f(x*)=1是否是最优点呢？用什么方法判断？是否是最优点呢？用什么方法判断？04),(0),(01),(. .) 3(),(min22121322121211222121xxxxgxxxgxxxgtsxxxxf)()()()(33)(22)(kkkggfxxx1410023204 . 032因此，所求是约束极小点。因此，所求是约束极小点。判断：判断：本次小结：本次小结：1 约束优化问题的最优化条件：约束优化问题的最优化条件：JuJug

21、hgfuupvvvJuuu00)()()()(11xxxx2 用随机方向法求解用随机方向法求解约束优化问题：约束优化问题： 1）基本思想基本思想 2）求解方法和步骤求解方法和步骤12()1F Xxx120;0 xx引例引例1、求解函数、求解函数的极小值，约束条件为：的极小值，约束条件为：起始点：起始点：1，0T ；0，1T ；1，1T说明复合形法的基本思想说明复合形法的基本思想(分区搜索分区搜索)。5-3 5-3 复合形法复合形法5.3.1 5.3.1 复合形法的基本思想复合形法的基本思想011)(08)(06)(01)(0)(. .41060)(min2152413221121222121x

22、xgxgxgxgxgtsxxxxxxfxxxxxx5.3.1 5.3.1 复合形法的基本思想复合形法的基本思想5.3.1 5.3.1 复合形法的基本思想复合形法的基本思想 5.3.1 5.3.1 复合形法的基本思想复合形法的基本思想在可行域内构成在可行域内构成初始复合形。初始复合形。找出坏点找出坏点X(H)。找出最好点找出最好点X(L)。找出函数值下降找出函数值下降方向。方向。5.3.1 5.3.1 复合形法的基本思想复合形法的基本思想X(R)= X(0)+(X(0)-X(H)X(R)为映射点，为映射点，=1.3。 取其余点的中点为取其余点的中点为X(0)。5.3.1 5.3.1 复合形法的基

23、本思想复合形法的基本思想 在迭代过程中，若映射点不满足适用性和可行在迭代过程中，若映射点不满足适用性和可行性，将映射系数减小，性，将映射系数减小， 重新取得重新取得X(R)， 使它满足适使它满足适用性和可行性。用性和可行性。复合形的顶点复合形的顶点K通常取通常取n+1K2n个。个。方法方法1：设计者确定：设计者确定方法方法2：随机产生：随机产生：1、产生、产生K个随机点个随机点 xi= ai +i (bi - ai) i=1,2,.,ni为（为（0，1）区间内产生的均匀分布的随机数，需）区间内产生的均匀分布的随机数，需要要n个随机数产生一个点个随机数产生一个点X (1)。同样，产生其它的随。同

24、样，产生其它的随机点机点X (2)、X (3)、X (K)。5.3.2 5.3.2 初始复合形的构成初始复合形的构成2、将非可行点调入可行域、将非可行点调入可行域 将产生的将产生的K个随机点进行判断是否在可行域内，重新个随机点进行判断是否在可行域内，重新排列，将可行点依次排在前面，如有排列，将可行点依次排在前面，如有q个顶点个顶点X (1)、X (2)、X (q)是可行点，其它是可行点，其它K-q个为非可行点。对个为非可行点。对X (q+1)，将其调入可行域的步骤是：，将其调入可行域的步骤是： 2、将非可行点调入可行域、将非可行点调入可行域 （1）计算）计算q个点集的中心个点集的中心X (s)

25、；（2）将第）将第q+1点朝着点点朝着点X (s)的方向移动，按下式产生的方向移动，按下式产生新的新的X (q+1)，即，即 X(q+1)= X(s)+0.5 (X(q+1)-X(s) 这个新点这个新点X X(q+1)(q+1)实际就是实际就是X X(s(s) )与原与原X X(q+1)(q+1)两点连线的两点连线的中点，如图。若新的中点，如图。若新的X X(q+1)(q+1)点仍为非可行点，按上式点仍为非可行点，按上式再产生再产生X X(q+1)(q+1)，使它更向，使它更向X X(s(s) )靠拢，最终使其成为可行靠拢，最终使其成为可行点。点。 按照这个方法，同样使按照这个方法，同样使X

26、X (q+2)(q+2)、X X (q+3)(q+3)、X X (K)(K)都变为可行点，这都变为可行点，这K K个点就构成了初始复合形个点就构成了初始复合形。12()1F Xxx120;0 xx例例1、求解函数、求解函数的极小值，约束条件为：的极小值，约束条件为：随机产生点：随机产生点：2，0T ；0，2T ；2，2T说明调入可行域的过程。说明调入可行域的过程。0321 xx（1）构造初始复合形；）构造初始复合形；（2）计算各顶点的函数值）计算各顶点的函数值F(X(j)，j=1,2,.,K。选出。选出好点好点X(L)和坏点和坏点X(H)。( )( )( )()()( ):()min (),1

27、,2,:()max (),1,2,LLjHHjXF XF XjKXF XF XjK（3）计算坏点外的其余各顶点的中心点）计算坏点外的其余各顶点的中心点X(0)。( )011,1KjjXXjHk5.3.3 5.3.3 复合形法的迭代步骤复合形法的迭代步骤（4）计算映射点）计算映射点X(R) 检查检查X(R)是否在可行域内是否在可行域内。若。若X(R)为非为非可行点，将映射系数减半后再按上式改变可行点，将映射系数减半后再按上式改变映射点，直到映射点，直到X(R)进入可行域内为止。进入可行域内为止。()(0)(0)()()RHXXXX（5 5）构造新的复合形）构造新的复合形 计算映射点的函数值计算映

28、射点的函数值F(X(R)，并与坏点的函数值，并与坏点的函数值F(X(H)比较，可能存在两种情况：比较，可能存在两种情况： 1）映射点优于坏点）映射点优于坏点 F(X(R) F(X(H) 这种情况由于映射点过远引起的，减半映射系数，这种情况由于映射点过远引起的，减半映射系数，若有若有F(X(R) F(X(H)，这又转化为第一种情况。，这又转化为第一种情况。2 2）映射点次于坏点）映射点次于坏点 若经过多次的映射系数减半，仍不能使映射点由于坏若经过多次的映射系数减半，仍不能使映射点由于坏点，则说明该映射方向不利，此时，应改变映射方向，点，则说明该映射方向不利，此时，应改变映射方向，取对次坏点取对次

29、坏点()()( ):()max (),1,2,SHSHjXF XF XjK jH的映射。的映射。( )01()(0)(0)()1,1()KjjRSHXXjSHkXXXX再转回本步骤的开始处，直到构成新的复合形。再转回本步骤的开始处，直到构成新的复合形。2 2）映射点次于坏点）映射点次于坏点1)各顶点与好点函数值之差的均方根值小于误差限各顶点与好点函数值之差的均方根值小于误差限，即即1( )( )2211 ()() KjLjF XF XK 2）各顶点与好点的函数值之差平方和小于误差限，）各顶点与好点的函数值之差平方和小于误差限， 即即 ( )( )21 ()()KjLjF XF X(6)(6)判

30、断终止条件判断终止条件3）各顶点与好点函数值差的绝对值之和小于误差限，）各顶点与好点函数值差的绝对值之和小于误差限，即即 如果不满足终止迭代条件，则返回步骤如果不满足终止迭代条件，则返回步骤2继续进继续进行下一次迭代；否则，可将最后复合形的好点行下一次迭代；否则，可将最后复合形的好点X(L)及及其函数值其函数值F(X(L)作为最优解输出。作为最优解输出。( )( )1()()KjLjF XF X(6)(6)判断终止条件判断终止条件按照迭按照迭代步骤代步骤给此图给此图找错：找错：011)(08)(06)(01)(0)(. .41060)(min2152413221121222121xxgxgxg

31、xgxgtsxxxxxxfxxxxxx例例1：用复合形法解下列问题的约束最优解：用复合形法解下列问题的约束最优解5.3 5.3 复合形法的例题复合形法的例题解解:(1)产生初始复合形的顶点，取顶点数为产生初始复合形的顶点，取顶点数为2n=4，人为选点：人为选点：5 . 33,4 . 62,41,5 . 5104030201xxxx验证满足约束条件。验证满足约束条件。（2）计算函数值，找出坏点：）计算函数值，找出坏点：75.26)(,56.46)(47)(,57.53)(04030201xfxfxfxf01)(xxH5.3 5.3 复合形法的例题复合形法的例题 （3）计算其余各点的形心：）计算其

32、余各点的形心：63. 425 . 334 . 624131)(310403020 xxxx（4）检查形心可行性：）检查形心可行性：864. 40620037. 41163. 42)(05xg（5）求映射点并检查可行性：）求映射点并检查可行性：499. 33 . 35 . 5163. 423 . 163. 42)()(00)(HRxxxx5.3 5.3 复合形法的例题复合形法的例题经验证，可行。经验证，可行。（6）比较映射点与坏点的目标函数值：）比较映射点与坏点的目标函数值：57.53)(59.24)()()(HRxfxf 替换坏点，构成新复合形：替换坏点，构成新复合形：5 . 33,4 . 6

33、2,41,499. 33 . 314131211xxxx 进行第二轮迭代，找出坏点为：进行第二轮迭代，找出坏点为：（要求学生接着做）（要求学生接着做）5.3 5.3 复合形法的例题复合形法的例题32125)(xxxf15 . 04200004. 0001. 0050302121321xxxxxx例例2：用复合形法解目标函数：用复合形法解目标函数的极小值，已知约束条件为：的极小值，已知约束条件为：5.3 5.3 复合形法的例题复合形法的例题212()412F Xxxs.t.22112213225000gXxxgXxgXx例例3、用复合型法求解目标函数、用复合型法求解目标函数的极小值，已知约束条件

34、为：的极小值，已知约束条件为：起始复合形顶点：起始复合形顶点：2，1T；4，1T；3，3T；方法特点：方法特点：5-4 5-4 惩罚函数法惩罚函数法(SUMT)(SUMT) 基本思想基本思想：通过构造罚函数把约束问题：通过构造罚函数把约束问题转化为一系列无约束最优化问题转化为一系列无约束最优化问题，进而用无，进而用无约束最优化方法去求解。约束最优化方法去求解。 又称为序列无约束最小化方法。又称为序列无约束最小化方法。 将有约束的优化问题转化为无约束优化问题来求解。将有约束的优化问题转化为无约束优化问题来求解。 前提：前提： min( ),. .( )01,2,( )01,2,njkfRst g

35、jmhklxxxx 构成一个新的目标函数，称为惩罚函数：构成一个新的目标函数，称为惩罚函数： ( )( )( )( )121211( ,)( )( )( )mlkkkkjkijrrfrG grH hxxxx5-4 5-4 惩罚函数法惩罚函数法(SUMT)(SUMT)F惩惩罚函数罚函数F惩惩罚因子罚因子F惩罚项惩罚项 ( )( )( )( )121211( ,)( )( )( )mlkkkkjkijrrfrG grH hxxxx几个概念几个概念:n从而有从而有( )11lim( )0mkikirG gx( )21lim( )0lkjkjrH hx( )( )( )12lim( ,)()0kkkk

36、rrfxx惩罚项必须具有以下极限性质：惩罚项必须具有以下极限性质： ( )( )( )( )121211( ,)( )( )( )mlkkkkjkijrrfrG grH hxxxx 根据约束形式和定义的泛函及罚因子的递推方法根据约束形式和定义的泛函及罚因子的递推方法等不同，罚函数法可分为等不同，罚函数法可分为: 内点法内点法 外点法外点法 混合混合法法惩罚函数法的分类：惩罚函数法的分类：1.内点法内点法 这种方法将新目标函数定义于这种方法将新目标函数定义于可行域内可行域内，序列迭代点在可行域内逐步逼近约束边界上的最序列迭代点在可行域内逐步逼近约束边界上的最优点。内点法优点。内点法只能用来求解具

37、有不等式约束只能用来求解具有不等式约束的优的优化问题。化问题。min( )s.t.( )0(1,2,)jfgjmxx对于只具有不等式约束的优化问题：对于只具有不等式约束的优化问题： 1.内点法内点法转化后的惩罚函数形式为：转化后的惩罚函数形式为：( )11( , )( )( )mkiirfrgxxx( )1( , )( )ln( )mkiirfrgxxx或：或：改书上符号内点法的一些几何概念和基本原理内点法的一些几何概念和基本原理: : 先构造惩罚函数：先构造惩罚函数：设数学模型为：设数学模型为：01)()(min1xXgRDXxXFxrxXgrXFrXkkk11)(1)(),(min)()(

38、)(极值点与因子极值点与因子r r的关系：的关系：解得：解得：取初始罚因子取初始罚因子r=1，罚因子的递减率，罚因子的递减率c0.1，则罚因子的递减序列为：则罚因子的递减序列为：0)1 (112)(xrdxdk)()(1)(kkrrx, 2 , 1 , 0)()1(kcrrkkxrxk11min)(01)(. .)(minxXgtsxXFr=0.1, x*=1.31r=0.01, x*=1.11r=0, x*=101210kkrrrrr1. 内点法内点法( )11( , )( )( )mkiirfrgxxx( )1( , )( )ln( )mkiirfrgxxxxrxXgrXFrXkkk11)

39、(1)(),(min)()()(用内点法时构造惩罚函数应遵循如下原则：用内点法时构造惩罚函数应遵循如下原则：(1)惩罚函数是定义域上的惩罚函数是定义域上的，即保证其，即保证其在域内处处有值，当调用需要求导数的无约束在域内处处有值，当调用需要求导数的无约束优化方法时，则还要求其可导。优化方法时，则还要求其可导。)(1)(),(min)()(XgrXFrXkk(2)惩罚项的惩罚作用惩罚项的惩罚作用:(2)(2)惩罚项的惩罚作用：惩罚项的惩罚作用：惩罚项相当于使各约束函数惩罚项相当于使各约束函数形成一道障碍，故又称之为形成一道障碍，故又称之为障碍项障碍项。 )(10)(XgXg当当x x在可行域内远

40、离约束边界时：在可行域内远离约束边界时：当当x x由可行城内靠近任一约束边界时：由可行城内靠近任一约束边界时：0)(Xg0)(1Xg由于内点法只能在可行域内迭代，而最优解很可由于内点法只能在可行域内迭代，而最优解很可能在可行域内靠近边界处或就在边界上，此时尽能在可行域内靠近边界处或就在边界上，此时尽管泛函的值很大，但罚因子是不断递减的正值，管泛函的值很大，但罚因子是不断递减的正值，经多次迭代，接近最优解时，惩罚项已是很小的经多次迭代，接近最优解时，惩罚项已是很小的正值。正值。 ：)(1)(),(min)()(XgrXFrXkk 例例5-2 5-2 用内点法求用内点法求2212min( )fxx

41、x1s.t.( )10gx x的约束最优解。的约束最优解。解解: 用内点法求解该问题时，首先构造内点惩罚函数用内点法求解该问题时，首先构造内点惩罚函数:22121( , )ln(1)krxxrxx思考：极值存在的必要条件是什么？思考：极值存在的必要条件是什么？1112220120krxxxxx 联立求解得：联立求解得：12112()2()0kkkrx rx r1112( )2rx r时不满足约束条件时不满足约束条件 应舍去应舍去1( )10g xx 考虑约束：考虑约束：无约束极值点为无约束极值点为:*1*2112()2()0kkkrx rx r4)(02)(4000rxfrxrT022. 2)

42、(0422. 1 )(2 . 1111rxfrxrT336. 1)(0156. 1 )(36. 0222rxfrxrT1)(01 )(0kTkkrxfrxr最优点图解最优点图解Trx02)(0Trx0422. 1 )(1Trx0156. 1 )(2Tkrx01 )(最优点图解最优点图解1）选择可行域内）选择可行域内初始点初始点X(0);2）选取初始）选取初始罚因子罚因子r(0)与罚因子与罚因子降低系数降低系数c，并置，并置K0；3）求）求min(x(K),r(K)解出解出最优点最优点xK*；4）KK+1，r(K)cr(K-1)， xK0 xK-1* ，并转步骤，并转步骤3）；）；5）按终止准则

43、判别，若满足转步骤）按终止准则判别，若满足转步骤6），否则转步骤），否则转步骤4）；）；6）输出最优解（）输出最优解（X*，F*），停止计算），停止计算。n1） 初始点初始点x0的选取的选取初始点：尽量选择初始点：尽量选择的的可行点可行点。 以不规则边界为例：以不规则边界为例：减少减少min(x(K),r(K) 求解的迭代次数或困难。求解的迭代次数或困难。常用的方法：利用随机数生成常用的方法：利用随机数生成初初始点。始点。？2） 惩罚因子初值惩罚因子初值r0的选取的选取r0 0取值过大，取值过大，迭代步骤多。迭代步骤多。2） 惩罚因子初值惩罚因子初值r0的选取的选取r0 0取值太小，取值太小，

44、形态恶劣。形态恶劣。 惩罚因子的初值：惩罚因子的初值： a） r0=150b）jjxgxfr)(1)(000 3) 3) 缩减系数缩减系数c c的选取的选取 在构造序列惩罚函数时，惩罚因子在构造序列惩罚函数时，惩罚因子r是一个是一个逐次递减到逐次递减到0的数列，相邻两次迭代的惩罚因的数列，相邻两次迭代的惩罚因子的关系为子的关系为 :通常的取值范围：通常的取值范围： 0.10.71kkcrr 4) 收敛条件收敛条件*111*11(),(),(),kkkkkkrrrrrrxxx*12()()kkrrxx例例3 3：用内点法求下列问题的最优解：用内点法求下列问题的最优解：0)(0)(. .)(min

45、12221121xXgxxXgtsxxXF0)(0)(. .)(min12221121xXgxxXgtsxxXF：解：首先写成标准形式2121)(ln()(),()(1)(),(jjkkjjkkXgrXFrXXgrXFrX构造惩罚函数：)ln()ln(),(121221xrxxrxxrXkkk010212212121211xxrxxrxxxrxkkk的最优解：用解析法求21214811xrxrxkk)0(481111xrxk考虑约束75. 1)(25. 15 . 0:1000XFXr当09. 1)(782. 0309. 0:5 . 0111XFXr当466. 0)(283. 0183. 0:2

46、5. 0222XFXr当0)(00:0238. 0)(135. 0103. 0:125. 0333kkkXFXrXFXr当当0)(12xXg0)(2211xxXg1x2x21)(xxXF0)(00kkXFX11225. 15 . 0:100Xr当782. 0309. 0:5 . 011Xr当283. 0183. 0:25. 022Xr当例例4 4：用内点法求下列问题的最优解：用内点法求下列问题的最优解：01. 0 11 011)(. .24)(min0222221TXxXgtsxxXF要求：用无约束优化方法求解选择哪种无约束优化方法呢？)(1)(),(XgrXFrXkk解：构造惩罚函数：) 1

47、(24),(222221xrxxrXkk125)(1) 1 (22210 xxXr125)(1) 1 (22210 xxXr坐标轮换法坐标轮换法求此求此的最优点：的最优点： 11011111111011eXX）第一轮轮换：24)1 ()(2111X0)(111TX1011步骤？步骤？22221112101010eXX1)1 (25)(2212X0)(212TX00120021111121eXX）第二轮轮换：0022222122eXX000122222XXX00)(0rX5 . 05 .24)(5 . 0)2(22211xxXr0010011111011eXX）第一轮轮换：)(11X0)(101

48、TX0011坐标轮换法求此坐标轮换法求此的最优点：的最优点：2222111201000eXX)(12X0)(202TX0012000)()(121rXX沿着第二个坐标方向轮换：沿着第二个坐标方向轮换：迭代终止否？判断5 . 05 .24)(2221xxX0)(00XFXT0)()(01rrXX（3）判断内惩法的收敛条件）判断内惩法的收敛条件：内点惩罚函数法不足：内点惩罚函数法不足：1）一个严格的初始内点；）一个严格的初始内点；2）不能解决带有等式约束的优化问题。）不能解决带有等式约束的优化问题。 2. 2. 外惩罚函数外惩罚函数法法01)()(min1xXgRDXxXF引例引例1：构造如下的函

49、数：构造如下的函数： 另一种形式：另一种形式：)(01 ()1 ()(01 (),(2)()(可行域外可行域内xxrxxxrxkk2)()()1 ( , 0max),(xrxrxkk0)1 (211)(xrdxdk)(211krx取初始取初始r0=1/4,c=2，不同惩罚因子时，不同惩罚因子时 的迭代值如下：的迭代值如下：其收敛关系见下图：其收敛关系见下图：)(01 ()1 ()(01 (),(2)()(可行域外可行域内xxrxxxrxkk)(211krx0.1250.250. 51从图可以看出从图可以看出规律：规律： (1)可行域内：惩罚函数和目标函数是完全重合。可行域内：惩罚函数和目标函数

50、是完全重合。 可行域外：惩罚函数值大于目标函数值，离约可行域外：惩罚函数值大于目标函数值，离约 束边界越远，曲线被抬高得越多。束边界越远，曲线被抬高得越多。2)()()1 (),(xrxxrxkk从上图可以看出，存在从上图可以看出，存在规律：规律： (2)罚因子的值越大，惩罚函数在可行域外的部分罚因子的值越大，惩罚函数在可行域外的部分被抬高得越快，惩罚函数的极小点越靠近约束边界。被抬高得越快，惩罚函数的极小点越靠近约束边界。2)()()1 (),(xrxxrxkk0.1250.250. 51从上图可以看出，存在从上图可以看出，存在规律：规律：（3）罚因子趋于无穷大时，惩罚函数的极小）罚因子趋于