（运筹学与控制论专业论文）求解半定约束二次规划逆问题的数值方法.pdf

大连理工大学博士学位论文 摘要 本论文研究了一类由半定约束二次规划问题产生的逆优化问题此逆问题通过尽量 小地调整半定二次规划问题的目标函数的参数，使得已知的可行解为调整后的问题的 最优解我们将此逆问题转化为带有半正定矩阵锥约束的极小化问题，并且经推导可知 其对偶问题为一个带有线性半正定矩阵锥约束的半光滑可微凸问题并且当问题的规模 很大时，对偶问题变量的维数远小于原问题变量的维数，所以本论文的中心就是研究 如何求解此对偶问题 本论文的内容概括如下： 1 在第一章中，首先介绍了逆优化问题的背景及其研究现状，然后提出了本文所要 研究的一类产生于半定二次规划问题的逆问题，并通过一系列等价转化得到其对 偶问题i s d q d ( a ，j e 7 1 2 第二章研究了用增广拉格朗日方法求解半定二次规划逆问题的对偶问题首先概述 了增广拉格朗日方法的背景和发展历史，接着回顾了半光滑分析的一些知识和半 正定矩阵锥的一些性质然后在一定的假设条件下，给出了增广拉格朗日方法求 解问题i s d q d ( a ，b ) 的全局收敛性和线性收敛速度最后给出数值实验结果 3 第三章的主要内容是用光滑化牛顿法求解半定二次规划逆问题的对偶问题 的k a r u s h k u h n t u c k e r 系统首先介绍了一种光滑化函数以及它的一些性质然后 运用此光滑化函数将问题i s d q d ( a ，b ) 的k a r u s h k u l m t u c k e r 系统转化为一个光滑 方程组，接着用光滑化牛顿法求解此方程组，然后给出了光滑化牛顿法的收敛性 和收敛速度最后由数值实验说明了此方法的有效性 4 第四章探讨了由光滑化牛顿法改进得到的非精确光滑化牛顿法求解对偶问 题i s d q d ( a ，b ) 的k a r u s h k u i m - t u c k e r t 系, 统首先引入了矩阵值函数的一些知识， 然后在严格互补和非退化性条件成立的假设下，给出了非精确光滑化牛顿法的收 敛结果最后我们对几种求解i s d q d ( a ，b 1 的方法进行了数值实验，并对其结果进 行了比较和分析 关键词：逆优化问题；增广拉格朗日方法：半正定矩阵锥；光滑化牛顿法；非精 确光滑化牛顿法 大连理工大学博士学位论文 n u m e r i c a lm e t h o d sf o ri n v e r s es e m i d e f i n i t eq u a d r a t i cp r o g r a m m i n g p r o b l e m s a b s t r a c t w ec o n s i d e ra ni n v e r s eo p t i m i z a t i o np r o b l e mr a i s e df r o mt h es e m i d e f i n i t eq u a d r a t i cp r o - g r a m m i n g ( s d q p ) p r o b l e m i n t h ei n v e r s ep r o b l e m ，t h ep a r a m e t e r si nt h eo b j e c t i v ef u n c t i o no f ag i v e ns d q pp r o b l e ma l ea d j u s t e da sl i t t l ea sp o s s i b l es ot h a tak n o w nf e a s i b l es o l u t i o nb e - c o m e st h eo p t i m a lo n e w ef o r m u l a t et h i sp r o b l e mi n t oam i n i m i z a t i o np r o b l e mw i t hap o s i t i v e s e m i d e f i n i t ec o n ec o n s t r a l n la n di t sd u a lp r o b l e mi sal i n e a r l yp o s i t i v es e m i d e f i n i t ec o n ec o n - s 廿a l 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 rv a r i a b l e st h a n t h eo r i g i n a lo n e t h e r e f o r et h i st h e s i si sf o c u s e do ns o l v i n gt h ed u a lp r o b l e m t h em a i nr e s u l t so ft h i sd i s s e r t a t i o na r es u m m a r i z e da sf o l l o w s ： 1 c h a p t e r1f i r s tg i v e st h ei n t r o d u c t i o n ，b a c k g r o u n da n dc u r r e n tr e s e a r c ho fi n v e r s eo p t i m i z a - t i o n 。t h e nw ed e s c r i b et h ei n v e r s es e m i d e f i n i t 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 s t u d i e d i nt h i st h e s i s ，a n dd e r i v ei t sd u a lp r o b l e mi s d q d ( a ，b ) 2 c h a p t e r2d e a l sw i t ht h ea u g m e n t e dl a g r a n g i a nm e t h o df o rt h ed u a lp r o b l e mo ft h ei n - v e r s es e m i - d e f i n i t 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 s i nt h i sc h a p t e rw ef i r s td e s c r i b e t h eb a c k g r o u n do ft h ea u g m e n t e dl a g r a n g i a nm e t h o d f o l l o w i n gap r e l i m i n a r yr e v i e w o fs e m i s m o o t ha n a l y s i sa n dt h ep o s i t i v es e m i d e f i n i t ec o n e ，w ep r e s e n tt h ec o n v e r g e n c e a n a l y s i so fa u g m e n t e dl a g r a n g i a nm e t h o df o rs o l v i n gt h ed u a lp r o b l e m i nt h ee n d , w e r e p o r t0 1 1 1 n u m e r i c a lr e s u l t s 3 t h ec o n t e n t so fc h a p t e r3a r em a i n l ya b o u tt h es m o o t h i n gn e w t o nm e t h o df o rt h ek a r u s h - k u h n t u c k e rs y s t e mo f p r o b l e mi s d q d ( a ，b ) ，f i r s tw ei n t r o d u c eas m o o t h i n gf u n c t i o n a n ds t u d yi t sp r o p e r t i e s t h e nw ep r e s e n tt h ec o n v e r g e n c ea n a l y s i so fs m o o t h i n gn e w t o n m e t h o df o rt h es m o o t hl i n e a rs y s t e mw h i c hi sas m o o t h i n ga p p r o x i m a t i o no ft h er e f e r r e d k a r u s h k u h n t u c k e rs y s t e m i nt h ee n do fc h a p t e r3 ，o u rn u m e r i c a le x p e r i m e n tr e s u l t s s h o wt h a tt h i sm e t h o di sv e r ye f f e c t i v e 4 i nc h a p t e r4 ，w ed i s c u s st h ei n e x a c ts m o o t h i n gn e w t o nm e t h o dw h i c hi sb a s e do nt h e 求解半定约束二次规划逆问题的数值方法 s m o o t h i n gn e w t o nm e t h o d f o l l o w i n gs o m ep r e l i m i n a r i e so nm a t r i xv a l u e df u n c t i o n s ， w ea p p l yt h ei n e x a c ts m o o t h i n gn e w t o nm e t h o dt os o l v ep r o b l e mi s d q d ( a ，b ) u n - d e rt h es t r i c tc o m p l e m e n t a r ya n d n o n d e g e n e r a c ya s s u m p t i o n s ，w eg i v et h ec o n v e r g e n c e r e s u l t so ft h ei n e x a c ts m o o t h i n gn e w t o n m e t h o d f i n a l l y ，i no u rn u m e r i c a le x p e r i m e n t w em e a s u r et h en u m e r i c a lp e r f o r m a n c eo ff o u rn u m e r i c a lm e t h o d sf o rs o l v i n gp r o b l e m i s d q d ( a ? b ) k e y w o r d s ：i n v e r s eo p t i m i z a t i o n ；a u g m e n t e dl a g r a n g i a nm e t h o d ；p o s i t i v es e m i d e f i n i t ec o n e ；s m o o t h i n gn e w t o nm e t h o d ；q u a d r a t i cc o n v e r g e n c e 一 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方 外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他己 申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的 贡献均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：蒸缝葺基乏釜基三垒盟兰尘堕必塑丝丛鱼墨丝 作者签名：赵! 坠监日期：王! ! ! 年l 月j l 日 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 芷鲢圭俎叁基三望趣盅! ) 迤! 盘选纽巡查盗 作者签名： 鱼边噍日期：幽卫年l 月上卫日 导师签名：划日期：巡年上月j l 日 大连理工大学博士学位论文 1绪论 1 1 逆优化问题的简介 近些年来，逆问题( i n v e r s ep r o b l e m , 有时也称为反问题) 引起了诸多学者的广泛研究 t a r a n t o l a 在1 9 8 7 年的著作t j q b 对逆问题是这样描述的： l e tsr e p r e s e n tap h y s i c a ls y s t e m a s s u m et h a tw ea r ea b l et od e f i n eas e t o f m o d e lp a r a m - e t e r sw h i c hc o m p l e t e l yd e s c r i b es a l lt h e s ep a r a m e t e r sm a yn o tb ed i r e c t l ym e a s u r a b l e ( s u c h a st h er a d i u so fe a r t h sm e t a l l i cc o r e ) w ec a no p e r a t i o n a l l yd e f i n es o m eo b s e r v a b l ep a r a m e t e r sw h o s ea c t u a lv a l u e sh o p e f u l l yd e p e n do nt h ev a l u e so f t h em o d e l p a r a m e t e r s t os o l v et h e f o r w a r dp r o b l e mi st op r e d i c tt h ev a l u eo ft h em o d e lp a r a m e t e r s t os o l v et h ei n v e r s ep r o b l e m i st oi n f e rt h ev a l u e so ft h em o d e lp a r a m e t e r sf r o mg i v e no b s e r v e dv a l u e so ft h eo b s e r v a b l e p a r a m e t e r s 我们通常见到的优化问题在上文中被称为正问题( f o r w a r dp r o b l e m ) ，在这些问题中 我们通过已知的参数( 比如，目标函数和约束中决策变量的系数，约束中的系数矩阵， 约束的右端项等等) 来求解出决策变量的最优解在现实中有很多优化问题，问题中的一 些参数是未知的，我们只知道这些未知参数的估计值，但是却可以通过经验、观测或 者试验得到某些解是该问题的最优解所谓逆优化问题( i n v e r s eo p t i m i z a t i o n ) 就是要调整 这些未知参数的值，使得这些值与它们的估计值相差最小，并且使己得到的解为调整 后的问题的最优解逆优化问题的研究是在其它领域中逆方法( i n v e r s em e t h o d ) 的广泛应 用( 比如瞄，3 j ) 的背景下开始的 最先开始研究逆问题的是地球物理学家他们在进行地球物理研究时经常会有一些 未知的模型参数，因为这些参数在现实中很难或者根本不可能得到( 比如地核的直径) ， 通常只会有一些估计值或者观测值因此，从2 0 世纪8 0 年代逆问题在地球物理领域中的 研究开始活跃起来逆问题在地球物理领域中的一个重要应用就是对地震运动的预测 t a r a n t o l a 在上文提到1 拘1 9 8 7 年的著作【l j 中对地球物理学中逆问题的相关理论进行了深 刻的论证，并给出了逆问题在其它领域的一些应用 逆问题另一个重要的应用是减少道路规划中的成本假定我们有一个道路网络以及 一些便民设施( 如公园等) ，通常情况下要考虑的问题是如何放置这些设施并使民众通过 道路网络到达这些设施的最大距离最小化但是在实际中，我们经常面对的事实是一些 求解半定约束二次规划逆问题的数值方法 设施已经被安放并且不可能被移动或者需要巨大花费才能移动在这种情况下，我们就 想尽量少的修改道路网络使得这些设施的位置达到最优( 或者使民众到达设施的距离不 超过给定的上界) 这是中央路径问题逆问题的一个例子当我们修改道路网络时，另一 个有效的办法是对某些道路征收税收使道路的应用更为合理( 参看文献 4 ，5 】) 1 2 逆优化问题的研究现状 在数学规划领域，对逆问题的研究兴趣起始于2 0 世纪9 0 年代初，同样是为了预测 地震运动，学者b u r t o n 和t o i n t 在1 9 9 2 年和1 9 9 4 年的两篇文献【6 ，j 对产生于地震层析成 像( s e i s m i cm m o g r a p h y ) 的最短路逆问题( i n v e r s es h o r t e s tp a t hp r o b l e m s ) 进行了研究从这 开始，关于逆优化问题的研究热情开始在运筹学家中间迅速的高涨起来，逆问题也 被大量地应用在组合优化的诸多领域比如，逆问题在投资组合优化中的应用【8 ，刿) ， 生成树逆问题【1 0 】( i n v e r s es p a n n i n g 优p r o b l e m ) ，网络流逆l n - - j 题 11 】( i n v e r s en e t w o r kf l o w p r o b l e m ) ，等等【1 2 - l6 1 但是在连续优化领域，逆问题的研究还没有引起广泛的重视， 迄今为止我们只能找到有限的几篇文献，比如关于线性规划的逆问题【17 ，1 8 j ，关于线 性二次规划的逆问题【l 引因此，关于连续优化逆问题的研究，有大量的工作需要去完 成 在本节中，我们介绍迄今为止已经解决的或者被研究过的一些优化问题的逆问 题( 其中组合优化逆问题部分主要来自于调查报告【1 6 j ) 其中一些问题的中文称谓是从英 文直译过来的，有些中文译名可能国内没有统一的翻译，我们在这些译名之后都给出 其英文原称如果中文译名引起读者的混淆和疑惑，请以英文原称为准 ( 1 ) 次模函数最大值问题( s u b m o d u l a rf u n c t i o nm a x i m i z a t i o n ) 次模函数最大值问题 最初由e d m o n d s 并t g i l e s 2 0 】提出的由文献 2 0 ，2 1 】可知，许多的组合优化问题f 例如网 络流问题) 都可以转化为次模函数问题c a i ，y 觚g 和l i 在文献【2 2 j 中研究了一类次模函数 逆问题，并将之转化为一个最小费用循环流问题( m i n i m u mc o s tc i r c u l a t i o np r o b l e m ) 由 文献【弱j 可知，此问题可以用一强多项式算法求解 ( 2 ) 最小费用流f = - i 题( m i n i m u mc o s tf l o w ) 文献【1 2 ，l7 j 考虑了一类2 】范数下的最小费 用流逆问题文献【1 2 ，2 4 1 ：k 碉：究了2 范数下的最小费用流逆问题，并证明其等价于一类 最小中值循环问题( m i n i m u mm e a nc y c l ep r o b l e m ) ( 3 ) 最短路径问题( s h o r t e s tp a t h s ) 实际上，最短路径问题是第一种引起学者研 2 大连理工大学博士学位论文 究其逆问题的优化问题( b u r t o n 和t o i n t 【o j ) ，并且引起了学者们的特别关注( 参见文 i t s 7 ，1 5 ，2 5 - 2 8 ) ( 4 ) 最短路径树问题( s h o r t e s tp a t ht r e e ) 盈柚g 和m a 在文献【2 刿研究了一类最短路径 树问题的逆问题，用线性规划方法将之转化为最小费用循环流问题 ( 5 ) 配置问题( a s s i g n m e n t ) 3 锨 1 2 ，1 7 ，1 8 ，2 9 考虑了一类逆配置问题( i n v e r s ea s s i g n m e n tp r o b l e m ) ，并用线性规划方法将之转化为一种最小费用循环问题从而求解 y a n g 3 0 j 证明了一类只有部分已知解的带有约束的逆配置问题是n p 难的( n p h a r d ) ( 6 ) 加权拟阵相交问题( w 萌g h t e dm a t r o i di n t e r s e c t i o n ) 5 礅 3 1 ，3 2 】用组合线性规划 方法求解一类加权拟阵相交问题的逆问题z l l a i l g 和l i u 【2 4 j 考虑了f 范数下一类无约束 逆问题，证明可以将之转化为最大中值循环问题( m a x i m u mm e a nc y c l ep r o b l e m ) ( 7 ) 最大拟阵基问题( m a x i m u mm a t r o i db a s i s ) d e l l a l l l i c o ，m a f f i o l i 和m a l u c e l l i 3 3 调查研究了一类逆最大拟阵基问题，并用贪婪算；法( g r e e da l g o r i t h m ) 对它进行了求解 ( 8 ) 最小生成树问题( m i n i m u ms p a n n i n gt r e e ) 文献 3 3 - 3 5 用不同的方法求解了一 类z 1 范数下不带约束的最小生成树逆问题文献【1 8 ，3 5 考虑了一类c o o 范数下不带约束的 最小生成树逆问题 ( 9 ) 最短树形问题( s h o r t e s ta r b o r e s c e n c e ) 文献 1 5 ，2 6 j 研究了两类不同的最短树形逆 n 题( i n v e r s es h o r t e s ta r b o r e s c e n e c ep r o b l e m ) ( 1 0 ) 最小割问题( m i n i m u mc u t ) 文献【l 厶j o j 分别用不同方法求解了一类逆最小割 问题文献【l l ，37 j 另外研究了两种不同类的逆最小割问题 ( 1 1 ) 最大流问题( m a x i m u mf l o w ) y a n g ，z h a i l g 和m a 【的j 研究了一类逆最大流问题 ( 1 2 ) 最大权完全匹配问题( m a x i m u mw e i g h tp e r f e c tm a t c h i n g ) 参见文献【3 8 j ( 1 3 ) 中心选址问题( c e n t e rl o c a t i o n ) 文献 1 4 1 考虑了一类带约束的逆中心选址问 题，并证明逆选址问题是n p 难的文献 3 9 ，4 0 研究了另外一种逆中心选址问题 ( 1 4 ) 最大容量问题( m a x i m u m c a p a c i t yp r o b l e m ) y a n g 和z h a n g 4 1j 研究了一类不带约 束的逆最大容量问题 ( 1 5 ) 线性规划问题( l i n e a rp r o g r a m m i n g ) 线性规划逆问题最初是 由z h a i l g 和l i u 【l7 j 开始研究的，他们将线性规划逆问题转化为一新的线性规划问题 h u a n g 和l i u 4 2 得到- 7 同样的结论a h u j a 和o r l i n 1 2 1 考虑了逆问题的对偶问题，他们表 示解一个问题等价于求解其对偶问题这个理论同样可以用于求解逆问题文献【18 】也研 究了线性规划逆问题 3 求解半定约束二次规划逆问题的数值方法 ( 1 6 ) 二次规划问题( q u a d r a t i cp r o g r a m m i n g ) 最近，有两篇报告【1 9 ，4 3 】对二次规划 逆问题进行了研究 注1 1 下面我们给出一些本论文将会用到的符号和定义： 伊表示由n 竹对称矩阵构成的空间 贸表示由佗n 半正定矩阵构成的锥 对任意的矩阵a 伊，t r ( a ) 表示a 的迹 对任意的矩阵a b 5 n ，a b 当且仅当a b t 宠 佗 对任意的矩阵a ，b 伊，( a ，b ) ：= t r ( a b ) = a i j 木b 西，l i a i i ；- ：= ( a ，a ) 是矩 i , j = l 阵a 的f r o b e n i u s 范数的平方 对任意的矩阵a 。耸，a 表示a 的平方根，i a i ：= ( a 2 ) 表示a 的绝对值 对任意的矩阵a 伊，h 毋( 月) ：= ( 月+ l a i ) 2 表示a 到t 耸上的投影 对任意的矩阵a ，b s 几，aob 表示a 和b 的h a d a m a r d 积，如果c ：aob ，那 么= 如幸，t ，j = 1 ，礼 4 大连理工大学博士学位论文 1 3 一类半定二次规划逆问题 本论文中，我们考虑一类带有半正定矩阵锥约束的二次规划问题： s d q p ( g ，c ，a ，b ) m i n 弛) ：= 互1 z 丁劬+ c t z s t z q 尸：= _ z 7 r ni k 75 口 ， 其中，g t 皿，b s m ，c 黔a ：r n s m 是一个线性算子，其定义为 咖：= y i a t ，职， i - = 1 其中a i 。弘，i = 1 ，竹因此4 的伴随算子4 就有如下定义 a + ( x ) ：= x x x ，v x s m 为了简化符号，我们引入一个映射“s o l ，它的自变量是一些优化问题比如对一个 优化问题( p ) ，s o l ( p ) 就表示优化问题( p ) 的最优解集 下面我们考虑由p f i 题s d q p ( g ，c ，么，刀) 产生的一个逆问题假定( g o ，c o ) , s n 酞佗是 参数( g ，c ) 的一个估计，可行点z o q 尸是问题s d q p ( g ，c ，a ，b ) 的一个最优解本论文 所研究的二次规划逆问题就是要找到一组( g ，c ) px 黔使得它是下述问题的最优 解， 1 m i n 割( g ，c ) 一( g o ，c o ) 1 1 2 s t z o s o l ( s d q p ( g ，c ，ab ) ) ， ( 1 2 ) ( g ? c ) 。皿瓞住， 其中”l i 是这样定义的，i i ( a 7 ，e ) l f ：= 丽丽f 丽对任意的( g ，c ，) 铲r n 通过对问题( 1 2 ) 的观察，我们很容易看出当扎非常大的时候，问题( 1 2 ) 的规模将非 常庞大( 决策变量的维数是扎+ n ( n + 1 ) 2 ) 自然而然我们就会想到去考虑它的对偶问题 而不是直接去求解问题( 1 2 ) 一5 一 求解半定约束二次规划逆问题的数值方法 1 4 半定二次规划逆问题的对偶问题 由经典的对偶理论可知，z o s o l ( s d q p ( g ，c ，a ，b ) ) 当且仅当存在一个矩阵q s m l 吏得 c + g z o + ( q ) = 0 ： q 。辨， 血o _ - ab ， ( q 出。一b ) = 0 令z o ：= 加。一b ，那么问题( 1 2 ) 可以等价地转化为 m i n 钏( g ，c ) 一( g o ，c 0 ) 1 1 2 s t c + g 一+ ( q ) = 0 ， ( 1 3 ) ( q ，伊) = 0 ， ( g ，c ，q ) 5 军匙n t s 7 假定7 l 为矩阵z o 的秩并且z o 有如下的谱分解， 肚，阱 其中p ：= 限辟 r m x m 是一个正交阵，只r m r 和辟舻( m - r ) 是p 中的分块矩 阵人r = d i a g l s i s ，( ) ，其中九 0 ，增广拉格朗日方法是全局收敛的 关于增广拉格朗日方法应用于等式约束问题( 2 1 ) 的线性收敛速度，b e r t s e k a s 5 4 得 到一个重要的结果，即收敛速度跟1 c 是成比例的这个结果的重要性在于理论上 我们可以选取一个非常大的c 来加快收敛速度而不影响数值稳定性，这也在一定程 度上解释了为什么增广拉格朗日方法在实际应用上有非常好的效果b e r t s e k a s 在著 作【5 5 ，c h a p t e r3 】中指出，如果严格互补条件成立，非线性规划问题f 2 2 1 也有同样的结 1 3 求解半定约束二次规划逆问题的数值方法 论另一方面，许多学者( 如c o i u l 等【5 6 】，c o n t e s s e - b e c k d 5 7 】，i t o 等 5 8 】) 证明了，不需 要假定严格互补条件成立，增广拉格朗日方法应用于非线性规划问题也是线性收敛的 关于增广拉格朗日方法的更多介绍，可以参考两本专著【5 5 ，5 9 】和一份调查报告【6 0 】 增广拉格朗日方法的经典收敛性结果都是在问题的目标函数和约束函数是二次连 续可微的前提下得到的，但是在本文中，问题i s d q d ( a ，b ) 的目标函数u o ( ) 是连续可微 而不是二次连续可微的因此，本章中的收敛性分析是在文献【19 ，6 1 】的启发下，用矩阵 投影算子的变分分析知识完成的 2 2 基本概念和预备知识 在本节，为了以后的讨论，我们介绍一些非光滑分析的知识以及半正定矩阵锥的 一些性质 令x 和y 是两个有限维向量空间，p 是x 中的一个开集，西：p x _ y 是定义 在集合p 上的一个局部l i p s c h i t z 连续函数由r a d e m a c h e r 定理可知，圣在集合p 中几乎处 处f r 6 c h e t 可微我们用珧表示函数西在0 中f r & h e t 可微点的集合那么函数圣在z p 处 i 拘b o u l i g a n d 次微分如西( z ) 定义如下， 如圣( z ) ：= ，l i m 了圣( z 七) iz 七司b ，z 是，z ， 尤， 其中了圣( z 七) 表示圣在z 知 的j a c o b i a n 圣在z 处的c l 面k e 【6 2 】意义下的广义j a c o b i a l l 是垂( z ) 的凸包，即 a 西( z ) = c o n y 如西( z ) ) 下面我们要介绍的半光滑的概念最初是由m i 笳i n 6 3 】提出的，后来被q i 和s u n 6 4 】推 广到向量值函数 定义2 1 令圣：o x _ y 是开集p 上的一个局部l i p s c h i t z 连续函数我们称圣在z p 处是半光滑的( s e m i s m o o t h ) ，当 ( i ) 圣在z 处是方向可微的； ( i i ) 对任意的x 弓a x _ 0 $ n v a 圣( z + a x ) ， 垂( z + z ) 一圣( z ) 一v ( a x ) = o ( i i a z i i ) 1 4 大连理工大学博士学位论文 进一步地，称西在z p 处是强半光滑的( s t r o n g l ys e m i s m o o t h ) ，如果西在z 处是半光滑 的，且对任意的x 弓a x _ 0 和v a 圣( z 十z ) ， 垂( z + a x ) 一中( z ) 一v ( a z ) = o ( 1 l z x z l l 2 ) 由c l a r k e 意义下的关于局部l i p s c h i t z 连续函数的隐函数定理( i m p l i c i tf u n c t i o n t h e o f e m “6 2 ，s e c t i o n7 。1 】，以及定理 6 5 ，t h e o r e m1 1 】和引理 6 6 ，l e m m a2 】，我们可以 直接得出下面的结论 引理2 2 假定h ：xxy _ x 是满足日( 虿，可) = o 的点( - ，可) xxy 的一个 开邻域上的局部l i p s c h i t z 连续函数i x ( a s ( r ，歹) ) 是a 且( ，蚕) 在空间x 上的投影如 果h x ( a 日( 面，可) ) 中的每个元素都是非奇异的，那么就存在可的一个开邻域p y 和一个 局部l i p s c l l i t z 连续函数z ( ) ：0 y _ x 满足z ( 可) = 虿，并且对任意的可0 y ，有 日( z ( 秒) ，可) = 0 另外，如果日在( 虿，歹) 的开邻域的每个点上都是( 强) 半光滑的，那么z ( ) 在o y 的每个点处 也是( 强) 半光滑的 下面我们给出半光滑可徼函数( s e m i s m o o t h l yd i f f e r e n t i a b l ef u n c t i o n ，参照文 献 6 7 ，6 8 】) 的定义 定义2 3 如果一个函数7 ：搬一酞在一个开集p 上是连续可微的，并且v 7 - 在p 上是 局部l i p s c h i t z 连续( 半光滑) 的，那么函数7 被称为开集p 上的l c l ( s e m i s m o o t h l yd i f f e r e n t i a b l e ，简写为s c l ) 函数函数7 ，( ) 在点z 处的广义h e s s i a n 【6 9 】是这样定义的， o = r ( z ) = c o n v ( 如【v 丁】( z ) ) ， 其中如【v 7 】( z ) 是v 7 - 在z 处的b 0 u l i g a i l d 次微分，其表达式如下 如 v 丁】( z ) = 日r p pf | z 七一z 满足v 7 在z 七处可微并且v 2 7 - p 知) _ 日 - 注意，a 2 7 - ( z ) 是由对称矩阵构成的非空凸紧致集另外，集值映射z _ p 2 丁( z ) 是局 部有界的，上半连续的 1 5 求解半定约束二次规划逆问题的数值方法 _ i _ _ l - _ l - _ _ - _ - - _ _ 一一一_ 对开集p 舻上的一个l c l 函数7 - ( ) ，我们有如下的二阶泰勒展开式( s e c o n d o r d e r t a y l o r - l i k ee x p a i l s i o n ) 和中值定理( t h em e a nt h e o r e m ) 6 2 ，6 9 对匆，秒，】c0 ，存在一个矩 阵日0 2 r ( w ) 以及伽( 拶，可7 ) 使得 7 ) = 7 l ( 耖) + ( v 7 ) ，可7 一可) + l o ) ，卢：= tl 入l = o ) ，7 ：= ii 入 e p 满足( 2 4 ) ，那么w 如n 辞( z ) 当且仅当存在眠如础i ( 0 ) 使得 w ( h 、= p 一下一，r 一一1 一 p 二日p q尸：日p 卢e a lo 尸：日p 磅日或w o ( - f i ；h - f i z ) 0 霹肪a 。e 7 口0 0 令q 是由所有例xi 3 1 的, - f 交阵构成的集合定义 一， p l 、h s p p ：= p 瞅x pp = 【r 昂b - - q ( 玮q ) e ，q q ) ( 2 5 ) 显而易见，所有的尸p 有相同的r 和鼻由业i ( 0 ) 的定义和引理【7 2 ，l c 煳4 7 可 知，如果a b n s 望j ( o ) ，那么存在矩阵q q 和q s 吲且q 中的元素q 巧 o ，1 】使得 w o ( d ) = q ( no ( q r d q ) ) q 丁，v d s i p i 因此，不需要过多解释，由引理2 5 可得下面的引理 引理2 6 对任意的如n s p ( 牙) ，存在两个矩阵p p 和e s p 满足( 2 4 ) ，使得 w ( h ) = p ( eo ( p r h p ) ) p r ，v h 酽 本节的最后，为了下文的分析，我们给出一个简单的结论它的证明是显然的 引理2 7 令a 6 和r 是三个正的标量定义 郴咖) ：= 口一熹， 那么，妒( ；r ，a ，6 ) 在 o ：+ o o ) 上是一个递减函数，并且 部n 】蚶邮b ) - - - - - a - - ；1 + 而1 ，t i o ，m a x ，j 砂( t ；r a , 6 ) = n ( 2 6 ) 1 8 大连理工大学博士学位论文 2 3 增广拉格朗日方法 i f i 题i s d q d ( 4 ，b ) 的增广拉格朗日函数【5 5 】为 厶( 可，三) ：= ( 可) + 互1 1 i n s e y ( - - - 一t 咒可) 临一i i z l l ； ， 其中三护是拉格朗日乘子( l a g r a n g em u l t i p l i e r ) ，t o 是参数令m ) 为剪处所有的拉 格朗日乘子的集合求解i h 7 题i s d q d ( a ，b ) 的增广拉格朗日方法如下， 算法2 1 步0 选取一个初始的拉格朗日乘子三o 毋与一个罚参亡o 0 令南：= 0 步1 在第k 次迭代，通过求解下面的子问题得到彭七， 然后计算下面的式子得至u - - k + l ， m i n 厶k ( 可，一奄) e 知+ 1 ：= 敛( 三七一t k t l y 七) 步2 如果( 矿，三七+ 1 ) 满足下面的条件就停止， 否则，转步3 步3 根据一定的规则，令t k + l 为 7 - y 知0 ，( 冗萨三七+ 1 ) = 0 ， t 七+ 1 ：= t 七或者t 知+ 1 ：= 庇七 其中k 1 是一个事先选取的正数令k = k + 1 ，转步1 ( 2 7 ) ( 2 8 ) 己知问题i s d q d ( 4 ，b ) 是一个凸规划问题，根据文献【5 2 ，我们可选取七三t ，其 中t 是一个正的标量因此，在本节中，当我们讨论问题i s d q d ( 4 ，b ) 的增广拉格朗e l ；h - 1 9 求解半定约束二次规划逆问题的数值方法 法的全局收敛性时，t k 兰t 是一个固定的正数实际中，在算法的步l 我们通常选取可七为 一个近似解，但是为了讨论的方便，这里我们认为y 七是问题面n 厶( y ，三七) 的精确解 当t 0 ，令 几( 三) ：= 1 1 1 1 厶( y ，三) ，几( | = i j ：=厶t 【，二j ， v 那么凡相对应的问题i s d q d ( a ，b ) 的对偶问题为， ( d ) m & x 凡( 三) s t 三酽 而问题i s d q d ( 4 ，b ) 的平凡对偶问题为 ( 9 0 ) m 觚t o ( e ) ( 2 9 ) s t 三t 穸， 其中 抖= 慨i n f u e “玑习嚣 l + o 。， 省贝u ， 且c o ( 可，三) ：= v o ( 可) 一( 三，爿可) 是i s d q d ( 4 ，b ) 的拉格朗日函数 下面我们介绍一个本节要用的假设条件 假设2 8 约束非退化条件在雪处成立：氕酞n = 伊 f - x b 受2 8 成立意味着朋( 哥) 是一个单点集 4 4 】，并且问题i s d q d ( a ，b ) 的广义s l a t e r 约 束条件成立因此由凸规划的经典的对偶理论，我们知道存在唯一的三t 使得 t o ( - - ) - m = 拶a x r o