（运筹学与控制论专业论文）约束优化最小二乘问题的一种适用的方法.pdf

摘要 约束优化非线性最小二乘问题在科学实验、测绘、设计和工程技术等各个领 域有着广泛的应用。约束优化最小二乘问题为约束最优化问题的特殊情况，由于 其结构的特殊性，存在很多利用其结构特征的有效算法。而序列二次规划、信赖 域方法及拟牛顿算法也是求解此种问题的常用方法。 本文根据约束优化最小二乘问题的特有性质，结合序列二次规划方法以及信 赖域技术，提出了一种新的信赖域算法。为了避免计算二阶信息项的复杂度，在 此算法中我们着重修正了最小二乘问题的l a g r a a s e 函数简约的h e s s i a n 矩阵 z 7 v 2 三似力z = z 7 c ( x d z + z 7 s ( 屯，五) z ，通过修正其简约的二阶信息项部分 z 7 s 瓴，五) z 来达到修正z 7 v 2 l ( x ，句z 的目的；并且讨论了价值函数与罚参数雎 的选取；以及信赖域矢经大小的选取准则。 最后，我们证明了在一定的条件下该算法具有全局收敛性，并且用数值实验 验证了该算法的具有合理性和有效性。 关键词：非线性最小二乘约束优化信赖域拟牛顿 a b s t r a c t n o n l i n e a rl e a s ts q u a m sp r o b l e mi se x t e n s i v e l yu s e di ne x p e r i m e n t a t i o n , p r o j e c t s a n ds oo n a sa ns p e c i a lc a s eo fc o n s t r a i n e do g i m i z 址i o np r o b l e m s i th a sal o to f m e t h o d st os o l v ef o ri t ss p e c i a ls t r u c t u r e a n ds q p , r e g i o nu u s ta n dt h eq u a s i - n e w t o n e q u a t i o na r co f t e nu s e di ns o l v i n g t h i sp r o b l e m t h i sp a p e rd e s c r i b e san e wr l l s t - r c g l o na l g o r i t h mf o rn o n l i n e a rc o n s t r a i n e d o p t i m i z a t i o np r o b l e m s ，a c c o r d i n gt oi t se s p e c i a lp r o p e r t i e sa n dc o m b i n i n g s o pa n dt r u s t r e g i o nm e t h o d f o ra v o i d i n gc o m p l i c a t i o n so fc o m p u t i n gt w o t h er a n ki n f o r 衄t i 加i t e m s 。w ee m p h a s i z e dt ou p d a t et h er e d u c e d h e s s i a nm a t r i xz 7 v 2 工( 而a ) z = z 7 c ( x a z + z r s ( 吒，五) zo fl a g r a n g e f u n c t i o n o fl e a s ts q u a r e sp r o b l e m w er e a l i z ei tb yu p d a t i n gt h er a n ki n f o r m a t i o n i t e m sz 7 s ( 屯，五) z w ea l s od i s c u s sp r e d i c t e df u n c t i o na n dt h es e l e c t i o no ft h e p u i l i s hp a r a m e t e ra n dt h er a d i u so ft r u s t - r e g i o n a tt h ee n d , w ee s t a b l i s ha g l o b a lc o n v e r g e n c et h e o r e mf o rt h i sa l g o r i t h mi ns o m e c o n d i t i o na n dn u m e r i c a le x p e r i m e n t sa t ep r e s e n t e di l l u s t r a t i n gt h er a t i o n a l i t ya n d v a l i d i t yo f t h ea l g o d t h m k e yw o r d s ：n o n l i n e a rl e a s ts q u a r e s ，c o n s t r a i n e do p t i m i z a t i o n , t r u s tr e g i o n ， q u a s i - n e w t o nm c + u h o d 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：詹荪囊日期：训7 留 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：虚选丝导师签名 日期：7 魄苫 第1 章绪论 第1 章绪论 卒论文研冤如f 的优化问题： r a m i n ，( 功 j t q o ) = 0 ， j = z ，2 ，m 其中n m ，目标函数，( 功：r “斗五，约束c ，( 力：f 斗且是二次连续可微函数 ，( 力具有如下的特殊形式 ( 功= 昙r ( 曲7 r ( 功= 吾杰彳( 砷， 厶f 耐 其中，胄( 刁= 【( 功，吃o ) ，( 瑚， 因此。我们考虑的问题模型为 n 。f i n 埘= 三喜一2 似 ( 1 。) s t 勺( 曲= o ， ，= l ，2 ，m o 此时，( ，) 称为残量函数，( 1 1 ) 叫做等式约束最4 , - - 乘问题特别的，当每个 ( 力和巳( 功都为工的线性函数时，称( 1 1 ) 为线性约束最小二乘问题：当每个( 力 和c ，( 功都为z 的非线性函数时，称( 1 1 ) 为非线性约束最小二乘问题。 1 1 非线性最小二乘方法 非线性最小二乘问题在数据拟合，参数估计和函数逼近等方面有广泛应用， 例如，要拟合数据“，乃) ，f = 1 ，2 - - , p ，拟合函数为以力，它是石的非线性函数。 我们要求选择z 使得拟合函数( ，功在残量平方和意义上尽可能好地拟合数据， 其中残量为 ( 功= 妒“，力一片，f = 1 2 ，a 接下来，我们求这个参量的平方和的最小值，这样就得到最小二乘问题( 1 1 ) 的目标函数；如果再考虑一些约束条件，即为我们所研究的等式约束最小二乘问 北京工业大学理学硕士学位论文 题的一般形式。 对于非线性最b - - 乘问题 n d n f ( x ) = 三月( 力7 且( 力= 三喜彳( 力， 其中，五( 力= 【o ) 吩吐( 瑚，( 力，f = l ，2 ，p z 次连续可微，( 力的 一阶导数表示为 g = 可= ，7 置( 功 它的h e s s i a n 矩阵为 g ( 力= v 2 ，( 力= 以7 ，( 功+ 口( 峨 丑( 曲= o ) v 2 咯， 荆：( 掣) ，七1 2 仍f l , 2 刀 呒 其中，为置( 的j a e o b i a n 矩阵 作为一个最优化问题。非线性最小二乘问题可以用一般的最优化方法求解， 例如拟牛顿算法 1 9 1 等。然而由于问题结构的特殊性，存在许多利用其结构特征 的有效算法。这些方法的一个共同点，在于充分利用非线性最小二乘问题的特殊 结构，通过不同途径形成目标函数的h e s s i a n 矩阵的近似 简要地介绍如下： 取g i 的第七步近似矩阵皿满足以一- - 一7 以，也就是忽略二阶项口( 功来近似 q ，其中以= ，( 毛) 位移盈由方程组 巩五= z 墨 ( 1 2 ) 确定。这时迭代式 1 i 1 2 1 l + 5 l 即为著名的高斯牛顿法 当取以= 盈为搜索方向进行线性搜索求得五 o ，则取 + l = 毛+ 五吨 即为阻尼高斯牛顿法。 2 第j 章绪论 高斯- 牛顿法的一个重要特征为仅仅利用函数的一阶导数的信息( 砌直接 得到h e s s i a n 阵的近似，矩阵皿一- - 一i t 以至少是正定的，由方程组( 1 2 ) 确定的 方向在多数情况下是下降方向，对于解决零残量和小残量问题是非常有效的；然 而如果j ( x d 不满秩，该方法没有定义，并且对于大残量问题，高斯一牛顿法收敛 速度慢，甚至不收敛，因此效果不是很好。 对于阻尼高斯牛顿法由于采取了线性搜索，因此它保证目标函数每一步下 降，几乎对于所有非线性最小二乘问题，它都具有局部收敛性，尽管如此，对于 某些问题，它仍然可能收敛很慢。 对高斯- 牛顿法的另一修正由l e v 即b e r g 和m a r q u r d t 提出该方法克服了 ，伍) 奇异的情形。因为通常情况下，“) 奇异，它采用了信赖域策略，研究约束 最小二乘问题，模型为 m i n q , ( a ) = i 卜瓴) + ，( 以) 钆 j f i , ，1 1 ：。 由【6 】可知，该模型的解五可由方程组求得；即求解此模型的迭代方程 ( j j , + l t d 6 i = 一j ：r t 求得，其中以 0 。则新的迭代点为 t + l = 以+ 五 即为著名的l e v e n b e r g - b a r q u r d t 方法( 简称l - m 法) 这种方法的关键在于选择 合适的调节参数以，使得目标函数在迭代过程中有充分的下降。数值实验表明， l e v e n b e r g m a r q u r d t 方法比高斯一牛顿法更有效，并且对于零残量问题和高斯一 牛顿法具有相同的收敛性。 上述方法都是忽略目标函数的h e s s i a n 矩阵二阶项部分曰( 功的大小，在非零 残量问题中，为了能够对目标函数的h e s s i a n 矩阵更好的近似，需要考虑二阶项 部分b ( x ) 的大小。直接计算曰( 曲是不明智的，它的计算量太大拟牛顿法是求 解其有效的算法，即用拟牛顿法确定占( 功的近似m ( 功。即： g ( 曲= v 2 ( 力* ，( z ) 7 ，( 力+ m ( 砷 北京工业大学理学硕士学位论文 i | 自曼曼曼! 蔓曼曼皇曼曼量曼量曼量| 曼曼皇量曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼鼍曼曼量| 置| 曼量量曼| 量! 曼曼一 基于拟牛顿修正的思想，对于口( 曲的近似矩阵肘( 曲应满足拟牛顿方程 m + l s k = 以 因此用拟牛顿方法 2 1 求解非线性最小二乘问题就转化为如何构造上述拟牛顿 方程。国内外学者给出了许多种途径来构造拟牛顿方程，并且得到拟牛顿方法对 于求解大残量非线性最小二乘问题是非常有效的方法 4 0 ，并且具有超线性收敛 性 1 3 1 2 信赖域算法 无论是研究无约束最优化问题还是研究约束最优化问题，我们关键是要找出 它们的最优解。，那么寻求无约束最优化问题的最优解的方法称为无约束最优化 方法；相应得寻求约束最优化问题的最优解的方法称为约束最优化方法 现在我们考虑一般的无约束优化问题： n f m f ( x ) 起始于p o w e l l 研究了它的无约束最优化方法信赖域方法。它首先指定 一个步长界a i ，然后用带约束得二次模型来确定位移的方向与大小，许多学者 都认为，这种方法将提供非常有效，并且有十分精致的整体收敛性质 2 2 】【4 6 】的 最优化算法。因此，它也是优化问题一类重要的数值计算方法【1 0 】【1 l 】，在近三 十来年受到非线性优化研究界非常的重视。它已经和传统的线收索方法并列为非 线性规划两类主要的数值方法，它也是求解约束优化重要的方法。 在这里，我们简单的看一下信赖域方法，由于步长受到使t a y l o r 展式有效的 信赖域的限制，故该方法又称为限步长法。 信赖域方法是一种稳健的迭代方法【8 】，在每次迭代的过程中，它要求通过 求解下列子问题来计算试探步s k ： 卿如) = 尹1 即+ v f ( x k ) 7 j ，( 1 3 ) ，上 i i s l l s 。 4 第1 苹绪论 其中且r 是v 2 ，( 以) 的某种近似，且。 0 称为信赖域矢径。我们定义目标 函数的实际下降量为a r e d = ，( 毛) 一( x t + s d ，而预测下降量为 p r e d = q t ( o ) - q t 蚧s t 令= 等= 哿铨著，则根据由r j 的舯来修 正色以及是否接受试探步气，如果0 r k l , a 为常数；否则不接受气，x t “= x t ， 以及a k + = 届，0 l , f l 为常数。 则无约束信赖域方法第_ | 步迭代的基本框架为： ( 1 ) 给出毛和a 。，计算既，皿； ( 2 ) 解信赖域模型( 1 3 ) 求出s k ； ( 3 ) 求出的t 值； ( 4 ) 如果o r t 1 , a 为常数 ( 5 ) 若兰o ，则屯+ 1 = x t ，a “i = p a t ，o o 则x 为问题( 1 1 ) 的一个严格局部极小点。 序列二次规划是基于l a g r a n g e n e w t o n 方法提出的，我们有如下的收敛结果 定理2 1 设八力和c ( 曲二次连续可微，如果矩阵 陉一0 _ 1 【一彳( 以) 7j 一致有界，则由算法1 2 所产生的点列饥) 之任一聚点都是问题( 1 7 ) 的k - t 点 定理2 2 设，( 力和c ( 力二次连续可微，如果矩阵 陉弦a ( x d a ( x d0 _ l【一 7 j 一致有界，则( ( 以，五) 的任何聚点都是方程 尸似句= 8 v ( 功一彳五n 肛 的根。 下面的定理是关于矩阵正定性方面的 定理2 3设为一正定矩阵，丑为与a 同阶的任一对称矩阵，m r ，则 存在 如 0 ，使得当m m 。时，b + 脱4 也是正定矩阵。 证明：设对v m 0 ，丑+ m a 都不是正定矩阵。则a s 肜。j 0 使得 ，( b + 刎1 j = s t b s + m s 7 a s o 这与我们的假设矛盾。故命题成立 对于无约柬信赖域方法我们有如f 的已知引理及收敛定理 定义2 3 设万 0 ，r 0 是两常数，如果气r 4 满足 删砒脚：m i l l ，器 和不等式 2 o ，届 o ，反( o ，1 ) ，以及( 1 ，2 ，3 ，) 的一个子集，使得 a i + l 屏，v 七e j ； 厶t + js 履a i ，v 七叠j ； 厶i r m k ，v r ； m + l2 肘t ，v k ； 1 m k 佃， 则必有l ，m 0 ，以及对于充分大的七，约 束1 1 , 1 1 ：i 此外，收敛速度是二阶的 2 2 本章小结 这一章中我们给出本篇论文所要用到的一些定义、引理及定理，这也是我们 第2 章基本条件及假设 以下章节讨论内容的理论基础 北京工业大学理学硕士学位论文 第3 章序列二次规划信赖域组合方法 3 1 等式约束问题 本论文研究如下的优化问题： 卿川 ( 3 1 ) s t q = o ，= l 2 ，肌 其中h m ，目标函数，( 砷：f - - ) r ，约束c ，( 功：置。j 置是二次连续可微函数 。r ( 力具有如下的特殊形式 f c x ) = 丢r ( 置o ) ：昙杰：， 其中，r ( 功= 【( 力，呸( 砷，( 功】， 然而目前，对于约束最优化问题，最常用的求解方法分为两类：一类是利用 约束问题本身的性质，直接求解约束问题。另一类方法是将约束问题转化为一系 列无约束问题，通过求解一系列无约束最优化问题，来得到约束问题的最优解。 这类方法称为序列无约束极小化方法 通常，序列二次规划( s q p ) 方法是解决此类问题的典型方法，但是为了扩 大它的收敛域- 需要一个全局的策略( 见 1 】) ，因而我们更热衷 b y r d o m o j o k u m 的信赖域技巧【2 - 3 】，因此本文讨论的序列二次规划信赖域方法，它们是把序列二 次规划与信赖域方法很好的结合，也就是使约束最优化问题转化为无约束最优化 问题进行求解。 3 2 约束优化问题的序列二次规划信赖域方法 现在我们研究问题( 3 1 ) 的序列二次规划信赖域方法。首先问题( 3 1 ) 的 l a g r a n g e 函数定义为 上“= ，( 的一a 7 “n 1 4 第3 章序列二次规划信赖域组合方法 同样，设= v q i x ) ，v f 2 ( 功，v c ( 瑚为约束条件j a c o b i a n 矩阵，五为l a g r a n g e 乘子，g 为该l a g r a n g e 函数的h e s s i a n 矩阵，即 6 = v l l ( z ，a ) = v l c x ) - ( 五) v ( 屯) i l l 则在当前迭代点工处，选为信赖域矢经，我们根据前面的推导，问题( 3 1 ) 的 二次规划问题【1 5 】为 卿v ( x ) r s + 1 2 s t g s ( 3 2 ) j ， c ( 力+ 彳( 砷j = 0 ( 3 3 ) ：s a ( 3 4 ) 然而，由于这个z 模的信赖域约束使得这个二次规划问题求解相当困难，并且满 足这个子问题约束条件c ( 功+ 彳( 力s = 0 的步长屯可能位于a k 之外，也就是约束条 件不可行，即这个二次规划子问题无可行解 3 5 1 。对于这种情况，我们不能仅仅 简单的扩大信赖域。使直线c ( 功+ z ( 咖= o 与之相交，因为如果这样就失去了在 上述二次规划中使用信赖域约束得意义，并且它也会破坏算法的收敛性，因此， 为了解决这个问题，分两步处理。首先忽略目标函数，使满足线性约束( 3 3 ) 的解能很好的落在信赖域内，令 4 ( x ) s + 0 c ( 功= 0( 3 5 ) 即我们求解如下新的“模子问题” m 。，i l l 0 4 0 ) ，+ c ( 砒 ( 3 6 ) “：丛 ( 3 7 ) 其中，善( 0 ，1 ) 是某个参数，一个典型的取值是孝= o 8 。把这个子问题的解吒称 为“模步”。这个问题有许多解，我们取使( 3 2 ) 有充分下降量的 ，因此，令 ( 3 5 ) 式中的踟( 力= ( x ) v ，得到新的子问题 m i nv ( x ) r s + _ 2 ls 7 函 ( 3 8 ) j j a ( 力s = 彳( 曲v( 3 9 ) ： ( 3 1 0 ) 显然，这个子问题的约束条件一定n - j 行( 因为当j = v 时，约束条件( 3 7 ) ( 3 9 ) ( 3 1 0 ) 都满足) 此时，我们求这个步长 ，使子问题达到最优。但是由于等 式约束条件( 3 9 ) ，这个子问题的求解过程不同于前边所给出的信赖域方法，现 在我们进行如下的推导，使其转化为无约束最优化问题，再应用信赖域方法使 问题最终得以求解 2 4 】【2 5 】 我们进行如下处理： 设矩阵z 叫一) 是厶。的零空间的正交基，即丘z = o ，z 7 z = j 且定义步长 j = 现+ 锄， 其中y 是任意一所阶矩阵，并且使得 r ；z 】。非奇异，西是一个掰维的列向量， 岛是一个万一肼维的列i 甸f 3 9 。 此时，把步长s 代入( 3 8 ) ，得 v ( z ) 7 ，+ 去j 7 西 = 夥( 现+ 现) + 妻( 现+ z p d 7 g ( r p , + z p d = 可( 耽+ v ( 妒现+ 三( 聊) 7 g ( 现) + l ( z p z ) 7 g ( z p z ) + ( z p z ) 7 g ( 现) = p z r 【z r + g 现) 】+ 妻z z r g z p z + 可7 耽 + i 1 ( 现) 7 g ( 现) + i ( y p d r g ( 现) ( 3 1 1 ) 把步长j 代入( 3 9 ) ，得 4 ( 力v = a ( x ) s = a ( x x y p , + j 弛) = a ( x ) r p , + 一( 工) 现 4 ( 力v = 彳( 力j 钆+ a ( x ) z p z ( 3 1 2 ) 把步长j 代入( 3 1 0 ) ，得 二1 1 4 ：s 。 轨+ z p z l l ：f f i ( 1 ：p r ) 7 ( r p , ) + 2 0 p 0 7 ( 锄) + ( 现) 7 ( 现 = 慨酗戌7 2 7 现s ( 3 1 3 ) 在( 3 i i ) - ( 3 1 3 ) 中，令1 ，= 现，且忽= o ，z 7 z = ，忽略常数项，可得 l ( 3 1 1 ) = 办z r ( 可+ g v ) 】+ 去z g z p z ( 3 1 2 ) = a ( x ) v = a ( x ) v 由( 3 1 3 ) 可得0 见l i ：s 2 一： 因此，根据上述推导( 3 8 ) - ( 3 1 0 ) 可以转化为 z 尝z 【z 7 ( v f + 】+ 三z z 7 g z p z 豇：0 习而 定义 g = z 7 眄+ ，b = z 7 g z ，厶= 扛2 一， 则，我们得到如下的等价形式 粤h ( p z ) = 幽+ 三z 现 ( 3 1 4 ) “ 慨b 五 ( 3 1 5 ) 转化为一个一般无约束信赖域子问题，用折线法( d o g l e g ) 即我们前边所述的信 赖域方法即可对它进行求解，具体的实现过程请看文献【5 】，解得 j = 】h + z p z ， 设 吒“2 毛+ 马 五+ = 一4 4 ) 1 4 ( + q s ) ， 如果屯+ 。使价值函数有适当的下降量则扩大信赖域，否则缩小信赖域的大小，再 计算新的步长。这样我们就可求得问题( 3 1 ) 的最优解。 同样，以一般见特殊，我们得到了最小二乘问题求解的总体思路，但是由于 最小二乘问题有其特殊的性质，因此，在研究其具体的求解过程中，我们利用其 性质可以使求解过程得以简化，这也是我们这篇论文所研究又一个基本内容。 1 7 北京工业大学理学硕士学位论文 3 3 本章小结 在这一章里，我们给出了等式约束优化问题求解的总体思路：把约束优化问 题首先化为序列二次规划信赖域子问题，再把它化为无约束最优化问题应用信 赖域方法进行求解重点是主要处理了序列二次规划信赖域子问题约束条件的 不可行问题，还具体给出了把约束问题推导为无约束的具体过程。 在下一章，我们将讨论求解最小二乘问题过程中具体内容，诸如，二阶矩 阵的修正，罚参数的选取等。 第4 章非线性最小二乘问题的新算法 4 1 最小二乘问题的一些基本推导 我们所研究的等式约束最小二乘问题的模型为 卿州= 三委权力= i 1 置o 。嘣， ( 4 1 ) j j c ，( 力= o ，j = l ，2 ，m( 4 2 ) 设r ( 力- 【1 ( z ) ，屹o ) ，( 功r ，( 的_ 【( 力，v ：，( z ) ，v ，r ( x ) f ，则最小二乘问 题的l a g r a n g e 函数的梯度和h e s s i a n 矩阵分别为 v ，三“a ) = ，( 工) r r ( 功一4 ( 功7 a ， v ：l o , 句= ，( 力7 以 + ( 力v 2 ( 功一丑v 2 q = c ( 力+ s ( x ， 其中疋为向量旯的第i 个元素，并且令 c ( 力= ，( 7 ，( 功， s ( x ，力：杰v z ( 功一杰乃v z q ( 功， ( 4 3 ) 因此，除了做一些精确地判定以外，有准确的j a c o b i a n 矩阵，( 曲和五( 功意 味着作为梯度计算的副产物对在h e s s i a n 矩阵部分的一个近似是可利用。注意， 二阶项s ( x ，要求计算m + p 个h e s s i a n 矩阵，是相当复杂费时的。事实上，有 一些问题经常忽略h e s s i a n 矩阵的二阶项s “ 1 2 1 ，但是通常情况下二阶项 s ( x ，旬是不可以忽略的；为了克服计算其复杂性，费时等困难，这时，我们做如 下处理。 现在将等式约束最小二乘问题的l a g r a n g e 函数的h e s s i a n 矩阵左右分别乘以 矩阵z ，则有 z 7 v 三l o , z ) z = z 7 c ( x ) z + z 7 s ( x z ) z 1 9 北京工业大学理学硕士学位论文 为了便于推导，令 占( 砷= z 7 吧上o ，z ) z ，w ( x ) = z r s ( x , a ) z ，e ( x ) f f iz 7 ，( 曲7 j ( x ) z 即 占( 习= 形( 力+ e 4 2 简约的h e s sia n 矩阵z r v z s ( 工，z ) z 的修正 对于一般的等式约束优化问题，在文献【6 】中作者应用b f g s式对简约的 l a n g r a n g e - h e s s i a n 矩阵刃v 2 工( 吒，五) 互进行了如下的修正 设从点( 吒，五) 到点( ，五+ ) 的步长为吒见，q = v 2 三( 黾，五) 有 q + i q 见4 v l ( x + a k p k ，五+ i ) 一v l ( x , ，0 1 ) 其中见= 毛+ i 一黾= z i 见+ 五n ，左乘z 得 刃q + 。互儿* 名q + 。k 吼办+ 乏【v z 瓴+ a k p k ，五+ i ) 一v l ( x ，五+ ) 】 目乏【v 己( 五+ a k p , ，五+ i ) 一v 瓴，五+ i ) 】 令皿= 2 f v 三二( ，五) z i ，得到割线方程 且+ 1 = 儿 其中 s t 2 a k p z , 儿= 乏【观阮+ a k p k ，) 一观瓴，五+ ) 】 最后应用麟公式使简约的l a n g r a n g e - h e s s i a n 矩阵乏v 2 工瓴，五) 互得到了修 正。 现在，我们考虑一个普通函数矗( 而，进行如下的构造。 假设在第t 个迭代点对于函数 ( 曲有 v 2 _ i l ( 矗) = h i ( 毛) + 马( 耳) ， ( 4 4 ) 其中设且( 屯) 是对称矩阵，并且容易计算。令 b ( x d = 且( 黾) + 形( 屯) ， 第4 苹非线性最小二乘问题的新算法 近似于v 2 h ( x k ) 。设矿( 丘) 近似于吼瓴) ，且迭代方程为 x k + 1 2 屯+ j ， 现在考虑如何修i fb ( x k ) ，使得e c x , ) 能够很好的近似于v 2 厅( 耳) ，我们要求+ 。满 足割线方程 p = 少， 定义 + i = + c ，o ，y p , ) 修正了+ i ，使得巨“近似于v 2 h ( x k 。) 的，即 _ ) ，= 羁( 以+ 。p + ) ， ( 4 5 ) 舷。= h ( 耳+ 。) + + ， ( 4 6 ) + = + u ( j ，少，) ，( 4 7 ) 这是我们对厅( 力这个普通函数h e s s i a n 矩阵修正的构造过程。 接下来，我们考虑最小二乘的l a g r a n g e - h e s s i a n 矩阵，由( 4 3 ) 知，它的 l a g r a n g e - h e s s i a n 矩阵由两部分组成，其中c ( 功是对称矩阵，s ( x ，句是一个二阶 导数矩阵，因为s ( 工，：( 力v z ( 曲一杰 v z q ( 对，根据泰勒公式有 j - ii - 1 杰暑阮。) v 2 c , 瓴+ h ：艺 阮+ 。) q 魄。) 一v c ( ) 】+ 训：) 0 1，- i = 【4 ( 。) 一彳( ) r ( 。) + d q k 蛙) * m ( 吒+ 。) 一彳( 毛) 】7 五( 屯+ ) ， ( 4 8 ) 窆瓴+ 。) v 2 + 。) = n ( 。) i v 2 r , c x , 。) 一v z 瓴) 】+ d 0 ：) ，i lf | l = 【，( + ) - j ( x a 7 屁( t + ) + d q k 肥) * j ( x t + 1 ) - j ( x k ) 7 r ( 气“) ( 4 9 ) l ii f ，o s b o r n e ，m r 得到割线方程， s ( + ”五+ ) & * 【，( 毛+ 1 ) - j ( x d 7 且( 屯+ ) - 【彳瓴+ ) 一4 ( ) r 五+ i 用b f g s 修i es ( x , 旬，从而修l e t 2 1 v ：工( 毛句= ，( 矿，( + 艺v 2 r , ( x ) - 艺4 v 2 q 因此，我们借助文献【6 】和“le ，o s b o r n e ，m r 的思想以及我们应用上述的 构造方法，修正最小二乘问题简约的l a g r a n g e - h e s s i a n 矩阵简约的二阶导数项部 分z 7 s ( x ，句z 具体操作如下，令 h , ( x d = z 7 c ( x d z ，月r a x d = z 7 s 瓴，五) z ， 下面我们考虑z 7 s 瓴，五) z 项，由( 4 g ) - ( 4 9 ) 得 墨+ 。墨= 【瓴+ 。) v 2 瓴+ 。) 一4 瓴+ 。) v 2 q ( ) k = ( + ) 审2 ( 黾+ h 一五( 。罗2 q ( k 。) = j ( x k + 1 ) 7 五( 吒+ 1 ) 一d ( x d 7 r ( 黾“) 一彳( 矗“) 7 五i 州+ a ( x d r 五“， 其中黾= + 一 = z i 艺+ 五b ，代入上式，可得 最“气= s 0 。( 乙易+ 五弓) = 墨。互b + 墨+ 。五0 = j ( x k + ) r r ( 黾“) 一，( 毛) 7 五( 黾+ 1 ) 一彳瓴h ) 7 五+ i + 彳( ) 7 五+ l ， 即 墨+ 。互尼= 臣+ l 耳弓+ j ( x b + i ) 7 用矗+ i ) 一j ( x d 7 r ( + ) 一a ( 耳+ ) 7 0 。+ a ( x d 7 五。 把上式左乘矩阵刃，则有 刃墨+ 互己= 一彳s i + 。五b + 乏【，( 黾+ ) 7 胄( 黾。) 一j ( x d 7 五( j r i + i ) 一( 】i + i ) 7 五“+ 彳瓴) 7 a m 】， 因为直角分解0 比切线方向分解芝能快速收敛到0 ( 因为弓二次收敛到0 ，最超 线性收敛到o ) ，即 札 j 从而省略z ：忍+ 。五0 项，则 乏。艮。z i + 。易一乏。【- ，( “) 7 孟( 屯+ i ) - j ( x d 7 r ( j ) 一彳瓴+ ) 7 五。+ a ( x d 7 五+ 。】( 4 1 0 ) 得到割线方程 + i 以= v k ， ( 4 1 1 ) 其中 以= 昱， 咋= z 0 。【j ( 黾+ ) 7 五( 吒+ ) 一j ( x d 7 r ( + ) 一4 ( 】i “) 7 五+ 彳( 毛) 7 五卅】， 然而，利用拟牛顿公式计算呒+ i ，与无约束优化本质不一样的是，对于价值函数 进行线搜索并不能保证 t y i o ， 从而不直接利用b f g s 公式，p o w e l l 建议按如下修正+ 哗= 呒+ 麓一警t t ，动 其中 儿= b + ( 1 一b ) 以， 。1 1 疙屹0 2 r ；扎 b 2 i o 8 露以( 以一以) 菇z o 2 刀蕞z 。 由上述可得，我们修正了z l i s ( + ，五h 。) 乙。项，利用( 4 4 ) 羽7 ) 的构造方 法，得 且+ = q ( j 。) + 哗， 从而修正了最j 、 - 乘问题的简约的l a g r a n g e - h e s s i a n 矩阵。 4 3 价值函数及罚参数的选取 价值函数【3 3 】是用来决定得到的解矗能否使目标函数有充分的下降量，现 在我们选取如下的价值函数 船川= i 1 只r + 扣功n ( 4 1 3 ) 因此，步长为s 时，从迭代点到屯+ 。价值函数的实际下降量为 a ，啦= 妒( ，以) 一烈毛+ “，以) ( 4 1 4 ) = 三酬嘣一i 1 酏+ 知( 气由+ 扣埘一卜+ 斗 现在有如下的预测函数 伊伍力= 三r ( 曲五7 + ，( 五+ 三，g 4 爿c + 一( 力干，( 4 1 5 ) 令 肼( 与= 三r ( 曲胄( z ) r + ，( 曲r r ( 曲+ 三2 ，g ；， 那么它的预测下降量为 p r 吐= 媳) 一烈以力= 巩( o ) 一+ 所1 v l _ e d , = 一，( 力r r ( 工) 一三，g 鼻所1 i c 瓴) 1 1 2 一肛魄) + 彳瓴) 币) ( 4 1 6 ) 其中 场吨刮酬卜卜m ( 吒) 币 此时，我们选取罚参数以，要求以足够的小，使得p r e 以为正数，并且与v p r e d 。 成比例，即 p r 吐芦断1 v p r e d k ， ( 4 1 7 ) 其中0 p 1 ，因此可取 所。= ( o ) 一( o ) ) ( 1 一历v p r e d 。+ l 旷 4 4 试探步接受与否及信赖域大小的确定 信赖域的关键组成部分是如何求得信赖域的试探步以及怎样决定试探步是 否可被接受。试探步一般是一个子问题的解，所以求得信赖域试探步实质上归结 于子问题的构造。决定试探步是否可被接受通常是利用某一价值函数，看试探步 能否使价值函数( 对于无约束问题，价值函数就是目标函数) 有充分的下降量。 首先，我们利用实际下降量与预测下降量，定义比值 ：筹， ( 4 1 8 ) p r 砒7 、 7 比值是衡量二次模型- m ( s k ) 近似目标函数f ( x k + ) 的程度，如果该比值越接近 1 ，表明近似程度越好。并且r k 在决定是否接受试探步以及如何调节信赖域半径 方面起到关键作用。 于是，根据我们给出 毛“2 耋+ 喜i 。j 岛 c 4 j 9 ) 而厶。由下式选取 a k + 1 2 若r k r h 若啊 0 ， 胄。，f 0 ； 1 k = 0 ，1 ，2 ，- 如果0 乏j ( 曲7 r ( 功l i ：+ l l q l ：s 占，则停止。否则，转到步2 ； 2 计算五，q ，4 ，( 功7 置( 力，通过( 3 2 h 3 1 5 ) 计算出子问题的近似解s 及 近似的乘子五。 五+ = ( 4 4 ) 。1 4 ( ，( 砷7 r ( 曲+ g i