（计算数学专业论文）一类非单调信赖域方法和数值试验研究.pdf

摘要 本文主要讨论了求解无约束极小化问题的非单调信赖域方法的相关 论题 在论文的第二章中，我们将非单调与自适应技术结合到信赖域方法 中，从而得到非单调的迭代序列相比于传统的信赖域方法，非单调的 算法放宽了接受迭代点的条件，在较大程度上改善了算法的实际计算效 果结合自适应技术，信赖域半径i 可以自动地进行调节以改进信赖 域方法的效率在信赖域子问题的求解上，利用b u n c h - p a r l e t t 分解构 造不定折线路径我们可以处理不定的近似海赛矩阵三k 这种不定折线路 径算法是容易应用的我们分析了这种算法的收敛性以及收敛速度数 值结果表明我们的算法是有效的 在第三章，我们首先比较了求解无约束最优化问题中两类非单调信赖 域算法的数值效率这两种算法的主要区别在于是否要求信赖域半径有 上界对于更有效的算法n t r 2 ，我们讨论了算法对于其输入参数肘， 以及初始信赖域半径a o 的敏感度通过选取适当的参数，我们可以提 高算法的数值效率在大量而详细的数值试验的基础上，我们给出了最 优的参数选择 关键词t 非单调信赖域方法，自适应方法，不定折线路径，无约束 极小化，总体收敛性，超线性收敛，参数 a b s t r a c t i nt h i st h e s i s ，w ec o n s i d e rs o m et o p i c sa b o u tt h en o n m o n o t o n et r u s tr e g i o n m e t h o df o ru n c o n s t r a i n e dm i n i m i z a t i o np r o b l e m s i nc h a p t e r2 ，w ec o m b i n et h en o n m o n o t o n et e c h n i q u ea n da d a p t i v et e c h n i q u e t of o r mat r u s tr e g i o nm e t h o d i n s t e a do ft h em o n o t o n es e q u e n c e t h en o n m o n o t o n e s e q u e n c eo ff u n c t i o nv a l u e sa r ee m p l o y e d w i ma d a p t i v et e c h n i q u e t h et r u s tr e g i o n r a d i u s c a l lb ea d j u g c e da u t o m a t i c a l l yt oi m p r o v et h ee f f i c i e n c yo ft r u s tr e g i o n m e t h o d s b ym e a l n so fb u n c h - p a f l e t tf a c t o r i z a t i o n w ec o n s t r u c ti n d e f i n i t ed o g l e g p a t hm e t h o d sf o rs o l v i n gt h et r u s tr e g i o ns u b p r o b l e mw h i c h c a nh a n d l et h ei n d e f i n i t e a p p r o x i m a t eh e s s i a n 既n er e s u l t i n gi n d e f i n i t ed o g l e gp a t ha l g o r i t h m s 唧e a s y t oi m p l e m e n t w ep r o v et h ec o n v e r g e n c ep r o p e r t i e so ft h e s ea l g o r i t h m sa n da n a l y z e i t sc o n v e r g e n c er a t e n u m e r i c a lr e s u l t sa r er e p o r t e dt os h o wt h a to u ra l g o r i t h mi s e f f i c i e n t i nc h a p t e r3 w ef i r s tc o m p a r et h en u m e r i c a le f f i c i e n c yo ft w oc l a s s e so fn o n - m o n o t o n et r u s tr e g i o n ( n t r ) a l g o r i t h m si nw h i c ho n eh a s u p p e rb o u n do nt h et r u s t r e g i o nr a d i u s ，a n dt h eo t h e rh a sn o ti nt h ec o n t e x to fu n c o n s t r a i n e do p t i m i z a t i o n f o ra l g o r i t h mn t r 2 , w ee x a m i n et h es e n s i t i v i t yo ft h ea l g o r i t h mo nt h ep a r a m e - t e r s ，硼c l l 柏m ，w h i c hr e l a t o dt ot h en o n m o n o t o n et e c h n i q u ea n dt h ei n i t i a lt r u s t r e g i o nr a d i u sa o w es h o wt h a tt h en u m e r i c a le f f i c i e n c yo fn t ra l g o r i t h mc a nb e i m p r o v e db yc h o o s i n ga p p r o p r i a t ep a r a m e t e r s o nt h eb a s i so fe x t e n s i v en u m e r i c a l t e s t s ，t h es u p e r i o rr a n g e so ft h e s ep a r a m e t e r sa l er e c o m m e n d e d k e yw o r d s 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 ，a d a p t i v em e t h o d ，i n d e f i n i t ed o g - l e gp a t h ，u n c o n s t r a i n e dm i n i m i z a t i o n ，g l o b a lc o n v e r g e n c e ，s u p e r l i n e a rc o n v e r g e n c e ， p a r a m e t e r s v 本文创新点 在无约束最优化问题的求解中，非单调技术受到越来越多的重视和应 用本文主要从理论和数值试验的角度研究了将非单调技术结合到信赖 域方法中的相关论题 本文的主要工作分为二部分， 在第一部分中，我们将非单调与自适应技术结合到信赖域方法中，从 而得到了一类非单调自适应信赖域算法相比于传统的信赖域方法，非 单调的算法放宽了接受迭代点的条件，在较大程度上改善了算法的实际 计算效果结合自适应技术，信赖域半径乱可以自动地进行调节以改进 信赖域方法的效率我们的算法与已有的非单调自适应算法【7 j 【2 8 】的主 要区别在于信赖域子问题的求解，利用文献【3 0 j 中提出的不定折线路径 算法，借助b u n c h - p a r l e t t 分解构造不定折线路径我们可以处理不定的近 似海赛矩阵鼠另外对于半正定的风我们构造了新的折线路径这种 不定折线路径算法是容易应用的我们分析了这种算法的收敛性以及收 敛速度数值结果表明我们的算法是有效的 第二部分的工作主要是针对非单调信赖域算法中的参数选择做了较 详尽的数值试验的研究通过选取大量的参数数据，我们首先比较了求 解无约束最优化问题中两类非单调信赖域算法的数值效率，这两种算法 的主要区别在于是否要求信赖域半径有上界我们发现当取消对信赖域 半径的上界限制时，算法效率有较大的提高对于更有效的算法n t r 2 ， 我们讨论了算法对于其输入参数m ，以及初始信赖域半径0 的敏感度 通过选取适当的参数，我们可以提高算法的数值效率在详尽的数值试 验和分析的基础上。我们给出了最理想的参数选择 c h a p t e r 1 i n t r o d u c t i o n i nt h i st h e s i s ，w em n s i d e rac l a 8 8o fa l g o r i t h m sf o rs o l v i n gu n c o n s t r a i n e dm i n i m i z a t i o np r o b l e m 罢雾m ) ， ( 1 1 1 ) w h e ，( 茁) i st w i c ec o n t i n u o u s l yd i f f e r e n t i a b l ea n db o u n d e db e l o w f i r s t ，w ei n t r o - d u c e 踯s t a n d a r dn o t a t i o n s ： 1 i i 札n o t a t i o ni | 0d e n o t e st h ee u c l i d e a nn o r mo n 舻 2 s u p p o s e 魄) i sas e q u e n c eo fp o i n t sg e n e r a t e db ya na l g o r i t h m ，w ed e n o t e f k = f ( g g k ) ，g k = g ( x k ) a n d 凰= h ( z k ) ，w h e r e 口( 甸舻a n dx 可c z ) 舻“哪 t h e 伊a d i e a ta n dh e s s i a no f ，( g ) e v a l u a t e da t 霉 3 玩i sas y m m e t r i cm a t r i x ，w h i c hi se i t h e rt h eh e s s i a nh ko ra na p p r c 口d m a t i o n o th k b ki sas a f e l yp o s i t i v ed e f i n i t em a t r i xb a s e do ns c b _ n a b e la n de s k o w 2 0 1 m o d i f i e dc h o l e s k yf a c t o r i z a t i o n ，b k2 b k + e k 。w h e r ee k = 0 - 迁b k i ss a f e l yp o s i t i v e d e f i n i t e , a n de ki sad i a g o n a lm a t r i xc h o s e nt om a k e 取p o s i t i v ed e f i n i t eo t h e r w i s e t r u s tr e g i o nm e t h o dn o wi sak i n do fi m p o r t a n ta n de f f e c t i v em e t h o df o rs o l v i n g ( 1 1 1 ) i tc 锄b et r a c e db a c kt ot h ew o r k so fl e v e n b e r g 1 2 】a n dm a r q u a r d t 1 3 o n n o n l i n e a rl e a s t - s q u a r e sp r o b l e m sa n dt h ew o r ko f g o l d f e l de ta 1 【9 】f o ru n c o n s t r a i n e d o p t i m i z a t i o n t h e nt h i sc l a s so fm e t h o d sw a sd e v e l o p e dt 0f o r mar o b u s tt h e o r e t i c a l a n dp r a c t i c a lf r a m e w o r kc o a t s i n i n gan u m b e o fl o c a l l yc o n v e r g e n ta l g o r i t h m sf o r s m o o t hu n c o n s t r a i n e dm i n i m i z a t i o np r o b l e m s ，s e e 4 1 【1 4 】【1 7 【1 8 i 【2 2 j t r u s tr e g i o nm e t h o d sa l eb a s e do nt h ef o n o w m gi d e a a te a c hi t e r a t i v ep o i n t 矾，i fi ti sn o tas t a t i o n a r yp o i n t ，8t r i a ls t e pi su s u a l l yg e n e r a t e db ys o l v i n gt h e f o n o w i n gs u b p r o b l e m r a i n c k ( d ) = 靠d + ；矿取d 8 t 1 f d l i s b 1 ( 1 1 2 ) n a n j i n on o r m a lu n i v e r s i t y c h e nj u n2 w h e r ea ki st h et r u s tr e g i o nr a x i i u 8 c o m p a r e dw i t ht h el i n es e a r c hs t r a t e g y , t r u s t r e g i o nm e t h o dd o e sn o tn e e d8 kt ob ep o s i t i v ed e f i n i t e f r o mn u m e r i c a le x p e r i m e n ta n dt h e o r ya n a l y s i s ，w ek n o wt h a tt h eb e h a v i o ro f t r u s tr e g i o nm e t h o da r ec l o s e l yr e l a t e dt ot h ec h o i c eo ft h em a x i m u mr a d i u saa n d t h es t r a t e g yo fa d j u s t i n ga k i nt r a d i t i o n a lt r u s tr e g i o nm e t h e 出t h et r o tr e g i o n r a d i u sa ki si n d e p e n d e n to fg ka n db k t h i ss i t u a t i o ns o m e t i m e sw o u l dd e c r e a s e t h ee f f i c i e n c yo ft r u s te e g i o nm e t h o d s t oi m p r o v et h i ss i t u a t i o n z h a n ge ta 1 3 1 1 p r o p o s e da n e w * t r u s tr e g i o ns u b p r o b l e m ，i nw h i c ht h ei n f o r m a t i o no fg ka n db k a r ee m p l o y e dt od e t e r m i n et h et r u s tr e g i o nr a d i u sa k ，s e e ( 2 1 2 ) w i t ht h i sn e w s u b p r o b l e m ，t h e yc o n s t r u c ta na d a p t i v et r u s tr e g i o nm e t h o d n u m e r i c a lr e s u l t s s h o wt h a tt h ea l g o r i t h mi sv e r ye f f i c i e n tf o rm o s to ft e s tp r o b l e m s f u r t h e r m o r e ，s o l v i n gs u b p r o b l e m ( 1 1 2 ) e f f i c i e n t l yi sc m c i mt ot r u s tr e g i o n m e t h o d i nf a c t w en e e do n l y 觚a p p r o x i m a t es o l u t i o nt oo b t a i ng l o b a lc o n v e r g e n c e a n dg o o dp r a c t i c a le f f e c t m o r er e c e n t l y , b a s e do nt h es i n g l ed o g l e gm e t h o d ，z h a n g e ta l 【3 0 】【2 9 jp r o p o s e ds o m ei n d e f i n i t es i n g l ed o g l e gp a t h sf o rt h es o l u t i o no f ( 1 1 2 ) w h i c hc a nd e a lw i t ht h en o n - p o s i t i v ed e f i n i t eb k t h e s ep a t h ea r ee a s yt oi m p l e m e n t i np r a c t i c e t h et r a d i t i o n a lt r u s tr e g i o nm e t h o di sac l a s so fd e s c e n tm e t h o d s 。i nt h a tt h e y g e n e r a t eas e q u e n c eo fi t e r a t e s 乳) s u c ht h a tt h en s s o d a t e ds e q u e n c eo fo b j e o - t i v ef u n c t i o nv a l u e s ，( 孤) ) i sm o n o t o n i c a l l yd e c r e a s i n g h o w e v e r ，s o m er e s e a r c h e s i n d i c a t et h a t ，a te a c hi t e r a t i o n ，t h ea l g o r i t h mw i t he n f o r c i n gm o n o t o n i c i t yo ft h e o b j e c t i v ef u n c t i o nv a l u ec a l lc o n s i d e r a b l ys l o wt h ep r a c t i c a lc o n v e r g e n c er a t ei nt h e m i n i m i z a t i o np r o c e s s at y p i c a lc a s ew h e r em o n o t o n i c i t yc a nc a l l s es e v e r el o s so f e f f i c i e n c yi sw h e nt h eo b j e c t i v ef u n c t i o nf e a t u r e sd e e pn a r r o wc u r v e dv a l l e y s f o r t h ed e t a i l so fn u m e r i c a le x a m p l e s ，i ti sr e f e r r e dt o8 e e 【6 】1 1 0 【2 3 】t h e r e f o r ei t a p p e a r st h a ta ni d e a lo p t i m i z a t i o nm e t h o ds h e , da l l o wa ni n c r e a s ei nf u n c t i o n v a l u ei ns o m ei t e r a t i o n s w h i l er e t a i n i n gg l o b a lc o n v e r g e n c e mt h eb a c k g r o u n d o ft h et t b o v er e s e a r c h e s ，t h en o n m o n o t o n et e c h n i q u eh a db e c o m ep o p u l a rf o ro p t i - m i z a t i o nm e t h o d si nt h el a t e s tt w e n t yy e n m i n1 9 8 0 s ，b a s e do nt h ei d e ao ft h e w a t c h d o gt e c h n i q u e ( 8 e ec h a m b e r l a i ne ta 1 3 1 ) ，g f i p p oe ta 1 【1 0 f i r s tp r o p o s e d an o n m o n o t o n el i n es e a r c hr u l ef o ru n c o n s t r a i n e dn e w t o n sm e t h o d s i n c et h e n 。 t h en o n m o n o t o n et e c h n i q u eh a sb e e ns t u d i e db ym a n ya u t h o r s t o i n t 【2 5 lg a v ea n a s s e s s m e n to nn o n m o n o t o n el i n es e a r c ht e c h n i q u e sf o ru n c o n s t r a i n e do p t i m i z a t i o n t h r o u g he x t e n s i v e l yn u m e r i c a le x p e r i m e n t s i n1 9 9 0 s ，d e n ge ta 1 【6 】f i r s te o m b i n e d t h en o u m o n o t o n et e c h n i q u ew i t ht r u s tr e g i o nm e t h o d sa n d p r o p o s e da n o n m o n o t o n e t r u s tr e g i o n ( n t r ) m e t h o df o ru n c o n s t r a i n e do p t i m i z a t i o n t h e nav a r i e t yo fn t r m e t h o d sf o rn o n l i n e a rp r o g r a m m i n gw e r ep r o p o s e db ym a n yr e s e a r c h e r s ，s e ef 4 】f 7 j 1 1 1 1f 2 3 1f 2 8 1 l i k em a n yo t h e ra l g o r i t h m s t r u s tr e g i o nm e t h o d sd e p e n do nt h ec h o i c eo fa c 7 iji n t r o d u c t i a n3 s e to fp a r a m e t e m f o rt h et r a d i t i o n a lt r u s tr e g i o nm e t h o d s ，g o u l de ta 1 f 8 1h a d e x a m i n e dt h es e n s i t i v i t yo ft h e s ea l g o r i t h m so nt h e i rp a r a m e t e r sr e l a t e dt ot h e s t e pa c c e p t a n c ea n du p d a t eo ft h et r u s tr e , o n s i m i l a r l y , t h en u m e r i c a lr e s u l t s o b t a i n e di ns o m el i t e r a t u r e s 【6 】1 7 1 2 8 1s h o wt h a tt h ep r a c t i c a lc o n v e r g e n c er a t eo f n o n m o n o t o n et r u s tr e , o na l g o r i t h m sa l s od e p e n d so n8 0 m ep a r a m e t e r s e s p e c i a l l y t h en o n n e g a t i v ei n t e g e rm ，t h eu p p e rb o u n do ft r u s tr e g i o nr a d i u sao rt h ei n i t i a l t r u s tr e g i o nr a d i u sa 0 s oe x a m i n i n gt h es e n s i t i v i t yo fn o n m o n o t o n et r u s tr e g i o n a l g o r i t h m st ot h e i rp a r a m e t e r sc o m db e 眦i n t e r e s t i n ga n dv a l u a b l et o p i c t h i 8t h e s i si so r g a n i z e d 蠲f o l l o w s mt h ef o l l o w i n gc h a p t e r2 ，w ep r e s e n ta n o n m o n o t o n ea d a p t i v et r u s tr e g i o nm e t h o dw h i c l ls o l v e st h es u b p r o b l e m ( 1 1 2 ) i 1 2 - e x a c t l yb yu s i n gt h ei n d e f i n i t ed o g l e gp a t ha l g o r i t h m n u m e r i c a lr e s u l t ss h o wt h e e f f i c i e n c yo fo u rn o n m o n o t o n et r u s tr e g i o nm e t h o d i nc h a p t e r3 w ec o m p a r et h e n u m e r i c a le f l l c i e n c yo ft h et w oc l a s s e so fn o u m o n o t o n et r u s tr e g i o n ( n t r ) a l g o - r i t h i n s f o rn t r 2a l g o r i t h m 。w ee x a m i n et h es e n s i t i v i t yt ot h ep a r a m e t e r s is u c h 隅 m ，w h i c hr e l a t e dt ot h en o n m o n o t o n et e c h n i q u ea n dt h ei n i t i a lt r u s tr e g i o nr a d i u s o f i n a l l y , t h em o s ts u i t a b l ec h o i c e so fp a r a m e t e r sa r er e c o m m e n d e d c h a p t e r2 n o n m o n o t o n ea d a p t i v et r u s t r e g i o na l g o r i t h m sw i t hi n d e f i n i t e d o g l e gp a t hf o ru n c o n s t r a i n e d f 上、1 1 n l m l z a t l o n 2 1i n t r o d u c t i o n w e c o n s i d e ra t r u s tr e g i o n a l g o r i t h m f o r s o l v i n g u n c o n s t r a i n e d m i n i m i 冽t i o n p r o b l e m 罢雾，扛) ， ( 2 1 1 ) w h e r e ( x ) i st w i c ec o n t i n u o u s l yd i f f e r e n t i a b l e m o r er e c e n t l y , z h a n ge t a 1 3 1 】p r o p o s e d8n e wt r u s tr e g i o ns u b p r o b l e m 船f o l - 1 0 w 8 m i n 机( d ) = 9 t d + z 1 - d r b k d ， s t i i d l is 女，( 2 1 2 ) w h e r e 氐= e l l g k l l m l = ，0 c 1 ，再瓦一8 反1 i i a n dp i san o n n e g a t i v ei n t e g e r t h i sm e t h o dd e f i n e sa a u t o m a t i c a l l yb a s e do ng ka n db k w i t ht h i sh e ws u b - p r o b l e m ，t h e yc o n s t r u c ta na d a p t i v et r u s tr e g i o nm e t h o d t h e o r e t i c a la n a l y s i sa n d n u m e r i c a lr e s u l t ss h o wt h a tt h ea l g o r i t h mi sv e r ye f f i c i e n t t h es i m p l ea n dp r a c t i c a lm e t h o d st oo b t a i na na p p r o x i m a t es o l u t i o no f ( 2 1 2 ) a r ep o w e l l 8s i n g l ed o g l e gm e t h o d 【1 7 a n dd e n n i sa n dm e i sd o u b l ed o g l e gm e t h o d f 5 1 b o t hm e t h o d sw o r k w e l lw h e nb ki sp o s i t i v ed e f i n i t e ，b u tt h e ya r eu n a b l et od e a l 4 6 h2 o ，l ，l o 协ea d a p t i v et r u s tr 研m a l g o r i t h m 。w i t hi n d e f i n i t e 姗蛔p a t h 5 w i t ht h en o n - p o s i t i v ed e f i n i t ee a s e r e c e n t l y , b a s e do nt h es i n g l ed o g l e gm e t h o d ， z h a n ge ta l1 2 9 l 【3 0 p r o p o s e ds o m ei n d e f i n i t es i n g l ed o g l e gp a t h sf o rt h es o l u t i o n o f ( 2 1 2 ) w h i c hc a nd e a lw i t ht h en o n - p o s i t i v ed e f i n i t eb k t h e s ep a t h sa r ee a s i l y i m p l e m e n t e di np r a c t i c e s o m er e s e a r c h e si n d i c a t e dt h a t ，a te a c hi t e r a t i o n ，t h em e t h o d 丽t he n f o r c i n g m o n o t o n i c i 够o ft h eo b j e c t i v ef u n c t i o nv a l u ec a nc o n s i d e r a b l ys l o wt h ec o n v e r g e n c e r a t ei nt h em i n i m i z a t i o np r o c e s s ，a s p e c i a l l yi nt h ep r e s e n c eo fn a r r o wc u r v e dv a l l e y s s o ，r e l a x i n gt h er e q u e s to nm o n o t o n i c i t ys o m e t i m e sc a l li m p r o v et h ee f f i c i e n c yo f 0 1 1 1 ：a l g o r i t h m g f i p p oe ta l 【1 0 1p r o p o s e dan o n m o n o t o n el i n es e a r c ht e c h n i q u e f o rn e w t o n 8m e t h o d s i n c et h e n ，t h en o n m o n o t o n et e c h n i q u eh a sb e e ns t u d i e db y m a n ya u t h o r s d u et ot h eh i g l le f f i c i e n c yo fn o n m o n o t o n em e t h o d ，t h i st e c h n i q u e h a sb e e nc o m b i n e dw i t ht h et r u s tr e g i o na l g o r i t h mt od e a lw i t hu n c o n s t r a l n e da n d c o n s t r a i n e do p t i m i z a t i o n s e e 6 11 7 1 【2 2 1 【2 3 l1 2 8 1 i nt h i sc h a p t e r , w ew i l ld i s c u s san o n m o n o t o n ea d a p t i v et r u s tr e g i o nm e t h o d w h i c hs o l v e st h es u b p r o b l e m ( 2 1 2 ) i n e x a c t l yb yu s i n ga l li n d e f i n i t ed o g l e gp a t h a l g o r i t h m c o m p a r e dw i t hf 7 】a n d1 2 8 1 ，o u ra l g o r i t h m 嘲ad i f f e r e n tc r i t e r i o no f a c c e p t i n gt h et r i a ls t e p 如a n de m p l o y sad i f f e r e n tt e c h n i q u ef o rs o l v i n gt h et r u s t r e g i o ns u b p r o b l e m t h en u m e r i c a lr e s u l t ss h o wt h a to u ra l g o r i t h mi se f f e c t i v e n 抡r e s to ft h i sc h a p t e ri so r g a n i z e da sf o l l o w s i ns e c t i o n2 2 讹d e s c r i b eo u r n o n m o n o t o n ea d a p t i v et r u s tr e g i o nm e t h o da n dg i v ea na l g o r i t h mf r a m e w o r k i n s e c t i o n2 3 ，f i r s t ，s o m ep r o p e r t i e so fb u n c h - p a x l e t tf a c t o r i z a t i o na n dt h ef o r m u l a t i o n o fn e g a t i v ec u r v a t u r ed i r e c t i o n sf o ri n d e f i n i t eb ka x ep r e s e n t e d t h e nw ed e s c r i b e t h ec o n s t r u c t i o no fi n d e f i n i t es i n g l ed o g l e gp a t h sf o rs o l i n gt h es u b p r o b l e m ( 2 1 2 ) t h e c o n v e r g e n c ep m p e r t i e so fo u ra l g o r i t h ma r ed i s c u a s e di ns e c t i o n2 4 f i n a l l y , i n s e c t i o n2 5 w eg i v en u m e r i c a lr e s u l t st os h o wt h a to u ra l g o r i t h mi se f f i c i e n tf o rt h e t e s tp r o b l e m s 2 2o u ra l g o r i t h m w ee m p l o yt h ea d a p t i v et e c h n i q u et ou p d a t et h et r u s tr e g i o nr a d i u s - ，8 8m e n - t i o n e di nt h ea b o v es e c t i o n ，i e w eo b t a i nt h et r i a ls t e p 如b ys o l v i n gt h ef o l l o w i n g s u b p r o b l e m 1 m i n 机( d ) = 靠d + ；矿鼠面 s t i i d l ls 女，( 2 2 1 ) w h e r e