（运筹学与控制论专业论文）uv分解在半光滑中的应用.pdf

大连理工大学硕士学位论文 摘要 2 0 0 0 年左右，l e m a r 4 c h a l ，o u s t r y 和s a g a s t i z d b a l 等人提出“v 一分解理论，给出了 研究非光滑凸函数的二阶性质的新方法“v 一分解理论的基本思想是将空间分解为两 个正交的子空间的直和，即r ”= 肼ov 的直和，使原函数在“空间上的一阶逼近是线 性的，而其不光滑性质集中于v 空间中，借助于一个中间函数一一“一l a g r a n g e 函数， 得到原函数在切于甜空间的某个光滑轨道上的二阶展式这对于我们在非光滑优化的研 究，特别是函数的二阶最优性条件的研究，以及对设计具有高阶收敛性的算法是一个很 重要的工具 对于“y 一分解理论能否推广到非凸函数，并以此工具研究非凸的非光滑函数的二阶 性质，是一项很重要的研究工作本文就是将“弘分解理论应用半光滑优化问题 本文的基本内容如下： 1 第1 章，阐述了“让分解理论的研究背景，翻一l a g r a n g e 函数的来源以及半光滑的相 关知识 2 第2 章，主要介绍了l e m a r c h a l ，o u s t r y 和s a g a s t i z d b a l ( 2 0 0 0 ) 1 1 2 】的“v 一分解理论和 凸函数的有限约束非线性规划 3 第3 章，首先对半光滑函数进行了“让分解，得出了u - l a g r a n g i a n 和最优解集w ( u ) 的相关性质，以及二阶近似展开之后，在非线性规划研究中，我们对具有半光滑性 质的最大值函数，d s 规划在v 一分解中进行了探讨，对它们的上“，二阶展开和 高阶收敛性质进行了研究 关键词：“y 一分解；半光滑函数；非线性规划； d s 规划；= 阶展开 甜1 l 分解在半光滑中的应用 t h ea p p l i c a t i o no f 甜vd e c o m p o s i t i o ni ns e m i s m o o t h n e s s a b s t r a c t l e m a x d c h a l m j 锄n s a g a s t i z d b a la n do u s t r y n ( 2 0 0 0 ) i n t r o d u c e dt h ed v - t h e o r y , w h i c h o p e n saw a yt od e f i n i n gas 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 rd e r i v a t i v eo fac o n v e xf m l c t i o n ，a tan o n d i f f e r e n t i a b l ep o i n t 牙t h eb a s i ci d e ai st od e c o m p o s e 毋i n t ot w oo r t h o g o n a ls u b s p a c e s “a n dvd e p e n d i n go n _ 萤8 0t h a tf sn o n s m o o t h n e s sn e s rt h ep o i n ti s c o n c e n t r a t e de s s e n t i a l l yi nv ac e r t a i nl a g r a n g i a na s s o c i a t e dw i t ht h ec o n v e xf u n c t i o n w a si n t r o d u c e d 、c a l l e d “一l a g r a n g i a n ，w h e n 歹s a t i s f i e sc e r t a i ns t r u c t u r mp r o p e r t i e s ，i t i sp o s s i b l et of i n ds m o o t ht r a j e c t o r i e s ，v i at h ei n t e r m e d i a t ef u n c t i o n ，y i e l d i n gas e c o n d o r d e re x p a n s i o nf o rf i ti sa ni m p o r t a n tt o o tt or e s e a r c ha b o u tn o n s m o o t ho p t i m i z a t i o n ， e s p e c i a l l ya b o u tt h ef u n c t i o n ss e c o n d o r d e ro p t i m a l i t yc o n d i t i o n s ，a n dd e s i g na l g o r i t h m s ( b ym e a n so fl o c a lq u a d r a t i ca p p r o x i m a t i o n s ) t h ee x t e n s i o no ft h e “v d e c o m p o s i t i o nt h e o r yt on o n c o n v e xf u n c t i o n a sw e l l8 5 t h es t u d yo nt h es e c o n d o r d e rp r o p e r t i e so fn o n s m o o t hf u n c t i o n s ，a r eu n q u e s t i o n a b l y i m p o r t a n t t h ef o c u so ft h i st h e s i si so i lt h ea p p l i c a t i o no ft h e 扪p d e c o m p o s i t i o nt h e o r y t os e m i s m o o t ho p t i m i z a t i o np r o b l e m s i nt h i sp a p e r w ef o e n so nt h es t u d yo f “y t h e o r ya n di t sa p p l i c a t i o n w eb r i e f l y s t a t ei t sc o n t e n t sa sf o l l o w s 1 i nc h a p t e r1 w er e c a l lt h eh i s t o r i c a lb a c k g r o u n da b o u tt h e 甜vd e c o m p o s i t i o nt h e o r y 、 t h eo r i g i no fl 6 l a g r a n g i a na n dt h er e l a t i v ek n o w l e d g ea b o u ts e m i s m o o t h n e s s 2 i nc h a p t e r2 w em a i n l yr e v i e wt h e “vd e c o m p o s i t i o nt h e o r yb ym i f i l i n s a g a s t i z d b a l a n do u s t r v ( 1 烈、a n dt h ec o n v e xf u n c t i o n sn l pw i t hf i n i t ec o n s t r a i n t s 3 i nc h a p t e r3 w ea p p l y “肛t h e o r yt os e m i s m o o t h n e s s ，o b t a i nt h ep r o p e r t i e so f “ l a g r a n g i a n ，t h es e to fm i n i m i z e r sa n dt h es e c o n d - o r d e re x p a n s i o ni n , 一s p a c et h e n ， i nn l ps e t t i n g ，w ed i s c u s st h em a x i m u mf i m c t i o na n dd s p r o g r a m m i n gw i t hs e m i s - m o o t hp r o p e r t i e s ，b a s e do nt h e d yd e c o m p o s i t i o nt h e o r y , a n ds t u d y t h e k , - l a g r a n g i a n s s e c o n d o r d e re x p a n s i o n s w ep r o p o s eas p a c e - d e c o m p o s i t i o na l g o r i t h m ，n a m e l y “让 d e c o m p o s i t i o na l g o r i t h m ，a n dd e m o n s t r a t ei t ss u p e r l i n e a rc o n v e r g e n c ei sd e m o n s t r a t e d k e yw o r d s ：“v d e c o m p o s i t i o n ；s e m i s m o o t hf u n c t i o n ；n l p ；d s p r o g r a m m i n g ； s e c o n d o r d e re x p a n s i o n l l 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或其他单位的学位或证书所使用过的材料与我一同工作的同志对本研究所 做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：煎查 日期： o 毛6 心 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 作者签名：直蕉 导师签名 兰! 型年笪月j 互日 大连理工大学硕士学位论文 1 引言 1 1 甜v 一分解理论的研究背景 在当今的科学技术发展和应用中，我们会经常碰见非光滑现象然而传统光滑假设 下所进行的大量的最优化和分析不能直接应用于非光滑的情况中，这就需要建立新的理 论体系( 非光滑分析) 来很好地处理这类问题八十年代c l a r k e ( 1 9 8 3 ) 2 】关于l i p s c h i t z 函数的微分学的研究成果使得非光滑微分学取得了突破性的进展，以l i p s c h i t z 函数为主 的非光滑分析与优化已形成独立的研究领域到目前为止，非光滑分析已经在很多方面 取得出许多重要的结果但是目前，对于非光滑函数的研究主要存在以下两个问题： 一般说来，次微分( 或c l a r k e 意义下的广义梯度) 较大且难以确定，其运算多以包含 形式来刻划，换言之，广义方向导数较大，即 ，o ( 。：；d ) ，7 ( z ；d ) 对于一阶近似的余项结构或性态不能清楚地表达出来； 另一个问题是关于函数的二阶近似，即二阶展开，它关系到算法的二阶收敛问题并涉 及到集值映射的微分学或近似这一问题成为自八十年代以来非光滑分析与最优化 研究中的一个核心课题本文正是针对这一问题进行的研究 非光滑函数的二阶性质与展开，自上一世纪三十年代以来，一直是学者们关注的课题 之一，它是与实际应用有密切相关的算法研究的基础，如数值代数、优化、控制及对策等尤 其是在计算机技术的迅速发展和应用中，很多了领域的研究为了满足实际计算的需要，非 光滑优化中具有高阶收敛性算法的研究成为主要的研究课题之一近二十年来众多的优 化专家不断地研究这一专题试图攻克非光滑函数的二阶近似的理论，以非光滑凸函数为 主攻方向近四、五年在这一专题的研究中有两项重要的结果，其一为( r o c k f e l a r ( 2 0 0 1 ) ) 关于非光滑凸函数的h e s s e 阵的结果，另一为关于凸函数次微分的v 酣分解理论的提出 目前，甜v 分解理论是一种新的研究非光滑凸函数二阶近似结构的方法，已解决几 类有价值的问题如特征值的计算问题，构造了一般的极大值函数类的二阶近似及优化算 法，等等但这一新的理论还仍然处于一个基本理论的框架，除理论上的研究仍要继续进 行外，更主要的耍研究新的能进行“1 ，分解的非光滑函数( 如凸函数类或半光滑函数类) 我们的工作是基于l e m a r c h a l ，m i f f l i n ，o u s t r y , s a g a s t i z d b a l 等人提出的关于凸函数次 微分的“弘分解理论，它的理论背景基于如下的问题：当我们将凸函数，在其不可微点 i 作二阶t a y l o r 展开时，主要困难是来自微分( 梯度) 已不再是个向量而是一个集合， 因此必须处理两个集合的差商，如何给出一个合理的表达是一个不易解决的问题在此 之前的许多结果 8 - i o i 都还只是抽象性的尝试，而没有形成较为有效的理论体系，但是这 些研究工作可以给我们带来许多启示 j 一b h i r i a r t u r r u t y 和c l e m a r d c h a l ( 1 9 9 3 ) 1 3 】指出，( z ；) 的线性空间甜满足如 下性质t ，( z ；。) 在吖上的限制是线性的且等于( s ，- ) ，其中8 是次微分o f ( x ) 中的任意 l v 一分解在半光滑中的应用 元素换句话说，甜是这样的元素h 的集合，使得函数h ，f ( x + h ) 在点h = 0 是可 微的，而a ，( z ) 在“上的投影是单点集( 即沿着“的方向，a f ( x ) 具有0 一宽度) 由此 可以得到如下两个事实： 第一，存在册的一个子空间“，使得，( 孟：) 在“上是线性的； 第二，定义，的二阶展开式无需沿着“以外的方向 在此基础上，c l e m a r d c h a l ，f o u s t r y 和c s a g a s t i z 曲出( 2 0 0 0 ) 提出4 v 分解理论 【1 2 】，其主要思想是将空间尼。分解成两个正交的子空间“和y 的直和，使函数在甜上 的一阶逼近是线性的，而其不光滑特征集中于v 中，借助于一个中间函数，1 4 一l a g r a n g e 函数，来得到函数在切于甜的某个光滑轨道上的二阶展式这样，设计非光滑最优化的 算法可以在此光滑轨道上考虑 事实上，l ，- l a g r a n g e 函数的思想来源于c ，s a g a s t i z i b a l 和c l e m a r g d l a l 的f 9 f 1 0 对于凸函数的一阶展开式中的余项问题以及凸函数与它的m o r e a u - y o s i d a 正则化的二阶 性质之间的关系的研究为了清楚起见，我们简要陈述如下：设妒是r n 上的有限值凸 函数，妒的m o r e a u y o s i d a 正则化定义为 垂( z ) ：= 船 妒( g ) + ；l l y - x 怫 它们的共轭函数之间满足关系式壬= 矿+ 划悒因此圣+ 与矿的光滑性是一致的，可 以通过探讨圣的性质褥到垆的二阶性质鉴于垂+ 的l i p s c h i t z 可微性、扩的h e s s e 阵 与矿的广义h e s s e 阵的关系以及“，y 空间的思想，给出如下起着重要作用的函数： 庐v = ，r a 。i + n ， 妒( ) 一( g ，) + ；i l z 一可1 1 2 ) 其中，g r 国妒( z ) ，v 一7 瓦扛) ( 9 ) 如果妒是有限值强凸函数，且在点 p 。= p ( z 。) = a r g ，m 。i n 。 妒( ) + ：- i l y - x o i l 2 ) 满足增长性条件：对任意的e 0 ，存在c 0 妒( p 。+ ) 妒。) + 妒0 ，。；h ) + i c l l h l l 2 ，讹b ( o ，) 则v 2 圣( 。o ) 存在当且仅当广义h e s s e 阵h c v ( p 。) 存在而西v 中去掉正则化项( g g - - 次 项) 与在y 上：= 甜上的二阶近似是一致的，这正是“一l a g r a n g e 函数的原型这些研究 工作为甜y 一空间分解提供了理论基础，而由此得到的v 和“= n o ，( 9 ) 揭示了r “和沿 v 空间和“空间分解的重要意义 迄今为止， “v 一分解理论考虑的函数都是凸函数，能否应用于非凸函数，取决于 空间酣，y 的确定对于某些非凸函数，次微分的概念已不再适用，需要寻求新的途径 f h c l a r k e 等的专著o p t i m i z a t i o na n dn o n s m o o t ha n a l y s i s ( 1 9 8 3 ) ， 2 大连理工大学硕士学位论文 n o n s m o o t ha n a l y s 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 l l a r 的文章 2 3 1 ， 以及r t r o c k a f e l l a r 和r j 一bw e t s 的专著y o r i 抚。竹口2 a 忱n 妇s 拈( 1 9 9 8 ) 为非凸函 数的研究提供了有效的工具，尤其是上图导数( e p i 一导数) 和近似次微分、( 广义) 次微分 的概念r m 矾n 和c s a g a s t i z d b a l ( 2 0 0 3 ) 2 4 1 研究了最大值函数的一阶、二阶上图导数 的特征，得出在“v 一分解理论下，当“一l a g t a n g e 函数的广义h e s s e 阵存在时，在“ 上的二阶e p i - 导数是有限的方向的集合但是，其工作仍是针对凸函数而进行本文正 是对非凸函数( 半光滑函数) 的甜v 一分解的一种尝试 1 2 半光滑的相关知识 半光滑函数的概念是1 9 7 7 年r o b e r tm i f f l i n 1 1 提出来的，定义如下 定义1 0 2 【1 7 】f ：舻一r 1 在ze r “是半光滑的若： ( i ) f 在z 的邻域内是l i p s c h i t z 的； ( i i ) 对每个d r “，任意 t k c r + ， 民) c 舻1 玑) c 舻且g k o f ( x + t k d + 钆) 使得 存在 m 埘埘l 。( d ) 半光滑函数是范围非常广泛的一类函数凸函数，分段光滑函数，次光滑函数等都属于 半光滑函数半光滑函数的线性组合、半光滑函数的复合函数仍然是半光滑函数；若向 量函数的每个分量都是半光滑函数，此向量函数是半光滑函数关于半光滑函数的性质 和应用，请参考f 2 2 2 7 【29 我们在研究非光滑函数，尤其是研究带约束问题的时候，就不能不用到方程组来研 究非光滑函数的性质( 最优点) 例如下面约束问题： ，m ( 1 2 ，2 ) r 其中，j g i ( i = 1 ：一，m ) ，砖0 = 1 ，r ) 均是r “上的二次连续可微实值函数 我们设( 1 2 1 ) 在局部最优点处满足某种约束规范( 如m a n g a s a r i a n p r o m o v i t z 约束 规范) 转化为k k t 形式： 设存在a r m 和p r 使得z = ( x ，a ，肛) t r 卅”柑满足下面k k t 系统： fv 。l p ) 垒v ，印) 一v 9 印) a v h ( x ) u = 0 ， 入0 ，9 ( 5 ) 0 ，入t g ( x ) = 0 ，( 1 2 3 ) 【 ( z ) ：0 3 = | | ，z， 仉o = 荆荆 l，、l 胁 砒 吖让分解在半光滑中的应用 其中9 ( z ) = ( g l ( 卫) ，9 2 ( z ) ，目h ( z ) ) t ，h ( x ) = ( h i ( z ) ， 2 ( z ) ，：h 。( 。) ) t k k t 系统有两种方法转化为非光滑方程组利用r a i n 函数和f i s c h e r b u r m e r i s t e r 函数是最受欢迎的两种方式显然，k k t 系统等价于下面方程组： 卜洳 _ o ( 口，b ) = v 伍+ b 2 一( n + 6 ) ( 12 4 ) ( 1 25 ) 其中毋满足 咖( n ，b ) 一0 车= = a 0 ，b 20 ，a b ：0 ，f 1 2 。6 ) 利用定义1 0 1 ，可以把k k t 可以转化为以下等价方程组； 坼，垒 翰) = 。 i ( z ) = l ( x ，a ，p ) = v f ( x ) 一v 9 ( z ) a v h ( z ) u ， 垂( z ，a ) = ( 曲1 ( 。，a ) ，一- ，咖m ( z ，a ) ) t 用上面两种方法转化为方程组后，其中大部份是对半光滑方程组的研究 在近2 0 年研究中，对半光滑函数的研究发展为求解半光滑方程组及其收敛性理论 的研究， 1 8 2 0 2 8 3 0 3 4 在q i s u n 1 8 】，q i 2 0 】中，考虑一般的非光滑的方程组； f ( z ) = 0( 1 2 7 ) 其中，f ：毋一册是半光滑函数 q i - s u n 1 ，q i 【2 0 j 提出了利用c l a r k e 广义导数代替 光滑情形的f r d c h e t 导数的牛顿法且提出了许多半光滑的性质、定理其中最重要的是 引理2 2 【1 8 】，我们将它记为： 引理1 0 3 【1 目设局部l i p s c h i t z 函数，：j p r 在x 的邻域内是方向可微的，那么 ( i ) ，( z ；) 是l i p s c h i t z 的 ( i i ) 对任意d ，存在g a ，( z ) ，使得，7 ( z ；d ) = ( g ，d ) 4 大连理工大学硕士学位论文 1 3 本论文的主要工作 在第2 章中主要介绍了l e m a r c h a l ，o u s t r y 和s a g a s t i z 曲a l ( 2 0 0 0 ) 【1 2 | 的“让分解理论 和凸函数的有限约束非线性规划并对凸函数的有限约束非线性规划的“一l a , g r a n g i a n 构造和最优解进行了分析 在第3 章中，首先对半光滑函数进行了“y 一分解，得出了“一l a g r a n g i a n 和最优解集 w ( u ) 的相关性质，以及二阶近似展开之后在非线性规划研究中，我们对具有半光 滑性质的最大值函数，d s 规划在“v 一分解中进行了探讨，对它们的“一l a g r a n g i a n ， 二阶展开和高阶收敛性质进行了研究最后将前面得出的半光滑“弘分解理论应用 到半光滑方程中求解，构造了一个概念性算法，并得出了一些性质定理 5 大连理工大学硕士学位论文 2 纠协分解理论及其在非线性规划中的应用 本章中我们讨论凡维欧氏空间r “上的函数，r ”中的内积记为( - ，) ，由内积导出 的范数为”忆对于r “中的子空间s ，诱导出的s 上的内积和范数分别记为( ，) s 和 恬设x 形，6 0 ，记册中以z 为中心，6 为半径的开球为b ( z ，6 ) ，而在子空间 s 中对应的开球为b s ( x ，6 ) 向量z 在子空间s 上的投影记为。s 2 1 凸函数的甜让分解理论 假设：设，是有限凸函数，在岳处不可微 令a ，( 牙) ，g 。r i a ，( 孟) 2 1 - 1 “弘空间分解 设，是定义在r ”上的有限值凸函数，在点x r “的次微分集合记为a 厂( z ) 给 定点孟r “，使得i n t o f ( n 2 ) = o ，但是r i o f ( 至) 0 ，且g o f 忙) 定义空间r ”在点孟 处的“p 分解为r “= “o v 其中，正交子空间“，y 可以通过三种方式来定义 定义2 1 1 【1 a ( i ) 设矾是使得方向导数，( 孟；) 为线性函数的子空间，：= o 硭因为，( 牙；) 是次线 性的，所以，有矾：= 弘r “：f 7 ( 孟；d ) = 一，7 ( 童；一d ) ) ； ( i i ) 设k 是平行于a ，忙) 所生成的仿射包的子空间，：= 世即，协：= l i n ( o f ( 牙) 一互) ， 其中，可a ，( 牙) 是任意的； ( i i i ) 设和协分别是a ，( 蜃) 在点g o r i o f ( 茔) 的法锥和切锥，其中g o 是任意的此 时，和k 必为子空间，见f 9 1 注：l i n m 表示由m 生成的线性空间 上面不同方式定义的空间分解，其结果是等价的 命题2 1 2 1 1 2 】由定义2 1 有， ( i ) 当g 。r i o f ( y ) 时，阮= d r “：扫一g 。，d ) = o ，v g o f ( e ) ) = m ) ( g 。) ，且与 9 。的选取无关； ( i i ) m = 比= 编= ：“ ( i i i ) 一般地，对雪a ，( 牙) ，有纠c 0 舳) ( 雪) 对比r “，有。= ( ，。v ) 上设。表示由“v 到r “线性映射记作： “”) v - - - + u o v = ( ：) 卯 7 “y 一分解在半光滑中的应用 其中甜，v 分别看作由札，v 组成的向量空间 按照r “中的数量积，有( g ，x ) = ( 鲫0 9 v ，x u o 。y ) = ( 9 u ，x u ) “- 4 - ( g v ，z v ) v 注：考虑如下定义的三个凸函数分别为 甜弓u hh i ( u ) ：= ，( 叠+ o u ) ，v v y v 弓 hh 2 ( v ) ：= ，渖+ uo ) ，v u “ “xv 弓h ( u ，v ) ：= ，( 孟+ uo u ) 它们的次微分别有这样的表达式： o h l ( u ) = 鼽：g a ，( 牙+ “o u ) o h 2 ( v ) = g v ：g 毋，( 牙+ u o u ) o h ( u ，v ) = t 0 9 v ：g a ，( 孟+ u o ) ) 2 1 2 甜- l a g r a n g e 函数 给定次梯度蚕a ，( 牙) ，其中v 一分量为雪v ，则f 相对于如的u - l a g r a n g e 函数定 义为 “弓u ”“( 珏) ：2 搿 坤+ 。 ) 一( 互v ，u ) v ) ( 2 1 1 ) 伴随于让空间的最优点集为 w ( 乱) ：= a r g g 船 ，渖+ uo ) 一( 互v ， ) v (212)i”e 。 见 1 2 引理2 1 3 【1 2 设雪r i a ，( 重) ，则存在充分小的，7 0 ，使得对任意的0 v 有 川。赤o f 0 使得 互+ ( b ( 0 ，7 7 ) n 忱) ca ，( 孟) 8 大连理工大学硕士学位论文 引理结论成立此外，由次微分的定义，对任意的( u ： ) “v ，有 m + u 。郇) 2 m ) + 胁。( v + 氚) ，u 。”) = ，( 牙) + ( 吼，“) “+ 扫v ，可) v + q l l v ij v 关于“一l a g r a n g e 函数，我们有下例性质 定理2 1 _ 4 【1 2 1l u 有如下的主要性质： ( i ) 厶，是处处有限的凸函数 ( i i ) ( 2 1 2 ) 中的点u w ( u ) 当且仅当9 a ，( 岳+ “o u ) 使得g v = 如 ( i i i ) 特别地，0 w ( o ) ，l u = ，( 牙) ( i v ) 当互r i o f ( 孟) 时，对任意的甜有w ( u ) 0 且w ( o ) = o ) 定理2 1 5 【1 2 】 ( i ) 上w 在u 的次微分可表示为 o l u ( u ) = 9 h ：g uo 雪v a ，( 牙+ uo u ) )( 2 1 4 ) 其中u w ( u ) 0 是任意的 ( i i ) 特别的，切在0 点可微，并且v 切( o ) = 勃，即所有g a ，( 孟) 有相同的“一分量 推论2 1 6 f 1 2 1 如果互r i a ，( 牙) ，则有 v 0 ，j 6 0 ：“6 辛i i u l l v l i u l l u ，讪w ( u ) ( 2 1 5 ) 即：w ( u ) = o ( 1 l u l l u ) 证明由定理2 1 5 中的( i i ) 切在0 点有一阶展开式 切( u ) = l u ( o ) + ( v l u ( o ) ，札) “+ o ( 1 l u t l “) = ，渖) + 弘，札) 甜+ o ( 1 l u l l ) 对任意的u w ) ，我们有k ( u ) = ，( 牙+ u o u ) 一( 如，u ) v 此外在( 2 1 3 ) 中取计= u 可得白( u ) ，( 孟) + ( 9 u ，u k + 圳叫i v 因此，有 o ( 1 l u l l “) = 厶( u ) 一，( 耍) 一( “，u ) “ 7 1 1 u 1 1 , 9 “y 一分解在半光滑中的应用 结论成立 推论2 1 7l u 在点札沿方向d 的方向导数有如下表达式 ( u ；d ) = ，7 ( 叠+ u o u ：d o0 ) = 扩( d oo l o f ( 互+ “o u ) n ( “o 互v ) ) 其中u w 似) 是任意的 证明因为切是有限值凸函数，由 1 中定理2 3 4 ，有 ( u ；d ) = 矿( d l a l u ( u ) ) 2 。品黠。) ( g u , d ) 2 m 。如m 晰a x i + 。毋。) ( g u 。9 v , d 。o ) = 矿( d oo l o f ( 牙) + u o “) n ( “o 口v ) = ，7 ( 牙+ “o u ；d o0 ) 定义2 1 8 t 1 2 j 称，在点互有一个径向l i p s c h i t z 次微分，如果存在d 0 及6 0 ，满足 a ，( 孟+ d ) ca ，( 孟) + b ( 0 ，d i i d l l ) ，v d b ( 0 ，6 ) ( 2 1 6 ) 或等价地，存在c 0 及e 0 ，满足 ，( 蜃+ d ) ，( 牙) + ，7 ( 牙；d ) + 1 c i i d l l 2 ，v d b ( o ，e ) ( 2 1 7 ) 下面，我们将考虑a b 在u = 0 附近的性质 定理2 1 9 t 1 目设对充分小的u 有w ( u ) 0 且( 2 ，1 6 ) 及( 2 1 7 ) 成立，则有 ( i ) 存在d 0 ，使得对所有u b u ( 0 ，6 ) ，有 o l u ( u ) c 阮+ b u ( o ，2 c 1 1 4 1 “) ( 即 9 u ：g u o 口v a ，( 露+ “o u ) ) c 弘+ b u ( o ，2 0 1 1 1 1 ) 这里u w ( u ) 是任意的) ； 1 0 大连理工大学硕士学位论文 ( i i ) 存在p 0 及d 0 ：使得对所有的乱b u ( o ，p ) ，有 功( u ) s 切( 。) + ( g u ，u ) + ；d 刍 关于非光滑凸函数，c l a r k e ( 1 9 7 7 ) 和r o c k a f e u a r ( 1 9 7 6 ) 都给出过广义h e s s e 阵的定 义我们借助于这一概念，可以得到，在某局部上的二阶展开式 称凸函数妒在点。o 具有广义h e s s e 阵h 妒( x o ) ，如果 梯度v 妒( z o ) 存在； 存在对称半正定算子日妒( z o ) 满足： 1 妒( 。o + d ) = o ( x o ) + v 妒扣o ) ，d ) + 妄( h 妒( x o ) d ，d ) + o ( 1 l d l l 2 ) ， 或等价地， o 妒( z o + d ) cv 妒( z o ) + h 妒( x o ) d + b ( 0 ，o ( h d l l ) ) 定义2 1 1 0 ”】设，是r ”上的有限值凸函数，如果毛，在点乱= 0 有一个广义h e s s e 阵 日切( o ) ，则称，在点牙有一个纠一h e s s e 阵，记为岛z ，( i ) ：= h l u ( o ) 定理2 1 1 1 【1 2 】设r i a ，( j ) ，且甜一h e s s e 阵黾，( 孟) 存在，对u “及h u ow ( u ) 有如下二阶展开式： 1 ，( 牙+ h ) = ，( 牙) + 扫，h ) + 妄( 月0 ，忙) 钍，札k + o ( f t h l f 2 ) ( 2 1 8 ) 证明因为互r i o f ( y ：) ，及定理2 1 4 中的( i v ) 知w ( 乱) 0 由l u 的定义，对其作展开 可得，对所有的札甜和u w ( “) ： l u ( u ) = ，( 孟+ 珏。叫) 一( 口v ，u ) v = l u ( o ) + ( x 7 l u ( o ) ，u ) “+ j ( j 毛，忙) u ，u ) u + o ( 1 u l l 吕) = ，( 牙) + ( 盈，u ) 酣+ j ( h u f ( x ) u ，u ) u + o ( 1 i “i b ) 由推论2 1 6 可知o ( 1 l u l l 刍) = o ( 1 l h l l 2 ) ，上式两端同加( 知，u ) v ，得证 2 2 凸函数甜y 一分解理论应用于有限约束的非线性规划 在这一节中，我们考虑的优化问题是 。m 土i n 。p 。z ( x ，) 。注小，。 其中妒，l c 2 是凸函数 ( 2 2 1 ) “协分解在半光滑中的应用 2 2 1具有有限约束的非线性规划问题的精确罚函数 假设孟是问题( 22 1 ) 的一个最优点且k k t 条件成立：对l a g r a n g e 函数 l ( x ， ) ：= 妒( ) + ； ( z ) ，( 茁， ) r ”r ”， t = 1 存在l a g - r a n g e 乘子使得 v 。l 忙天) = v 妒忙) + 墨，元v ( 牙) = 0 i 元0 ，天t ， ( 牙) = 0 ，i = i ，m 下面记1 ：= v 妒，g f ：= v 以，彳：= r e ( z ) ，吼：= v ( 牙) 考虑( 2 2 1 ) 的精确罚函数 f ( x ) ：= 妒( 。) + ”m a x f o ( z ) ， 。( z ) ) ， 其中 0 是罚参数，f o ( x ) i0 且9 0 ( x ) ! v o ( z ) 三o 记： g ( x ) ：= j o ，m ) ：砂( z ) + 7 r 矗( 茁) = ，( z ) ) 函数，是r n 上的凸函数，一般说来，是非光滑的 计算，的次微分 o f ( x ) = - y ( x ) + r c o g a x ) ：j ，忙) ) 记集合： i ：= 0 “，m ) ： ( 牙) = o ) 一般地，我们假设，0 ( 否则没有意义) ，则很容易看出j ( 孟) = ，u o ) 记： 皿i ：= a t ，i ，；皿o ：= 7 ( 2 2 2 ) ( 2 2 3 ) ( 2 2 4 ) 2 2 2 非线性规划精确罚函数的u v 一分解 为了研究，在点1 - 的b t v - 空间分解以及它的展开问题，我们做如下的假设： 假设a 积极约束梯度集合 或 惦j 是线性无关的； 元 0 , v ，； 7 r 九 拒j 对于这类有限个约束的非线性规划问题，空间“和v 有非常具体的表达形式 命题2 2 1 若假设a 成立，则在。= 蜃有下列关系式成立： 1 2 大连理工大学硕士学位论文 ( i ) a ，( 牙) = v 5 + e p i 亟：p 0 ，e p i ”) i e l i ， ( i i ) 由b v 一分解所生成的子空间甜和v 为 ( i i i ) 互= 0 r i o f ( 牙) y = l i n 慨 埏j “= d r ”：( 。，d ) = 0 ，i ，) 引理2 2 2 【1 2 】设z 充分接近孟且假设a 成立则j ( x ) cj ( 牙) = i u o ，且关于 卢，b 。j ( 。) 的方程组 f ( 死，y ( 。) ) + p y g j ( z ) ) = 0 ，v i i p 妊“ ( 22 5 ) i厶p j2 “ lj j 扛) 有( 唯一) 解当且仅当j ( x ) = j ( 2 ) = i u o ) 其解肛( z ) 满足如( z ) 0 ，v j ，( z ) = ，( 牙) 此外，z 一芦) 在x = 孟是可微的 2 2 3 非线性规划的“一l a g r a n g e 函数的性质 对于0 r i o f ( 2 ) ，的“一l a g r a n g e 函数为 l 。( “) 2 蔷 施+ u 。”) 一( o ，”) v ) 2 瓣 雕+ u 。”) ) 其在空间1 ，中的最优解集为 ( “) = a r g r o 删i n m + u 。 ) ) 下面的定理刻画了w ( ) 中的点 定理2 2 3 1 1 2 】假设a 成立对充分小的u “，w ( u ) 是单点集， 量v v 下列系统的唯一解 忙+ u o ) = 0 ，v i 五 “一l a g r a n g e 函数具有如下的性质 定理2 2 4 【1 2 假设a 成立 1 3 p ( u ) ) ，u ( “) 是关于变 ( 2 2 6 ) “1 九分解在半光滑中的应用 ( i ) l o ( u ) 在0 的小邻域内是可微的，对于分别在引理2 2 2 和定理2 2 3 中得到的p ( ) 和u ( ) ，记z ( u ) = 孟 4 - “o u ( “) 当u 充分小时，- f 面$ j 等式成立： v ( 乱) 。0 = ，y ( z ( u ) ) + 脚( 卫( u ) ) 鲫( z ( 札) ) ( 2 2 7 ) j j ( i i ) l o ( u ) 在“= 0 的h e s s e 阵存在，若对l a g r a n g e 函数的h e s s e 阵分块 v 弘耻( 老苏) 且有v 2 l o ( 0 ) = h u u 现在对任意的互r i o f ( 孟) ，得出，的吖一l a g r a n g e 函数的一般结果 定义函数 f ( x ) ：= f ( x ) 一( 雪7 ：z ) = 砂( 。) + ”m a x ，0 ( 卫) ， 。( z ) ) 一( 雪7 ，z ) = 7 ( z ) 一百7 h - r c o g j ( x ) ：j j ( 。) ) a f ( 孟) = 彳一口7 + 7 r c o 功：j ，( 牙) ) 同引理2 2 2 一样，由0 r i 0 f ( 2 ) ，系统 f ( 或，7 ) 一雪7 ) + p j ( 虱，毋 ) ) = 0 ，v i ， p 咋以蝴 ( 2 2 8 ) i 吩= 7 r 7 lj e j ( x ) 有( 唯一) 解当且仅当j ( x ) = j ( 孟) = 儿j o ) 记，相对于互7 r i a i ( 孟) 的b - l a g r a n g e 函数为l ；，则 l ( 扎) = ：酣雕+ u 。 ) 一籼 ) v ) l 孑( “) = i 醇 ，( 牙+ u o ) 一( 互7 ，牙+ u o u ) y 2 瓣 ， + 钍。”) 一( v