（应用数学专业论文）一类非凸dc约束优化问题的uv分解理论.pdf

摘要 摘要：本文主要讨论一类非凸d c 约束优化问题的w 一分解理论。 全文共分四章。第一章是引言，主要介绍了关于w 一分解理论的历史 概述与研究背景，及对本文的研究工作。第二章是预备知识，首先介 绍了w 一空间分解理论及其相关性质，然后引入了u - l a g r a n g e 函数， u - l a g r a n g e 高阶性质及其最优解集，最后给出广义海赛阵的定义及 性质。第三章研究的是非凸d c 约束优化问题的w 一分解理论。由于 非凸d c 函数在其有效域相对边界点处的次微分集合非空，则它是一 个无界集。次微分集合的无界性使得有限值非凸函数的w 一分解理论 不能直接应用于d c 函数上。因此第三章首先对非凸d c 函数的次微 分集合的结构进行分析，然后借助于次微分分解定理得到了一个有界 闭凸集。经过分析这个有界凸集与次微分集合对于w 一分解理论所起 的作用类似，因此我们借助于这个有界闭凸集进行w 一空间分解，得 到其一l a g r a n g e 函数，并且借助于一l a g r a n g e 函数的展开式得到它 在某个轨道上的二阶展开式。第四章是总结与展望，主要对本文所作 的工作进行简短的概括总结，并对d c 函数在非凸集合的约束优化问 题做以展望。 关键词：非光滑最优化；d c 函数；u v 一分解；u - l a g r a n g e 函数 c o n t e n t ： a b s t r a c t t h eu v - d e c o m p o s i t i o nt h e o r yi sa l le f f e c t i v em e t h o dt os o l v et h e s e c o n d - o r d e r a p p r o x i m a t i o n o fn o n s m o o t hc o n v e xf u n c t i o na n d o p t i m i z a t i o np r o b l e mo fn o n s m o o t hc o n v e xf u n c t i o n 【1 】i nt h i sp a p e r , t h e u v - d e c o m p o s i t i o nt h e o r yi su s e dt os t u d yac l a s so fn o n c o n v e xd c c o n s t r a i n e do p t i m i z a t i o np r o b l e m t h ef i r s tc h a p t e ri sf o r w a r d w em a i n l y i n t r o d u c et h eb a c k g r o u n do f k n o w l e d g eo fu v - d e c o m p o s i t i o nt h e o r y t h e s e c o n dc h a p t e ri sp r e l i m i n a r yo fk n o w l e d g e ；f i r s t l y , w em a i n l yi n t r o d u c e t h ec o n c e p t i o n sa n dp r o p e r t i e so f u v - d e c o m p o s i t i o nt h e o r y s e c o n d l y , w e i n t r o d u c e u l a g r a n g ef u n c t i o n ，o p t i m a ls o l u t i o ns e tw ( u ) a n dt h e s e c o n d - o r d e ra p p r o x i m a t i o n i n c h a p t e rt h r e e ，t h eu v - d e c o m p o s i t i o n t h e o r ya n du l a g r a n g ef u n c t i o na r ep r o v i d e df o rd c f u n c t i o n s i n c et h e s u b d i f f e r e n t i a lo fd c f u n c t i o ni sau n b o u n d e ds e t ，w ed e f i n eas e tw h i c h h a st h es a n l ef u n c t i o na st h es u b d i f f e r e n t i a ls e t b a s e do nt h i ss e t ，w e i n t r o d u c et h ed e f i n i t i o no ft h ed e c o m p o s i t i o no ft h es p a c e ，u l a g r a n g e f u n c t i o n ，o p t i m a ls o l u t i o ns e tw ( u ) a n dt h es e c o n d - o r d e ra p p r o x i m a t i o n t h el a s tc h a p t e ri st h eo u t l o o kf o rt h i sa r t i c l e ，h o p i n gt of i n dab e t t e rw a y t oq u a d r a t i cp r o g r a m m i n g s k e yw o r d s ：n o n - s m o o t ho p t i m i z a t i o n ；d c f u n c t i o n ；u v - d e c o m p o s i t i o n ； u - l a g r a n g ef u n c t i o n 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加以标注 和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同志的研究成果对本 人的启示和所提供的帮助，均已在论文中做了明确的声明并表示谢意。 学位论文作者签名：鱼! 建 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有权保留并向 国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权辽宁师范大学，可以将 学位论文的全部或部分内容编入有关数据库并进行检索，可以采用影印、缩印或扫描等复制手段保 存、汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：一二立良一 指导教师签名： 签名日期：年月日 1 引言 一类非凸d c 约束优化问题的w 一分解理论 1 1 历史概述及研究背景 在科学技术，管理科学和经济学等理论与实际应用的研究中，非光滑现象不可避免且经常出现因 此，非光滑分析与最优化理论一直备受关注由于非光滑函数本身的特征较为复杂，使得在传统光滑假 设下所进行的大量的最优化和分析不能直接应用于非光滑的情况中，需要有一种新的理论体系( 非光 滑分析) 来很好地处理这类问题七十年代c l a r k e 关于l i p c h i t z 函数的微分学的研究成果使得非光滑 微分学取得了突破性的进展，以l i p c h i t z 函数为主的非光滑分析与优化已形成独立的研究领域八十年 代以来非光滑分析与最优化研究中的一个核心课题 非光滑函数的二阶近似与二阶展开是某些与实际应用有着密切关系的领域中的算法研究的基础， 如数值代数，优化，控制及对策等，一直是学者们关注的课题之一由于计算机技术的不断进步，非光滑 函数在实际问题中的广泛出现，需要设计具有高阶收敛性的算法，对非光滑函数的二阶近似结构及性 态的研究显得尤为重要，正因为如此，众多的优化专家不断地研究这一专题试图攻克非光滑函数的二 阶近似的理论，并以非光滑凸函数为主攻方向，其主要方法包括构造一个二阶导数的公式来逼近凸函 数的二阶近似，定义一种集值映射的近似以代替次微分的近似，利用双方向定义二阶方向导数以用于 逼近凸函数的二阶近似以及利用函数的上图得出上图二阶近似等这些研究工作为以后的非光滑分 析与优化，无论在理论研究还是在应用问题探讨方面都打下了良好的基础 近四五年在这一专题的研究中有两项重要的成果，其一为r o c k a f e l l a r ( 2 0 0 0 ) 关于非光滑凸函数的 h e s s e n 阵的研究成果，另一为l e m a r e c h a l 等人提出的关于凸函数次微分的u v 分解理论u v - 分解理论 是一种研究非光滑凸函数二阶近似结构的新方法，其理论背景是基于如下的问题当我们将凸函数f 在 其不可微点；作二阶t a y l o r 展开时，主要困难是来自微分( 梯度) 已不再是一个向量而是一个集合， 因此必须处理两个集合的差商，如何给出一个合理的表达是一个不易解决的问题，在此之前的许多结 果都还是抽象的尝试( 【1 】，【2 】，【3 】，【4 】，【5 】) ，而没有形成较为有效的理论体系，但是这些研究工作可以给 我们带来许多启示 j - b h i r i a r t - u r r u t y 和c s a g a s t i z a b a l ( 1 9 9 3 ) 指出，厂 ；) 的线空间u 满足如下性质： u 是这样的 元素h 的集合，使得函数j i 专几+ 功在点乃= o 是可微的，而钞( x ) 在u 上的投影是单点集( 即沿着u 的 方向，o f ( x ) 具有o 宽度) 由此可以得到如下两个事实： 第一，存在r n 的一个子空间u ，使得厂( 葛) 在u 上是线性的； 第二，定义f 的二阶展开式无需沿着u 以外的方向例如，考虑情况f = - m a xf 五， 其中z 是光滑的，即使仅知道f 在u 上的二阶性态，其序列二次规划型的的最小化算法仍是超线 一类非凸d c 约束优化问题的w 一分解理论 性收敛的q 6 ，【7 】) 在此基础上，c l e m a r e c h a l ，e o u s t r y , 和c s a g a s t i z a b a l ( 2 0 0 0 ) 提出沙一分解理论【1 】，其主要思想是 将空间r “分解成两个正交的子空间u 和y 的直和，使函数在u 上的一阶逼近是线性的，而不光滑特 征集中于矿中，借助于一个中间函数，u l a g r a n g e 函数，来得到函数在切于u 的某个光滑轨道上的 二阶展式这样，设计非光滑最优化的算法可以在此光滑轨道上考虑 2 0 0 0 年c l e m a r e c h a i ，f o u s t r y , 和c s a g a s t i z a b a l 关于w 一分解理论的奠基性文章“t h e u - l a n g n g i a no fac o n v e xf u n c t i o n ”【8 发表，文章以【9 ，0 0 的研究成果为基础，给出了凸函数f 相对于某 一点的；的w 一分解的三种等价形式的u l a g r a n g e 函数的基本形式，并对其基本性质进行了研 究得出的主要结果有： 在某些条件下，点i 附近的7 r 在u 上的限制与u l a g r a n g e 函数直到二阶一致，可以借助于 u l a g r a n g e 函数的展开式得到函数厂在切于u 空间的某个轨道上的二阶展开式；w 一分解理论 在非线性规划及一类半定规划上的简单应用以及应用w 一分解理论设计了一种概念型的超线性收 敛的最小化算法 1 2 本文的研究工作 在非光滑优化中，函数的二阶导数及二阶展开对于最优化条件的研究以及设计具有高阶收敛性 的算法都是必不可少的工具因此，非光滑函数的二阶性质与展开的理论和应用方面的研究一直倍受 关注 2 0 0 0 年，c l e m a r e c h a l ，f o u s t r y , 和c s a g a s t i z a b a l 等提出的u v - 分解理论，给出了研究有限值非光滑 凸函数的二阶性质的新方法【1 1 】这一理论能够推广到一类非凸d c 函数上来本文贝n 对一类非凸 d c 函数进行讨论。若非凸d c 函数在其有效域相对边界点处的次微分集合非空，则它是一个无界 集，次微分集合的无界性使得有限值非凸函数的w 一分解理论不能直接应用于d c 函数上因此必 须首先对非凸d c 函数的次微分集合的结构进行分析，然后借助于次微分分解定理得到了一个有界 闭凸集经过分析这个有界凸集与次微分集合对于w 一分解理论所起的作用类似，因此我们借助于 这个有界闭凸集进行w 一空间分解，得到其u l a g r a n g e 函数，并且借助于u l a g r a n g e 函数的展 开式得到它在某个轨道上的二阶展开式 2 一类非凸d c 约束优化问题的一分解理论 2 预备知识 2 1w 一空间分解 设厂是定义在犬”上的有限值凸函数，厂在点x r ”的次微分集合记为矽( x ) 给g n xe r ”使 得i n t 钞( _ ) = a 但是r i 可( ；) g ，且g 矽( - ) 。定义空间r ”在点；处的u v - - 分解为 r “= uov ，其中，正交子空间u ，v 可以通过三种方式来定义 定义2 1 【1 2 1 ( i ) 设u 是使得方向导数厂7 ( ；) 为线性函数的子空间，k - 时n y of ( ；) 是次线性的，所以， 有u 一 u e r 以：厂( ；“) = 一f ( - ；一材) ； ( i i ) 设k 是平行于矿( ；) 所生成的仿射包的子空间，醍：= 时即，净h n ( 可( ；) 一；) ，其 中，；可( ；) 是任意的； ( i i i ) 设配和巧分别是矽( ；) 在点g 。r i 可( ；) 的法锥和切锥，其中g 。是任意的此时，玑和巧必 为子空间 注：l i n m 表示由m 生成的线性空间 上面不同方式定义的空间分解，其结果是等价的 命题2 1 t 1 2 1 定义2 1 中， ( i ) 当g 。r i 妒( ；) 时，以= d 彤：g g 。，j ) = o ，v g 可( ；) ) = ( ；) ( g 。) ，r - 与g 。的选 取无关5 ( i i ) u = = 虬= ：u ； ( i i i ) 一般地，对；彭( ；) ，有uc ；) ( ；) 2 2u l a g r a n g e 函数 给定次梯度；钞( - ) ，其y 一分量为；，则相对于虿，的u l a g r a n g e 函数定义为 u ，z ，h 乞( “) ：= i 蝇。矿 ( ；+ “。v ) 一( 西) ，) ( 2 1 ) 伴随于矿一空间的最优点集为 一类非凸d c 约束优化问题的沙一分解理论 ( “) ：= a r g r r d n 删 厂( ；+ “。v ) 一( 如) ， ( 2 2 ) 见【1 2 】 引理2 1 设；r i 钞( 一) ，则存在充分小的r o ，使得对任意的o 1 ，矿有 ；啪菏钞( ；) 特别地，对任意的( “，1 ，) u xv ，有 厂( ；+ 甜。v ) 厂( ；) + ( 互，材) 。+ ( ；) ，+ 州l ，( 2 3 ) 关于u l a g r a n g e 函数我们有下列性质 定理2 1 1 2 1 厶有如下的主要性质： 1 l g - 是处处有限的凸函数 2 ( 2 2 ) 中的点w ( 甜) 当且仅当存在g 钞( ；+ 甜。w ) 使得& = ；， 特别地，0 缈( o ) ，乞( o ) = 厂( ；) 当；r i 钞( ；) 时，对任意的甜有矿( 甜) 彩，且矿( o ) = o 定理2 2 【1 2 l ( i ) 之在甜的次微分可表示为 吃( 甜) = g u ：邑。；，彭( ；+ “。w ) ) ， ( 2 4 ) 其中w e w ( u ) 囝是任意的 ( i i ) 特别地，乞在。点可微，并且眩( o ) = ；。，即所有g 可( ；) 的相同u 一分量 推论2 1 如果；r i 钞( ；) ，则有 v s o ，j 8 o ：1 1 , , 1 1 。 i l w l l ，- - - 1 1 , , 1 1 。，v w 形( 列) 即；形( “) = d ( 。) 4 一类非凸d c 约束优化问题的沙一分解理论 二 推论2 2 l g 在点材沿方向d 的方向导数有如下表达式 乞( “；d ) = 厂( ；+ “。w ；d 。o ) = 万。( d 。o l 耖( ；+ “。w ) r 、( u 。；，) ) ， 其中w e 形( 甜) 是任意的 2 3u l a g r a n g e 函数的高阶性质 定义2 2 1 。1 称在点；有一个径向l i p s c h 蛇次微分，如果存在d o 及万 0 ，满足 矿( ；+ d ) c 钞( ；) + 曰( o ，o l l d l l ) ，v d b ( o ，万) ( 2 5 ) 或等价地，存在c 0 及占 0 ，满足 厂( ；+ d ) 厂( ；) + f ( ；d ) + 丢c l l d l l 2 , v d 丑( o ，f ) ( 2 6 ) 考虑吃在 = 0 附近的性质，我们有 定理2 3 1 2 1 设对充分小的掰有形( 甜) o ，且( 2 5 ) 及( 2 ，6 ) 成立贝i j 有 ( i ) 存在艿 o ，使得对所有的“鼠( o ，万) ，有a l ( 甜) c 云+ 尻( o ，2 c 恤忆) ( 即 邑：。；，妒( ；+ z ，。w ) c 否。+ 色( o ，2 c l l 甜儿) ，这里w 形( 甜) 是任意的) ； ( i i ) 存在夕 o 及d o ，使得对所有的材色( o ，p ) ，有( 甜) ( o ) + ( ；。，掰) + 专d 芒 2 4 u l a g r a n g e 函数的最优解集 对于“u 及w 缈( “) ，作集合g ( ；+ 材。w ) - g 妒( ；+ z ，。w ) ：毋= g l t 显然，对任意的u e u 及w r e ( 甜) ，g ( ；+ 甜。w ) 是尺斤中的凸集 定理2 4 对任意材u ，集合g ( ；+ 甜。w ) 与w 矽( 甜) 的选取无关即对任意的 ，心矿( 甜) ，有 ：鼠。夏钞( ；+ 甜。w 1 ) = g 。：。；，可( ；+ “。w 2 ) 推论2 3 对任意w 形( 甜) ，有g ( ；+ 材。w ) = 可( _ + 甜。矿( z ，) ) n ( 甜。；，) 推论2 4 ( 2 ，) 彩当且仅当g ( ；+ 甜o w ) g 5 一类非凸d c 约束优化问题的u y 一分解理论 2 5 广义海赛阵 关于非光滑凸函数，c l a r k e ( 1 9 7 7 ) 署l lr d c l ( a f e l i 斫1 9 7 6 ) 均给出过广义h e s s e 阵的定义我们借助于这 一概念，可以得到厂在某局部上的二阶展开式 称凸函数驴在点而具有广义h e s s e 阵日伊( 确) ，( 见【3 8 】) ，如果 i 梯度v 缈( ) 存在； i i 存在对称半正定算子日伊( ) 满足 矽( 而+ j ) 2 伊( ) + ( v 9 ( x 。) ，d ) + 三( 却( ) 州) + 。( 1 l , t l l 2 ) ， 或等价地a 妒( 而+ d ) cv 妒( ) + 日矽( ) d + b ( o ，d ( 肛0 ) ) 定义2 3 1 2 1 设厂是彤上的有限值凸函数如果乞在点钌= o 有一个广义h e s s e 阵心( o ) ，则称 厂在点x 有一个u h e s s e 阵，记为风( x ) ：= 月= 乞( o ) 定理2 5 设；r i 钞( ；) ，r u - h e s 阵鼠厂( ；) 存在对z f u 及办甜。( “) ，有如下二阶 展开式 币+ 办) = 水) + ( 酬+ 三伍作) 刚) + o ( 1 l h l l 2 ) 6 一类非凸d c ：约束优化问题的w 一分解理论 3 非凸d c 约束优化问题的w 一分解理论 考察d c 函数的约束最优化问题 ( d c p ) f m i n f ( x ) = ( x ) 一矗：( z ) t s j x e c 其中，啊( x ) 是尺“空间的有限凸函数，h ：( x ) c c 2 , c 为凸多面体集合于是问题( j d c p ) 等价于 r a i n f ( x ) ，其中，f ( x ) = 红( x ) 一j l z ( x ) + 6 ( 石t c ) 3 1w 一空间分解 对于非凸函数f ( x ) ，我们先利用其近似次微分来研究w 一空间分解和函数f ( x ) 的二阶近 似 定义3 1 1 【3 1 ：向量亭尺”称为f 在点x 如硝的一个近似次梯度( 或p 一次梯度) ，如果 ( 亭，一1 ) 易( x ，( x ) ) ，这里，n e s ( z ，厂( z ) ) 是印矿在点( x ，厂( 工) ) 的近似法锥所有这样的点亭 所成之集称为f 在axe d o m f 的近似次微分，或p 一次微分记为a p ，o ) 注：若f ( x ) 如上定义，则a p f ( x ) - a i l l ( z ) 一v h ：( z ) + c ( x ) ，其中帆( z ) 是凸函数i i l l ( x ) 在 x 点的次微分，n 。( x ) 是c 在x 点的法锥 定义3 1 2 ：a g e a 。f o ) ，则存在g a j l l l ( z ) ，g ”e n d ( x ) ，使得g = g 一：( 工) + g ” 我们用三种方式定义w 一空间分解如下： ( i ) u l 。 d 尺“d l i n t , ( x ) ，碍o ；d ) = 一硝 ；一d ) ，k = u 1 上 ( i i ) 砭f f il i n ( a 魄o ) 一g7 ) + ( c o ) 一g ”) 】，u ：。k 上 ( i i i ) 虬定义为a p f 0 ) 在点g 一a p f o ) 的近似法锥，记为n 。p ，( ，) 国) 匕定义为a p f ( x ) 在age r i a p f o ) 的切锥 注：( i ) 中l n 为集合的线空间 定理3 1 1 ：( i ) 设g a 。f o ) ，g = g 一乳( x ) + g ”，其中g 叽( z ) ，g ”c ) ， 7 一类非凸d c 约束优化问题的w 一分解理论 ( i i ) = d e r ”：( d ，g ) = ( d ，g + v h 2 ( x ) - g 。) ，v g a 啊( x ) ) = 赢( 工) ( g + v h 2 ( x ) - g 。) ( i i i ) q = = 弘= u 证明：( i ) 由a p f ( x ) = 饥( x ) 一v 如( x ) + c ( x ) ，对于坛o p f ( x ) ，3 9 砒( x ) ，g 也( x ) 使得 d e a ，f ( ，) ( g ) ( d ，g 一v h 2 ( x ) + g 。一g ) s o ( d ，9 7 - ( v 魄( x ) - g 。+ g ) ) o d 磊( 工) ( g + v h 2 ( x ) 一g 。) ( i i ) 由( i ) 得：= k “) ( g + v l h ( x ) - g ”) 令n = d e r ”：( d ，g ) = ( d ，g + v t h ( x ) - g ”) ) 若j ，则有( d ，9 7 一( g + v ( x ) - g ”) ) = o 因此d ， 如果g r i o p ，( x ) ，贝ag + v h 2 ( x ) - g ”r i a t 毛( x ) ，其中g ”n a x ) 对d 磊( x ) ( g + v h 2 ( x ) - g ”) 及g 阮( z ) ，由f 4 】，r 需i i e ( d ，g 一( g + v 缟( x ) - g ”) ) o 取v = 一( 9 7 一( g + v 忽( x ) - g ”) i l g 一( g + v ( x ) - g 佩由g + v h 2 ( x ) - g ”，一溉( x ) ， 则存在召 o ，使得g + v ( x ) - g ”+ 蟹v 弛( x ) 因此有 ( g + v h ( x ) - g ”+ 刁v - ( g + v h ( x ) - g ”) ，d ) = ( ，7 v ，d ) f l l 】( g - ( g + v h 2 ( x ) 一g ”) ，d ) o 于是有( g 一( g + v 红( x ) - g ”) ，d ) = o ，2 乩因此= 乩 ( i i i ) 设de u , ，则矗三i 疗瓦( x ) ，群( x ；矗) = 一研( x ；一d ) 令蜀，9 2 砒( x ) - g + c ( x ) 一g ”， k = g i g = 五蜀+ a u g ： = 三加( a 啊( x ) 一g + 札( x ) 一g ”) ( d ，g ) = ( d ，五蜀+ 五) = o ，则有d ，因此u 设d ，令g = g l + g 一v ( x ) + g ”，则g ，g 。- v h z ( x ) + g ”a p f ( x ) ， ( d , g - ( g 一v 呜( z ) + g ”) ) = ( d ，岛) = o ， 有( d ，g ) - - ( e ，g + v h ：( x ) - g ”) 因此d ，有s 设舀配有( 舀，g ) = ( 矗，g + v 呜( x ) 一g 哆，- 于是s u p ( x ，d ) = i n f ( x , d ) ，x a 向( x ) 8 一类非凸d c 约束优化问题的w 一分解理论 r d l i n t 。( x ) ，即d u ，因此u ，证得u = = 乩 3 2 u l a g r a n g e 函数 设；r ”，g a p ，( 一) ，则珐就( ；) ，g 一c ( _ ) ，使得g = 9 7 一( ；) + g ，令 m = c n 三切乏( _ ) ，定义： 乓( 甜) = 姊 啊( i + “。v ) 一( g ：，v ) ，+ 万( i + 材。v i c ) 一( 彰，v ) ，) 一( 坼) + ( v 坼灿) 。+ 丢( 矿皿弧) 。) 限， ) = a r g 。m ，i n 坼( i + “0 1 ，) 一( g ：，1 ，) ，+ 万( i + 材0 1 ，i c ) 一( g ， ( 3 2 ) v 鲥 。7 定理3 2 l ：( i ) w 形( “) 当且仅当存在g a 。f ( i + “ow ) 使得g ，= g ：一v 吃( i ) + 彰 ( i i ) 特别地，o 形( o ) 且乞( o ) = f ( 舅) 证明：( i ) 乓( 甜) = 璐伟( i + 甜。v ) 一( 或，v ) ，+ o f f + “。v i c ) 一( g ：，v ) ， 一( ( 孑) + ( v 缟( i ) ，甜) 。+ 丢 。) 二 ，“ = i n f h a ( 2 + “。v ) 一( 或，v ) ，+ 艿( i + 甜。v i c ) 一( 彰，v ) ， 一( 昧) + ( ( 巩甜) 。+ 三( 矿皿弧 。h v i m ) t ( u ) 是u 上的凸函数，由凸函数的最优性条件 5 】， w 形( 材) o 讹( i + 掰o w ) 一g ：+ m ( i + “ow ) 一彰 g ：+ g ：a 啊( i + 甜ow ) + 札( i + 甜ow ) 或一v 缟( i ) + g ：o h , ( i + “ow ) 一v 岛( i ) + 札( i + 甜ow ) 营s g = 邑+ g ，o f ( i + 群ow ) 使得g ，= g ：一v 吃( i ) + g ： ( i i ) 对甜2 0 ，在( i ) 中可取w = o 及g _ 9 7 一( i ) + g 一o p f ( 2 + o + o ) ，由此得o 肜( o ) 且 9 幺( o ) = ，( i ) 综上，得出u l a g r a n g e 函数： t ( “) = a ( i + 甜。w ) 一( 式，”，+ 万( z + “。w l c ) ( 彭，”， 一( 坼) + ( v 螈咖) + 妒皿孤x ) 乓( o ) = 拐( 虿+ o 。o ) 一( g ：，o ) ，+ 万( i + o + o i c ) 一( 酢o ) ， 一( ( i ) + ( v 坞( - ) ，。x + 三( 矿日2 玩，畛) = f ( i ) 定理3 2 2 ：设“使得形( 甜) o ，则乓在u 上的近似次微分有如下表达式： a ，乞( “) = 邑：邑。( g v ( i ) 一酊) a p f ( i + 材。w ) ，其中w 形( “) 特别地，匕( 甜) 在都= o 点处是可微的，r v l g ( o ) = 或- v h ：( x ) 。+ 爵 证明：任取v m 有下列等价关系： 邑a 户乞 ) 乞( z i f ) 乓( 甜) + ( ，甜- “) 。+ d ( 肛一“ 啊( i + 掰。v 7 ) 一( g ：，v ) ，+ 艿( i + 。v 7 i c ) 一( 或，v ) ， 心( ；) + ( v 呜( 桫) 。+ 妒媳玩) 7 j i ( m 。w ) 啦w 7 ) ，+ 万( m 。w 阱( 站d ，一( 忽( ；) + ( v 红( 酬。+ 巩玩) + ( ，甜一“) 。+ d ( j j “一砧4 l v 砧b ( 甜，万) ，v y 7 ，w ( z ，) ， 盔( i “。矿) 啊( i + “。w ) + ( ( 邑+ v 吃( i ) ) 。( g ：+ 彭) ，( 牡材) 。( v ，一_ ) + 扣一“) r 万7 皿万( 小甜) + 谁。 ( + v 红( i ) ) 。( g ：+ 彰) 弛( i + 甜。w ) + m ( i + 材。w ) 营邑。( 或一v 红( - ) ，。v + g ) 砒 + 甜。w ) 一v ( i ) + c ( i + 甜。w ) 特别地，对掰= o ，0 w ( o ) ，则有 a ，乓( o ) = f 邑：邑。( 一( i ) + g ? ) a p f ( i ) = 邑一v 6 ( r ) 。+ 酣：邑。或铂( i ) 1 0 ，厂， n 一 利用最优解集的上述性质，我们将得到f ( x ) 在石点处的一阶二阶展开 定理3 2 3 ：若掰u 满足w ( 甜) 彩，则有 f ( i + “。w ) = f ( i ) + g 一v 缟( ；) + g ，甜。+ p ( 陋0 ) 。 证明：由定理3 2 及( 3 1 ) 式， t ) = t ( o ) + ( v t ( o ) ，掰) 。+ o ( i i 铭i i ) 。 = t ( o ) + ( 盛一v 魄( - - ) + 。w ，“) 。+ o ( 1 1 甜眈= ，( i ) + ( 或一v 坞( i ) + 彰，“) 。+ o ( 1 1 材i i ) 。 对w w ( “) ，有 t ( z ，) = 曩( - i + uo w ) 一( 或，砖，+ 万( m 。w 阱( 靠 ，一( 忽( ；) + ( ( i ) ，甜) 。+ 三陬玩，甜) 。) = f ( i + 材。w ) + 红( i + z ，。w ) 一( v 呜( i l 。( 或+ 薛) 加_ 一红( i ) 一丢( 甄面，“) 。( 3 3 ) 因为吃e c 2 , 吃( i + 甜o w ) = ( i ) + ( v 缟( i ) ，“o w ) + d ( 陋o w 0 ) 因此有 ，( i + “。w ) + 缟( i ) + ( v 如( i ) ，“。”+ d ( 0 “w l i ) 一( v 忽( i ) 。( g ：+ 彰) ，“。w ) 一( i ) 一三( 甄诜，甜) 。 = f ( i ) + ( 或- v 吃f f ) + g ：，甜) 。+ o ( 1 1 z ， f ( i + “o w ) = f ( i ) + ( g - v h ：( 2 ) + g ，甜o w ) + d ( 0 甜w i d 定义3 2 1 ：设材使得( z f ) g ，且函数乓( “) 在“= o 处有一个广义h e s s e n 阵，称为函数 f ( x ) 在i 点的群一h e s s e n ，记为风f ( - ) 定理3 2 4 6 1 ：如果f 在i 的“一胁髓p 行阵鼠f ( - ) 存在，并且g r i o ，f ( - ) ，则对于z ，u ，函数 r ( x ) 有如下的二阶展开： f ( i 乜) = f ( i ) + ( 一v 吃( i ) + 矿，x ) + 三( 也f ( 孑) _ “) 。+ 。( m ：) ( 3 4 ) 其中x “+ ( “) ，并且鼠，( _ ) = 且一万r 皿玩，q 是 l l 一类非凸d c 约束优化问题的w 一分解理论 _ g ( “) = 赠 向( i + “。v ) 一吃( i + 材。v ) + 艿( i + “。v i c ) 一( g ，v ) ，) 在0 点的广义h e s s e n 阵 矾驰) 也一( 坼) + v 垤) 。+ 丢( 矿皿玩，“ 。) = f ( ；) + ( 一( i ) + g ”，“) 。+ 丢( 吼f ( ；) 灿) 。+ 咖哟 有( 3 3 ) 及条件吃c 2 知( 3 4 ) 成立 1 2 一类非凸d c 约束优化问题的沙一分解理论 4 总结与展望 本章我们对本文所作的工作进行简短的概括总结，并对与之相关的问题进行进一步的分析，作为 对今后工作的展望 本文在第三章中论述了一类非凸d c 约束优化问题的c 厂y 一分解理论通过对其次微分结构的 研究，我们得到了其u l a g r a n g e 函数，并借助与u l a g r a n g e 的展开式得到函数在切于u 空间 的某个轨道上的二阶展开式对于d c 函数在非凸集合的约束优化问题本文并没有讨论，但是这类优 化问题是广泛存在的，还需进一步研究 1 3 一类非凸d c 约束优化问题的w 一分解理论 参考文献 【1 j p a u b i n , c o n t i n g e n td e r i v a t i v e so fs e t - v a l u e dm a p sa n de x i s t e n c eo fs o l u t i o n st on o n l i n e a ri n c l u s i o n s a n dd i f f e r e n t i a l e q u a t i o n s ，m a t h e m a t i c a la n a l y s i sa n da p p l i c a t i o n s ( l n a c h b i n , e d ) ，a c a d e m i c p r e s s ，l9 8 1 ，1 5 9 2 2 9 【2 】j - b h i r i a r - u r r u t y , an e ws e t - v a l u e ds e c o n do r d e rd e r i v a t i v ef o rc o n v e xf u n c t i o n s ，f e r m a td a y s 8 5 ：m a t h e m a t i c sf o r o p t i m i z a t i o n( j b h i r i a r - u r r u t y , e d ) ，m a t h e m a t i c s s t u d i e s ，1 2 9 n o r t h - h o l l a n d ，1 9 8 6 ，1 5 7 1 8 2 【3 】b s m o r d u k h o v i c h , g e n e r a l l i z e dd i f f e r e n t i a lc a l c u l u sf o rn o n s m o o t ha n ds e t - v a l u e dm a p p i n g sj o u r n a l o fm a t h e m a t i c a la n a l y s i sa n da p p l i c a t i o n s18 3 ( 1 ) ，19 9 3 ，2 5 0 - 2 8 8 【4 】r a p o l i q u i n ，p r o t o - d i f f e r e n t i a t i o n o f s u b g r a d i e n ts e t v a l u e dm a p p i n g s ，c a n a d i a nj o u r n a lo f m a t h e m a t i c s ，4 2 ( 3 ) ，1 9 9 0 ，5 2 0 - 5 3 2 【5 】j b h i r i a r - u r r u t y , m i s c e l l a n i e s o nn o n s m o o t h a n a l y s i sa n do p t i m i z a t i o n ，n o n d i f f e r e n t i a b l e o p t i m i z a t i o n ：m o t i v a t i o n s a n da p p l i c a t i o n s ，v e d e m y a n o va n dd p a i l a s c h k e ，e d s ，l e c t u r e n o t e si n e c o n o m i c s a n dm a t h e m a t i c a ls y s t e m s ，s p r i n g e r - v e r l a g ，b e r l i n ，2 2 5 ，19 8 5 ，8 - 2 4 【6 】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 ，j o h nw i l e ys o n s ，n e wy o r k , 19 8 3 【7 r t r o c k a f e l l a r , g e n e r a l i z e ds e c o n dd e r i v a t i v e so fc o n v e xf u n c t i o na n ds a d d l ef u n c t i o n s ，t r a n s a c t i o n so f t h e a m e r i c a nm a t h e m a t i c a ls o c i e t y , 3 2 2 ( 1 ) ，1 9 9 0 ，5 1 - 7 8 【8 】t f c o l e m a na n da r c o n n ，n o n l i n e a rp r o g r a m m i n gv i aa l le x a c tp e n a l t yf u n c t i o n ：a s y m p t o t i ca n a l y s i s ， m a t h e m a t i c a lp r o g r a m m i n g2 4 ，1 9 8 2 ，1 2 3 - 1 3 6 【9 】m j d p o w e r , t h ec o n v e r g e n c eo fv a r i a b l em e t r i cm e t h o d sf o rn o n l i n e a r l yc o n s t r a i n e do p t i m i z a t i o n c a l c u l a t i o n s , n o n l i n e a rp r o g r a m