（运筹学与控制论专业论文）一类二次规划反问题解法的数值比较.pdf

大连理工大学硕士学位论文 摘要 在一般的优化模型中，通常都假定与目标函数决策变量相关的参数值或约束集合的 参数值是已知的，我们求解一个优化问题就是在己知这些参数值的条件下，找到问题的 最优解然而在实际应用中有很多例子，我们只能知道参数的估计值以及从试验，观察， 经验中获得的最优解，需要计算出参数的精确值本文所要讨论的二次规划反问题就是在 己知问题参数估计值的前提下，尽可能小的调整给定二次规划问题的参数值，使已知的 可行解成为最优解尽管对于反问题很多学者进行了深入的研究，做了很多工作，取得了 令人瞩目的成就，但大多是组合优化发面的研究，在连续优化反问题方面进展比较小， 本文对【1 中提出的一类二次规划反问题的数值求解进行探讨 在第一章介绍了这个问题的最小化模型，它是一个正半定锥约束模型 在第二章推导这个二次规划反问题的对偶问题，它是一个线性约束半光滑可微的凸 规划问题，变量的个数比原反问题的少的多，只需求这个对偶问题的最优解就可以得到原 问题的最优解我们采用了f l l e e 的增广拉格朗日方法求解对偶问题，集中比较子问题的 不同数值方法的求解对计算效果的影响我们采用拟牛顿法和牛顿法两个方法对子问题 求解，比较它们的数值试验的结果，发现采用拟牛顿法求解子问题的方法比采用牛顿法 求解子问题的方法的计算效果好得多 在第三章中，我们用障碍函数法重新解这个二次规划反问题的对偶问题。首先给出 了关于问题的凸性的证明，说明采用障碍函数法的合理性，在障碍函数的子问题求解中， 我们同样采用拟牛顿法的b f g s 算法配合a r m i j o 线搜索同样对于这个算法也给出了数 值试验检验该算法的有效性，数值结果表明障碍函数法在求解此问题时没有增广拉格朗 日方法有效 关键词：反问题；二次规划；拟牛顿法；障碍函数法 一类二次规划反问题解法的一些改进 s o m ei m p r o v e m e n t so fat y p eo fi n v e r s eq u a d r a t i c p r o g r a m m i n gp r o b l e m s a b s tr a c t 1 1 1a no p t i m i z a t i o nm o d e lt h e r ea r ep a r a m e t e r sa s s o c i a t e dw i t hd e c i s i o nv a r i a b l e si nt h e o w e e t i v ef u n c t i o no ri nt h ec o n s t r a i n ts e t w h e ns o l v i n gt h eo p t i m i z a t i o np r o b l e m ，w eu s u a l l y a s s u l t i et h a tt h e s ep a r a m e t e rv a l u e sa r ek n o w na n dw en e e dt of i n da no p t i m a ls o l u t i o nt oi t h o w e v e r ，t h e r ea r em a n yi n s t a n c e si nt h ep r a c t i c e ，i nw h i c hw eo n l yk n o ws o m ee s t i m a t e sf o r p a r a m e t e rv a l u e s ，b u tw em a y h a v ec e r t a i no p t i m a ls o l u t i o n sf r o me x p e r i e n c e ，o b s e r v a t i o n so r e x p e r i m e n t s a ni n v e r s eo p t i m i z a t i o np r o b l e mi st of i n dv a l u e so f p a r a m e t e r sw h i c hm a k et h e k n o w ns o l u t i o n so p t i m a la n dw h i c hd i f f e rf r o mt h eg i v e ne s t i m a t e sa sl i t t l ea sp o s s i b l e t h e r e a r em a n yi m p o r t a n tc o n t r i b u t i o n st oi n v e r s eo p t i m i z a t i o na n dal a r g en u m b e ro fi n v e r s e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sh a v eb e e ns t u d i e d ，b u tf o rc o n t i n u o u so p t i m i z a t i o n ，w e d on o ts e em u c hs t u d yo nt h e i ri n v e r s ep r o b l e m i nt h i sp a p e r o u rc o n c e i t li st h en u m e r i c a l c o m p a r i s o no fd i f f e r e n t m e t h o d sf o rs o l v i n gat y p eo fi n v e r s eq u a d r a t i c p r o g r a m m i n g p r o b l e m si n t r o d u c e di n 【1 c h a p t e r 1i n t r o d u c e st h ei n v e r s eq u a d r a t i c p r o g r a m m i n gp r o b l e m ，w h i c h i sa m i n i m i z a t i o np r o b l e mw i t l la p o s i t i v es e m i d e f i n i t ec o n ec o n s t r a i n t c h a p t e r2d e r i v e st h ed u a lo ft h ei n v e r s eq u a d r a t i cp r o g r a m m i n gp r o b l e m ，w h i c hi sa l i n e a r l yc o n s t r a i n e ds e m i s m o o t h l yd i f f e r e n t i a b l ec o n v e xp r o g r a m m i n gp r o b l e mw i t hf e w e r v a r i a b l e st h a nt h eo r i g i n a lo n e i m p o r t a n t l y ，w ea d o p tt h ea u g m e n t e dl a g r a n g i a nm e t h o d ， g i v e ni n 【1 ，f o rt h ed u a lp r o b l e m 诫也s u b p r o b l e m sb e i n gs o l v e db yt h eq u a s i n e w t o n m e t h o da n dt h en e w t o nm e t h o d ，r e s p e c t i v e l y w ef o c u so nt h ec o m p a r i s o no fn u m e r i c a l r e s u l t si r n p l e m e m e db yt h e s et w oa p p r o a c h e s n l en u m e r i c a lr e s u l t ss h o wt h a tt h em e t h o d u s i n gt h eq u a s i - n e w t o nm e t h o di sm u c hm o r ee f f e c t i v et h a nt h eo l l eu s i n gt h en e w t o n m e t h o d i nc h a p t e r3 ，w el 1 s et h eb a r r i e rf u n c t i o nm e t h o df o r s o l v i n gt h ei n v e r s eq u a d r a t i c p r o g r a m m i n gp r o b l e m sa n dt h es u b p r o b l e m sa r es o l v e db yt h eq u a s i - n e w t o nm e t h o dw i t h a i m i j ol i n es e a r c h w er e p o r tt h en u m e r i c a le x p e r i m e m st h a ts h o wt h ee f f i c i e n c yo ft h e b a r r i e rf u n c t i o nm e t h o d ，b u tt h eb a r r i e rf u n c t i o nm e t h o di sl e s se f f e c t i v et h a nt h ea u g m e n t e d l a g r a n g i a nm e t h o df o rs o l v i n gt h i sp r o b l e m k e yw o r d s ：i n v e r s eo p t i m i z a t i o n ；q u a d r a t i cp r o g r a m m i n g ；q u a s i - n e w t o nm e t h o d ；b a r r i e r f u n c t i o nm e t h o d 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连受2 z - 大学或者其他单位的学位或证书所使用过的材料与我一同工作的同志对 本研究所做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：姚丝日期：! 丑! ! 堕 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文 作者签名：盗煎丝 导师签名二墟圭坠 型丑年月丝日 大连理工大学硕士学位论文 1 绪论 1 1引言 1 1 。1 本文的研究背景 对工程逆问题方法的关注，最早开始于地球物理学家a t a r a n t o l a 的工作，他在文 献 1 1 仲对其做了如下的描述：设s 代表一个物理系统( 例如整个宇宙，或一个星系， 或一个量子粒子等) ，假设能够定义一组完全描述s 的参数模型，这些参数可能并不都 是可直接测量的，我们可以在计算上定义一些可观测参数，希望他们的实际值依赖于模 型参数值球解正问题就是对给定的任意模型参数值预测可观测的参数值，而求解反问题 则是根据给定的可观测参数的观测值来推断模型参数值 对于最优化逆问题研究始于d b u r t o n 和p h l t o i n t1 9 9 2 年的论文在他们提出最短 路逆问题及其解法之后1 1 2 1 【1 3 1 ，人们将反问题的研究范围大大扩大，相继给出了狭义反 优化，部分受限反问题，边界约束反问题，以及给定目标函数取值范围的反问题等一系 列问题的描述和定义，对它们的求解算法与应用等展开研究并针对不同的应用背景的研 究，分别讨论了逆最短路问题，逆指派问题，逆最小费用流问题，逆最小生成树问题， 逆工程选址问题等 优化逆问题的研究正受到日渐广泛的关注，在诸如运输流量均衡，网络选址以及多 准则优化等众多领域取得了一些理论和应用成就【1 “1 15 1 ，因此优化逆问题无论在理论还是 实践中都有广阔的前景 1 1 2 优化问题逆问题国内外研究现状 优化逆问题其一般提法是：给定某优化问题的一个可行但非最优解p ，要求在某种 范数下，通过对目标函数中价值参数作尽可能少的调整，使之转化为新问题的最优解 显然，由于在这里改变价值系数参数并不影响问题的可行域，因此要求给定的解p 必须 是可行的该类反问题最初主要应用于：在某些情况下，尽管建立了线性规划模型，但目 标函数中的价值系数参数很难精确给定，如果根据经验或实验，能够得到所需要的最优 解，人们希望运用这些已知的信息来尽可能小的调整价值系数，以获得满意的结果 目前在优化问题反问题领域研究比较多的是线性规划反问题- j z h a n g 和z l i u 等最 早对此类问题进行了研究，并证明了在厶范数下，一般形式的线性规划反问题可以通 过转换成为一类线性规划问题来解决他们给出了线性规划反问题的一般形式，根据最小 费用流问题及指派问题的组合性质，分别给出了求解其相应反问题的一类强多项式时间 一类二次规划反问题解法的一些改进 算法，并提出了指派问题的限制反问题以及利用组合性质得到的求解方法对网络流规划 与组合优化中常见的0 1 规划问题的反问题进行了深入研究，给出了在厶范数与匕范 数下反线性规划的一般模型及算法【1 1 刁在筠，关秀翠等探讨了一般形式反线性规划问题在各种范数下的求解，基于求解 凸二次规划的原，对偶内点算法，给出了一个o ( n 3 l ) 算法和一个实用算法f 】1 1 ，基于线性 规划问题的最优性条件( k u l m t u c k 条件) ，将l 范数下的反线性规划问题转化成为 仅带有变量非负约束的凸二次规划问题，并利用具有二次收敛性的预校正内点法( t h e p r e d i c t o r - c o r r e e tp o i n tm e t h o d ) 来求解【1 9 1 针对反线性规划问题的价值向量中有些分量不 允许调整的情况，提出了一般线性规划的限制逆问题，结合线性规划的最优性条件，得 出了其在l 范数，厶范数和厶范数下的数学模型分别对应为线性规划和二次规划的 结论 2 0 1 ，证明了由限制逆问题的可行解和最优解可相应地得到反线性规划问题的可行解 和最优解，并进而给出了反线性规划问题的一种简化模型 j z h a n g 和l z h a n g 研究了一类二次规划反问题，建立了这个问题的最小化模型， 通过解这个问题的反问题得到原问题的最优解它的对偶问题是一个线性约束的半光滑 可微凸规划问题，在求解这个对偶问题中采用了增广拉格朗日方法，而对于增广拉格朗 日的子问题采用半光滑牛顿法，并证明该方法的全局收敛性和局部二次收敛速度 1 1 3 当前研究中的一些问题及本文的内容 综合对现有文献资料的分析，不难发现当前优化问题反问题领域的研究上存在一些 问题与不足之处，有待于进一步发展与完善当前关于优化问题反问题的研究工作仅仅是 局限在针对组合优化中的一些具体问题的反问题进行建模，并应用组合优化的某些理论 和方法对其进行计算求解，我们可以看到的文献大多数是组和优化方面反问题的研究， 在连续优化反问题方面的进展很小，除了线性规划反问题外，我们没有看到更多的研究 成果而对一般形式线性规划反问题也只是停留在理论探讨的阶段，大规模的工程实际应 用还没有深入开展 本文所要研究的一类二次规划反问题就是连续优化反问题，我们建立了该问题的一 般化模型，由于变量很多的时候问题的规模会很大，故我们通过解问题的对偶问题求解 原问题，这样可以使问题的求解规模大大减少在第2 章我们在求解增广拉格朗日问题的 子问题时采用拟牛顿法和a r m i j o 线搜索取得了很好的计算结果，并通过数值试验对比 以前文献中采取的牛顿法的结果可以看到我们对算法改进的效果在第3 章中求解对偶 问题，运用了障碍函数法，我们证明了这个算法可以求解该问题，给出目标函数凸性的 证明，并通过数值试验证明算法是有效的 大连理工大学硕士学位论文 1 。2 本文研究的问题模型 我们考虑的二次规划问题的形式是 ( p ) m i n f ( x ) ：= 三2 x 7 g 知+ c r x s t x q 。# x 兄i a x 2 b 其中g 置是对称矩阵，c r ”，a g ”，b r ”令 a ：= ( 口l ，口_ ) 1 ，口，er “，i = 1 ，埘， 是押月对称矩阵的全体，s o l ( p ) 是问题的最优解解集，给定可行点p q 。， ( g o ，扩) x r ”是对( g ，c ) 的估计 我们要解决的二次规划反问题就是找到一对( g ，c ) r “，使它们满足： ( i p ) m i n 妄0 ( g ，力一( g o ，) 1 1 2 ( 1 2 ) 上 s t x o s o l ( q p ( g ，c ，a ，b ) ) ( g ，c ) s ：g “ 这里霹是中的正半定对称矩阵锥，j | 定义为 l ( g ，c 圳- 乃( g 7 g ) + c ? c ，其中( g l c g x g 问题( p ) 是一个目标函数是二次的锥约束优化问题，当n 很大时问题的决策变量数 将是n + n ( n + 1 ) 2 ，规模会非常大，直接求解该问题很复杂我们想要通过求解它的对偶 问题实现对该问题的求解对偶问题是半光滑可微的，并且决策变量比原问题要少的多， 它的可行集是一个凸锥 大连理工大学硕士学位论文 2 对偶问题 2 1 预备知识 这一部分我们将回顾非光滑分析在半光滑映射下的一些结论，正半定矩阵锥的性质 以及凸规划对偶理论，这些结果会在下面的分析中用到 令x 和y 是两个有限维实向量空间，0 是x 上的开集，o ：o 并一y 是开集o 上局 部l i p s c h i t z 连续函数根据r a d e m a c h e r 定理，m 在开集0 上几乎处处f r e c h e t 可微我们 把玩定义为m 在开集0 上f r e c h e t 可微点的集合那么m 在x 0 处的b 微分用a 口m ( x ) 表示 a 。m ( x ) ：= ! 觋，中( x ) 吼，聋_ x j ， 这里j d p ( x ) 用来表示在0 上的j a c o b i a n 阵细 ) 定义为： a ( 工) = c o n v a 日( 工) ) 下面的半光滑的定义首先被m i f f l i n 用于函数，被q i 和s u n 扩展到向量值函数 定义2 1 ：令o ：0 x 寸r 是开集0 上的局部l i p s c h i t z 函数我们说巾在点x 0 初半 光滑的如果 ( i ) 西在点x 处方向可微 ( i i ) 对于任给x x ，v a 垂“+ a x ) ，当a x - 0 时， 中( x + x ) 一o ( x ) 一v ( a x ) = d ( 0 x 1 1 ) 并且如果巾在x 处是半光滑的，对于任意缸x ，v a 和伍十缸) ，当缸呻0 时， o o + 缸) 一o ( x ) 一矿( 缸) = d “缸 则称西在点工0 处是强半光滑的 由c l a r k e s 局部l i p s c h i t z 连续函数的隐函数定理，我们可以直接得到下面的结论 引理2 1 ：假设函数h ：x x y 呻彳是 ，歹) 爿y 的开邻域上的局部l i p s c h i t z 连续函 数，满足日( i ，y - - ) = 0 如果1 i r ( a h ( i ，刃) 中的每一个元素都是a h ( i ，歹) 在空间x 上的投 影，是非单值的，那么存在歹处的开邻域q ，局部l i p s e h i l z 连续函数石( _ ) ：q _ 工满足 x ( 刀= i ，那么对于每一个y q ，日( 力，力= 0 定义2 2 ： 函数f ：r ，一r 在开集o 掣上是半光滑可微的，如果f 在o 上连续可微， v r 在o 上局部l i p s c h i t z 连续，f 在x 处产生的h e s s i a n 阵定义为由p x p 矩阵组成的集 合a 2 f ( x ) 其中 = 耋三姿塑型星旦嬖坚堡墼二些墼鲨 a 2 f ( x ) = c oa 。【v r 】( z ) ， 这里a 。 v d ( x ) 是v f 在x 点处的b 微分，可以表示为下面的形式： a 。【v f 】( x ) = f 日e r ”i 存在一x ，v f 缸处可微，并且v ( ) - r h 引理2 2 ：设函数：r ”x r ”_ 豆是正常的下半连续的凸函数，考虑原始问题 n 。c l n 妒( x ) ， 矿( 功：厂( t o ) ， 与它的对偶问题 m 野 ) ，妒( 力：= - f ( o ，y ) ， 其中9 是凸的下半连续的，矿是凹的上半连续的，令 p ( “) = i n f ( x ，却) ，u = d o m p ，g ( v ) = i n f ，厂( v ，y ) ，v = d o m q ，这些集合与函数均是凸的 ( a ) 不等式i n 妒( x ) s u p ，妒( y ) 总是成立的，i n f ，e ( x ) - o o 当且仅当0 u 进一步， i n f t p ( x ) = s u p $ ( y ) ，如果或者0 i n t u ，或者0 i n t v y ( b ) 集厶a r g m a x y 驴0 ，) 是非空的且有界的当且仅当o e i m u ，且值i n f 妒( 功= p ( o ) 是有限 的，此种情况，a r g m a x ，9 ( y ) = a p ( o ) ( c ) 集合a r g m a x ，9 ( 功是非空的且有界的当且仅当o i n t 矿，且值s u p 妒( 力= - - q ( o ) 是有限 的，此种情况，a r g r a i n ，妒( 功= a q ( o ) ( d ) 最优解通过下述的f e r m a t 原则的原始对偶形式刻画 i a r g r a i n ，妒( 功 歹a r g m a x y 庐( y ) ( o ，力矿 ，o ) 营 ，o ) e f ( o ，歹) i n f 驴( x ) = s u p s ( y ) l 。 ，i 这就是著名的凸规划对偶理论，证明见参考文献明 2 2 建立对偶问题模型 如果g s ? ，那么善oe s o l ( q p ( g , e , a , b ) ) 当且仅当存在“足满足 c + g x 。一“，口，= o ，“，2o ，i = 1 ，p 则问题( 口) 可以等价的表示为下面的形式： 一6 一 大连理工大学硕士学位论文 m i n 抓g ，c ) 一( g 。，c 。) 1 1 2 ( 2 1 1 s tc + g x o a r u = 0 ， 。 ( g ，c ，“) s ：r ”r ? 这个问题的规模是捍仞+ 1 ) 2 + 狞+ p ，当n 很大时，考虑它的对偶问题会使问题易于求 解 为了导出( 2 1 ) 的对偶问题，我们需要引入一个有限维空间t 令y ：r ”x r 9 满足如内积 的形式： ：- 乃( g 1 r g 2 ) + c 1 ，c 2 + “盯, 2 ( g 4 ，c j ，材) t , i = l ，2 ， 空间的范数l l 定义为： 8 ( g ，f , ) l - - , m g 7 g ) + c 7 c + u 7 甜，( g ，c ，u ) t 定义线性算子a ：t r ”为： b g ：( ， ) r ，( g ，。，砧) ey ， 这里 ”：( 生掣一，_ a ) ，f 乩，刀， 其中p 。e 屁“，是第i 个单位向量那么问题( 2 1 ) 可以写为下面的形式 i q p ( 氏b ) m i n 圭 ( g ，c ) 一( g o , c o ) | 2 ( 2 2 ) s ja ( g ，c ，“) ；0 ， ( g ，f ，“) k ：= s ：r8 r ? 命题2 1 ：问题( 2 1 ) 满足s l a t e r 约束条件，也就是说 a ：t _ r ”是满射，存在( g ，亭，订) k 满足a ( 辱，# ，疗) = 0 证明：显然，a 是满射 令舌。4 彳1 ，一工o ，矗= 1 ，g = 厶 其中1 ，= ( 1 ，1 ) 7 r ， 则( d ，5 ，z t ) k 并且a ( d ，占，奇) = 0 现在来推导i q p ( a , b ) 的对偶形式 i q p ( a b ) 举jl a g r a n g i a n 函数l ：t x r ”一r 可以表示为： 一类二次规划反问题解法的一些改进 l ( ( g ，c ，“) ，2 ) - - - 三f k g ，力一( g 。，c 。) 8 2 + ，( g ，c ，甜) t ，z 震” 故i q p ( a , b ) i 堑jl a g r a n g i a n 对偶问题可以表示为 ：絮v ( z ) 净( 咖i n f ) l f 三( ( g ，。，“) ，2 ) ( 2 3 ) 命题2 2 ：由( 2 3 ) 定义的函数v ( z ) 可以有下面的表达式 v ：阳z h 2 - t - c o t z - - 三0 n 霹( 承z ) ) 卜妒睁如o 【m 其它情况 其中百( z ) ：go 一堡：兰：! ： z 证明：由函数v ( z ) 的定义可以得到 啡) = 以i 绯n f 。 i l l 。h “扣g 0 n ：彳伽 ；j 峨缸删 三卜。卜扣- g o 睁，国o ，当a o z 观 【。，其它情况 ：j i n 彬专0 c - - c 0 1 1 2 + z r c + i n 之亏1o u u 0 峙2 + g t 溆。) ，当a 。z o ， c m ， 其它情况 对于无约束优化问题 r a i n 吾1 1 c - c 。卜九 由无约束问题解的一阶必要条件，可得最优值 ，( z ) = c o 一= ， 因此我们有 畋矿母_ c 0 1 1 ：+ z r c = 一圳1 2 _ 从下面的表达式 嗨权 扣卅妊4 - z t 酝。 = 吒 扣g g o 盼2 一 一8 一 ( 2 4 ) ( 2 5 ) 大连理工大学硕士学位论文 我们知道最小值在下面这个点处达到 g = n ( g ( ；) ) ( 2 6 ) 所以我们有 吒 扣一g 。眭+ z r g x 。) 一翱否( = ) 一n 群( 否( 砌眭一l 召( 耀+ 俐：1 ， = 一言6 n 肆( 吞( z ) ) 旺+ 圭o g 。幢 故函数v ( z ) 有表达式( 2 4 ) 成立 口 由( 2 4 ) 问题( 2 3 ) 的对偶问题可以重新写为下面的形式 i q d ( a ，b ) 衄x v o ( z 1 ( 2 7 ) s ta z s 0 111 其中v 。( z ) = 一l | z 2 + f ”z 一，r ，：( g ( z ) ) 幢+ | i g 。瞻 ( 2 8 ) 这个问题是1 1 维的，当n 很大时，该问题的规模比( 2 1 ) 小的多 下面引入一个线性算子b ：r ”_ s ”。定义为 b ：型4 上互， ( 2 9 ) 则伴随算子b 表示为 b g ：- ( ， n ( 2 1 0 ) 函数v o 的连续微分 v v o ( ：) = 一= + co j g ( z ) 。( g ( = ) ) = 一：+ c 。+ b l i 。( g ( z ) ) 由于映射，( ) 是不可微的，v v o ( ) 是不可微的，则v o ( ) 是非二次可微的但因为 ，( 一) 是强半光滑映射，v o ( ) 是半光滑连续可微函数，我们可以得到一个v o ( ) 的广义 h e s s i a n 阵的结论 定理2 1 ：函数( ) 是连续可微强凹的，v v o ( ) 是强半光滑的，v o ( ) 的广义h e s s i a n 阵满 足如下结论 ， a 2 v o ( ：) c - i b y i 。( g ( z ) ) 丑( 2 1 1 ) - 二兰垦三姿塑型垦塑墅塑些塑二些塾篓 定理2 2 ：如果问题i q d ( a , b ) 存在唯解，令2 是i q d ( a , b ) 的唯一解，则 ( g ，c ) = c ( g ( z 。) ) ，c 。一：) 汜1 2 1 就是原问题的解 证明：由于v o 是强凹函数，i q d ( a b ) 的约束集合是一个极锥，问题i q d ( a ，b ) 有唯一解 由命题2 1 注意到i q d ( a ，b ) 满足广义s l a t e r 条件，我们从凸规划经典对偶理论知 道，如果( g ，c ，7 , ) 是下面这个问题的唯一解 r a i n 工( ( g ，c ，”) ，= + ) ：( g ，c ，) k 那么 o 令k ：= o 步1 由( 3 2 ) 构造增广l a g r a n g e 函数t ( 工，a ) 步2 以x ( k - d 作为初始点，求解无约束问题 r a i nl 。( 工，a ) 得解工 步3 ( 终止准则) 若 i k ”) + i i m i i i 毋( x 。，) ，彳1 砰州s ， 则得解善 一类二次规划反问题解法的一些改进 步4 ( 进行乘子迭代) 由( 3 3 ) 确定a + ”令后净k + l ，转步1 3 2 增广l a g r a n g e 算法解对偶问题 对偶问题i q d ( a ，b ) 的增广l a g r a n g e 函数可表示为 三，( ：，旯) ：= v o ( z ) 一= l _ 1 1 a + r ao z 】+ | | 2 一l f a 2 】， ( 3 4 ) 这里 】+ 表示上的投影算子，r 0 是参数用增广l a g r a n g e 方法解问题i q d ( a ，b ) 令 o ，群是首个l a g r a n g e 乘子由下面的式子计算a ( m ) a + 1 = n 肆? ( a 一“彳。z ) “+ l ：= k 或者k + l ：= k r t 注意到问题i q d ( a ，b ) 是一个凸规划问题，由文献 1 9 我们可以选择对于所有的k 都有0 ；r ，这里r 是正的数量在实际中，我们通常选择的近似值，但是为了方便问 题的讨论，这里选择z 。的精确值令 f ，( a ) ：= 所口z 三，( z ，旯) 对偶问题可以写做 c p ， f i n z 经 s ， i q d ( a ，b ) 的原问题表示为 c 域， ：n ? 置 a ， 这里 m i n 砸) # ：“2 _ l 揣况 i + 。o 。头匕1 肓优 其中l o ( z ，a ) = 1 o ( z ) 一 是i q d ( a ，b ) 的l a g r a n g e 函数 为了讨论方便设4 是行满秩在这个条件下s l a t e r 约束规范成立经典对偶理论对凸 规划成立，至少存在一个r 满足 ) = m 哑t o ( z ) = v a l ( i q d ( a , b ) ) 因为l o ( z ，a ) 是强凹的，m a ) 【，厶( z ，a ) 有唯一解令z 是m a ) 【：4 ( z ，) 的唯一解， 则：s o l ( i q d ( a , b ) ) ，故求解问题i q d b ) 就等价于求解无约束问题m a x ：厶( z ，r ) 大连理工大学硕士学位论文 如果我们获得问题( 2 1 7 ) 的解，那么函数f ，( a ) 有下面的表达式： “a ) = 癣“纠呱a ) + 剖a + 一a l | 2 对于每个r o ，( d r ) 与原对偶问题( d 0 ) 有相同的最优值 从上面的分析可知，如果由增广l a g r a n g e 方法产生的序列 ( ，) ) ，满足 收敛到a s o l ( d , ) ，并且n o ，当k 足够大时，忙一，8 n 忱一r 0 成立，那么我们可以 推出 z 。卜z s o l ( i q d ( a , b ) ) ，这样我们就能够从定理2 1 的结论得到原问题 i q p ( a , b ) ) 的解( g ，c ) = ，( g ( z ) ) ，c o z ) 关于识 _ a 可以由下面的定理得到，证明 见文献 1 】 定理2 3 令4 是行满秩的，z 是i o d ( a ，b ) 的唯一解，a 是唯一的l a g r a n g e 乘子，由增广 l a g r a n g e 方法可产生一个序列 ( 矿，) ) ，则 ， ，a ) ，当k o d 时 尽管r o e k a f e l l a r 给出了增广l a g r a n g e 方法在凸规划中的收敛性，但分析要求函数 是二阶可微问题，这里我们给出的定理证明了在更弱的条件下，目标函数不是二次可微， 而是半光滑连续凸的情况下的收敛性 3 3 拟牛顿法解子问题 现在我们考虑问题 m a x ：( = ，a ) ( 3 7 ) 迭代过程中子问题的求解令 p ( z ) = l ( z ，旯) ， 这里0 ：r “一盖是半光滑连续的强凹函数，我们想要用拟牛顿法解这个问题 在众多的迭代算法中，拟牛顿法是非常重要的一类方法，关于拟牛顿法的全局收敛 性研究也取得了许多重要进展当，是凸函数时，采用精确搜索的b r o y d e n 族算法具有全 局收敛性p o w e l l g e 证明了采用w o l f - p o w e l l 非精确性搜索时b f g s 算法的全局收敛性 b y r d n o c e d a l ，y u a n 将p o w e l l - g e 的结果推广至除d f p 外的b m y d e n 族算法大量数值试 验结果表明b f g s 算法是众多拟牛顿法中数值效果最好的算法 在这里我们考虑用拟牛顿法解这个目标函数是半光滑可微的问题，先给出算法步骤 采用a r m i j i o 型线搜索的b f g s 算法： 一类二次规划反问题解法的一些改进 步l 取初始点2 ( 0 彤，初始对称正定矩阵鼠e r ，精度 0 令k - - - o 步2 若l l v e ( z ) i 喀s ，则算法中止，得问题的解z ( “ 步3 解线性方程组 置d + v e ( z c k ) = o ， 得解d ( “ 步4t 扫a r m i j i o 型线搜索确定步长以 步5 令z 纠= z + a k d “若| i v p ( z 。“) j i - 。0 确定盈。 其中s 。= ：忙“一z n ，= v o ( z 卅) 一v p ( 工耻) 步6 令k ：= k + 1 转步3 拟牛顿法与牛顿法相比，不但保持了相当满意的收敛速度，同时也避免了计算导数， 不仅如此拟牛顿法还因为一些矩阵方向的计算技巧避免了每次迭代时求解线性方程组 另外拟牛顿法有全局收敛性，对任何初始点p 算法产生的点列 都收敛到x 称该 算法具有全局收敛性这一特征有助于算法的推广，牛顿法不具备此特征，当初始点离最 优解较远时，算法失效，拟牛顿法正是克服了此不足而发展起来的，大多数拟牛顿法在 适当条件下都具有全局收敛性 拟牛顿法之所以有效是因为多数拟牛顿算法都具有良好的特性，应用非常广泛，至 今仍处于不断发展中影响拟牛顿算法的主要因素有：目标函数的光滑型和凸性，拟牛顿 方程中参数的选取，同一类拟牛顿算法选取不同的参数，对应的算法性能差异很大，同 一种拟牛顿算法采用不同的步长的获取方法，直接影响算法的有效性，可行性，特别是 不精确步长搜索法，依据不同的准则，效果有明显差异 3 4 数值试验结果 3 4 1 实验数据 这节我们对2 4 节和2 5 节的算法进行数值试验，并列出了文献 1 】中算法的数值 结果，用于和本算法进行比较 大连理工大学硕士学位论文 首先需要说明以下几点： ( 1 ) 所有程序都是m a a b 程序； ( 2 ) 算法中的数据，4 ，g o ，c o 随机选取； ( 3 ) 首个l a g r a n g e 乘子九= ( 1 ，1 1 ) ； ( 4 ) 拟牛顿法的子问题中我们选取初始对称矩阵日为单位矩阵： ( 5 ) 算法停止准则的精度设为1 0 - 6 ； ( 6 ) 对表头的说明：p 和n 是矩阵的维数；r o 为罚参数，i n t e rl a g 是拉格朗日算 法最大迭代步数，k 是该算法迭代步数，c p ut i m e 是完成计算所需要的时间， f u ne v a l 为函数调用次数； ( 7 ) 表2 2 是对文献【l 】中的用牛顿法解增广拉格朗日方法子问题做的数值试验结 果用于与本文算法的结果做比较 一类二次规划反问题解法的一些改进 表2 1 数值试验结果( 增广l a g r m g i a n 法，拟牛顿法求解子问题) t a b 2 2 t h e d a t a f o r n u m e r a l e x a m p l e ( t h ea u g l x l c l l t c dl a g r a n g i a nm e t h o da n dq u a s i - n e w t o nm e t h o d ) n p r 0 l t e r l a g k c p ut i m ef u ne v a l 1 0 01 00 11 0 0 0 02 74 6 1 7 27 0 0 6 1 0 01 011 0 0 0 062 7 4 0 6 05 4 6 6 1 0 01 01 0 1 0 0 0 0 31 2 2 8 4 4 03 1 4 6 1 0 01 01 0 01 0 0 0 061 9 3 2 22 5 3 6 1 0 0 1 0o 12 03 22 9 1 7 1 05 8 9 9 1 0 01 01 2 0 61 1 4 8 42 3 9 1 1 0 0 l o 1 0 2 0 1 1 4 0 3 1 3 01 1 6 1 1 0 0 1 0 1 0 0 2 029 1 4 5 3 04 1 6 0 2 0 02 01 01 052 8 1 2 9 7 07 8 2 8 2 0 02 0l o1 0 073 6 8 8 3 15 6 9 4 2 0 02 01 01 0 0 096 2 9 5 6 85 9 3 3 5 0 05 01 02 01 13 6 2 刮田0 39 6 8 2 5 0 05 0l o1 0 01 04 6 8 酣巾0 38 5 6 4 5 0 05 01 0 01 0 01 96 5 4 e + 伽36 3 2 1 7 0 07 012 02 37 9 0 刮巾0 35 9 2 0 8 0 0 8 0 1 2 01 22 2 6 e + 0 0 44 8 9 2 9 0 09 0 l2 01 34 5 2 e _ 卜0 0 48 3 6 4 1 0 0 0l ol2 099 1l 时0 0 47 9 2 3 1 0 0 01 0 0l2 07s 6 1 酣0 0 58 6 2 1 - 1 6 大连理工大学硕士学位论文 表2 2 数值试验结果( 增广l _ a g u m g i a n 法，牛顿法求解子问题) t a b 2 2t h ed a t af o rn u m e r a le x a m p l e ( t h ea u g m e n t e di 弼r a n g i a nm e t h o da n dn e w t o nm e t h o d ) n p f 0l t e rl a gkc p ut i m ef u ne v a l 1 0 0 1 0 o 11 0 0 0 0 2 0 04 4 0 1 6 05 0 7 】o o 1 0 】0 0 0 0 l o 4 5 3 1 3 0 2 7 3 l o o 1 0 1 0 i 0 0 0 05 1 7 5 5 9 3 0 1 2 4 5 1 0 0