求解带约束连续型minimax问题的罚函数区间算法.pdf

第3 4 卷第1 期 中国矿业大学学报 v 0 1 ．3 4N o ．1 2 0 0 5 年1 月 J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g yJ a n ．2 0 0 5 文章编号1 0 0 0 1 9 6 4 2 0 0 5 0 1 。0 1 2 9 0 4 求解带约束连续型m i n i m a x 问题的 罚函数区问算法 黄秋红1 ，曹 1 ．中国矿业大学理学院，江苏徐州2 2 1 0 0 8 ；2 ． 德欣1 ，邓喀中2 中国矿业大学环境与测绘学院，江苏徐州2 2 1 0 0 8 摘要研究了带约束连续型m i n i m a x 问题的数值方法，其目标函数和约束函数都是L i p s c h i t z 连 续的；建立了针对带约束连续型m i n i m a x 问题的罚函数法，从而将其转化为无约束两层规划问 题，并证明了算法的收敛性；最后，用无约束两层规划问题的区间算法进行求解，给出了数值算 例．结果表明，该算法是可靠和有效的． 关键词连续型m i n i m a x 问题；两层规划问题；罚函数；区间算法 中图分类号O2 4 2 ．2 9 ；02 2 1 ．2文献标识码A P e n a l t yF u n c t i o nI n t e r v a l S o l v i n gC o n s t r a i n e dC o n t i n u o u s M e t h o df o r Mi n i m a xP r o b l e m H U A N GQ i u h o n 9 1 ，C A OD e x i n l ，D E N GK a z h o n 9 2 1 ．S c h o o lo fS c i e n c e s ，C h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y ，X u z h o u ，J i a n g s u2 2 1 0 0 8 。C h i n a ； 2 ．S c h o o lo fE n v i r o n m e n ta n dS p a t i a lI n f o r m a t i c s ，C h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g y ， X u z h o u ，J i a n g s u2 2 1 0 0 8 ，C h i n a A b s t r a c t An u m e r i c a lm e t h o dw a ss t u d i e dt os o l v ec o n s t r a i n e dc o n t i n u o u sm i n i m a xp r o b l e m sw i t h aL i p s c h i t zc o n t i n u o u so b j e c t i v ef u n c t i o na n dc o n s t r a i n e df u n c t i o n s ．T h ep e n a l t yf u n c t i o nm e t h o d w a sb u i l tt ot r a n s f o r mac o n s t r a i n e dc o n t i n u o u sm i n i m a xa l g o r i t h mi n t oab i - l e v e lp r o g r a m m i n g p r o b l e m ，a n dt h ec o n v e r g e n c eo ft h ea l g o r i t h mw a sp r o v e d ．A tl a s t ，t h eu n c o n s t r a i n e db i l e v e l p r o g r a m m n gi n t e r v a la l g o r i t h mw a sa p p l i e dt os o l v et h ep r o b l e m ，a n dn u m e r i c a le x a m p l e sw e r e g i v e nt os h o wt h ee f f i c i e n c ya n dt h er e l i a b i l i t yo ft h i sa l g o r i t h m ． K e yw o r d s c o n t i n u o u sm i n i m a xp r o b l e m ；b i ～l e v e lp r o g r a m m i n gp r o b l e m ；p e n a l t yf u n c t i o n ； i n t e r v a la l g o r i t h m M i n i m a x 问题是一类重要的数学规划问题，用 区间数学方法求解无约束m i n i m a x 问题已取得了 一些成果阻6 | ．但是对带约束的连续型m i n i m a x 问 题的算法研究的成果还很少．本文将考虑带约束的 连续型m i n i m a x 问题 m i nm a x f x ，y ， 1 z ∈X o y ∈Y O 式中X ∞’ { z z 1 ，z 2 ，⋯，X n 0 Tf z 。E a i ，b i 3 C R ， i 一1 ，2 ，⋯，咒o } ；Y ∞’一{ Y 一 y 1 ，Y z ，⋯，Y 。， Ty iE [ c ，d i ] C R ，i l ，2 ，⋯，咒1 ，，2 n O 翘l ，目标函数 f x ，y 和约束函数g i z ，y z ∞’一 x ∞’，Y ∞’ c R ”一R 均为L i p s c h i t z 连续函数，且其L i p s c h i t z 常 数分别为C ，和c 。 以I Z ∞’ 表示z ∞’上的所有区间向量的集合， 以m z 和W Z 分别表示区间向量Z E I Z ∞’ 的 中点和宽度，尺 z Ⅳ z ／2 为Z 的半径．对于区 间函数F z 分别用￡ z 和- P z 表示区间值的左 收稿日期2 0 0 4 0 3 2 6 基金项目国家自然科学基金项目 5 0 1 7 4 0 5 1 作者简介黄秋红 1 9 8 0 一 ，女，安徽省芜湖市人，硕士研究生，从事计算数学理论和应用方面的研究 万方数据 1 3 0中国矿业大学学报第3 4 卷 端点和右端点，即F z 一E L z ，万 z ] ．如果函 数厂 z 和区间函数F Z 满足F 2 一， z ，， 2 ∈F z Vz f f z ，则称F z 为厂 2 的区间扩张． 有关区间数学的其它概念和内容可参见文献[ 7 8 ] ． 1罚函数法 设g z ，y 一m a x 。{ g 。 z ，y } ，q z ，y m a x { 0 ，g x ，y ，构造罚函数 t l z ，y ，卢 - f x ，y 一p q x ，y ． 2 定理1 设t 。 z ，y ，| 8 为由式 2 定义的函数， 且陬 1 ≥厥 0 ，如果m a x t l z ，Y ，陬 和m a x t l z ， y E Y ‘”’y E Y ‘”’ Y ，依 ， 的全局最优解分别为y 强’与y 强 1 ’，则 t l z ，y ‘蚪，厥 1 4 t l z ，y ‘舯, i l k ， 3 q x ，Y ‘抖“ 4 q x ，Y ‘‘’ ， 4 f x ，Y ‘计 4 f x ，Y ‘6 ’ ． 5 证明 点，故 由于风 。≥＆，Y 强’是t 。 z ，y ，厥 的极大 t 1 z ，y 强’，像 1 、f x ，y ‘6 1 ’ ～胁 l q x ，y ‘‘ 1 ’ ≤≤ f x ，Y ‘蚪1 ’ 一f l k q x ，Y ‘蚪1 ’ ≤ f x ，j ，‘肋 一f l 女q x ，Y “’ ￡1 z ，Y 强’，陬 ． 6 式 3 得证． 另一方面，Y 强十1 ’是t 。 z ，y ，陬 。 的极大点，故 f x ，y 强’ 一陬 1 q x ，y ‘的 ≤ f x ，Y ‘6 1 ’ 一卢女 1 q x ，y ‘6 1 ’ ． 7 式 6 和式 7 相加可得 卢々 1 q z ，y 油 一q x ，y 强’ ≤ 卢女 g z ，y ∞ 1 一q x ，Y 强’ ． 又风 ，≥＆ o ，所以 q x ，y ‘抖D ～q x ，y ‘舢 4 0 ． 式 4 得证． 由上面结论可知 f x ，y 幢十1 ’ 一陬q x ，Y 1 ’ ≤ f x ，Y 伯’ 一风q x ，Y 强’ ≤ f x ，Y ‘“ 一陬q x ，Y 强 ， 即 f x ，Y 旺“’ 4 f x ，y 娃’ ． 式 5 得证． 证毕． 定理2 设对任意取定的z ∈X ∞’，约束最优 化问题 m a x f x ，y ， y E Y 。’ 8 S ．t ． g j z ，y ≤0 i 1 ，2 ，⋯，优 的最优解存在．又设{ 陬} 是正数序列，满足＆十。≥ 陬 志一1 ，2 ，⋯⋯ ，l i m 陬一 。。，且对每个k ，问题 m a xt ， z ，Y ，厥 的全局最优解Y ’存在．那么， y E y ‘o ’ { Y ’ 的任何聚点Y ’均是问题 8 的全局最优解． 证明不妨设对任意固定的z ∈X ∞’对应问题 8 的最优解为y ，则q x ，j ， o ．所以有 f x ，y 一厂 z ，y 一f l k q x ，y 一 t 1 z ，Y ，佛 4 t l z ，y 强’，展 ． 9 所以序列{ t ， z ，y ∞’，像 } 为有下界数列，且由定理 1 知其为单调递减数列，所以其必有极限，不妨设 其极限为f ． 另一方面， f x ，Y 强’ 也是单调递减的，并且 由式 9 还可知 f x ，Y 娃’ ≥f l z ，y 强’，厥 ≥厂 z ，y ． 1 0 所以序列{ f x ，Y 强’ 也是单调递减有下界的，它 也肯定有极限，不妨设其极限为／ ．于是 l i m f l k q x ，Y ‘6 ’ 一 l i m 厂 z ，了聃’ 一．t l z ，y 唯’，卢 厂’一￡i ． 又因为l i m 厥一 。。， 女’∞ 所以必有l i m q x ，y 强’ 0 ． 由于Y 强’一了 ，且q x ，y 连续，所以q x ，Y l i m q 2 ，Y 强’ 一0 ，即Y 是可行解． 因为Y 是问题 8 的最优解，故厂 z ，∥ ≥ f x ，3 r ，再由式 1 0 知f x ，Y 一l i m f x ，了㈤ ≥， z ，y ，所以f x ，y 一， z ，y ” ． 证毕． 设问题 8 对应z 的最优解为y z ，令 t o z ，y z ，卢 一／ z ，y z 硒 z ，y 丁 ． 1 1 类似可证得下面的定理3 ，4 ． 定理3 设t 。 z ，y z ，f 1 为由式 11 定义的 函数，且p 抽 1 ’≥p 豫’ o ，如果m i nt o z ，y z ，卢伸’ T ∈X ‘“’ 和m i nt 。 z ，y z ，卢强上1 ’ 的全局最优解分别为z 强’ z ∈X ‘”’ 与z 强州’，则 t o z ‘‘ ，y x ‘‘ 1 ’ ，卢‘6 1 ’ ≥ t o 丁‘“ ，y x ‘4 ’ ，J 8 ‘‘’ ， 1 2 q x ‘抖，y x ‘抖1 ’ 4 q x ‘柏，y x ‘‘’ ， 1 3 f x ‘蚪，y x ‘‘ 1 ’ ≥， z ‘n ，y x ‘6 ’ ． 1 4 定理4 设约束最优化问题 m i nf x ，y ， z ∈x ‘∞ 1 5 S ．t ． g ， z ，y ≤0 i 1 ，2 ，⋯，优 的最优解存在．又设{ p ∞’ 是正数序列，满足p 仕 1 ’ 万方数据 第1 期 黄秋红等求解带红束连续型m i n i m a x 问题的罚函数区间算法1 3 1 ≥』9 仕’ 志一1 ，2 ，⋯⋯ ，l i m f l ∞’一 。。，且对每个正， 问题m i nt 。 z ，∥ z ，卢伯’ 的全局最优解z 强’存在． x E X ‘”’ 那么，{ z 强’ 的任何聚点z 。均是问题 1 5 的全局最 优解． 2区间扩张与区间算法 由定理2 ，4 知，问题 1 可近似转化为如下无 约束两层规划问题 m i nt o z ，Y ，f l o ， 1 6 z ∈X ‘”’ 其中j ， z 是下面问题的解 m i n 一t 1 z ，y ，p 1 ， 1 7 y E y t ”’ 式中 风，p 。 0 ．当f 1 0 ，卢。一 。。时，问题 1 6 、 1 7 的解收敛于问题 1 的解． 定理5由式 2 和式 1 1 定义的函数t 。 z ， j ，，岛 和t 1 z ，Y ，岛 是L i p s c h i t z 连续的，其 L i p s c h i t z 常数分别为f ，。2 c s P 。m H a x { ‘q } 和C t l 。C f f l lm a x { ％．} ． 证明令g 。 z ，j ， 一o ，易知c 。． o ，则 f t l z ，Y 1 ，卢1 一t 1 z ，Y 2 ，卢1 1 一 I f x ，歹1 一p l q x ，Y 1 ～ ， z ，了2 ～卢1 q x ，y 2 I ≤ } f x ，Y 1 一f x ，Y 2 } m卅 卢1m a x g x ，Y 1 - m a x g x ，y 2 I ≤ C fl lY 1 一∥21 l 。。 p 1m a x g x ，Y 1 一m a x g x ，Y 2 I ． 不妨设m 。a x g x ，Y 1 ≥m 。a x g x ，Y 2 ，且 m a x g i x ，y 1 一g 。、 z ，Y 1 ， m a x g i z ，Y 2 一g 。。 z ，Y 2 ， l U 。 打z l ，m 2 E { 0 ，1 ，⋯，优 ． 易知g 。， z ，Y 1 ≥踟。 z ，Y 2 ，故 m a x g x ，y 1 一m a x g x ，Y 2 f g 。， z ，y 1 - - g 。。 z ，Y 2 ≤ g 。， z ，Y 1 一g 。 z ，Y 2 ≤ m 8 7 { ％ I J ∥，一Y zJ I 。． 所以 I t l z ，Y 1 ，p 1 一t 1 z ，Y 2 ，卢1 I ≤ C f { fY l y 2f l 。。 卢1m a x { f 。．} | { Y 1 一Y 2I f 。。一 c s f 1 1m a x { c 。．} f fY 1 一Y 2f | 。。． 由上式可知函数t 1 z ，Y ，展 是L i p s c h i t z 连续 的，其I ．i p s c h i t z 常数为o ，一c f f 1 1m a x { 勺． ． 同理可证函数t 。 z ，Y ，9 0 也是I ．i p s c h i t z 连续 的，其L i p s c h i t z 常数为f “ 1 什f l om a x ％．} ． 证毕． 利用定理5 中L i p s c h i t z 常数o 。和Q ．，可构造 函数t 。 z ，y ，风 和f 。 z ，Y ，p 。 的区间扩张如下 VZ E I Z ㈤ 丁o Z ，p o 一￡o m Z ，卢o C 。| lR z I I 。。[ ～1 ，1 3 ， 1 8 T 1 Z ，p 1 一f 1 研 Z ，p 1 Q ．0R z 0 。。[ 一1 ，1 ] ． 1 9 将区域z ∞’ x ∞’，Y ∞’ 划分为M 部分，z “，’ 一 X ‘订，Y ‘o ’ i 一1 ，2 ，⋯，州；．j 一1 ，2 ，⋯，Ⅲ， ，M y m ，，z ∽一0 zc 忉，zc 。，一l 二} z ∽．引入下面的 酉 J 2 l8 1 记号 G M m a x f fW Z 嘶’ f l 。。， l ≤。≤坍，l ≤J ≤巩 丁∥ 丁1 Z “”，卢1 ，7 ’5 忉一丁o Z “J ’，岛 ， ￡；门一m a x 丁；啪，∥一m i n 互P ，tf4 ’一r a i n7 T ∥， 1 ≤J 每”，l ≤J G m il ≤，≤m ， ￡∥ m a x7 1 ∥，∥ r a i nT ∥， l 每J 冬m ， 1 G j G m i t o m i n t o “，如一m i n t o “． 定理6 [ 1 。31 对于3 7 ∈X “’，设t l “ 一m i nt 1 z ， ，∈Y ㈩ Y ，p t ，则 ￡i ∈隧”，tP ] ，l i r atl i 一l i r a t { n f i ． 。M U。M U 2 设P { i ，歹 lz ‘。’满足T I 忉一t _ l 订 ￡} ．设￡占 一m i n m a x ．T o 。’，茹一m i nm a x ∥，t o “ 是问题 1 ≤l ≤m f ，J E P1 ≤，≤” f ，』 ∈尸 1 6 、 1 7 的最优解，且对于任意z ∈X “’，m i n ，E y O t ， z ，Y ，p ， 有唯一解，则 f 彳E [ 菇，f 孑] ，l i m t o p l i m t P o t o ． o M 一0“M 一0 根据定理6 ，利用区域二分法、区间扩张和区 域删除原则可构造求解问题 1 6 、 1 7 的区间算 法．算法从区域 X ∞’，Y ∞’ 开始产生一个数据表 L ，表L 中的元素形如 X “’，S “’，H 扎H I “，tP ， 其中Ⅳ护一[ ∥，搿’] ，H { n E t l “，￡P ] ，而5 “’为子 表，它的元素又形如 y ㈤i j ，丁 ∥，丁P ．表L 中的元 素按旦护的升序排列，子表S “’中的元素按照 l } w y “p | } 。。的大小降序排列．每一个区域 x “’， Y 何’ 均由上一次的表L 中的第一项或子表S 中第 一项中的区域按照最大宽度坐标方向二分得到． 罚函数区间算法的基本步骤为 万方数据 1 3 2中国矿业大学学报第3 4 卷 步骤1 针对问题 1 构造函数t 。 z ，y ，风 和 t ， z ，y ，p ， ，将问题近似转化为问题 1 6 、 1 7 ． 步骤2 构造t o z ，y ，风 和t 。 z ，y ，卢， 的区间 扩张T 。 X ，Y ，_ | 9 。 和T ， x ，Y ，卢， ． 步骤3 生成初始化数据表L ． 步骤4区间算法嘲．在不断进行区域二分和 无解区域删除的过程中，逐渐求出定理6 给出的问 题 1 6 、 1 7 的解的区间值，即问题 1 的m i n i m a x 值的区问值，同时求出m i n i m a x 点的区间值，并输 出． 步骤5当数据表L 为空时，完成全部计算． 3 数值算例 一9 ．9 9 9 9 6 1 8 5 3 0 3 1 0 1I ， Y 、一{ 一9 ．9 9 9 9 9 0 4 6 3 2 6 1 0 1 ， 一9 ．9 9 9 9 8 0 9 2 65 1 1 0 1 ] ， Y 2 [ 9 ．9 9 9 9 8 0 9 2 6 5 1 1 0 ～， 9 ．9 9 9 9 9 0 4 6 3 2 6 x1 0 1l ， F [ 1 ．9 9 9 9 9 7 1 3 8 9 8 ，2 ．0 0 0 0 0 0 9 5 3 6 7 ] ， L c o u n t 8 ，B c o u n t 一5 6 ． 参考文献 [ 1 ] [ 2 ] 利用上述算法，用V i s u a lC 6 ．0 编程进行 一一 数值实验，下面仅给出两个算例，其中记号e 表示 ⋯。 最优值精度，C f 和c 。．分别表示目标函数和约束函 数的L i p s c h i t z 常数，记号L c o u n t ，B c o u n t 表示结果 中链的个数、分半次数． 例1 m i nm a x z 2 y - - 0 ．5 2 ， z ∈F ∞y f f y O S ．t ．x y ≤0 ， 其中 x ‘0 ’，Y ∞’ [ ～1 ，1 ] ，E 0 ，1 ] ． 其m i n i m a x 点 z ，Y 一 o ，o ， m i n i m a x 值f 0 ．2 5 ． 用罚函数区间算法计算输出的第一个结果为 ￡ 1 1 0 ～，f ， 3 ，C 。一2 X l 一2 ．7 4 6 5 8 2 0 3 1 2 5 1 0 ～， 一2 ．5 9 3 9 9 4 1 4 0 6 3 1 0 4l ， Y I1 ．5 2 5 8 7 8 9 0 6 2 5 1 0 ～， 1 ．6 7 8 4 6 6 7 9 6 8 8 1 0 _ 4f ， F 一[ 2 ．4 9 5 1 1 8 1 5 7 2 4 1 0 1 ，2 ．5 0 1 6 7 9 4 3 6 5 4 1 0 1 ] ， L c o u n t 一7 。B c o u n t 一] 4 7 ． 例2 m i nm a x z 一2 y l Y z ， z ∈X 0 ，∈Y o S ．t ．x y 1 十了2 ≤0 ， 其中 X ∞’，Y ∞’ 一 [ 一1 ，1 ] ， [ ～1 ，1 ] ，[ 一1 ，1 ] ． 其m i n i m a x 点 z ，Y 一 一1 ， 一1 ，1 ， m i n i m a x 值f ’一2 ． 用罚函数区间算法计算输出的第一个结果为 ￡一1 1 0 ～，c f 4 ，C g 3 X r 一9 ．9 9 9 9 7 1 3 8 9 7 7 1 0 一， [ 4 ] [ 5 3 [ 6 ] [ 7 ] [ 8 3 [ 9 ] D e m ’y a n o vVF ，M a l o z e m o vFN ．I n t r o d u c t i o nt o m i n i m a x [ M ] ．N e wY o r k J o r nW i l e y ＆S o n s ，1 9 7 4 ． S h e n ZH ，N e u m a i e rA ，E i e r m a n nMC ．S o l v i n g m i n i m a xp r o b l e m s b yi n t e r v a lm e t h o d s [ J ] ．B I T ， 1 9 9 0 3 0 7 4 2 7 5 1 ． 曹德欣，李苏北，吴彦强，等．求连续m i n i m a x 问题整 体解的区间算法[ J ] ．高等学校计算数学学报，2 0 0 2 ， 2 4 4 3 5 9 3 6 5 ． C a o D X ，L iSB 。W u Y Q ，e ta 1 ．I n t e r v a l m e t h o d f o r g l o b a ls o l u t i o n so fc o n t i n u o u sm i n m a xp r o b l e m [ J ] ． N u m e r i c a lm a t h e m a t i c sAJ o u r n a lo fC h i n e s e U n i v e r s i t i e s ，2 0 0 2 ，2 4 4 3 5 9 3 6 5 ． W o l f eMA ．A ni n t e r v a la l g o r i t h mf o rc o n s t r a i n e dg l o h a lo p t i m i z a t i o n [ J ] ．J o u r n a lo fC o m p u t a t i o n a la n d A p p l i e dM a t h e m a t i c s ，1 9 9 4 5 0 6 0 5 6 1 2 ． 曹德欣，沈祖和．一类非光滑优化问题的区间算法 [ J ] ．高等学校计算数学学报，1 9 9 8 ，2 0 1 2 3 3 3 ． C a oDX ，S h e nZH ．I n t e r v a la l g o r i t h m sf o rac l a s so f n o n s m o o t h o p t i m i z a t i o np r o b l e m s [ J ] ．N u m e r i c a l M a t h e m a t i c sAJ o u r n a lo fC h i n e s eU n i v e r s i t i e s ，19 9 8 ， 2 0 1 2 3 3 3 ． 曹德欣，叶帅民，王海军．A ni n t e r v a lm a x i m u m e n t r o p y m e t h o df o rac l a s so fc o n s t r a i n e d n o n d i f f e r e n t i a b l eo p t i m i z a t i o np r o b l e m s [ J ] ．运筹学学 报，1 9 9 9 ，9 1 5 5 6 4 ． C a oDX ，Y eSM ，W a n gHJ ．A ni n t e r v a lm a x i m u m e n t r o p y m e t h o df o rac l a s so fc o n s t r a i n e d n o n d i f f e r e n t i a b l eo p t i m i z a t i o np r o b l e m s [ J ] ．O R T r a n s a c t i o n s ，1 9 9 9 ，9 1 5 5 6 4 ． M o o r eRE ．M e t h o d sa n da p p l i c a t i o no fi n t e r v a la n a l y s i s [ M ] ．P h i l a d e h i a S I A M ，1 9 7 9 ． A l e f e l dG ，H e r z b e r g e rJ ．I n t r o d u c t i o nt oi n t e r v a lC O m p u t a t i o n s [ M ] ．N e wY o r k A c a d e m i cP r e s s ，1 9 8 3 ． 叶帅民．两层规划问题的区问算法[ D ] ．徐州中国矿 业大学理学院，2 0 0 0 ． 责任编辑邓群 万方数据