（计算数学专业论文）求解极小极大问题的新算法.pdf

求解极小极大问题的新算法中文提要 中文提要 极小极大问题是一类重要的不可微优化问题，它不仅在工程设计、电子 电路规划、对策论等诸多领域中有着广泛的应用，而且还和非线性方程组、 多目标规划、非线性规划等数学问题有着紧密的联系 目前求解该问题的方法有直线搜索法、s q p 方法、信赖域算法、有效集 方法等例如，c c h a r a l a m b o u s 和a rc o n n 提出了直线搜索法，w m u r r a y 和l o v e r t o n 提出了投影拉格朗日方法，a v a r d i 提出了有效集信赖域算法 等。这些方法的理论条件较强，适用范围小。近年来，求解非线性规划的过滤 方法适用范围广，计算效果好，本文利用过滤方法思想讨论极小极大问题。 求解极小极大问题的通常做法是：将该问题转化为不等式约束优化问 题，再使用惩罚函数作为效益函数进行讨论。本文利用过滤方法的思想，提 出求解极小极大问题的一种新方法，每次迭代，分成法向步和切向步，其中 法向步改善可行性条件，切向步改善目标函数的值本文中可行性条件采用 非单调格式，从而放松了尝试步的接受条件，理论上算法更有一般性，实际 上也能提高计算效率。本文在没有积极约束梯度线性独立的假设条件下讨 论了算法的全局收敛性，并进行了数值实验 关键词：极小极大，信赖域，全局收敛性 作者：赵奇 指导老师：陈中文 an e wm e t h o df o rm i n m a xp r o b l e m a b s t r a c t an e wm e t h o df o rm i n m a xp r o b l e m a b s t r a c t t h em i n m a xp r o b l e mi so n eo fa ni m p o r t a n tn 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 ，i td o e sn o to n l yh a sb r o a d e ra p p l i c a t i o n si ne n g i n e e r i n gd e s i g n i n g 、e l e c t r o n i c m i c r o c i r c u i t sp r o g r a m m i n g 、g a m et h e o r ya n ds oo n ，b u ta l s oh a sv e r yc l o s er e a l a t i o n s h i pw i t hn o n l i n e a re q u a t i o n s 、m u t i o b j e c tp r o g r a m m i n g 、n o n l i n e a rp r o g r a m m m i n g e t c a tp r e s e n t ，t h e r ea r es o m em e t h o d s ，e g ，l i n es e a r c hm e t h o d ，s q pm e t h o d ，t r u s t r e g i o nm e t h o da n dt h ea c t i v e s e tm e t h o d ，f o rs o l v i n gm i n m a xp r o b l e m s f o re x a m p l e ， c c h a r a l a m b o u sa n da r c o n ng a v et h el i n es e a r c hm e t h o d w m u r r a ya n dl o v e r t o np r e s e n t e dt h ep r o j e c t e dl a g r a n g i a nm e t h o d a v a r d ip r e s e n t e dt h et r u s t r e i g o nm e t h o dw i t ht h ea c t i v e - s e t t h e s em e t h o d sh a v es t r o n g e rt h e r o t i c a lc o n d i t i o n s a n dn a r r o w e ra p p l i c a t i o n s r e c e n t l y , t h ef i l t e rm e t h o df o rn o n l i n e a rp r o g a m m i n gh a s b r o a d e ra p p l i c a t i o n sa n dg o o dn u m e r i c a le f f e c t t h em o t i v a t i o nf r o mf i l t e rm e t h o di s a p p l i e df o rm i n m a xp r o b l e m g e n e r a l l ys p e a k i n g ，t h em i n m a xp r o b l e mi sa l w a y st r a n s f e r e dn o n l i n e a rp r o g r a m r u i n gw i t hi n e q u a l i t yc o n s t r a i n t sa n dt h e ni ti sd i s c u s s e dw i t hap e n a l t yf u n c t i o na s am e r i tf u n c t i o n an e wm e t h o df o rs o l v i n gm i n m a xp r o b l e mi sp r e s e n t e dw i t ht h e m o t i v a t i o no ff i l t e rm e t h o di nt h i sp a p e r a te a c hi t e r a t i o n ，t h et r i a ls t e pi sd e v i d e d i n t on o r m a ls t e pa n dt a n g e n t i a ls t e p t h en o r m a ls t e pw i l li m p r o v et h ef e a s i b i l i t yo f t h ec o n s t r a i n t sa n dt h et a n g e n t i a lw i l li m p r o v et h eo b j e c tf u n c t i o n o nt h eo t h e rh a n d ， t h en o n m o n o t o n i cf r a n kw i l lb eu s e d ，w h i c hr e s u l t si nt h eg e n e r a l i t yo ft h ea l g o r i t h m a n dg o o dn u m e r i c a le f f e c t u n d e rn ol i n e a ri n d e p e n d e n c eo ft h ea c t i v ec o n s t r a i n t s ，w e a n a l y s et h eg l o b a lc o n v e r g e n c e f i n a l l y , w eg i v et h ep r i m a r yn u m e r i c a lt e s t k e y w o r d s ：m i n m a x ，t r u s t r e g i o n ，g l o b a lc o n v e r g e n c e ， i i w r i t t e nb yz h a oq i s u p e r v i s e db yp r o f c h e nz h o n g w e n 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不含其他个人 或集体已经发表或撰写过的研究成果，也不含为获得苏州大学或其它教育 机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明本人承担本声明的法律责任。 j - 研究生签名：每车日期：乒1 6 o ) p 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合 作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布 ( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 导师签名 起盘日期：j ! ! i ：) 啦 | 1| 簋缒日期：趔：夕虹 求解极小极大问题的新算法一引言 考虑 第一章引言 。m 舻i n1 m m a x 。f j ( z ) ， 其中办( z ) ( j = 1 ，2 ，m ) 是定义在肝上的二阶连续可微函数 价于非线性优化问题 问题( 1 1 ) 等 s t 赫一 0 ， m i n ( d ，i ) = 川最+ v 最r , ：e l l 2 ， 晖( ) = ( 露。，。，霹) r 2 求解极小极大问题的新算法 二 算法 考虑子问题 m i n 讥( 毋) = d “+ d 盯凤d ， s t v f d t = 0 , ( 2 3 ) 弧+ 扩”+ 一0 ， i l d t | i 。 其中风为问题( 2 1 ) 的l a g r a n g e 函数l ( x ，可，t ，a ，t ) 的h e s s e 矩阵的近似记 ( 2 3 ) 的解雌( ) = ( 雄，硭，) r ，在( z ，y k ，埘t 的尝试步d 七( ) = d j ( ) + ( ) 为了判断尝试步是否可接受，定义问题( 2 1 ) 中等式约束可行性的预测 下降量 p r e d k ( a ) = i i f k l i 2 一l i 最+ v 风t 靠( ) 1 1 2 和实际下降量 a r e d k ( a ) = i i f t l l 2 一i i f ( ( x k ，讥，“) t + 以( ) ) 1 1 2 如果a r e d k ( a ) p l p r e d k ( a ) ，p l ( 0 ，1 ) 为常数，则对于( 2 1 ) 的约束条件，法向 步靠( ) 是可以接受的但为了允许i i 最的非单调性，类似于文【2 】) 定义松 弛的实际下降量 r a r e d k ( a ) = m a x r k ，p 如i | 最一，m i l f ( ( x k ，y k ，t k ) r + d k ( a ) ) l i 2 其中v k - - 1 肛女，：l ，诈：m i n o ，p 1 是整数于是，接受尝 试步的条件可放宽为r a t e d 女( ) p l p r e 以( ) 关于r t 的计算，类似于文献【2 1 中算法r ，但这里选择范围更广 算法r ：选取序列满足o ，0 m i n c r a j 。，硎弧忆则令r k = l i f k l i 2 求解极小极大问题的新算法二 算法 同样，我们要求目标函数也有足够的下降，为此，我们定义( 2 1 ) 目标函 数的切向预测下降量 p r e 磙( ) = 饥( d ：( ) ) 一仇( d 七c a ) ) 以及关于整个尝试步的预测下降量 p r e ( ) = 一讥( ) ) 关于整个尝试步的实际下降量 如果 吖e ( ) = t k 一( “+ 壤( ) ) = 一磙( ) p r e ( ) 用”e ( ) 且p r e ( ) p r e d k ( h ) ( 2 4 ) 则要求目标函数和约束条件同时改善，否则，只需改善约束条件 算法2 1 步0 ：给定n p l ，y l ( o ，1 ) ，他 1 ，0 q ，p j 1 ，初始点( 黝，y o ，t o ) t j 护+ “，m 。0 ，k ：= 0 ，如：= 0 步1 ：( o ) ：= ，i ：= o ，计算f 七，v 取 步2 ：解子问题( 2 2 ) 和( 2 3 ) 得到耀( ( i ) 和嚷( ( ) ，调用算法r 计算凤 步3 ：若窿( ( ) = 4 c a ( ) = 0 ，则停止 步4 ：若( 2 4 ) 成立，则转步4 1 ，否则，转步4 2 步4 1 ：若r a r e d 女( a ( ) p t p r e d k ( a ( ) 或a r e d y k ( a ( ) 0 和 r a r e d k ( a ( i ) 的定义，对充分大的i 有r a r e d k ( a i ) ) p r e 呶( “) 其次，由甄0 知0 不是子问题( 2 3 ) 的稳定点，故问题( 2 3 ) 在= 0 存在可行下降方向五即 存在q 0 使得v 昭i = o ，瓠+ 萌0 且五+ 。+ 1 ) ) 及 州m ) ) = ；1 1 f k l i 2 一嗜雅+ i m ( 2 ， 当i 充分大时有p r e d k ( ac ) ( 2 1e t _ - 1 只| - m a ( i ) ( i 銎l 最i ( “ 9 求解极小极大问题的新算法三 全局收敛性 若銎1 只= 0 ，则由于f k 0 ，故存在某个民 0 使得p r e d k ( a ( i ) ) 卢。a ( o 根据引理1 及 i i d k ( a ( i ) | | l i 嚷( ac ) | | + 1 l ( ( i ) i | 2 a ( i ) 有： 剑里墨墨二里墨堡：! 型! ：! ! ! ：! 墨 一 尻 + 螋幽兰坠等掣生丝盟堂一。 故r a r e d ( a ( i ) p l p r e d k ( a ( ) 对充分大i 成立如果p r e ( ( i ) 用，r e ( ( i ) 且p r e ( ( ) p r e d ( a ( i ) 则p r e d ：t ( ( i ) 2p 觑( ( ) 那么 i 蕊a r e d ( a ( i ) 一1 i 垒旦划墨粤坠竺- o ，当i 斗0 0 根据算法，d 七( ) i p r e ( ( i ) ) 1 i 2 p z lc ac i ) ) j5 1 k 撕畀伍毗p 是成功迭代步如果矿e ( ( ) p 矽e ( ( ) 或p r e 以( ( t ) p r e 呶( ( t ) ，则 由算法，呶( ( t ) 也是成功迭代步 综上，引理得证 引理3 假设存在正整数k 。扩，使得对所有的k k 。有： 一1 r a r e d = m a x i | r 限胀，i i r 一，n l i f ( c z 柚幢，t k ) + 如旧( 3 2 ) 1 0 求解极小极大何题的新算法三全局收敛性 则对所有的k k ，有 七 i r + l i | 2 h - 躐鲰蜀一p 1r = k l z m j n k - r , u 矿e d r ( 3 3 ) 证明记尬。= m a x k l - v , 。1 _ p l i 最一r ” 对所有七k 成立从而a + l = a + 1 故靠- + 。o 由引理4 ，有l i m 女- + 。i i 最i l s l i m + 。上唼：l i m 羔= 0 a o 、p k - o oq o 、p 定理2 设 ( 弧，t 。) t ) 是算法2 1 产生的序列，则在假设条件下，该序列 的任一极限点( z 。，玑，厶) r 有f ( x 。，y 。，t 。) = 0 证明假设( 玑，) t 是( y k ，“) t 的任一极限点，反设命题不成立，则 存在无穷指标集合k 使 。l i m 。( x k ，y k ，t 女) = ：( j ，! ，+ ，2 ) ，f ( 3 ：，。) o 设以是子问题( 2 2 ) 对应于a = 乱的可行解 ( 1 ) 曼只0 时，取五：下s i g n ( 曼只) e 。+ m + 。趣，那么，五是子问题( 2 2 ) 对 t = l t = l 应于= 的最优解，根据引理2 中的证明有 删舭蛇2 1 蓥f i l - m r a k ) 心刈苎1 = 1 f d a - , , r = r a i n ，斟 ( 2 ) 曼只= 0 时，由于最0 故存在某个民 0 ( 3 6 ) v 砰d = 0 ， 、 i i d l i 。a 7 其中i i 鼠| | m 令出是问题( 3 6 ) 的解，那么，似( 以) 0 矛盾 1 8 求解极小极大问题的新算法 四 数值试验 第四章数值试验 问题的基本形式是 。r a 舻i n 逡笛乃( z ) ( 4 1 ) 我们利用文【4 】中的三个问题进行数值试验，问题如下： 问题1n = 2 ，m = 3 ，初始点z o = ( 1 ，一o 1 ) r ( z ) = 。 - i - ，b ( z ) = ( 2 一z ) 4 - ( 2 一) ，b ( 。) = 2 e x p ( 一z - 4 - z 2 ) 问题2n = 2 ，m = 3 ，初始点。o = ( 1 ，一o 1 ) f l ( z ) = z 4 - z ；，f 2 ( 正) = ( 2 一。i ) 4 - ( 2 一) ，b ( z ) = 2 e x p ( 一z l4 - j ：2 ) 问题3n = 2 ，m = 3 ，初始点z o = ( 3 ，1 ) f l ( z ) = = 。 4 - 。；4 - x l x 2 ，足( z ) = s i n ( x 1 ) ，r ( 。) = 0 0 8 ( x 2 ) 对于算法2 1 ，我们选取参数 。i 。= 1 0 5 ，。= p = 0 1 ，扩= 1 p = 0 0 1 ，p 1 = o 0 0 1 ，饥= o 2 5 ，7 2 = 2 ，a o = 2 并规定最大迭代数为1 0 0 ，序列 q ) 如下选取： a 02m i 邮9 ，i l s o l l + i i d o l l ，2 焘 初始点为：g o ，迭代次数记为n i t ，函数值计算次数和雅可比矩阵计算次数分 别记为f n g ，目标函数值记为t ，终止准则取为 r e s = m 8 z d n i i d y l l ) s1 0 1 9 求解极小极大问题的新算法四数值试验 计算结果见表一 n - t o n i tn fn gr e st l ( 1 , - 0 1 ) 56 6 l 6 7 3 1 b 91 9 5 2 2 e 0 2 ( 1 , - 0 1 ) 5562 4 6 5 0 b 82 0 0 0 0 e 0 3 ( 3 0 ，1 0 ) 1 62 11 72 1 7 6 6 b 66 1 6 4 3 8 1 求解极小极大问题的新算法 参考文献 参考文献 1 】z c h e ne ta l ，ag l o b a l l yc o n v e r g e n tt r u s tr e g i o na l g o r i t h mf o ro p t i m i z a t i o nw i t h g e n e r a lc o n s t r a i n t sa n ds i m p l e eb o u n d s ，a c t am a t h a p p l s i n i c a ，1 5 ( 1 9 9 9 ) p p 4 2 5 - 4 3 2 2 】m u l b r i c he ta l ，n o n m o n o t o n et r u s tr e g i o nm e t h o d sf o rn o n l i n e a ro p t i m i z a t i o n s u b j e c tt oc o n v e xc o n s t r a i n s ，m a t h p r o g ，7 7 ( 1 9 9 7 ) ，p p 6 9 9 4 【3 】薛毅，求解m i n m a x 问题的s q p 方法，系统科学与数学，2 2 ( 2 0 0 2 ) ，p p 3 5 5 一 【4 】a v a r d i ，n e wm i n m a xa l g o r i t h m ，j o p t i m t h e o r y a p p l ，7 5 ( 1 9 9 2 ) ，p p 6 1 2 6 3 4 【5 】y y ue ta l ，n o n m o n o t o n el i n es e a r c ha l g o r i t h mf o rc o n s t r a i n e dm i n m a xp r o b - l e m s ，j o p