（运筹学与控制论专业论文）一个新的ulagrange函数.pdf

大连理工大学硕士学位论文 摘要 在非光滑优化中，函数的二阶性质与展开的理论与应用方面的研究是倍受关注的课 题 l e m 盯6 c h a l ，m i f 丑i n ，s a g a s t i z 曲a l 和o u s t r y 等提出的“v 一分解理论，给出了非光滑 凸函数厂在不可微点癣的二阶性质的新方法“v _ 分解理论的基本思想是将r “分解 为两个正交的子空间“和v 的直和，使得原函数在“空间上的一阶逼近是线性的，其 不光滑特征集中于1 ，空间中，借助于中间函数( 蹦一l a g r a 丑g e 函数) ，得到函数在切于甜的 某个光滑轨道上的二阶展式 本论文的内容如下： 1 第一章介绍了l e m 盯6 c h a l ，m i m i n ，s a g a s t i z 如a 1 和o u s t r y ( 2 0 0 0 ) | 4 】等提出的“让 分解理论研究的历史概述与理论背景，甜一l a g r a n g e 函数的来源( 这为重新定义甜一 l a g r a n g e 函数并对其作进一步的研究作了准备) ，以及与这一基本理论有关的其它的 研究工作 2 第二章介绍酣弘分解理论的基本思想，借助于中间函数酣一l a g r a n g e 函数，得到这 一函数的一些基本性质及它的高阶性质，由此得到函数的二阶展式“v 。分解理论 可应用到数学规划中；对于有限个约束的非线性规划问题，可以对这一问题所对应 的精确罚函数作“协空间分解 3 在第三章，我们定义了一个新的弘l a g r a n g e 函数，讨论了这一函数的一些重要性质 ( 一阶，高阶，微分性质以及它的最优解集的性质) 当广义“一h e s s e 阵，( 岳) 存在 时，我们可以得到函数，沿着光滑轨道孟+ 0w ( ) 的二阶展式 4 在第四章，我们确立了定义的“一l a g r a n g e 函数与函数，的m o r e a u - 1 y r o s i d a 正则化函 数之间的关系我们也讨论了函数，的“一h e s s e 阵存在的充分必要条件，这一条件 确保了函数作二阶展开的可行性，这也正是我们为什么要讨论新定义的“一l a g r a n g e 函数的原因所在极小化一个凸函数可以采用在“v 一空间分解理论基础上提出的概 念型超线性收敛算法，也可以采用极小化这一凸函数的m o r e a u y o s i d a 正则化函数 的算法，因为这是一个凸规划的光滑最优化问题 关键词：“v 一分解；弘l a g r a n g e 函数；m o r e a 小y o s i d a 正则化；二阶展开 一个新的甜_ l a g r a n g e 函数 an e w 甜一l a g r a n g i a n a b s t r a c t i nn o n s m o o t ho p t i 工i l i z a t i o n ，t h es t u d yc o n c e r n i n gt h et h e o r ya n d 印p l i c a t i o no fs e c o n d o r d e ra n a l y 8 i 8o fn o n s m o o t hf u n c t i o nh a sb e e np a i dm u c ha t t e n t i o n l e m a r 6 c h a l ，m i m i n ，s a g a 8 t i z 矗b a l 雠do u 8 t r y ( 2 0 0 0 ) 【4 】i n t r o d u c e dt h e 甜v d e c o m p o s i t i o nt h e o mw h i c ho p e n saw a yt od e f i n i n ga8 u i t a b l er e s t r i c t e ds e c o n d o r d e r d e r i v 扯i v eo fac o i e xf u n c t i o n ，a tn o n d i 赶、e r e n t i a b l ep o i n 骨 t h eb a s i si d e ai 8t od e c o m p o s e 豫“i n t o 押oo r t h o g o n 出s u b 8 p a c e 8 “锄dvd e p e n d i n go n 蜃，s ot h a tt h e 丘r s t a p p r o ) d m a t i o no f ，i i l “i sl i n e 缸，a n d ，sn o n s m o o t h n e s sn e a rt h ep o i n ti sc o n c e n t r a t e d e s s e n t i a l l yi v ai n t e r m e d i a t ef i l n c t i o na s 8 0 c i a t e dw i t ht h ec o 玎v e xf u n c t i o nw a si n t r o _ d u c e d ，c a l l e d “- l a g r a n 西a n ，at h el a g r a n g i a n ，i ti sp 0 8 s i b l et o 矗n d8 m o o t ht r a j e c t o r i e s a 血dt h es e c o n d o r d e re ) 币a n s i o no f ， i nt m sd i s 8 e r t a 土i o n ，w ep r o p o s ean e w “一l a g r 龇1 9 i a n ，s t u d y i n gi t s p r o p e r t i e sa n d a p p l i c a t i o n s t h ec o n t e n tc a nb es u n l m a f i z e d ： 1 i nc h a p e r1 ，w ei n t r o d u c et h et h e o r e t i c a lb a c k g r o u pa b o u tt h e “v d e c o m p o s i t i o n ， t h eo r i g i no ft h e “一l a g r a n g i a n ( w h i c hi sp r e p a 肥f o rd e f l n i n gan e w 己，l a g r a n g i a n ) m o r e o v e r 、s o m er e c e tr e 8 u l t si nt h ed i r e c t i o na r ea l s od i s c u 8 s e d 2 i nc h 印e r2 ，w er e c a l l 七h eb a s i ct h e r o yo f 甜v d e c o m p 。s i t i o n s o m eb a s i cp r o p e r t i e s o ft h e “一l a g r a n 西a na r ep r e s e n t e d t h e s er e 8 u l t sc a nh e l pu st od e e p l yu n d e r s t a n d t h ef i r s ta n ds e c o n d _ o r d e re x p a n s i o no f ，o nt h e “一s p a c e f 1 l r t h e 皿o r e ，t h e “v d e c o m p o s i t i o ni sa p p l i e dt on l p ：t h et h e o r yo nt h ep e n a l t yf u n c t i o no fc o n s t r a i n e d l i i l i l i z a t i o nw i t haf i n i t en u i l l _ b e ro fc o n 8 t r a 主n t sa r eg e n e r a h z e d 3 i nc h 印e r3 ，an e w “一l a g r a n g i a ni si n t r o d u e e d w bd i s c u s st h ep r o p e r t 主e so ft h e n e wf n c t i o n ( 吼l c ha 吕t h e 缶s t i o r d e r ，h i g h e r o r d e r 阻dt h es u b d i f f e r e n t i a lp r o p e r t i e s ) w h e n7 l 白，( 孟) 。d s t s ，t h es e c o n d o r d e re x p a n d s i o n 。f ，出o n g 牙+ 0w ( ) c a nb e a b t 8 j 玎e d 4 i nc h a p e r4 ，w ee s t a b l i s ht h er e l a t i o nb e t w e e nt h ef u n c t i o nfa n di t st h em o r e a u y o s i d ar e g u l a r i z a t i o n w ea l s od i s s c u s st h e8 u f 王i c i e n ta n dn e c e s s 盯vc o n d i t o l l sf o r t h ee ) d 8 t e n e eo ft h e “一h e s 8 i a n b a s i n go nt h ep r o p o s e d 甜v t h e o r y ，ac o n c e p t u a l s u p l i n e a rc o i l v e r g e n t 甜g o r i t h mc a nb eu s e dt om i n i m i z eac o n v e xf u n c t i o n ，w b 出s o c 0 1 l s t n l c ta na l g o r i t h mf o rm i l l i m i z i n gi t sm o r e a u y o s i d ar e g u l a r i z a t i o n ，b e c a n s et h i s i sas m o o t hc o r e xo p 伯n i z a t i o np r o b l e m ， k e yw b r d s ：“v d e c o m p o s i t i o n ；甜一l a g r a i l g i a n ；m o r e a u - y b s i d ar e g u l a l r i z a t i o n s e c o n d - o r d e re x p a n s i o n 1 1 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：壬龇日期：a 剜! 五：2 墨 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名；土龇 导师签名 尘鲤年臣月丑日 4 1 大连理工大学硕士研究生学位论文 1 引言 本章对非光滑分析和最优化的研究给出了简短的综述，陈述了甜弘分解理论的历史 概述和研究背景，甜弘分解理论的主要思想，中间函数l a g r a n g i a n ) 的来源，以及与 之相关的进一步研究的主要结果，论述了这一理论的应用价值 1 1 “弘分解理论综述 1 1 1 “弘分解理论历史概述 “协分解属于非光滑优化研究领域 优化理论的研究最早出现于1 6 世纪2 0 年代，其主要标志性的工作是费尔玛解决了 这样一个优化问题： m a x z 剪 s t z + 可= 1 0 到1 6 世纪4 0 年代， n e w t o n 和l e i b n i z 提出了微积分学基本定理，这一定理可以 用来解决众多的极小极大问题利用这一有效的工具可以使光滑( 可微) 函数的优化问题 的求解变得相当简单 但是，在科学技术，管理科学和经济学等领域的研究中，非光滑现象不可避免，因而 非光滑最优化理论一直是一个倍受关注的重要研究课题由非光滑的复杂性，使得在传 统光滑假设下所进行的大量最优化不能直接应用于给光滑情况中，因此需要有新的理论 体系 七十年代c 1 盯k e ( 1 9 7 3 7 5 ) 广义方向导数与微分引入之后，非光滑最优化成为一个独 立的研究方向此时，对于非光滑函数的研究主要存在两个问题： 1 一般说来，次微分( 或c l 盯k e 意义下的广义梯度) 是一个集合从而难以确定，其 运算多以包含关系形式来刻画，换句话说，广义方向导数较大，即 ，o ( z ；d ) ，7 ( 。；d ) 对一阶近似的余项结构或形态不能清楚的表达 1 一个新的“一l a g r a 血g e 函数 2 关于函数的二阶近似，即二阶展开，这关系到算法的二阶收敛性问题，这是白八 十年代以来非光滑分析与最优化研究中的一个核心课题 非光滑函数的二阶近似与二阶展开是研究实际问题所需要的某些算法的基础随着 计算机的进步以及非光滑函数在实际中的广泛应用，需要设计具有高阶收敛性的算法， 因此对非光滑函数的二阶近似结构以及形态的研究显得尤为重要正因为如此，众多的 优化专家不断地研究这一课题试图攻克非光滑函数的二阶近似理论，主要以非光滑凸函 数为主攻方向其主要方法包括构造一个二阶导数来逼近凸函数的二阶近似，定义一种 集值映射的近似以代替次微分的近似，利用双方向定义二阶方向导数来用于逼近凸函数 的二阶近似，以及利用函数的上图得出上图二阶近似等这些研究工作为以后的非光滑 分析与优化无论是在理论研究还是在应用问题的探讨都打下了良好的基础 近五、六年在这一专题的研究中有两项重要成果： 其一为r o c k a f e l l a r ( 2 0 0 0 ) 关于非光滑凸函数的h e 8 s e 阵的研究； 另一为l e m a r 6 d l a l ，m i 毋i n ，s a g a s t i z 如“及o u s t r y 等人提出的关于凸函数次微分的 “让分解理论这一理论的提出为非光滑优化的研究提供了一种有效的工具 1 1 2 “y - 分解理论的理论背景 当函数，在不可微点牙处作二阶t a y l o r 展开时，主要困难是来自次微分( 梯度) 不 是一个向量而是一个集合，要得到函数的二阶展式需要处理两个集合的差商，如何能够 给出一个合理的表达是一个不容易解决的问题对于这一问题的处理，以前的结果给了 我们很多的启示 首先， j 一b h i r i a r t u r r u 毋和c l e m a 挺c 1 1 a 1 ( 1 9 9 3 ) 剐指出，7 ( z ；) 的线空间“满 足如下性质： ，7 ( 。；- ) 在甜上的限制是线性的且等于( 8 ，- ) ，其中s 是次微分a ，( z ) 中的 任意元素纠是使得函数九一，( o + 九) 在点h = 0 处是可微的，而a ，( z ) 在纠上的投 影是单点集( 即沿着“的方向，a ，( z ) 具有o _ 宽度) 由此可以得到下面事实： 第一，存在靴的一个子空间酣，使得，7 ( 圣；) 在纠上是线性的； 第二，定义，的二阶展开式无需沿着酣以外的方向 基于上面的思想， c l e m 盯6 c h a l ，f 0 u s t r y 和c s a g a s t i z 幻a l ( 2 0 0 0 ) 提出了“v 分 解理论 1 _ 1 _ 3 酣- l a g r a n g e 函数的来源 弘l a g r 龃g e 函数的思想来源于c l e m 盯6 c h a l 和c s a g a 8 t i z 曲a 1 对凸函数的一阶展开 中的余项问题以及凸函数与它的m o r e a u - 1 内s i d a 正则化的二阶性质之间的关系的研究 设妒是r ”上的有限值凸函数，妒的m o r e a u _ y b 8 i d a 正则化定义为 垂( 茁) ：= 黜 妒( 。) + 扣一z 仍 正则化函数的共轭函数为圣+ = 妒+ + 驯悒这里我们可以看到西+ 与具有相同 2 大连理工大学硕士研究生学位论文 的光滑性，可以通过研究垂的性质得到妒的二阶性质 整个空间妒可分解为两个直交的子空间：黔= o 丁，其中与丁互为极锥， 即任意s r “都可以表示为s = w + s 丁，其中s ：= p r o ( s ) ，s 丁：= p r o j 丁( s ) 给定 一点知及9 0 a 妒) 则我们可以利用这一分解= p ( ：。) ) 和丁= 码p ( 。) ( 踟) 设 g a 垆) ，令s 丁：= g 一跏丁，当t o ，1 】i9 0 + t s 丁a c p ( 劲) 则由 1 j 定理2 3 5 有 妒+ ( 跏+ t s 丁) = 一妒( 约) + ( 9 0 + t 8 7 | ，铂) = 一妒( 幻) + ( 卯，勾) + t ( s 丁，韧) = 【p + ( g o ) + t ( s 丁，劲) 由此可知矿在丁上是局部仿射的 定义函数： 西 ( s ) ：= 矿( 卯+ s ) + 引s r i | 2 = ( 9 0 + s ) + 驯g 一跏1 1 2 它的对偶函数为： 惦( 。) 2 舞磐 妒( g ) 一卯，可) + 划z | | 2 ) 把这里的丁记为v ，上式可以变形为 咖v ( z ) = 高 妒( 可) 一( m 9 ) + 扣一石怫 上式的最优点记为 p v ( 。) ：2 盯g 离 妒( 可) 一( 卯，掣) + 扣一。仍 由【7 】的命题4 1 有这样的性质 | 9 a p ( p v ( 。) ) 使得p v ) 一z = p r o j v ( 9 0 目) 并且 a v ( z ) = 一9 0 十 9 a 妒( p v ( z ) ) ：p v ( z ) 一z = p r o j v ( 9 0 一可) ) 如( ) 中去掉正则化项( 即二次项) 与原函数妒在v 上的二阶近似是一致的，这正是 酣一l a g r a n g e 函数的原型这些工作为甜v 一空间分解的研究提供了理论基础 1 2 “v 一分解理论的进一步研究 对于“让分解理论的进一步研究主要是两方面的工作： i ) f o u s t r y 等对最大特征值函数( m e f ) f 3 1 】【3 2 】的酣v 一分解及“一l a g r a n g e 函数的研究 吼它为半定规划的研究提供了一种有效的途径； i i ) r m 堋i n 和c s a g a s t i z 曲d 对一类特殊的函数一有限个光滑函数的最大值函数的“v 一 分解及“一l a g r a n g e 函数的研究嗍 3 一个新的纠一l a g r a n g e 函数 事实上，这两类函数都可归结为更广泛的一类具有特殊结构的函数，称之为具有原始 对偶梯度结构( p 电) 的函数【o ) 对于这样一种特殊的函数，可以在一系列限制条件下， 如： 让最优性( 协o p t i m a l i t y ) 条件，可行性( f e 嬲i b i l i 锣) 及横截性( t r a s v e r 8 d i t y ) 条 件等，得到弘h e s 8 e 阵存在的相对较弱的充分条件，得到“一l a g r a n g e 函数的最优点集 ( “) 和由其产生的切于“空间的轨迹孟+ u 0 ( 让) 进而，m 佃i n 和s a g a s t i z 如a l 定义了函数，在最小点孟处的一个快速轨道( f b t n a c k ) ( 由弘l a g r a n g e 函数的最优解集产生通向极小点的光滑轨迹) ，并讨论了这一轨道 所具有的性质，在此轨道上得出了函数的二阶展式对于具有原始对偶梯度结构的函数， 他们讨论了在快速轨道上的二阶展开式结构，进而为以后的超线性算法提供理论依据； 并指出当一点充分接近函数的最小值点时，函数对应的m o r e a u y o s i d a 正则化函数的最 优点就在这一快速轨道上王炜研究了“一l a g r a n g e 函数的最优解集w ( 札) 的性质【川】， 包括最优解集的特征和外半连续性，给出了弘l a g r 舡1 9 e 函数的共轭函数的代数性和径向 强凸性 以上讨论的函数都是凸函数，这也是“让分解理论考虑的前提若想将它应用到非 凸函数，则取决于空间甜，y 的确定对于非凸函数，次微分的概念已经不适用，必须寻找 新的理论基础f h c l a r k e 的o p t i l i z a t i o na n dn o n s m 0 0 t ha n a l y 8 i s ( 1 9 8 3 1 【儿】， n o 璐m o o t ha n a l y 8 i sa n dc o n t r o lt h e o r y ( 1 9 9 8 ) 【r t r o c k a f e u 缸的文章【”和 r t ，r d c k a f e l l a r 和r j 一b ，w j t s ( 1 9 9 8 ) 的、k i a t i o n a la n a l y s i s 【i 钏这些理论都为非 凸函数的研究提供了有效的工具利用近似次微分的概念，王炜定义了一类d c 函数 的“v 一空间分解，并给出了这一类函数的“一l a g r a n g e 函数的表达式，证明了相应的性 质她也利用函数的正则次微分和正则次导数的概念，给出了下半连续函数的甜v 一分解 及其“一l a g r a n g e 函数，并证明了相关的性质最后她也给出了h i l b e r t 空间上的凸泛函 的“v 一空间分解及其弘l a g r a n g e 函数的基本形式这些结果充分说明，我们可以利用 这一新的工具，将凸函数的“弘空间分解理论应用到更广泛的非光滑函数及其优化问题 中 拟可微函数类是有着应用背景的一类非光滑函数，其二阶近似以及相应的优化问题的 最优性条件是研究者关注的课题d e i n y n o v ，p o l 3 ，a l ，0 v a 趟和s h a p i r o 【删给出了拟可微 优化的必要性条件的几何形式x i a 【4 u 】，g a 0 【4 l 】分别对拟可微约束优化中具有l a 盯a n 印 乘子的最优性条件进行了讨论d c 函数是特殊的拟可微函数，王炜以甜v 一分解理论 作为工具对于一类特殊形式的d c 函数，讨论了它的最优性条件【 ，以及“v 一算法的 超线性收敛性【1 1 3 “协分解理论的应用 玎让分解理论具有十分重要的应用价值： ( i ) “v 一分解在非线性规划以及一类半无限规划中的应用； 4 大连理工大学硕士研究生学位论文 ( i i ) 应用“y 一分解理论设计了概念型的超线性收敛的最小化算法 非线性规划问题的精确罚函数可以利用罚函数方法将约束优化问题转化为最大值凸函数 的无约束优化问题，因此我们将甜弘分解理论应用到具体的非线性规划问题，得出它 的“一l a g r a n g e 函数有其具体的形式，进而研究其二阶展开对于有限个最大值函数的极 小化问题，m i m i n 给出了这一函数在最优点附近的“让空间分解和相应的光滑轨迹， 以及在这一轨迹上，在最优性条件的经典强二阶充分条件相对较弱的条件下同样可得到 弘l a g r a n g e 函数的二阶展开并对具有无限多个不等式约束的一类半无限规划问题，借 助于凸分析的知识，将其转化为最大值凸函数的无约束优化问题，“y 一分解为解决这类 半无限规划问题提供了一种处理方法在“让分解理论框架下，l e m 氆r 6 c h a l ，o u s t r y 和 s a g a s t i z 曲出设计出具有高阶收敛性算法 王炜将“v 一分解理论应用到非线性规划【醐；一类半无限极小化问题( j4 】；也用于 l o w e r - g 2 函数f 37 】 1 - 4 主要研究结果 本文的工作主要围绕下面问题展开的； ( i ) 定义凸函数的一个新弘l a g r a n g e 函数 在“p 空间分解以及“一l a g r g e 函数的基本理论下，本文重新定义一种新的“一 l a g r 8 n g e 函数，讨论了这一函数所具有的性质 ( i i ) 纠一l a g r 蛐g e 函数与m o r e a u y o s i d a 正则化函数的关系 由酣谚空间分解设计的算法具超线性收敛性考虑到，与正则化函数的关系，可以 用以设计算法 5 大连理工大学硕士研究生学位论文 2 豺弘分解理论的基本思想和甜一l a g r a i l g e 函数 这里讨论的是n 维偶氏空间咿上的函数，r “中的内积记为( ，) ，由内积导出的 范数记为”卧对于渺中的宇空间s ，诱导出的5 上的内积和范数分别记为( ，) s 和 恬设z r “，6 o ，则以z 为中心，以6 为半径的开球记为b ( z ，d ) ，而在子空间s 中对应的开球记为b s ( z ，6 ) 记z s 为向量z 在子空间s 上的投影 2 1 预备知识 这里介绍本文所要用到的一些重要的基本概念： 次微分：向量勘黔称为凸函数，在点z d o m ，的一个次梯度( s u b g r a d i e n t ) ，如 果满足 ，( 2 ) ，扛) + ( ”，z 一。) ， v 2 所有这样的点所作成的集合称为，在点。d o m ，的次微分，记为a ，( z ) 方向导数：称函数，在点z 处关于变量有单边方向导数，如果极限 胞沪珊堑学， 存在( + 。，一o 。都可以看成是极限存在的情况) 共轭函数：一个闭凸函数，( 即下半连续函数) 的共轭函数是 ，4 ( g ) ：= s u p ( g ，z ) 一，( z ) ) 相对内部：武”中的凸集合c 的相对内部为 r i g = 。a 矗gj j o ，( z + e b ) n ( a 缸a ) ce ) 法锥：一个向量z + 称为凸集c 在点n 处的法向量，如果满足( 矿，z 一口) s0 ，对于任 意的z c c 在点。处所有的法向量的全体所作成的集合称为c 在n 处的法锥 2 2 “协空间分解 设，是定义在r ”上的有限值凸函数，在点。腿“的次微分集合为a ，( z ) 给定 点圣黔使得i n t a ，( 孟) = 0 但是r i a ，( 孟) 口，且豆a ，( 孟) 下面的假设是本文我们要 考虑问题的前提： 7 一个新的“一l a g r a n g e 函数 假设2 1 设，是有限值凸函数，牙是一固定点，口a ，( 孟) 将空间r ”在点牙处的作空间分解舻= 甜o y ，其中互为正交的两个子空间“，v 可 以通过以下三种方式来定义 定义2 2 ( i ) 设阮是使得方向导数，( 量；- ) 为线性函数的子空间，v l ：= 埘因为，( 牙；) 是次线 性的，所以，有 碥：= “f 矿：，7 ( 孟；u ) = 一，( 牙；一札) ) ； ( i i ) 设k 是平行于a ，( 牙) 所生成的仿射包的子空间，：= 1 坩，即屹：= 1 i n ( a ， ) 一雪) ， 其中，雪a ，忙) 是任意的； ( i i i ) 设和k 分别是a ，( 雪) 在点g 。r i a ，( 牙) 的法锥和切锥，其中口。是任意的，此 时，阮和弘必为子空间 口 注：u n m 表示由m 生成的线性空间 由相对内部的定义有 9 。r i a ，( 牙) = 争j 卵 o 有9 。+ ( b ( o ，叩) n 屹) ca ，( 至) 成立( 2 2 1 ) 上面不同方式定义的空间分解，其结果是等价的 命题2 3 【4 】定义2 2 中 ( i ) 当g 。r i a ，( 圣) 时， o f 3 = d r ”：g 一9 。，d ) = o ，v 9 a ，( 蜃) ) = 甜渖) ( 9 。)( 2 22 ) 且与g 。的选取无关； ( i i ) = = 阮= ：甜； ( i i i ) 一般地，对互8 ， ) 有酣ca 岛脂) ( ) 证明( i ) 为证明( 2 2 2 ) ，取扩r i a ， ) ，设：= 爵( z ) ( 9 。) 由法锥的定义，显 然成立，我们只需证明反方向包含关系成立即可设d ，9 a ，憧) ，只需0 9 。，d ) o 事实上( 假设9 一扩o ) ， ：= 一；三薪屹，由( 2 2 1 ) 及d 有 。( 9 。+ 7 7 u g 。，d ) = 一丌石_ 二；j i ( g 一夕。，d ) ，叩 。 即有( 9 一g 。，d ) 0 下证( 2 2 2 ) 式与扩的选取无关，对 。r 谄，( 王) ，r g 。则 8 大连理工大学硕士研究生学位论文 f i i ) 由 1 9 ，( i ) ( 7 。) = d r ”：( 9 ，d ) = ( 7 。，d ) = ( 9 。，d ) ，v 9 a ，( 童) ) = m 2 4 矶，黼) ( g ，d ) _ ，现) ( 9 ，d ) ) ( 2 驯 9 a ，( ) g a ，( i ) 。、7 由( i ) 则有= 阮，只须证c c 设d ，对铷= ( 毋一口) 让，缈a ，( 孟) ，从( ? ? ) 中可知 j ( ，d ) = ( ( 毋，d ) 一( 雪，d ) ) = o ； j 因此，d 设d = 蠼，由协的定义知佃一互，d ) = o ，坳a ，( 巩的a ，( 岳) 则d 阮 ( i i i ) 设d “= ，对口a ，( 牙) ，有( 扩，d ) = 9 ，d ) = ( 雪，d ) ，对均a ，( 牙) 成立， 因此，d ，憧) ( 雪) 口 设v ，矿分别是空间u 纠的基矩阵则对于任意z 豫n 都可以有如下分解： 肽”弓z = 驴( 矽上。) + 矿( 【扩上伊 一1 矿上z ) = 驴观f + 矿。v = z “ o z vg d i w r d i m v 换句话说，o 表示了从“v 到黔上的线性映射，即 “v 弓c u ，钞，一钆。”：= ( ：) 琏“ 其中“和v 是向量空间鼢的内积可写为如下形式： ( 口，。) = 锄。加，锄o z v ) = ，) “+ ( 跏，z v ) v 标记2 4 考虑如下定义的三个凸函数 l ， 2 ， “弓u 一丘1 ( ) ：= ， + u o ) ，对于任意的口v v 弓 一危2 ( ) ：= ，归+ u o 口) ，对于任意的仳酎 甜v 弓( 札，口) h 危( u ， ) ：= j f ( 孟+ 钍o u ) 它f f 丁的次微分有这样的表达式 a 1 ( 札) = 嘶：目a ，( 牙+ 钍o u ) ) ， a 危2 ( u ) = 卯：9 a ，( 孟+ 孔。口) ， a ( 乱，u ) = 鲫0 9 v ：9 a ，( 蜃+ u o ) ) 9 一个新的甜一l a g r a n g e 函数 2 3 甜一l a g r a n g e 函数 2 3 1凸函数的“一l a g r a i l g e 函数的定义 给定次梯度互a ，( 牙) ，其v 一分量为如，则，相对于如的岛函数定义为 “弓一五口( ) ：= i 鲢 ，忙+ uo ”) 一( 口v ，口) v )( 2 3 1 ) 口ty 伴随v 一空间的最优点集为 w ( u ) ：= a r g 鼍船 ，( 牙+ 札。”) 一( 互v ， ) v ) ( 2 3 2 ) 见i4 1 注：由( 2 3 1 ) 所定义的函数岛被称为甜一l a g r a n g e 函数“一l a g r a n g e 函数及其最优解 集均依赖于如，我们可以采用完整的记号切( 札；v ) 和啦，( 札；口v ) 引理2 5 设口r i a ，( 孟) ，则存在充分小的叩 o ，使得对任意的0 v 有 川。蒜叫( 童) 特别地，对任意的( 让， ) “ v ，有 ， + u o u ) ，( 至) + ( 盈z ， ) “+ ( 灸b ”) v + q 【i 口i l v ( 2 3 3 ) 证明 假设口r 谄，( 孟) ，由相对内部的定义，存在叩 o ，使得 + ( 即川n ) c a m ) 即得雪+ o 。涨州站 此外，由次微分的定义，对任意的( u ，”) “o k 有 ， + u o u ) ，渖) + 妇o ( 如+ 福静) ，“o u ) = ，( i ) + ( h ，u ) “+ 如，u ) v + ”i 1 勘i l v 2 3 2 甜一l a g r a n g e 函数的性质 定理2 6 假设2 1 成立厶有如下的性质； ( i ) 岛是处处有限的凸函数 ( i i ) ( 2 3 2 ) 中的点t 7 w ( 乱) 当且仅当存在g a ，渖+ 札o ) 使得卯= 口v ( i i i ) 特别地，o w ( o ) ，岛( o ) = ，( 雪) ( i v ) 当口r i a ，( 孟) 时，对任意的乱“有w ( “) 0 ，且w ( o ) = o ) 1 0 大连理工大学硕士研究生学位论文 定理2 7 1 4 】假设2 1 成立 ( i ) 设u 使得w ( 乱) o ，则岛在札的次微分可表示为 口 a l 蜃( 乱) = ( 9 “：9 甜。雪v a ，( 互+ o 鲫) ) ( 2 3 4 ) 其中w w ( “) 0 是任意的 ( i i ) 特别地，岛在。点处可微，并且v 岛( o ) = 姒，即所有g a ，( 牙) 有相同的“一分 量 口 v 耍疗如( ”卜麓鏊 _ - _ _ 、 眵 、 、 、 磁i ) 、 、 、 、 n 图1 岛( u ) 的次微分 注：( 2 34 ) 也可表示为a 岛( “) = a ，( 牙+ “ow ( u ) ) n 佰+ “) k 当如= o 时，有a 岛( u ) = a ，( 牙+ 乱o w ( 让) ) n 纠( 2 3 5 ) 从图1 中很明显可以看出： 岛的次微分不依靠于”( u ) 推论2 8 f 4 】假设21 成立如果雪r 徊，( 孟) ，则有 v e o ，3 艿 o ：i l 札l bs6 ：争i l 叫l i v 墨l i u i k ，v 叫仉7 ( 乱) 。( 2 3 6 ) 即；w ( u ) = o ( 恻l “) 证明 由定理2 7 中的( i i ) ，岛在0 点的一阶展开式 l 口( u ) = 岛( o ) + ( v l 口( o ) ，u k + d ( 1 i 乱l k ) = ，( 岳) + ( 勃，u ) 甜+ d ( 1 l u ij “) ， 1 1 一个新的“一l a g r a n g e 函数 对v 山w ( u ) ：我们有岛( 乱) 一，( 孟+ u o 训) 一( 如，u 7 ) v 在( 2 3 3 ) 中取u = 叫，可得 工口( u ) 三，( 牙) + ( “，虬) “+ q | 1 训1 f v 因此，有 因而结论成立 o ( | u | | “) = l 互( 乱) 一，( 牙) 一( 互“，乱) “2 圳l 叫j i v 口 2 3 3 “一l a g r a n g e 函数的高阶性质 定义2 9 4 j 称，在点牙有一个径向l i p s 出t z 次微分，如果存在d 0 及6 0 ，满足 a ，( 牙+ d ) ca ，睁) + b ( o ，d l 蚓1 ) ，v d b ( o ，6 )( 2 3 7 ) 或等价地，存在e 0 及 o ，满足 1 ，+ d ) s ， ) + ，( 牙；d ) + 妄a i d l l 2 ，寸h b ( o ，e ) ( 2 3 8 ) 下面的定理表述了a 岛在u = 0 附近的性质 命题2 1 0i 4 j 假设2 ，1 成立，且对充分小的“有w m ) 0 且( 2 ，3 7 ) i ( 2 3 8 ) 成立，则 有 ( i ) 存在6 o ，使得对所有玩，( o ，6 ) ，有 a 岛( 钍) c 目 + b “( o ，2 g l | u | | “) ( 即 鲫：姒。互v a ，( 牙+ 札。叫) ) c 勃+ 助( o 2c f i i “l l “) 这里叫( “) 是任意的) ； ( i i ) 存在p o 及d o ，使得对所有的“玩，( o ，p ) 、有 三( 乱) i ( o ) + “，铭) “+ 去d l l u i 甚 f 即 1 ，忙+ o 训) ， ) + 佰，札。叫) + ；d l l 训旧) 口 关于非光滑凸函数，c l a r k e ( 1 9 7 7 ) 和r d c k a f e l l a r ( 1 9 7 6 ) 都给出过广义h e s s e 阵的定 义我们借助于这一概念，可以得到，在某局部上的二阶展开式 称凸函数妒在点。o 具有广义h e s s e 阵日妒( z o ) ( 【4 】) ，如果 梯度v 妒( z o ) 存在； 1 2 大连理工大学硕士研究生学位论文 存在对称半正定算子日妒( z o ) 满足： 妒( 黝+ d ) = 妒( 跏) + ( v 妒( ) ，d ) + ；( 日妒( 跏) d ，d ) + 。( | | d | | 2 ) 1 0 】中一个重要的结论是上式可等价于， a 妒( z o + d ) cv 妒( 。o ) + 日妒( z o ) d + b ( o ，d ( i i d i ) ) 这里b 是单位球- 注意到当a 妒在的邻域内是单值函数，则广义h e s s e 阵疗妒( 。o ) 就是经典的h e s s e 阵v 2 妒( ) 定义2 1 l 【4 】设，是碾”上的有限值凸函数，如果岛在点：0 有一个广义h e s s e 阵 日岛( o ) ，则称，在点圣有一个“一h e s 8 e 阵，记为 既f ，( 牙) ：= 日岛( o ) 口 定理2 - 1 2 设雪r i a ，( 牙) ，且纠一h e s s e 阵玩，( 岳) 存在，对甜及 u 。( “) ， 有如下二阶展开式： 珩+ ) = 雕) + ( 互， ) + ；( 勘m ) 札，u ) “+ 。( 。) ( 2 3 9 ) 证明因为雪r i a ，( 孟) ，及定理2 ，6 中的( i v ) 知w ( u ) 0 由岛的定义，对其作展开 可得，对所有的u “和训( u ) ： 岛( u ) = ， + 乱 鲫) 一( 口v ，甜) v = l ( o ) + ( v l 口( o ) ，u ) “+ j ( f 玩，( 孟) u ，札) “+ o ( 1 i u i l 刍) 一，忙) + ( 协，u ) “+ ；( 觇，渖) 让，乱k + o ( i l i b ) ， 由( 2 3 6 ) 知d 川圳磊) = 。( ，上式两端同加( 如，叫) v ，得证 2 4 甜让分解理论在数学规划中的应用 2 4 1 具有有限个不等式约束的非线性规划问题 考虑下面的非线性规划问题： 其中妒， g 2 是凸函数 丑1 1 n s t 1 3 口 ( 2 4 1 ) 一个新的甜一l a g r a n g e 函数 2 4 2对应于精确罚函数的甜协空间分解 假设孟是问题( 4 1 1 ) 的一个极小点，则k k t 条件成立：对于l a g r a n g e 函数 l 扛，) 、) ：= 缈扛) + a 。五( z ) ， 扛，) 、) r “r ”， # = l 存在l a g r a 丑g e 乘子九使得 f v 。l 忙，天) ： v 妒忙) + 壹元v ( 牙) ：o i 五o ，元五( 圣) = o ， i = 1 ，一，m 考虑( 4 1 1 ) 的精确罚函数 ，( z ) ：= 中( z ) + 田妒( z )( 2 4 2 ) 其中妒( z ) ：= m a