（应用数学专业论文）非线性优化方法在大气运动可预报性研究中的应用.pdf

摘要 本论文分为两个部分： 第一部分提出了一个用于求解大规模非线性优化问题的算法，此 算法是一种非精确线搜索的共轭梯度法。它具有存储需求小、收敛速 度快的优点，实质上是一种特殊的二维拟牛顿方法。它避免了常规的 共轭梯度法在求解非线性优化问题中的缺点。在一维搜索中，采用了 齐次函数插值的方法，比以往用抛物线插值的方法提高了收敛速度。 数值计算结果表明此算法比目前公认的数值效果最好的p r p + 方法普 遍更有效。 论文第二部分对非线性最优扰动进行了较深入的研究，提出了最 大值原理，将通常要用条件非线性最优化来解决的问题化为无条件最 优化问题。同时根据此结论，通过变量变换，把目标函数的维数降低 了一维，从而在很大程度上减小了计算量，提高了计算效率。最后以 l o r e a z 方程为侧，数值求解对应的非线性优化问题，采取的优化方法是 第一部分的修正共轭梯度法。揭示了非线性最优扰动与线性最优扰动 的根本区别。 关键词：无约束最优化、共轭梯度法、非精确线搜索、非线性优化、 可预报性、扰动 a b s t r a c t l i d sp a p e ri ss e p a r a t e di n t ot w op a r t s ： i nt h ef i r s tp a r t ，a l la l g o r i t h mf o rs o l v i n gl a l g es c a l en o n l i n e a r o p t i m i z a t i o np r o b l e m s i sd e s c r i b e d i ti sac o n j u g a t e g r a d i e n tm e t h o db yu s i n gi n e x a c tl i n es e a r c h ，b yv i r t u eo f t h e i rs t o r a g es a v i n gp r o p e r t i e sa n d g r e a t l yc o n v e r g e n c er a t e 】i ti sas p e c i a l2 - d i m e n s i o n q u a s i n e w t o nm e t h o di ne s s e n c e w i t hh o m o g e n e o u sf u n c t i o ni n t e r p o l a t i o ni n s t e o x lo fp a r a b o l i ci u t e r l ) o l a t i o n l i c a l g o li t h mc a nb eg r e a t l ya c c e l e r a t e dc o n v e r g e n c er a t eb yi n e x a c tl i n es e a r c h t h ei t c h y a l g o l i t h ma v o i d ss o m es h o t t c o m i n ge x i s t e di nc o l n f l l o nc o n j u g a t eg r a d i e n ti l l e h o d i nt h i sp a p e r ，t h en e wa l g o r i t h mi sc o m p a r e dt m m e r i e a l l yw i t ha n o t h e rc o n j u g a t e g l m l i e n t m e t h o d t h e r e s u l t s o fn u m e r i c a l t e s t s i n d i c a t e t h a t i t i s a g o o d a l g o , i t h m t h a n t h e ， r p a l g o r i t l m r 1 nt h es e c o n dp a r t ，w eh a v ea u r t h e rr e s e a r c ht on o n l i n e a ro p t i m u mp e t t m b a t i o l l m i d ( 1 0 s ( r i b et h em a x i m a lp r i n c i p l ei tc a l lt r a n s f o r mt h ep r o b l e mo fe o n d i t i oj m lo p t i m i z a ti o nt ot h ep r o b l e mo fn o n - e o n d t i o n a lo p t i m i z a t i o n 0 l it i r eb a s i so ft h i st h e o r y , w en l a k et i l ed i m e n s i o no ft h eo b j e c tf u n c t i o nd o w na n di l l l p r o v et h ec o i n p l l | a t i o t m ie l - f i c i e n c yb ) ，u s i n gt h et r a n s f o r m a ，t i o no fv a r i a t i o n s a tl a s t , ，w ec h o o s el o t e l l ze q u a t i o n a ne x a m p l et h em e t h o do fo p t i m i z a t i o nw ep r e f e r e di s c o n j i t g a t eg r a d i c n tm e t h o d l nt l mnr s tp m tt h en o n l i t l e a , rc h a r a c t e r i s t i c so ft h em o d e la r ed i s c l o s e ( 1 ，t o n l yf i o i n t h ei n i t i a l p a t t e r n sb u ta l s of r o mt h en o n l i n e a re v o l u t i o n k e yw o r d s ：l a r g es c a l eu n c o n s t r a i n e do p t i n d z a t i o n c o n j u g a t eg r a d i e n tm e lh o d e x a c tl i n es e a r c h ，n o n l i n e a ro p t i m i z a t i o n ，p r e d i e t a b i l i 吼p e r t u r b a t i o n ；硕士学位论文答辩委员会成员名单 孓年墨r 骖u 姓名职称单位备注 务农写9 欲旋错舰壮涨西氟 脉撇、殿援僻烨胁蝴、皋 礴星瞳融毅授4 繇炜允六匿颊辣 毕平计炜轹绛施大涨匿糸 枷鸟 学位论文独创性声明 术人所呈交的学位论文是我在导师的指导f 进行的研究i 作及取得的研究成粜。 据我所知，除文t p 已经注明引f j 的内容外，术论文不包含其他个人已经发发或撰写 过的研究成果。对本文的研究做；l 重要贡献的个人和集体，均已在义中作r 卿椭说 i 纠并表示谢意。 作者签名：苏意九【l 期：够夕、汐 学位论文使用授权声明 术人完全了解华东师范大学有关保留、使川学位论文的规定，7 校有权保科、 位论文并向固家土管部j 或其指定机构送交论文的电了版和纸质版。有权将。学位论 文川i ：非赢利口的的少量复制并允许论文进入学校冈书馆被询。有权将位论艾 的内容编入数据库进行检索。有权将学位论文的标题和摘耍汇编版。保密的。位 论义在解密后适朋木规定。 学位论文作者签名纭磊导! f i i j 签私 u 期：纺岁，芗们 烈永瑚 第一章一个高效的修正共轭梯度算法 1 1引言 共轭梯度法是最优化中常用的方法之一。它具有算法简便、存储 需求小等优点，十分适用于大规模优化问题。在石油勘探、大气模拟、 航空航天等领域出现的特大规模的优化问题常常是利用共轭梯度法求 解的。 在所有需要计算导数的优化方法中，最速下降法是最简单的，但它 速度太慢。牛顿法收敛速度很快，被广泛认为是非线性规划中最有效 的方法。但牛顿法需要存储二阶导数信息，以及通过求解线性方程组 来计算搜索方向，这对于求解大规模问题几乎是不大可能办到的。而 共轭梯度法由于其算法的简便性，所需存储量等方面均与最速下降法 差别不大，对于正定二次目标函数，当执行精确一维搜索时，其收敛 速度有二次终止性。对于满足一定条件下的一般非二次函数，虽然采 用精确一维搜索与再开始技术的共轭梯度法有总体收敛性，但不再有 二次终止性。另外，实行一维精确搜索时，随着叠代次数的增加，函 数下降的幅度越小，因此产生了用近似一维搜索的共轭梯度法来解非 二次函数的优化问题，这种方法时于满足一定条件下的一般非二次函 数，也有总体收敛性，因此共轭梯度法在实际中得到广泛的应用。 1 2 共轭梯度法 共轭梯度法是f l e t c h e r 和r c c v c s ( 1 9 6 4 ) 直接由h e s t e l l e s 和t i e f d ( 1 9 5 2 ) 的 解线性方程组的共轭梯度法发展而来的，其一般算法如下： 设目标函数，( z ) 的水平集 l = f z 月“：，( z ) s ，( z 1 ) ，n 2( i ) 有界，( z ) 的导数l i p s e h i t z 连续： l i ，( t ) 一，( i ) | | l r i ， v z ，虿r ” ( 2 ) 其中采用e u c l i d 模。：c ，为初始点( 列向量) 。，的极小点r 。通过在方 向轧上的线拔索序列 墨二王二全壶垫塑丝生兰堑竖堕墨鲞 s l = 一g l ，乱+ l = 一g k + 1 + k 8 k 七= l ，2 ，一，n l 在( 5 ) 式中，弧= _ ，( z t ) 是，在孤的梯度，其中b t 由共轭条件 s 矗l h s k = 0 ，k = 1 ，2 ，n 一1( 6 ) 所确定，其中h = ，“( z ) 是，的h e r e 阵其中上标r ，表示转置 其基本原理是：对于二次正定函数，在精确线搜索时，按( 5 ) 和( g ) 确定的搜索方向是两两共轭的线性无关向量，第 ( 曼n ) 次精确线搜索 得到的点z 是函数- 厂在k 维子空间x k + s p a n ( s 。，豫) 中的极小值点。 因此在搜索次数不大于n 时可求得极值点。此时各梯度向量g 。，9 2 ，g t 是两两正交的。注意，如果第一次线搜索的方向不是最速下降方向， 则虽然相继的两个线搜索方向是共轭的，但在所得的( 2 ) 个线搜索 方向不一定是两两共轭的。这时算法可能不会在有限次求得极小点。 在共轭梯度法中由b * 的不同表达形式产生不同的算法，分别叙述 如下： 由( 5 ) 5 式得d a n i e l 的形式： = 1 2 ( 7 ) 为避免矩阵的存储，用差分来近似( 当是二次函数时是精确地) 表示 ( 6 ) 式，得h e s t e n e s s t i e f e l ( 简称h s ) 的形式( c f h e s t e n e s s t i e f e l1 9 5 2 ) ： 心糍等掣，b 啪， 当第k 次线搜索( 3 ) 是精确时， ( 8 ) 式化为 “：亟血型，女：1 , 2 8 ；虬 笙二童二尘壹塾塑堡生苎塑竖壅茎兰， 又当k ：l ，或女2 ，且第一1 次线搜索也是精确时，有p o l a k r i b i e l e i o l y a , f 简称p r p ) 的形式 蠹g k 七= l ，2 我们知道，当，是二次函数且按( 4 ) ，( 5 ) ，( 6 ) 搜索时，有 彰1 9 k = 0 ，j 女 ( 1 2 ) 这时( 1 0 ) 式成为共轭下降法( c o n j t ，g a t ed e s c e n t m e t h o d ) ( 简称c i ) 方法) 的形 式( c f f l e t c h e r ，1 0 s o ) ： “：一g ；i + l g k + l ，女：1 ，2 8 ；9 k ( 8 ) 式成为d y 形式( c f d a i y u a n ，2 0 0 0 ) 。* = 恭t - ，k = l , 2 ( 1 1 ) 式成为f l e t c h e r r e e v e s 简称f r ) 的形式 沁：挚，：l ，2 雕肌 ( 1 3 ) ( 1 5 ) 除了以上方法，还有混合( h y b r i d ) 共轭梯度法，如( c f t o u a t i a h m e d s o l e y ) ： b k = m 泖，m m ( 畿 掣) ) ( j 6 班鲰 它实质上是最速下降法，p r p 方法和f r 方法的混合。还有最速下降 法，h s 方法和d y 方法的如下混合： ，a x ( o , m i n ( 糍 二掣，碧血业1 ) ) - g k ) 5 ( m + l 一肌) ” 1 3 非精确搜索的共轭梯度法 以上各种共轭梯度法对于目标函数是二次凸函数，线搜索是精确 时效果是一样的，即从同一个初始点出发，得到的点序列是相等的。 但应用于非二次目标函数时结果是大不相同的。虽然对于非二次凸函 第一章一个高效的修正共轭梯度算法 数( 即使是二次凸函数，对于大规模问题，或初鲐点远离极值点时，由 于计算机舍入误差的存在) ，共轭梯度法并不具有有限终止性。但理 论上和数值实验上都已经表明共轭梯度法仍然不失为一个好的算法。 由于共轭梯度法简便、存储需求小，在一定的条件下具有n 步二阶收 敛性，特别适合于计算大规模的优化问题。在非二次函数的优化问题 的各种算法中，一般采用两个技术，一是近似线搜索，因为精确线搜 索的计算机开销太大。二是再开始技术，即在某些情况取负梯度方向 为搜索方向，这是必须的，因为在二次正定函数的特殊情形下，第一 步的线搜索方向必须是负梯度方向才具有二次终止的性质， 近似线搜索：从z t 点出发，沿方向s t 作线搜索，当满足一些条件 时线搜索完成，得到下一个可接受点z 川= z 。4 - o , s 。，称为近似线搜索， 通常采用如下的准则 蛾s * c t 必t ，o c t j 1 ( 1 8 ) 也称为共轭下降公式。 f ( t k4 - a 8 ) s f ( x ) + c 2 a g f s ，0 如 0 ( 2 0 ) 也称为充分下降条件。 最l s 女q 露8 k ，0 c 2 c l “8 ) ( 1 9 ) f 2 0 ) f 2 1 1 其中( 1 9 ) 和( 2 1 ) 两式称为w o l f e p o w e l l 条件；( 1 8 ) 和( 1 9 ) 两式称为强 w o l f e p o w e l l 条件。 重开始技术：重开始技术是必要的，因为即使是二次凸函数，如果 第一次的搜索方向不是最速下降方向，共轭梯度法的收敛速度可能只 是线性收敛的( c f c r o w d e r & w o l f e ，1 9 6 9 ) 。但每n 步沿负梯度方向重开始 的策略对于大规模问题是无意义的。通常采用重开始判别准则有如下 两种： 9 矗l 轧+ l c 4j b 女+ l 2 1 1 8 + t i 2 ，0 哪0 l 肌+ i ，0 0 ，m l 是实常数。 记t = t j ，j = l ，2 ，3 为三个不同的点，记乃= f ( t ，) ，j = 1 , 2 ，3 ，d j = f 似，) ，则有 t t o = t 3 + 7 n d l ( 岛一f 3 ) ( t l 如一r ) ( d l t 3 ) - d 2 ( f , - & ) ( t 型 d 3 ) 一( n 一凡) ( d 2 一d 3 ) d 3 ( t 2 t a ) ( d l d 3 ) 望! ! ! ! 二垫! ( 望! 二望12 ( n 凡) ( d z 一风) ( 3 1 ) ( 3 2 ) 线搜索的初始步长对于算法的效率起着重要的作用。我们的程序 在线搜索的初始步长取为： r a i n ( 1 ，2 i ( ，( z ) 一e s t ) ( g t s k ) 1 ) 其中e s t 是目标函数的极小点的估计值当目标函数的极小值未知时， 在第一步线搜索时初始步长取为l ，以后第k + l 步线搜索的初始步长 驭为上一步线搜索结束时的步长。 终止条件是( c fl i u & n o c e d a l ) ： 1 1 9 k | | b + 1 ，它的轨道关于z 一9 平面是中心对称的。取权 矩阵w = ，时目标函数的最大值点也县有这种对称性。我们求出一个 最大值点，根据对称胜就得到另一个。 以下我们用球坐标变换z = r c o s 日c o s 记= 月c o s 日s i n 妒，z = 尺s i n 口把条 件极值问题化为无条件极值问题，并且使得求梯度更方便和快捷： 球坐标下的l o r e n z 方程为 陲豢鎏兰篓麓州m 妒 数 其中，- ，2 ，3 是月，妒，口的函数，可以用倍角公式化为2 妒，- ，0 的函 q i r s 1 i 8 1 h 再利用三角公式，令= a r c t a i 高，得 掣一6 j ( 1 + 2 卅2 6 几! ! ! ! 丝s i i i 扫 c 。s ( 2 妒+ 曲。) l 芸s i n 2 妒姓忭口 7 圳 舢 川一 毯朴 整书器扣擎 止 ，i，、l【 器 几 凡 iii，、lilll、 笪三主兰墅生垡丛望蔓兰垄! 亟圣叠! 塑垫些塑窒主塑廛盟 一 ：1 8 解九个微分方程的方程组： 初始条件为 塑7 0 i , d r o ，1a 妒o ，l 8 口 b 铀，堂孕q 妒o 。a 妒a o 口丽 坠一o | 2 a r 0 1 l8 毒j 净 l6 i 塑，一a o r a a f ，r o o ：o 却1 3 o 妒：蕞蓊 i 靶i堂拿皂c p o o 妒a 垆o a pe 巧i 堕一o 、8 r ? 娃8 孑? 强葫、 o ?壁擘母jo 妒b j 0 88 酝 竖一8 h 8 最t 8 k 8 审jo b 0 6 熟，堂譬皂a 妒a o 矿石丽 竺一。氏。诧o 38 莓jo h 、j 6 a 靠a r a a 垆a a 万石瓦 厅( o )= 风 驴( o )= 妒n o ( o )= 如 罂( o ) ：o 静、。 蓊? 一 蓊o 刮 秽? 刮 蓊卜。 硫( o ) 2 1 就同时解得我们需要的目标函数值7 ，以及偏导数( 蓑，裟) 可作为梯 度向量。 ”o 型时坦堕程有三个平衡态：( o ，o ，o ) ，( 、届f 可，币_ 二可，一1 ) ， ( _ 的一1 ) ，一6 ( r 一1 ) ，r 1 ) ( 后两个平衡态关于z 一平面中心对稚) 。 当， ? ( s + b + 3 ) m b 1 ) 时，这三个平衡态都是不稳定的。 当参数取典型的值：s = ，r = 2 8 = 时，有混沌现象发生。除 原点以i 冲m 。，力曲- - 个平衡点为i ( 0 6 娩：6 以，2 b 7 ) ，8 ( 一3 6 以，一6 以，2 7 ) ，茬原点附迸 第二章非线生优化方法在大气运动可预报性研究f l , 的应用 出发的轨道将在这三个平衡态附近反复地无规则地绕行。方程的解具 有对初值的敏感性。鉴于此原因以及计算的截断误差和舍入误差的原 因，积分的时间长度丁不能取得太大。另外由于本方程的混沌性质，我 们还要限制a ，t 的大小，为此，我们可以取as0 1 ，t s0 5 利用常微分 方程的m a t l a b 求解程序o d e 4 5 来求。根据极值原理，我们采用球坐标 变换。以下我们取若干个不同的a ( 从。叭到0 1 ，问隔0 1 ) ，及不同的 t ，r 从01 到0 5 ，间隔0 ，l 。n ：0 0 1 时取初始值点= 0 6 6 ，靠= 一0 0 i ， o = 0 0 2 时取初始值点为= o 0 1 时得到的最值点，直至计算到n = 0l 时 对应的最大值点，及对应的最大值。 在数值模拟过程申，我们不能穷尽所有的初始模态。为此，我们考 察在所有初始距平模态中具有重要作用的初始模态，即在预报时刻非 线性发展最大的模态，这在提高大气运动预报技巧方面具有非常重要 的意义。 条件非线性最优扰动实际上就是相应目标函数的全局极大值点，在 优化计算中，选取多个初始猜测值，如果这几个值都正确地收敛到某 一点，且具有相同的目标函数值，那么，我们认为该点就是目标函数 的一个极值点。有时，可能会有几个局部极值点，在约束条件范围内， 它们是非常有限的，此时，只要通过比较目标函数值就可以确认目标 函数的全局极大值点。具体数值结果参见如下表格。 第= 章非线性优化方法在起气运动里预报一塑窭主堕壁旦 f = o 1 时： ar 妒 8 0o l0 0 3 6 506 7 4 7 ( j0 0 ( 1 2 o0 20 0 7 3 l0 6 7 4 700 0 0 5 o 0 3 0 1 0 9 60 6 7 4 70 0 0 0 7 0 0 40 1 4 6 106 7 4 7 00 0 0 9 0 ( 1 5 0 1 8 2 706 7 4 700 0 1 2 0 0 60 2 1 9 2 06 7 4 7o 0 0 1 4 0 0 702 5 5 70 6 7 4 7 0 0 0 1 6 lo 0 80 2 9 2 306 7 4 7 一o0 0 1 8 10 0 903 2 8 806 7 4 7 0 0 0 2 1 l0 103 6 5 4 06 7 4 70 0 0 2 3 t = 0 2 时 ar妒 口 0 ( 1 l0 1 2 0 00 6 6 2 0 00 ( 0 4 1 2f ) 2 4 0 ( 10 6 6 2 ( )一0 【) 0 0 9 0 0 30 3 6 0 00 6 6 2 00 0 0 1 3 00 404 8 0 006 6 2 io 0 0 1 7 0 0 506 0 0 00 6 6 2 200 0 2 2 u0 607 1 9 906 6 2 30 0 0 2 6 0 0 70 8 3 9 906 6 2 3 00 0 3 0 0 0 80 9 5 9 90 6 6 2 4 一( 1 0 0 3 5 o0 9 10 7 9 80 6 6 2 400 0 3 9 0ll1 9 9 706 6 2 40 0 0 4 3 i 、= o 3 时 r 妒 口 o o l0 ，3 9 i 70 ，6 6 1 40 0 0 0 7 0 0 207 8 3 40 6 6 1 50 0 0l 2 00 3 11 7 4 90 ，6 6 1 600 0 1 8 0 0 4 1 5 6 6 40 6 6 1 700 0