（运筹学与控制论专业论文）异方差模型下带有随机区组影响的d最优设计研究.pdf

摘要 本文主要讨论a b s 算法和b f g s 算法在最优试验设计当中的应用研究利 用a b s 算法确定最优试验设计中由一系列线性不等式组约束产生的最优工艺区 域，即一个超定线性不等式组所讨论的线性不等式组限定为列满秩的超定不等 式组并利用b f g s 算法求解异方差模型下的二阶d 最优回归设计点最后利 用凸分析和优化算法对异方差模型下带有随机区组影响的d 最优设计进行了初 步的研究 本文取得的主要结果可概括如下： l _ 在第二章中，我们研究用a b s 算法确定最优工艺区域a x b ，其中a r t m ”r ， m n 利用隐式l u 算法对原问题的等价形式 a z + s s = b ，8 o ，中的 线性方程组a x + s s = b 进行求解，得到变量z 和松弛变量s 的关于变量 q r “”的通解表达形式进而对s ( q ) 20 求解变量q 铲“由隐式l u 算法的特殊性质，s ( q ) 0 可以转化为一个带有等式约束的线性不等式组 本章利用卢新明，吴方提出的方法( l w 方法) 对其进行了求解，得到了最院 工艺区域相容的判断条件 2 在第三章中，我们提出了一种求解异方差模型下二阶d 一最优回归设计点的 b f g s 算法二阶d ，最优回归设计点的求解可以转化为一个目标函数为非凸 函数的无约束优化问题算法拟牛顿算法中的b f g s 算法为基础，对目标函 数的近似h e s s e 矩阵进行适当的修正，在保证拟牛顿条件成立的同时，保证每 一步通过h e s s e 矩阵得到的迭代方向为下降方向，并结合线性搜索一般模型 证明了算法的局部收敛性和全局收敛性在特定的假设条件下，结合a m i j o 线性搜索步长准则给出了算法的超线性收敛性证明并对回归设计点进行了 求解 3 在第四章中，我们研究异方差模型下带有随机区组影响的d 。最优设计首 先，构造了一般的具有随机区组影响的异方差模型，并给出了采用二阶多项 式模型拟合响应曲面时d 一最优回归设计点存在的必要条件采用b f g s 算 法对最优回归设计点进行了求解之后，引入了带有随机区组影响的d 一最 优设计利用凸分析中的右乘函数，对不同误差分布函数下的迹函数做同胚 变换，转换为了一个一般a 的迹函数公式通过证明，给出了存在新的d 一最 优设计点的条件及求艇新的d 最优设计点、区组权数的公式 关键词：最优试验设计，a b s 算法，非凸函数，拟牛顿法，b p g s 算法，局 部收敛性，超线性收敛性，d 最优设计 a b s t r a c t t h i sd i s s e r t a t i o ns t u d i e sm a i n l yt h ea p p l i c a t i o no ft h ea b sa l g o r i t h ma n dt h e b f g sa l g o r i t h mi n t ot h eo p t i m a le x p e r i m e n td e s i g n u s i n gt h ea b sa l g o r i t h mt o d e c i d et h eo p t i m a lt e c h n i c sr e g i o n ，w h i c hi sc o n s t r u c t e db ya no v e r d e t e r m i n e dl i n e a r i n e q u a l i t i e ss y s t e m jo ft h eo p t i m a le x p e r i m e n td e s i g nt h el i n e a ri n e q u a l i t i e ss y s t e m i sl i m i t e dt oc o l u m nf u l lr a n k u s i n gt h eb f g sa l g o r i t h mt os e a r c ht h ed u p t i m a l r e g r e s s i o np o i n t si nh e t e r o s e d a s t i cm o d e l s t h e ns t u d yt h ed o p t i m a ld e s i g nw i t h r a n d o mb l o c ke f f e c t si nh e t e r o s e d a s t i cm o d e l s t h em a i nr e s u l t so b t a i n e di nt h i sd i s s e r t a t i o nm a yb es u m m a r i z e da sf o l l o w s ： 1 c h a p t e r2p r e s e n t sa na b sa l g o r i t h mf o rs e a r c h i n gt h eo p t i m a lt e c h n i c sr e g i o n ： a z b ，w h e r ea r m “a n dm nt h ee q u i v a l e n c es y s t e mi s a z + s s = 6 ，s 0 s o l v i n gt h ee q u a t i o na s+ss=6b yt h ei m p l i c i tl ua l g o r i t h m ，o n e c a ng e tt h eg e n e r a ls o l u t i o n ( z ) s ) w i t ht h ep a r a m e t e rq 口“：t h e ns o l v et h e i n e q u a l i t i e ss y s t e ms ( q ) 20 w i t ht h ep r o p e r t i e so ft h ei m p l i c i tl ua l g o r i t h m ， t h es y s t e ms ( q ) 0c a nb ec h a n g e di n t os y s t e m m y = b ，y o ) u s i n gt h el w m e t h o dp r e s e n t e db yl ux i n m i n g w uf a n gt os o l v es y s t e m m y = b ，y 0 ) ， t h e no n ec 8 2 1g e tt h ec o m p a t i b l ec o n d i t i o no ft h eo p t i m a lt e c h n i c sr e g i o n 2 c h a p t e r3p r e s e n t sab f g sa l g o r i t h mf o rs e a r c h i n gt h ed o p t i m a lr e g r e s s i o np o i n t s mh e t e r o s e d a s t i cm o d e l st h ep r o b l e mc a nb et r a n s f o r m e dt oau n c o n s t r a i n e do p t i m i z a t i o np r o g r a m m ew h i c ho b j e c t i v ef u n c t i o ni sn o n c o n v e xt h en e wa l g o r i t h m m o d i f i e st h ea p p r o x i m a t eh e s s em a t r i xo ft h eb f g sa l g o r i t h mt og e tt h ed e s c e n t d i r e c t i o na s s o c i a t e dw i t ht h eg e n e r a ll i n e s e a i c hm o d e l w ec a no b t a i nt h el o c a l a n dg l o b mc o n v e r g e n c ep r o p e r t i e so ft h en e wa l g o r i t h m u n d e rs o m ep a r t i c u l a r a s s u m p t i o n s ，t h es u p e r l i n e a rc o n v e r g e n c ep r o p e r t yo ft h en e wa l g o r i t h mi sp r o v e d f i n a l l y ) t h en u m e r i c a lr e s u l t si sg i v e n 3 c h a p t e r4s t u d i e st h ed o p t i m a ld e s i g nw i t hr a n d o mb l o c ke f f e c t si nh e t e r o s e d a s t i c m o d e l s f i r s t l y , w ec o n s t r u c tag e n e r a lh e t e r o s e d a s t i cm o d e l w h e nu s i n gt h e s e c o n do r d e rp o l y n o m i a lr e g r e s s i o nm o d e l st os i m u l a t et h er e s p o n s es u r f a c e ) w e 百v et h en e c e s s a r yc o n d i t i o no ft h ee x i s t e n c eo ft h ed o p t i m a ld e s i g np o i n t s t h e n t h ed o p t i m a ld e s i g nw i t hr a n d o mb l o c ke f f e c t si sc o n s i d e r e d w et a k eh o m e o m o r p h i s mt r a n s f o r m a t i o nt ot h et r a c ef u n c t i o nb yu s i n gt h er i g h ts c a l a rm u l t i p l i c a t i o n f u n c t i o nf i n a l l y , a ne x i s t e n c ec o n d i t i o no fn e wd o p t i m a ld e s i g np o i n t si sg i v e n a n dag e n e r a lf o r m u l a t i o nf o rf i n d i n gt h en e wd o p t i m a p o i n t sa n dt h ep o w e r so f t h eb l o c k si sa l s og i v e n k e y w o r d s ： o p t i m a le x p e r i m e n td e s i g n ，a b sa l g o r i t h m ，n o n - c o n v e xf u t i c - t l o n ，q u a s i - n o w t o nm e t h o d ，b f g sa l g o r i t h m ，l o c 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 ，o p t i m a lr e g r e s s i o nd e s i g n 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版 权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等 复制手段保存和汇编学位论文。 保密回，在2 年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“4 ”) 作者签名 指导导师签名 到蛔 圣：堑盥 2 立碰年鱼月上日 1 绪论 这一章首先介绍最优试验设计产生的背景及其发展状况，并着重介绍 了最优i 艺区域和异方差模型的发展状况之后，介绍了a b s 算法产生的 背景及莫在求解线性规划和求解线性不等式组等方面的研究进展并介绍 7b f g s 算法的研究背景、发展现状以及优化算法在最优试验设计当中的 应用情况 1 i 最优试验设计理论产生的背景及其发展状况 试验设计是- - i q 研究如何正确地安排试验和分析数据，并以较少的试验获得 最佳试验结果的科学它是统计学一个最基本的分支，可以说统计学的最初发展 与试验设计的出现是分不开的 试验研究包括两个方面：一个是通过被动地观测来获得知识；另一个是通过 试验来获得知识，即人们主动地影响或操作研究材料并取得观测结果在科学试 验的实践中，人们往往自觉或不自觉地忽视试验的设计阶段，而只注重观测结果 的统计分析出现这种情况的原因有两个： 1 试验研究的传统； 2 研究者的行为模式 过去，由于计算手段落后，进行试验设计需要做大量的工作，比简单地做试 验、收集数据，然后再确定研究的目标以及从数据中试图获得可靠的结论这样的 过程要困难得多 由于在科学研究的实践中，试验往往受到经费的限制，怎样傲到少花钱多办 事并达到预期的试验目的就成了试验设计研究者所关心的问题在进行试验设计 日寸i 要求建立试验次数较少，而精度较高的回归方程，这就要求摆脱古典回归分 析，主动把试验的安排、数据的处理和回归方程的精度统一成一个整体加以考虑 和研究，这就是“最优试验设计”所要研究的问题 大连理工大学硬士学位论文：异方差模型下带有随机区组影响的d 一最优设计研究 长久以来最优试验设计中研究的都是同方差模型，关于同方差设计的绝大 部分重要文献能在p u k e l s h e i m ( 1 9 9 3 ) 1 】的书中找到关于处理对照有大量的文献 ( 见s h a h s i n h a ( 1 9 8 9 ) 1 2 1 综述专题) ，关于最优区组设计却只有很少的结论，而且 不适于实际操作1 9 5 8 年，m o t e 证明了平衡不完备区组设计b i b d 的e 一最优 性，k s h i r s a g a r 证明了b i b d 及约当设计的a _ ，d 最优性k h u f i ( 1 9 9 2 ) 3 研究了 具有随机区组影响的响应面模型的正交区组设计 c h e n g ( 1 9 9 5 ) 4 针对c h a s a l o w ( 1 9 9 2 ) 5 】中的试验给出同方差情况下具有随机区组影响的响应面模型的回归设 计a t l d n s 和c h e n g ( 1 9 9 9 ) 6 给出了同一问题的直观表达式及分析证明，w o n g ( 1 9 9 3 ) 1 7 一，g u o ( 2 0 0 3 ) 1 q 对于不戈分区组的异方差模型的最优设计给出了一些 结论众所周知，异方差模型更贴近实际，涵盖更广，描述问题也更为精确本 文考虑具有随机区组影响的异方差模型，把凸分析和优化理论应用于最优试验设 计中去得到了一系列结论在误差同方差性假设下，已有很多学者做了大量关于 构造和研究大样本d 一最优设计的工作，例如a t w o o d ( 1 9 6 9 ) ( 1 5 ，k i e f e r ( 1 9 8 5 ) 1 1 q 和 f e d o r o v ( 1 9 7 2 ) ” 若试验域n 相对较小而且试验条件几乎恒定，则同方差性假设 是有效的若试验域n 很大，则同方差性假设一般不满足这时就须从异方差模 型入手研究试验设计的特性， 当设计的方差是常数时，可以通过k w t 构造d ，g 一最优设计对于异方差 模型，d 一最优设计和g - 最优设计通常是不等价的这时，仍能通过使用k w t 来构造d 一最优设计，但较难于构造g 一最优设计 w o n g ( 1 9 9 4 ) 1 0 给出通过使用 某种广义化的k w t 寻找g - 最优设计的方法文中给出了d 一，g - 和a 一最优准则 的等价条件，并对几种最优设计的效率进行了比较 最优化理论与算法的研究经过半个世纪的发展，已经形成了一个完整而有机 的整体把最优化知识应用于最优试验设计的研究将为最优试验设计的研究提供 强有力的工具最优试验设计当中涉及很多复杂的不同类型的优化问题，将两门 学科进行交叉结合不仅可以解决最优试验设计中的许多复杂问题，也可以进一步 完善和发展最优化理论与应用本文把修正的b f g s 算法用于最优试验设计，求 解异方差模型中二阶多项式模型d 最优回归设计点，取得了不错的效果在第 四章将做具体的介绍 1 2 求解线性不等式组的a b s 算法研究 a b s 算法是一类求解线性与非线性方程组的投影算法，是由a b a i b y , b r o y d e n 和s p e d i c a t o ( 1 9 8 2 1 9 8 4 ) 1 8 g 】提出的在a b s 算法诞生之前，已经有很多学者 2 第1 童绪论 做了大量与a b s 算法密切相关的工作，如w e d d e r b u r n 系统地论述了矩阵校正 方法与计算问题e g e r v a r y 继承了w e d d e r b u r n 的工作，研究了校正阵的紧缩形 势并将萁应用于求解方程组 a d a c h i ( 1 9 7 1 ) 2 0 】最先采用矩阵校正方法给出了拟 牛顿方程的一般解h u a n g ( 1 9 7 5 2 1 对于求解二次规划问题提出了一种求解线 性方程组的直接法，a b a f f y ( 1 9 7 9 ) 2 2 i 对h u a n g 算法进行了推广，提出了更多的 参数选取方法，赵金熙( 1 9 8 1 ) 23 】提出了求解相容方程组的h u u n g 算法并傲了推 广所有这些理论的进展都孕育着a b s 算法的诞生上世纪六十年代末到七十 年代初，拟牛顿法的研究获得了迅速的发展，取得了大量重要的、实践性很强的 进展七十年代中后期，匈牙利数学家a b a f f y 教授通过设置一个参数推广了求解 二次规划中线性方程组的h u a n g 算法1 9 8 2 年，a b a f f y 教授与英国著名的优化 与计算数学专家b r o y d e n 教授以及意大利著名的优化与计算数学专家s p e d i c a t o 教授在共同合作研究中发展了一类具有三个参数、用于求解线性方程组有限步终 止的迭代投影算法后来正式命名为a b s 算法i r a ，【1 9 j a b s 算法最初用于求解线性方程组，是一类有限次迭代的直接算法经过 二十多年的发展，a b s 算法不仅可以用于构造求解线性、非线性方程组的具体 算法等有关的数值代数问题，而且还可以用于求解线性规划和具有线性约束的非 缉洼规划等问题上世纪末本世纪初，a b s 算法又有了新的发展，已经在求解 d i o p h a n t i n e 方程、算法的并行实现、求解线性不等式组以及带有不等式组约束的 线性方程等方面得到了很好的结果 1 9 8 9 年，a b a f f y 教授和s p e d i c a t o 教授合作写了一本关于a b s 算法的专著 a b s 投影算法一求解线性和非线性方程组的数学方法1 2 4 ，对于a b s 算法 诞生以来的各种算法系统地进行了总结，研究了大量的经典算法，如s l o b o d a 方 法，b r e n t 方法及p y l y 方法等同a b s 算法类之闯的关系并归纳了构造a b s 算 法五种不同形式的计算公式，介绍了一些典型的a b s 算法，如h u a n g 算法，隐 式l u 算法，尺度化的a b s 算法，q r 算法等b o d o n & s p e d i c a t o ( 1 9 9 1 ) “】给出 了基于矩阵分解形式的迭代格式及校正方法s p e d i c a t o z h u ( 1 9 9 4 ) 2 6 】提出了 基于校正n u l l ( a t ) 基的校正公式z h a n g ( 1 9 9 7 ) 2 1 推广了原始的a b s 算法，得 到了日1 为奇异的推广形式的a b s 算法s p e d i c a t o ，g a o & y u ( 1 9 9 0 ) 2 8 j 研究了 g m r e s 算法，系统地阐述了共轭方向法的a b s 形式，y a n g z h u ( 1 9 9 4 ) 2 9 】研 究了隐式c h o l e s k i 算法，s p e d i c a t o ，x i a z h a n g ( 1 9 9 7 ) 3 q 提出了隐式l x 算法 s p e d i c a t o ，c h e n b 0 d o n ( i 9 9 6 ) 3 1 给出了求解k k t 方程组的若干a b s 算法 非线性a b s 算法最初是由a b a f f y , g a l a n t a i s p e d i c a t 。( 1 9 8 4 1 9 8 7 ) 吲一州以 大连理工大学硕士学位论文：异方差模型下带有随机区组影响的d 一最优设计研究 逐个方程形式提出的，分块形式的算法见a b a 开y g a l a n t a i ( 1 9 8 7 ) 3 “之后的工作 集中在收敛性质的进一步研究与数值试验方面，如d e n g ，s p e d i c a t o & z h u ( 1 9 9 4 ) 3 6 】 将a b a i f y , s p e d i c a t o ( 1 9 8 9 ) 1 3 7 婚8 1 的有界条件去掉，证疆了收敛性结果 o a l a n t a i ( 1 9 9 3 ) 1 3 9 卜【4 l 】研究了广义隐式l u 算法求解非线性方程组的收敛性s p e d i ， c a t o h u a n g ( 1 9 9 5 ) 1 4 2 证明了最优稳定尺度化子类算法求解不定非线性方程组 的局部收敛性h u a n g ( 1 9 9 2 ) 4 目给出了块状非线性a b s 算法的收敛性分析 h u a n g ( 1 9 9 2 1 9 9 3 ) h 4 】- 【4 9 】研究了求解非线性方程组的离散型a b s 算法和求解非 线陛最小模问题的a b s 算法及其收敛性h u a n g ( 1 9 9 4 ) 5 0 卜【5 2 】研究了求解非线性 方程组的行校正问题g a l a n t a i ，j e n e y ，h u a n g & s p e d i c a t o 还进行了大规模的数值 试验，见g a l a n t a i ，j e n e y s p e d c a t o ( 1 9 9 3 ) i 5 3 m q 及h u a n g s p e d i c a t o ( 1 9 9 4 ) 1 5 5 】一【“ s p e d i c a t o 等人于1 9 9 0 年首次用a b s 算法研究构造求解带有线性约束的最 优化问题的可行方向法a b s 算法在最优化中的应用已取得众多进展如拟牛 顿法统一公式的研究，见s p e d i c a t o x i a ( 1 9 9 2 ) 5 目稀疏拟牛顿方程的研究，见 s p e d i c a t o z h a o ( 1 9 9 3 ) 5 9 1 可行方向法的研究，见x i a & l i u ( 1 9 9 3 ) 6 “，s p e d i c a t o x i a ( 1 9 9 2 ) 6 1 j ，【6 2 1 考虑如下的线性不等式组 a x b( 1 2 1 ) 其中，a 彬m 茎n 很多种方法已经被设计出来用于求解不等式组( 1 21 ) ， 同时许多学者也研究了如何用a b s 算法求解等式和不等式系统，例如，e s m a e i l i ， m a h d a v i - a m i r i ( 2 0 0 0 ) 6 3 1 e s m a e i l i ，m a h d a v i - a m i r i & s p e d i c a t o ( 2 0 0 1 ) 6 q 提出一种求 解线性不等式组的a b s 算法，记为e m s 算法，算法在a 行满秩的条件下求解 ( 1 2 1 ) ，并且假设r a n k ( a ) = m ，m n 可以证明在这些假设条件下，原问题可以 写成如下的形式 a x d 错 a x = v ，sd ) 用e m s 求解线性不等式组可以得到解的一般表达形式施光燕( 1 9 9 2 ) 6 5 1 提出了 一种全局收敛算法，这种算法通过采用h u a n g 算法产生一个特殊的迭代点列， 使得迭代点逐步满足变量z 非负的条件，从而满足如下的线性系统 翁6 zz ， 其中，a r m 一，b r ”，z r n ，m n 张立卫( 1 9 9 2 ) 6 6 m 1 提出了一种a b s 算 法形式的投影算法它等价于采用b l a n d 规则的单纯形法求解线性规划问题，以 4 第1 章绪论 寻找下列线性不等式组的一个可行解 a z b ( 123 ) 其中，a r m 一，6e 驴z 册，msn 张立卫同时研究了秩亏一的( 1 2 ，3 ) 不 等式组的相容性问题张立卫( 1 9 9 5 ) ”】提出了一种用a b s 算法中的h u a n g 算法 求解线性不等式组的最小欧式模方法张立卫( 1 9 9 5 ) 6 s 同时还提出了o o l d f a r b - i d n a n i 策略赵金熙( 1 9 8 9 1 9 9 1 ) 6 9 】， 7 0 】提出了一种用a b s 算法求解线性不等式 组的直接法李兴斯和他的学生们在用极大熵方法求解( 1 , 21 ) 方面的工作也取 得了很多的进展 1 3 求解无约束优化问题的拟牛顿法的研究 拟牛顿法是求解无约束优化问题的一类实用性很好的算法其中，b f g s 算 法是数值结果最好的算法之一在非精确线性搜索条件下，关于变尺度法的收敛 性证明，目前的结果都是在凸性假设下给出的d e n n i s ，m o ，e ( 1 9 7 7 ) 7 1 】给出了该 算法的局部收敛性结果b f g s 算法用于求解无约束凸规划的全局收敛性研究 也有很多好的成果，p o w e l l ( 1 9 7 6 ) 7 2 】给出了非精确线性搜索下，变尺度法全局收 敛的第一个结果，他证明了若目标函数( x ) 是光滑的凸函数，且，有下界，则算 法在w o l f e 步长准则下是收敛的在较强条件下，他证明了b f g s 算法的超线性 收敛速率w e r n e r ( 1 9 7 8 ) 7 3 】在一致凸假设下将d e n n i s 的结果推广到了其它几个 实用线性搜索策略p d t t e r 在步长的某种限制条件下将d e n n i s 的结果推广至限 制b r o y d e n 族b y r d ，n o c e d a l y u a n1 7 q 将d e n n i s 的结果推广至限制b r o y d e n 族中除d f p 以外的所有方法b y r d & n o c e d a l 7 5 】引入一种新的分析方法，利用 矩阵函数妒中心沦证了b f g s 算法在凸性下的收敛性。袁亚湘( t 9 9 4 ) 等【7 6 】利用 b y r d 和n o c e d a l ( 1 9 8 9 ) 7 5 j 引入的皿函数把b y r d n o c e d a l 的方法推广到b r o y d e n 族，重新证明了算法在凸性下的结果但是对于非凸函数的无约束优化问题，包 括b f g s 算法在内的变尺度法的局部收敛性一直未能解决，该问题成为人们关注 的难点之一本文通过构造非凸函数的近似h e s s e 矩阵，给出了求解非凸函数无 约束优化问题局部极小点的b f g s 算法在假定局部极小点已知的条件下，证明 了该算法在线性搜索一般模型下具有局部收敛性 1 4 本文主要工作 本文研究求解最优工艺区域和异方差模型下二阶d 一最优回归设计点的方法 5 大连理工大学硕士学位论文：异方差模型下带有随机区组影响的d 一最优设计研究 以及这些方法在最优试验设计中的应用主要工作如下 1 在第二章中讨论了用a b s 算法求解最优工艺区域a xsb ，其中a 舻一， m n 利用隐式l u 算法的特殊性质，实现了把原问题转化为一个线性不等 式组问题，并利用卢新明，吴方提出的方法( l w 方法) 对其进行了求解，得 到了原问题a x b 的相容性条件 2 ，在第三章中提出了一类求解异方差模型下二阶d 最优回归设计点的b f g s 算法结合线性搜索一般模型证明了算法的局部收敛性和全局收敛性在一 定的假设条件下，结合a m o 线f 陛搜索步长准则给出了算法的超线性收敛性 证明 3 在第四章讨论了异方差模型下带有随机区组影响的d 最优设计构造了一 般的异方差模型，并给出了二阶多项式模型拟合响应曲面时d 最优回归设 计点存在的必要条件，并用b f g s 算法对其进行求解利用凸分析中的右乘 函数概念，将不同误差函数分布下的迹函数做同胚变换，转换为了一个一般 的迹函数公式，通过证明，给出了存在新的d 最优设计点的条件及求解新 的d 一最优设计点，区组权数的公式 6 2 一种求解最优工艺区域的a b s 算法 本章研究了最优i 艺区域a x s6 ，a r “r ，z 舻，b r ”：m n 的求解方法 利用a b s 算法中的隐式l u 算法及其性质对问题进行求解把原问题转化为一个 带有等式约束的线性不等式组，并利用l w 算法对其进行求解，进而实现求解超定 线性不等式组 2 1 问题的提出 考虑如下的线性不等式组 a z sb ，( 2 1 1 ) 其中，a = ( a l ，o m ) r r m r ，。r ”，b r m ，m n ，同时m ，n r + 考 虑a 满秩，即r a n k ( a ) = m 时的情形，不失一般性假设a 强非奇异 e s m a ? i l i m a h d a v i a m i r i ( 2 0 0 0 ) 4 “，e s m a e i l i ，m a h d a v i - a m i r i & s p e d i c a t o ( 2 0 0 1 ) 4 1 提出了一种 求解线性不等式组的a b s 算法，记为e m s 算法算法的思想是把( 1 2 1 ) 转化为 a x d a z = ，gsd ) 其中a r “一，m n ，r a n k ( a ) = m 用e m s 算法求 解线性不等式组( 1 2 1 ) 得到通解 z h t w , , 。( a t h t w m ) 一r y + h 三+ 1 日f t z l + 日i + 1 qly d ，g r 4 ) ： 其中，向量y r ”，皿为一个任意给定的非奇异矩阵，。l 为一个任意给定的初 始息这一节将利用a b s 算法构造一种求解不等式组( 2l _ i ) 的新方法首先， 给出基本的a b s 算法及其性质 2 2 基本的a b s 算法及其性质 2 2 1 基本a b s 算法 考虑线性方程组 a z = 6 7 ( 2 2 1 ) 大连理工大学硕士学位论文：异方差模型下带有随机区组影响的d 一最优设计研究 其中，a = ( a ，。) 7 r m 一，b 胛，z 舻a b s 算法是一类求解线性方程 组的直接法，它产生一个近似解序列 吼) 譬1 ，这个序列具有这样的性质，即第i 次迭代得到的z 州是前i 个方程的解从几何直观来解释，所得到的孔就是前 i 一1 个超平面的交集，即前i 一1 个线性流形的交集 n ，1 = 。1 巧z = b ，j = 1 ，2 ，一，i 1 ) 盈为集合n 中的一点，沿位于线性子空间蛆一1 = l 巧= o ，j = 1 ，2 ，一，t 一1 ) 且不与线性子空间 zi 。i z = o ) 平行的一个向量p l 0 进行搜索，得到下一个 位于吼中的迭代点z 计，这样在第m 次迭代结束时，得到。+ 1 ：即为线性方程 组a x = b 的解 如何构造p i 是a b s 算法的核心，三位科学家均采用下面的公式 p 。= h d , 其中，r a n g e ( h i ) n u l i ( a r l ) ，m = ( a l ，a 2 ，a 女) ，a b s 算法中的甄的校正类 似于拟牛顿法中的迭代矩阵的校正结构，但这里是降秩的下面是非尺度化基本 a b s 算法的迭代步骤 算法2 i ( 非尺度化a b $ 算法) ( a 1 ) 初始化，任意给定向量。l 形，任意的非奇异矩阵，即s p e d i c a t o 参数h i 印一置i = 1 ，i f i a g = 0 ( b i ) 计算乱= 凰吼和气= t t e 。= d i z 一b r e i ( c i ) 检查线性方程组的相容性如果8 i 0 ，那么转至( d i ) ；如果黾= 0 并且n = 0 ，那么置z + 1 = 乱和凰+ 1 = 皿并转至( f 1 ) ，第i 个方程 是前面i 1 个方程的线性组合；否则，停止，线性方程组无解 ( d 1 ) 通过鼽= 胛劫计算搜索方向p ；r “其中，b r o y d e n 参数盈在 保证孝甄乱0 的条件下任意给定 ( e 1 ) 通过x i + 1 = 观一。，鼽校正近似解x ；其中，步长锄由以下公式确 定啦= t i a t p i 如果i = m ，则停止 。+ l 就是线性方程组的解 r 第2 章 一种求解最优工艺区域的a b s 算法 ( f 1 ) 校正a b a 伍a n 矩阵凰计算 凰+ l = 凰一凰o 。”，凰w ，鼠( 2 2 2 ) 其中，a b a f f y 参数姚且“在保证，凰乱= l 和玎凰啦o 的条 件下任意给定 ( g 1 ) 指标集i 加1 转向( b 1 ) 2 2 2 a b s 算法的基本性质 a b s 算法总是适定的，即算法的执行与系数矩阵a 的秩无关，见a b a f f y s p e d i c a t o ( 1 9 8 9 ) f 2 0 的推论3 3 下面列出基本a b s 算法的若干重要性质，其它的 性质见a b a f f y s p e d i c a t of 1 9 8 9 ) 2 “ ( p 1 ) 风a i = 0 当且仅当吼是a l ，a 2 ，。一1 的线性组合 ( p 2 ) 若4 是行满秩的，则r a n k ( 凰) = n i + 1 ( p 3 ) 若a 是行满秩的，则 n u l l ( h + 1 ) = r a n g e ( a ) ，n u l l ( a t ) = r a n g e ( h t l ) ( p 4 ) 若a 是行满秩的，则”1 ，w ”一，。是线性无关的，且 n u l l ( h 5 1 ) = s p a n w l ，w 2 ， 。 ( p 5 ) 若a 是行满秩的，则 n u l l ( 鼹1 ) ( 件1 n u l l ( h 5 1 ) ( h 1 a r nj2 m z ， 叫mj = 7 7 t z ( p 6 ) 凰日f l g j = 日m 酞( i ，j ) ( p 7 ) 若a 是行满秩的，则p b p 2 ，p ：均非零且线性无关 ( p 8 ) 若a 是行满秩的，定义最= ( p l ，p 2 ，a ) ，则 厶= 盯只 是下三角非奇异矩阵 9 大连理工大学硕士学位论文：异方差模型下带有随机区组影响的d 一最优设计研究 ( p 9 ) x i + l 是碍z = b i 的特解，其中b = ( b l ，b 2 ，巩) r ( p 1 0 ) 碍$ = b 。的通解可以表示为x i + l + 酸1 s ，其中s 为舻中的任意 向量 证明：以( p 6 ) 为例进行证明因为j i 与i 一1 情况的证明过程是类似 的，所以只给出i2j 条件下的证明采用归纳法，当 = 1 时，( p 6 ) 显然成立 现在假设( p 6 ) 对于不超过i 的下标均成立，即 对j = t + 1 ，有 h t 札h h3 = h 1 h h l h i l h l = t h 。一h 再越h a h i l t h 。一e ；t 谴h a = 甄一2 噩o i 甄+ 凰n 。( ，皿吼) 仉7 甄 = 甄+ 1 对j i + 1 也有 h t + 1 h i l h i = h * 1 所以，定理结论成立 a b s 算法最重要的性质是a x = b 的通解有如下形式 z 2 x m + l + h t + l q 、 口 ( 2 23 ) 其中q 毋任意给定为了求解超定不等式组( 2 1 1 ) ，我们构造一个等价的不等 式组，通过对等价系统的求解对原问题进行求解下面介绍一下将要用到的a b s 算法中的隐式l u 算法的一些性质 2 3 隐式l u 算法及其性质 定义2 3 1 ：h l = ，砘= 岛， 。= e i e ，凰。的a b s 算法称为隐式l u 算法 隐式l u 算法具有以下性质： ( 1 ) 当且仅当系数矩阵a 强非奇异时，算法是可执行的 ( 2 ) 搜索方向p 。的前i 个分量不等于零并且第i 个分量等于1 因此矩阵 只= 扫h，p 。) 是一个单位上三角矩阵 】0 第2 章一种求解最优工艺区域的a b s 算法 ( 3 ) 记e j t = ( e 1 ，e 2 ，e z ) ，e t = ( e i + l ，岛+ 2 ，一，e n ) ，由( 2 22 ) 可以得到 从而有 于是有 甄+ 1 = j a ( 霹a ；) - 1 e 0 。 磷h h l = 0 ， 既+ l 晶一严晶。 霹j 。凰+ 1 e i = 一硪：a i ( 砰a 。) 。 = ( 未 ( 2 3 1 ) 其中尬口一4 有如下形式 甄= 一e 0 。a ( 砑a 。) 。( 2 32 ) 2 4 隐式l x 算法及其性质 定义2 4 1 ：h i = ，忍= e 女 。= e ，e 五觑。t ，其中k i 是一自然数，l5 兢s 礼 满足 e h e 乏凰口。o 这时的a b s 算法称为隐式l x 算法 ( 24 1 ) 隐式l x 算法由s p e d i c a t o ，x i a z h a n g ( 1 9 9 7 ) ”】提出，它是隐式l u 算法的 推广算法的执行不需要系数矩阵a 强非奇异的假设假设a 是行满秩的，则 至少存在一个指标满足( 241 ) ，基于计算上的稳定性考虑，可选取满足 = a r gm l e 于凰吼 j = 1 ，2 ，m )( 2 4 2 ) 记且= ( 1 ，2 ，乜) ，肌= ( 1 ，2 ，n ) b 。，算法有如下的性质 、； 。k 大连理工大学硕士学位论文：异方差模型下带有随机区组影响的d - 最优设计研究 ( 1 ) 礤l e k = 0 ，b 鼠； ( 2 ) 必在i 一1 中选取 ( 3 ) 鼽= 碰8 缸，且 甄+ l i 凰一髦篮( 2 4 3 ) 硝o ( 4 ) p 。有n 一 个零分量，它的第个分量为1 ，即 p t e k 。= 1 ( 2 4 4 ) ( 5 ) 若2 1 = 0 ，则x i + 1 是前i 个方程基本形式的解； ( 6 ) h , + l e k = ，k 旭； ( 7 ) 记q 。= ( e 且，) ，则 q t th i 埘。= ( 譬笔) 其中，r = 碥凰+ 1 砜； ( 8 ) 设酝如( 7 ) 中所定义，则 如= ( 冠0 ) 其中，兄r i 是单位上三角矩阵若m = n ，可以得到a 分解形式 a = l n r ：1 q ： 其中，l 。= a r 是下三角壬巨阵； ( 2 4 5 ) ( 2 46j 的如下 ( 2 4 7 ) ( 9 ) 记e s = ( e k l ，。乜，e k 。) ，b m ，e n = ( e n l ，e n 2 ，一。e n ) ，y j t r l ，a b = a e b ，a = a e n ，