（运筹学与控制论专业论文）优化中空间分解方法的某些研究结果.pdf

摘要 本文主要研究非线性规划中的一类空间分解方法，包括适于并行的光滑和非光滑空 间分解方法、适于串行的非光滑分解方法给出各种方法的收敛性及收敛速度定理的证 明，并对其中的一类空间分解方法给出数值试验 本文取得的主要结果属于理论性的，可概括如下： 1 在第二章中，我们在综述已有研究工作的基础上给出一种空间分解原理，引进算法 映射等概念，把算法看成是点到集合的映射( 集值映射) ，绘出一个空间分解方法的 统一结构与描述，对不同的具体集值映射构造出适于串行的、适于并行的异步及同步 空间分解方法，并且应用集值分析，对各类方法形成一般的收敛理论，即利用闭映射 的概念来证明算法的主要收敛性定理，使得该理论在包含已知的收敛结果的同时， 提供了几个新的结果最后在这个统一结构中给出具体的空间分解方法，如并行梯 度分布( p g d ) 法、并行变量分布( p v d ) 法、ja l c o b i 块法、并行变量变换( p v t ) 法， “协分解法等算法 2 在第三章中，首先给出几种非单调p v t 算法及其收敛性定理，然后利用负曲率方向 和二次曲线搜索，给出了非凸无约束规划的二阶p v t 算法，证明了算法的收敛性定 理，最后，给出相应的数值试验，及数值试验结果 3 研究非光滑分解算法及其收敛性是本文的一个主要工作，在第四章中，利用m o r e a u - y o s i d a 正则化，给出一种无约束p v t - m y r 算法，并证明了算法的收敛性定理及收敛 速度定理给出了具有块状结构约束的非光滑p g d 算法及其收敛性对于具有不可 分离约束集的非光滑问题，给出了非精确p v d 算法及相应的收敛性定理最后，利 用次梯度投影给出非光滑约束p v t 算法及其收敛性定理 4 由于非光滑函数自身的特点，它的二阶展开不易得到，难于构造出快速优化方法在 第五章中，我们利用凸函数的甜弘分解理论，对一类dc 函数进行“让分解，利用 n l a g r a n g e 函数，给出d c 函数的二阶展开式，从而给出无约束和约束d c 规划的 空间分解算法，即“v 分解算法，并证明算法是超线性收敛的 关键词：非线性规划，非光滑最优化，m o r e a u - y o s i d a 正则化，“v 一分解，空间分解， 并行计算 a b s t r a c t t h i sd i s s e r t a t i o nm a i n l ys t u d i e sac l a s so fs p a c e - d e c o m p o s i t i o na l g o r i t h m sf o rn o n l i n e a r p r o g r a m m i n gp r o b l e m s ，i n c l u d i n gs m o o t ha n dn o n s m o o t hs p a c e - d e c o m p o s i t i o na l g o r i t h m s s u i t a b l et op a r a l t e l i z i n ga n dn o n s m o o t hs p a c e - d e e n m p o s i t i o na l g o r i t h m ss u i t a b l et os e r i a l i z i n g t h e c o n v e r g e n c et h e o r e m so i lc o n v e r g e n c ea n dc o n v e r g e n c er a t ef o rv a r i o u sa l g o r i t h m sa r ed e m o n - s t r a t e d ，a n dn u m e r i c a le x p e r i m e n t sf o ro n e c l a s so fs p a o e d e c o m p o s i t i o na l g o r i t h m sp r o p o s e di n t h i sd i s s e r t a t i o na r er e p o r t e d t l em 越nr 端u l t so b t a i n e di nt h i sd i s s e r t 戤i o na r es u m m a r i z e d 矗8f o l l o w s ： 1 + i nc h a p t e r2 ，t h es p a c e - d e c o m p o s i t i o np r i n c i p l ea n dt h ec o n c e p to fa l g o r i t h mm a p p i n g s ”ei n t r o d u c e db a s e do nt h ep r e s e n tr e s e a r c hr e s u l t s 1 e a d i n gt oau n i f y i n gf r a m e w o r ko f s p a c e - d e e o m p o s i t i o na l g o r i t h m si nw h i c h a l g o r i t h mi sr e g a r d e d 8 sas e t - v a l u e dm a p p i n g ， d i f f e r e n ts p e c i f i cs e t - v a l u e dm a p p i n g sp r o d u c ev a r i o u ss p a c e - d e c o m p o s i t i o na l g o r i t h m ss u i t - a b l et os e r i a l i z i n g ，a s y n c h r o n o u sp a r a l l e t 诬i n go rs y n c h r o n o u sp a r a l l e l i z i n g ag e n e r a lc o i l v e r g e n c et h e o r yi s e s t a l i s h e db a s e do ns e t v 越u e da n a l y s i s ，n a m e l yt h em a i nc o n v e r g e n c e t h e o r e mi sd e m o n s t r a t e db a s e do nt h en o t i o no fc l o s e ds e t - v a l u e dm a p p i n g s t h eg e n e r a lt h e o r yn o t o n l yu n i f i e st h ee x i s t i n gc o n v e r g e n c er e s u l t sb u ta l s op r o v i d e ss e v e r a ln e w r e s u l t s s e v e r ns p e c i f i cs p a c e - d e c o m p o s i t i o na l g o r i t h m s ，i n c l u d i n gp a r a l l e lg r a d i e n td i s - t r i b u t i o nm e t h o d ( p g 劲，p a r a l l e lv a r i a b l ed i s t r i b u t i o nm e t h o d ( p v d ) ，p i e c e w i s ej a c o b i m e t h o d ，p a r a l l e lv a r i a b l et r a n s f o r m a t i o nm e t h o d ( p v t ) ，a n d “v d e c o m p o s i t i o nm e t h o d ， a r ed e r i v e df r o mt h eu n i f y i n gf r a j n e w o r k ， 2 ，i nc h a p t e r3 ，s o m en o n m o n o t o n ep v t a l g o r i t h m sa r ec o n s t r u c t e da n dt h e i rc o n v e r g e n c e t h e o r e m sa r ed e m o n s t r a t e d as e c o n d - o r d e rp v t a l g o r i t h mf o rs o l v i n gn o n c o n v e xu n c o n - s h a i n e do p t i m i z a t i o np r o b l e m s ，b a s e do nn e g a t i v ec u r v a t u r ed i r e c t i o n sa n dq u a d r a t i cc n s v e s e ”c h a s li sp r o p o s e d ，a n di t sc o n v e r g e n c et h e o r e mi sp r o v e n n u m e r i c a le x p e r i m e n t so ft h e s e c o n d - o r d e r 壬) v ta l g o r i t h ma r er e p o r t e dt os h o wt h ee f f i c i e n c yo ft h e 蠢g o r i t h m 。 3 a n o t h e rc o n t r i b u t i o no ft h i sd i s s e r t a t i o nl i e si nt h ec o n s t r u c t i n go fn o n s n m o t hs p a c e - d e c o m p o s i t i o na l g o r i t h m sa n dt h e i rc o n v e r g e n c et h e o r e m s ，i nc h a p t e r4 ，a nu n c o n s t r a i n e d p v t m y r a l g o r i t h m ，b a s e do nm o r e a u - y o s i d ar e g u l a r i z a t i o ui sg i v e na n d i t sc o n v e r g e n c e t h e o r e mi sd e m o n s t r a t e d ，an o n s m o o t hp g d a l g o r i t h md e m i n g w i t hb l o c ks t r u c t u r ec o n - s t r a i n t si sp r e s e n t e da n di t s c o n v e r g e n c ei s e s t a b l i s h e d a ni n e x a c tp v d a l g o r i t h mf o r n o n - s e p a r a b l ec o n s t r a i n e dn o n s m o o t hp r o b l e m si sp r o p o s e da n di t sc o n v e r g e n c et h e o r e m i sp r o v e d ap v 霉a l g o r i t h m ，a d o p t i n gs u b g r a d i e n tp r o j e c t i o nt e c h n i q u e ，f o rs o l v i n gn o n ” s l n o o t h l yc o n s t r a i n e do p t i m i z a t i o np r o b l e m s a n di t sc o n v e r g e n c er e s u l t sa r ep r e s e n t e da 8 4 b e c a u s eo ft h ei n s t r i n s i cf e a t u r e so ft h e m ，s e c o n d o r d e re x p a n s i o n so fn o n s m o o t hf u n c t i o n s 8 a en o te a s i l ye s t a b l i s h e da n df a s ta l g o r i t h m sa r en o te a s yt oo b t m n i nc h a p t e r5 b a s e do n t h e “弘c o m p o s i t i o nt h e o r yo fc o n v e xf u n c t i o n s ，s e c o n d o r d e re x p a n s i o n s a r eo b t a i n e df o ra c l a s so fd c f u n c t i o n s ，w i t ht h eh e l po f u - l a g r a n g i a n s a c c o r d i n g l y ，as p a c e - d e c o m p o s i t i o n a l g o r i t h m n a m e l y “v d e c o m p o s i t i o na l g o r i t h m f o rs o l v i n gu n c o n s t r a i n e da n dc o n s t r a i n e d d c p r o g r a m m i n gp r o b l e m s ，i sp r e s e n t e d ，a n di t ss u p e r l i n e a rc o n v e r g e n c e i sd e m o n s t r a t e d k e y w o r d s ：n o n l i n e a rp r o g r a r a m i n g ，n o n s m o o t ho p t i m i z i n g ，m o r e a u - y o s i d ar e g u l a r i z a - t i o n ，“v d e c o m p o s i t i o nis p a c e - d e c o m p o s i t i o n ，p a r a l l e lc o m p u t a t i o n 第一章譬|富 引言包括非线性规划分解方法中的空间分解方法的简短综述，本文所 研完婚拢纯中两囊室翔分辨方法妁背景，以及主要帮 党结果。 本论文所涉及的主题词“窑间分解方法”避指优化箨法中的空间分解方法，缆者说奎 闻分解方法是基于奎间分癣理论的一种优化方法“蕊类空间分鳃方法”，一类是以减小 闯越规模为舀静而避行靛奎筒分憋并浚并事予格式来实瑶诗冀的傀话方法嚣类是黻 次微分所决定的空间分解，用光滑方法来实现优化计算的优化方法如， 把一个优， 匕同题 r a i n m ) 1 ) 分解为菪干个子问题 蕊妒f 坤蕊) ，z 乩一 其中，s r ”，s ，f = 1 ，一，p ，是分解s 以嚣得到的相应的子集，并且最后的最优辫是 由这些乎双题的藏倪簿生成罅务辫冀法思想警烈用于处理邪强太系统优化问题， 1 1 空间分解方法 空间分解方法源于微分方程中的“区域分解方法”，其原始思想可追溯到十九世纪 焉期蓥国数学家h 。a s c h w a r z ( 1 8 7 0 ) 掰提出的著名s c h w a r z 交营法s c h w a r z 本意是储 用交替法论证非规掰椭圆搿方程解的存在佳每难一穗，直蓟二十整鳃溢千年代才有天淝 s c h w m z 方法用于计算d a n t z i g 和w o f f e ( 1 9 6 0 ，1 9 6 1 ) 猩解决资源问题中，将求解微分方 栽审豹“送壤努鼹派4 懿蒜想葶l 久裂求察一类其毒特殊结蓰麴缓经艇魏麓题土，挺舞一 种求解线性规划的分解方法( d - w 分解方法) ，即约束矩阵具有带边界的对角块结构与爵 撂遁数是绒娃越霹分离阉题， p 备 a = 岛乏三1 i ：二) ， 太连理盛大学博士学位论文；优化中盛问分解方法的某蟪研究结粟 觅 i 8 j ，f 1 9 b r o s i l o w ，l a s d o n 和p e a r s o n ( 1 9 6 5 ) 掇出的分解算法皆要求目标函数和约束具 有可分离的形式。即完全分离，见 6 】c o h e n ( 1 9 7 8 ，1 9 8 0 ) 提出的可微优化问题的辅助问题 摄瑾，帮甓诧耀题 蚴了( n ) 4 - 函( u ) 静辫霹由爨纯阕题 rm i n u e t lg ( 札) 十五( 乱) 1 s t g ( u ) = j 7 ( ) k 来求得其中了是可徽函数，况是下毕连续黼数( 研究可微优化问题时，另= o ) ，g 是 凸的可微函数，e 0 是常数然后用分解的一般方法，即变量分解来处理不可分离的情 援，凳 l 繇| 1 8 l ， 随着并行机的出现，优化中分解方法的研究也随着计算技术的迅速发展不断地取得 薮螅遘晨，以适应并褥诗算按零鲍发骚及诗算上戆器拳，共捷零锯犬艇摸阕透鲍葵法憝 得到不断更新 由于将一个大规模最优他阅题分勰为一系剜规模较小的容易求鳃的予问题，是设计 最傀亿并行算法的基本方法之一，丽这燕子阕糕的求簿穗往是独立的，所以科角多处理器 极易组织成并行算法下面引用费浦擞教授和陈忠教授必于并行算法的部分综述【2 剐， 班瓣述努惩穷法瓣都努瑟憨蠢派理。 例如，最容易分解的是可分函数， 僻 f 0 ) = 蠡( ) ， ( 1 1 1 ) 其孛，$ 。f t ，i = 1m ，圣l 强一# ，。舻。峦f 鳇影式囊早2 f ( # ) 蔗安慰建簿，即 f 铲州吼v 。捌1lv 2 办( # 2 )l v 2 f 。) = l - iv 2 岛( ) 利用n e w t o n 法将很容易实现谈问题的并行计算实际上求( 1 , 1 1 ) 的极小德本身就归结为 分别求撂支( 劫极，、馕这m 个独立的小溉摸鲍偬化问题。这秘方法称之为完全分勰法。 d a y d e 将完全分解法的思想应用到约束问颞中去产生了一类对偶方法，称为d a y d e 对偶方法，它将( 1 1 1 ) 推广到约束规划问题 m 孤m ) = 銎t 拖)2 1 l s t 拇nl h i j ( 吒) 0 ，j = 1 ，m 乖j 蔺l a g r a n g e 乘手法，可以簧出( 1 1 2 ) 的对稻形式 “( “j f l13 ， 2 第一章引言 其中2 ( u ) _ r a i n 。工( z ，“) ，其相应的辅助函数为 nm 呼l ( 圳) = ( ，( q ) 一u j h l j ( x i ) ) i = 1 ，= 1 对固定的u ，l a g r a n g e 函数l 关于各个变量缸是可分的，利用变量分解思想可以将 ( 1 13 ) 分解为n 个相互独立的无约束优化问题 m 晒n 工，( “。) = ( 甄) 一u j h 甜( q ) ，b1 2 一，n ， “ j = l 从而可实现( 1 1 2 ) 的并行计算 利用分解方法的思想，还可以设计求解超定非线性方程蛆 f ( x ) = 0( 11 4 ) 的并行算法，d i n l z - e h r h a r d t 等在( 1 9 9 3 ) 础，中利用正交投影法提出了一种较好的并行算法，这里 f 只”_ r m ，m n ，f 在r “中是可微的，i 表示e u c l i d e 范数利用正交投影法求解问题口利 的解，其基本思想是，斗寿f ( x ) 的元素分威8 块，分别记为只( z ) ，这里e ：r “一凡舢，= 1 ，2 ，s ， 并且：l m 。= m ，定义z ( z ) 是第 块( i = 1 ，2 ，8 ) 的j a c o b i 阵对v x r ”，考虑线性流形 k 和) = ( u r “b = a r g m i n i i f c x ) + 只扛) 扛一x ) l l ， 其中 = 1 ，2 ，s 记$ 在k ( z ) 上的正交投影为 z ( ) = z j ，如) 只( 。) ， 这里万( z ) 是z ( $ ) 的广义逆给定初始值z o r “和常数a ，i = 1 ，2 ，8 ，使得：1 。= 1 ，则 并行投影算法为 z ( + 1 1 = 妒( $ ( ) 这里妒( z ) = z 一：。对( z ) 皿( z ) m o r a n d i 和s g a l l a r i ( 1 9 9 0 ) 在【5 3 中，同样利用变量分解思想，即一种特殊的空间分 解思想，对于d e n n i s 和s t e i h a n g 在( 1 9 8 6 ) 2 3 】中提出的求解问题 砌r a i n _ 一m ( 1 _ 1 5 ) 的串行算法，给出了一种求解问题( 1 1 5 ) 的并行格式，见【5 3 】，其中a 是m n 的行满秩 矩阵，但算法并行效率并不高陈忠等对该方法进行了修正，见1 1 2 】，使得p 台处理器的 负载基本平衡，而且只在算法的最后一步进行数据交换，提高了算法的并行效率，并且 讨论了算法的收敛性 多阶段最优化决策问题由于其决策变量的阶段性，也给按变量分裂提供了方便r u s z - c y n s k i ( 1 9 9 3 ) 提供了一种并行分解方法，该方法用有限步可找到问题的一个最优解或者发 现问题的不相容性，见【6 7 】秦裕瑗在( 1 9 9 0 ) 【6 5 】中提出的嘉量原理，把多阶段决策问题 3 夫连_ 瑷i 夫学博士学德论文：侥纯申空藏分辨方法的基些研竞结最 归结为摹姬阵的连摹乘积问题，利用连摹乘积的可结会挫，吖以实现多处理机的并行计 算，郑慧娆教授在( 1 9 8 9 ) 2 7 l 等文中，据既对一些闻磁建立了穗应的并行算法。并讨论了 如何提高并行效率。关于状态集为菇限情况下的嘉蟹原理，赞浦生教授等曾程f 2 6 1 中进 行了讨论+ 众所胤知，变尺度法是解奂光滑无约柬优化问鼷的一个很有效的方法，网此研究该 类算法的势李亍他处理是 曼熏要的出于在变尺度法中大量的工作是计箕函数馕与函数的 导数，因戴大多数该类算法的并行处理是基于函数德和梯度德的并行计算，如d a y e d 谯 【2 0 1 提出的求解无约束问题的并行变尺度法其基本思想是同时利用n 个线性无关的方 农，殴瑟窀 蠢与上一步迭健锑疫懿麓惫，寒修歪翼拣避数戆二羚近戳矩阵，爽嚣算法戆 并行化这种并行处理，实际上是把原有的串行方法中的具体计算，让不同的处理器来 遴行+ i i a n ( 1 9 8 9 ) 在此基础上辅用空间分解原瑗，把空间分为着干个关于对称磁定矩阵b 棚甄共轭的子空间， t = 五+ + 焉， 从而把子问题分解为互相独立的小问题，计箅毗为下面问题的解，。 ， 一一 r a i n 三埘。磊毛叫+ v ，0 y 邑w + ，( 。) 其中，嘎一互皱，z = z 1 + + z 。，五是空阕五的慕组成的艇终，z 的校正为喜= a z 。 m 是对称正定阵， 是非奇异阵，它们的选择由具体算法来决定这样d = d l 十+ ， 形成u c s 法，见【3 6 】如果_ 8 被选为目标瞒数，的h e s s e 阵v 2 ，扛) ，则并行1 铲问题的解 熊梅遣舞，在。赢戆牛顿方惫文审来对算法霄效黢绘鑫臻确戆说繇，也寒鲶瑶收敛速 度的证明 u s c 方法驳葵法鹭形式上来藿，虽然逐楚恕漂蠢熬串稳算法戆具体诗箕努绘不霹鹣 处理器来处理，但实际上即相当于利用空同分解，将予问题分为若干个小规模的二次规划 问题来隶解，这一慰想与九十年代巾后期出现的一批新颖的弗行算法的思想有着密切的 联系在遮一时期，一类更暹子簿爹并行税上进行落 ：诤算酶空阉努解算法被撩出来，弗 谯理论上取得了一定的进展，其中舆有代袭性和标忠性的工作可参阅m a n g a s a r i a n ( 1 9 9 5 ) 懿p g d 雾法，冕1 5 0 ，f e r r i s 毒羹m a n g a s a r i a n ( 1 9 9 4 提出静p v d 雾法，霓鎏霹，以发 h k u s h i m a ( 1 9 9 8 ) 的p v t 算法，见f 3 l 】，等簿为了叙述的方便起见，有时称这几种算法 为m f f 类算法 现在，对m f f 类算法几顼主要的工作徽一简单的综述，这是本论文所论述的研究工 作的基础与主体融骞之一，即一类嶷闻分解方法 m a n g a s a a a n ( 1 9 9 5 援& 一种静志秀p g d 翡并符挽亿算法，宅是一释交量分解方法， 即通过将变量分解为 兰( 茁l ，- 一，) r “， f 就蜘， 4 ( 1 1 弗) 弛 = m ， 第一章引吉 的形式，使得p 个并行处理器可以同时进行不同的算法，每个处理器可以独立完成某个 串行算法的一步或多步，得到子问题的最优解在每个子处理器中，利用目标函数分配 给它的一部分梯度来确定搜索方向其步长和方向分别为 一v f ，( z ( 。) 7 d 1 ( 1 i v f ，( z ( ) i i ) ，f = 1 ，- ，p ， m ( ) m ) + a 脚”z 胁( v j m ( 1 ) 7 舻) ，f _ 1 ，p 最后，在同步化步骤中，求得优于子问题最优解的解作为下一步迭代的迭代点，即 ，( 。+ 1 ) s ，m 。i 。n 。f ( 。 + a ，。；) 这一方法所得到的迭代点列的任意聚点都是稳定点如果目标函数是凸的，则任意聚点 是全局最优点，见【5 0 】注意，在算法中每个子处理器可以选择与其他处理器不同的方向 和步长对于凸规划，在同步化步骤中可选择从p 个处理器得到的p 个解的强凸组合， 作为下一次迭代的迭代点另外，收敛性的证明虽然是一般串行方法的直接扩展，然而 其结果却有较重要的理论和计算价值例如，由它可得到神经网络的并行反方向遗传算 法和并行多种类识别问题的收敛结果和计算结果，见【5 l 】 与p g d 算法类似，利用变量分解( 1 1 6 ) ，f e r r i s 和m a n g a s a r i a n ( 1 9 9 4 ) 提出了一种称 之为p v d 算法的并行算法，它也是一种变量分解方法。见【2 8 1 在这种并行格式中，向 量也被分配到每个处理器中。每个处理器除了主要校正这块向嚣外还以指定的方式( 指 定的方向和固定的维数) 校正其它的向量块。 ( “，a 扩) = a r g ，爨粤、妒( ) = ，( 轨，”+ 磷q a ；埘) ， 其中d ；一d i a g d i “，d j 竺，丑，d 翁，秽) 最后，在同步化步骤中，使得下次迭代的 迭代点满足 m 1 ) h m i 。n 。f ( y t ，z + 掣a m 得到的迭代点列的任意聚点都是稳定点注意p v d 方法与j a c o b i 块法，坐标下降法和 p g d 法的基本不同点是，p v d 方法的并行步提出了”f o r g e t m e - n o t ，1 项( 巩，z ；) + 叫带) ， 每个子处理器不仅校正属于自己的那块向量聃，而且还兼顾其它块的向量，并以固定的 方式校正它们，即) + 珥带在处理具有不可分闭凸抽象约束集的约束优化问题的 p v d 方法中，第二部分向量块的校正采用投影梯度方向，并说明每个子问题不需要求得 最优解，只需求近似解即可 2 0 0 0 年s a g a s t i z a b a l 和s o l o d o v 给出了一般非线性约束p v d 方法对于可分离的非 凸约束问题，即问题( 1 0 1 ) 中的约束集s 为 s = 。lc ( z ) s0 ，c ：r “，冗” c ( x ) = ( c 1 ( 1 ) ，c p ( 昂) ) ，。i ：r ”一r “，2 _ l 5 m = n ， n | | m ，闽 p 大连理工大学博士学位论文t 优化中空间分解方法的某些研究结果 并行步采用序列二次规划法获得搜索方向对于不可分离的凸约束问题，在同样的分解 之下，并行步采用近似投影梯度方向 d l = 扛p g 扛一v ，( z ) ) ) f ，f = l ，p 作为搜索方向，基于某种误差界的结果，利用这种近似方向可避免用大量时间来进行投 影运算，提高算法效率进一步，s o l o d o v 对p v d 法的并行步和同步化进行了改进，给 出了非精确搜索p v d 法和非单调p v d 法 l i u 和t s e n g ( 1 9 9 9 ) 所提出的空间分解方法，见【4 7 1 ，可以看作是p v d 算法和伴随分 解法的推广，它把p g d 算法和分解算法( 如j 8 c o b i 法等) 结合在了一起，并且说明任何 收敛算法只要满足一定的条件就可以用来求解它的子问题另外，如果继续分解成一维 空间，则一维搜索方法就可以直接应用到子问题的求解中去这样，这种空间分解算法 就可以由线搜索组成 f u k u s h i m a ( 1 9 9 8 ) 也提出了一种分解算法的并行格式，并行变量变换法，记为p v t 算 法，见f 3 1 】_ 在这个算法格式中，一个n 维问题被分解成若干个小维数子问题， f 。) = a r g m i nl p 砷( 轨) 皇，( a q 轨+ 茹( ) 每个子处理器可以独立地处理这些子问题在同步化步骤中。由本次迭代点、子问题产 生的最优解生成了新的空问，在这个空间里产生的最优解作为下一次迭代的迭代点 z ( k + 1 ) = 口( ) 。( k 其中z ( k ) a r g m i n f ( b ( k ) ；) ，b ( k ) 是n 加+ 1 ) 矩阵，它的列为$ ( ) 和a 计+ 。 f = 1 ，pp v t 方法可看作是p g d 法和p v d 法的推广，在这里算法没有强调把变量 分解并分配到各个子处理器中，而是通过线性变换把整个空间分成若干个子空间，从而 把原问题分解成几个低维问题同前面所述的方法不同，这里子空间之间可以相互重叠， 也就是子空间的维数和可以大于n j o h n s o n ( 2 0 0 1 ) 在他的博士论文中将p v d 格式应用到椭球算法中，对大规模的非线 性规划问题进行了数值计算，见【4 l 】 1 9 9 9 年f r o m m e r 和r e n a u t 利用加或乘的s c h w a r z 预处理提出了一种处理无约束问 题的空间分解算法，建立了相应的收敛理论，见【2 9 】 t a i ( 1 9 9 5 ) 给出的一种g a u s s - s e i d e l 空间分解法和j a c o b j 空间分解法也属于m f f 类算 法，见【7 5 1 l e m a r d c h a l 、o u s t r y 和s a g a s t i z a b a l ( 2 0 0 0 ) 对凸规划问题给出空间分解方法，见【4 3 】 这足本文所涉及的另一类空问分解方法，即“v 分解方法，它将在下节中提到 在我国，随着以银河系列巨型机为代表的向量和并行计算机的出现与应用，适于并 行计算的并行优化算法已在科学计算，工程设计，数据处理和人工智能等方面的应用中 发挥了重要作用，许多学者从事这方面的研究工作林梦雄教授曾对非线性问题的并行 6 第一章引言 算法作过较系统的介绍，见 4 6 1 ；费浦生教授也对1 9 9 0 年以前的数值优化的并行算法的研 究作了综述，见【2 5 】陈忠教授、费浦生教授在并行拟牛顿算法方面有许多优秀的结果 赵凤治教授对线性规划的并行特征作过详细的剖析，见【8 4 】朱道立教授对大系统优化问 题进行了研究，见【8 6 】，他把静态大系统优化问题的解法分为三类t 直接方法：即把原有的方法加以改进，用于求解大系统问题； 新方法：如在解决美国大型电话系统优化的动机下提出的线性规划的多项式算法； 分解方法：即把原来的大系统优化问题分解为独立的的子问题求解 科学技术和生产的不断发展，使人们越来越多地面临处理大系统优化问题，如各种 大型的社会经济系统、通讯、运输、分配、能源、企业管理系统的运行管理和控制，大型 工程技术，高科技与国防等某些问题都是大系统优化问题，都涉及到大规模优化计算 无疑地，分解方法的并行化( 算法) 的理论与计算上的研究，就成为解决大系统、大规模 问题中，在计算上的主要工具之一 分解方法与数值线性代数、微分方程有着密切的联系，它在生物、化学等领域也有 着广泛的应用，如蛋白质模型等分解方法的应用，其中包括并行化方法的应用已渗透 到科学技术的各个领域 1 2 本文的研究背景，选题及主要研究结果 1 2 1 背景与选题动机 中小规模的优化问题，已有许多有效算法，其研究工作正在不断地取得新的进展， 如何将适于中小规模的算法与研究成果应用于求解大规模问题，这是一个既有意义又比 较困难的问题许多解小规模的有效算法还不能很好地直接用到解大规模问题上来，然 而，对某些大规模优化问题特别是具有一定结构的问题，使得求解小规模的有效算法在 用于求解大规模的问题上是可行的在大型互联系统的研究中发现，系统的子问题之间 的交互作用的数目或强度相对于子系统之间的互联是弱的，可以进行某种程度的分解， 因而产生了分解优化理论一般说来，解大规模问题需要较大的存储量和运算量，并行 化处理技术是解决这一问题的方法之一，它依据分解来构造相应的算法 从当前并行算法研究及结构来看，并行算法的研究可分为两类其一是将已有的串 行算法并行化，另一类是完全从并行的思想来构造算法目前，以串行算法并行化的研 究居多，而完全依据( 同步或异步) 并行的思想与并行机的结构特点来构造算法，将是并 行算法的研究趋势 空间分解方法可以通过并行格式来实现并行计算，为了简便起见，论文中将通过并 行计算来实现求解一个优化问题的一类空间分解方法。称为适于并行的空间分解算法 论文中所论述的第一类空间分解方法，即适于并行的空间分解方法就属于上述第二 类算法，它更适于目前出现的并行机的结构，相应的算法理论及算法的实现等研究也是 重要的研究课题 7 太连鹱l 大学搏士学位论变= 拢纯中空越分解方法辞莲些研究缝栗 优化中鳃分船方法，特别是适于势行的分解方法，在上缴纪九十华代有了迅速的发 袋，讨论箨法酶全褥收敛後获成为这类闻簌的一个纂本理论磷究课题之一，磁如韩继渡 教授( 1 9 9 0 ) 所说的，“从统一的观点去分析和综合戢忧化方法的结构及其收敛性是一条 妊然嚣骚突途径”，踅 翻，获跌誊文慰瑟淫论缝二类空阉分辩方法绘密了一拿统一懿攮 架+ 从而将现有的些分解算法，如前面摄到的m f f 算法统一在这个框架之中，并给出 一些收敛性结果 目前，对分解算法，特剐是论文后面将论述的第一类空间分解方法的研究，主要集 中于光滑问题上对于目标函数或约束是不可分离的和不可微等情形涉及较少，而在大 蔑穰傀琵麓题串帮经常暹臻这种馕琵鲷魏，力掌上静大系统榜檠撬铃倪琵瓣惩、夫觏 横接触问题等所以对非光滑优化问题的空间分解方法需要进行研究当把念空间分解 成有限个子空阕糖，对于个 # 光澄蠡数，寒说，一个意，嚣使在爨有予空翘孛，都魑 ，的最优点，仍不能保证它在全空间也是，的最优患因茈，非光滑优化问磁的空间分 解方法的收敛性证明是一个难点，本论文着麓对这方面问题加以研究 既使对光滑情形，由于优亿下降算法强j 暖序静限箭，下降算法率身的并行算法毙怒 绒性代数计算领域并行算法的研究还是要困难得多，因此我们需要研究分解方法中的一 释j 荤瀑瓣并行纯箨法，塔挺嵩算法静毒效性+ 褒毒戆一些察耀努鼹方法，黪翻是逶予 并行的空间分解方法，其收敛性结果一般熟收敛到问题的稳定点，如何能使空间分解方 法对非凸规是 收敛剜二阶稳定点，也是所要研究的。 对于a # 光滑优化问题，人们一赢致力予寻采陕速优化方法，l e m a r 6 d m l 、o u s t r y 和 s a g a s t i z a b a l ( 2 0 0 0 ) 对凸规划阅题给燃了相应的空间分解理论及空间分解方法。觅【4 3 】， 如何将这一理论撩广窝更一觳静蠡数类牵，并梅造浚蘧算法楚本文新簧研究鹣 1 2 。2 主要研究缀榘 空问分解方法的统一结构及收效性 首先，测薅集德映射的概念，缭斑空闻势解方法的一种统一结构岛籀述，对不同具体 集值映射梅遣出适于擎行的空间分解方法、适予并行的黼步空闻分解方法及异步并 行空间分解方法并且应用集使分析理论，对各类方法缭出了一般的收敛理论，即利 焉 罨浚袈懿强念寒涯骥算法懿烹要数敲缝定理，搜褥滚联论在奄会巴翔抟寝敛终袋 的同时，提供丫几个新的结果，即串行、同步并行和异步并行的收敛性最后，在这 个统一框架里绘出具体盼空超转缨方法，翔并纷梯度分枣( p g d ) 法、并彳亍变量分帮 ( p v d ) 法、j a n o b i 块滚，并行嶷鬣变换( p v t ) 法 光滑问题酶第一类空阉分解方法的故簸褴 对于光滑无约束同题，首先给出儿种非单调的p v t 算法波其收敛性定理，然后利用 受鼗攀方海穰：次莲线搜索，飨出了嚣茫无约寨援翅熬冀验p v 譬算法，_ l 蒌硬了雾法 的收敛性定理最后，给出相应的数值试验，及数值试骏结果 8 第一章引言 非光滑问题的第一类空间分解方法的收敛性 利用m o r e a u y o s i d a 正则化，给出了一种无约束p v t m y r 算法，并证明了算法的收 敛性定理及收敛速度定理给出了具有块状结构约束的非光滑p g d 算法及其收敛 性对于具有不可分离约束集的非光滑问题，给出了非精确p v d 算法及相应的收敛 性定理最后，利用次梯度投影给出非光滑约束p v t 算法及其收敛性定理 非光滑的第二类空问分解理论及算法 由于具有次微分的非光滑函数，它的二阶展开一般地不能显式地给出，难于构造出 快速优化算法因此，本文论述了第二类空间分解方法的理论及算法利用凸函数的 “v 分解理论和最新研究成果，对一类d c 函数进行吖v 分解，给出非凸函数的分 解理论利用u - l a g r a n g e 函数，给出d c 函数的二阶展开式，从而给出无约束和约 束d c 规划的空间分解方法，即甜弘分解算法，并证明算法是超线性收敛的 9 第二章算法的基本结构 本章j 引进空间分解方法的算法映射等概念，给出了一种统一的空间 分解的抽象算法模型的结构，及在这个结构下的几类不同的空间分解 的抽象算法；利用闭映射的概念证明了算法的主要收敛性定理；给出 具体的空间分解方法与并行化 2 1 空间分解方法的算法映射 2 1 1 空间分解方法 空间分解 依一定规则，将一空间分解为若干个子空间，称为空间分解例如，可将空间舻做 如下分解t 1 比较常见的是把变量分块，将空间分解为 r “= sx s = i i 冬l s ， 其中， s = z f r m t i x = ( l ，一，x ，一，。p ) 品”) ，p - l ，n f = n 2 利用线性变换，将空间分解为 咒”一 墨i g = 饥r m e i a q y t + z ( ) r n ) ， r “。m z ，f = 1 ，- ，p ) ， 其中，。( k ) = ( 。 1 ，拶) 可视为固定 3 利用函数的性质，如函数的次微分，将空间分解为 r n = 甜v 其中，v = l i n a ，( z ) ，“= 伊，使得函数，在“空间上具有某种光滑性 在上面的空间分解中，前两个空间分解属于一类空间分解，子空间的维数可人为控制， 分解的主要目的是降低子问题的规模最后一个空间分解属于另一种空间分解，子空间 的维数取决于函数，的性质，分解的目的是分离出产生函数中的光滑成分的子空间 空间分解方法 在引言的开始已提到，空间分解方法是指：基于空间分解的优化方法不同的空间 分解对应着不同的空间分解方法本文所涉及的两类空间分解方法，就是基于如例所示 的两类空间分解 l ，2 ) 和 3 ) ，而提出的适于并行的第一类空间分解方法和适于串行的 第二类空间分解方法 大连理工大学博士学位论文：优化中空问分解方法的某些研究结果 2 1 2 算法映射 考虑优化问题 州m i n m ) f 2 1 1 ) 其中，是目标函数，而x 是可行集问题( 21 1 ) 的求解，可视为一个迭代过程，它按照 已给的一组指令和终止准则产生一个点序列 算法映射 给出一个向量。( “，应用算法指令，得