（基础数学专业论文）lipschitz函数的极小化理论与统一算法.pdf

摘要 本文主要研究目标函数和约束函数都是局部l i p s c h i t z 函数的非光滑最优 化问题内容涉及到局部l i p s c h i t z 函数的广义不变凸性，集值映射的广义单调 性，在没有任何约束规格条件下的各种非光滑最优化问题的最优性充分条件和 必要条件，混合对偶理论，l a g r a n g e 鞍点理论以及非光滑单目标优化问题的非 单调线搜索算法和信赖域算法分四部分介绍如下： 一、局部l i p s c h i t z 函数的广义不变凸性和集值映射的广义单调性 利用j e y a k u m a r 和l u c 给出的局部l i p s c h i t z 函数的j l 次微分( 也称为 c o n v e x i f i c a t o r ) 的定义，引入了非光滑的广义( 严格) 不变拟凸函数和广义( 严格) 不变伪凸函数以及集值映射的广义( 严格) 不变拟单调性和广义( 严格) 不变伪 单调性，研究了广义不变凸性与广义不变单调性之间的关系，特别地，分别建立 了一个局部l i p s c h i t z 函数的不变拟凸性和它的j l 次微分映射的不变拟单词 性之间的充分必要条件，以及一个局部l i p s c h i t z 函数的( 严格) 不变伪凸性和 它的j l 次微分映射的( 严格) 不变伪单调性之间的充分必要条件 二、非光滑最优化问题的最优性条件，混合对偶理论以及l a g r a n g e 鞍点理 论 不需要任何约束规格条件，建立了非光滑数学规划的一阶最优性充分必要 条件，以此为基础建立了几类非光滑最优化问题的混合对偶规划，并且在没有任 何约束规格条件下证明了弱对偶定理，强对偶定理以及l a g r a n g e 函数的鞍点存 在性定理对于极小极大分式规划和凸的广义极小极大分式规划，分别建立了 它们的混合对偶规划该对偶规划统一了著名的m o n d - w e i r 对偶模型，w o l f e 对偶模型和参数对偶模型基本上解决了由l “、l i u 和t a n a k a 在1 9 9 9 年提 出的两个问题 三、非光滑最优化问题的非单调线搜索算法 把强制函数应用于非单调线搜索技术，并且把该技术应用到目标函数是局部 l i p s c h i t z 函数的非光滑无约束最优化问题的研究中去，得到了一个非单调线搜 索方法的一般框架，并且建立了该方法的全局收敛性结果作为特殊情况，可以得 到非光滑无约束最优化问题的线搜索算法的广义a r m i j o - 准则，广义g o l d s t e i n 一 准则和广义w o l r e - 准则 四、非光滑最优化问题的非单调信赖域算法 研究了无约束非光滑最优化问题的非单调信赖域算法模型算法中所解的 2 信赖域子问题是q i 和s u n 在 47 】中研究的，子问题含有一个迭代函数，因此 具有般性一方面，我们将非单调技术用于q i 和s u n 的信赖域算法，给出了 一个非光滑无约束极小化问题的一个非单调信赖域算法，并且证明了该算法是 整体收敛的非单调信赖域算法可以保证，当迭代点进入弯曲的峡谷中时，算法 有较好的收敛速度但是，对此非单调信赖域算法我们只能证明。由算法产生的 迭代点列中存在个聚点是稳定点的收敛性质因此，我们采用t o i n t 的思想对 算法进行了改进，给出了问题( p ) 的个修正的非单调信赖域算法，该算法有 较好的收敛性质，由该算法产生的迭代点列中每一个聚点都是一个临界点另 一方面，在同样的假设条件下，我们给出一个问题( p ) 的半径有下界的信赖域 算法这个算法是也是一个标准的信赖域算法，唯一的区别在于成功迭代后的 信赖域半径的修正，算法选择了一个较小的半径“。做为新的半径的下界另 外，我们用传统的方法给出算法的收敛性证明 最后，我们用类似的方法研究了l c l 问题，即目标函数的梯度v ，是一个 局部l i p s c h i t z 函数通过解孙文瑜等人用二阶d i n i 方向导数建立了的一种新 的信赖域子问题，给出了一个l c l 问题的一个非单调信赖域算法，并且证明了 该算法是整体收敛的 关键词j l 次微分，广义不变凸函数，广义不变单调集值映射，非光滑规 划，混合对偶，极小极大分式规划，非单调线搜索算法，非单调信赖域算法 a b s t r a c t i nt h i st h e s i s ，w es t u d yt h en o n - s m o o t h o p t i m i z a t i o np r o b l e mw h e r et h eo h - j e c t i v ef u n c t i o na n dc o n s t r a i n e df u n c t i o n sa r ea l ll o c a l l yl i p s c h i t z i a nf u n c t i o n s t h et h e s i si n c l u d e st h eg e n e r a l i z e d i n v e x i t y o fl o c a l l yl i p s c h i t z i a n f u n c t i o n s ： t h eg e n e r a l i z e di n v a r i a n tm o n o t o n i c i t yo fs e t v a l u e m a p sa n dt h er e l a t i o n s h i p s b e t w e e nt h eg e n e r a l i z e di n v a r i a n tm o n o t o n i c i t yo fc o n v e x i f i c a t o r sa n dt h eg e n e r a l i z e di n v e x i t yo fn o n s m o o t hf u n c t i o n s ；t h eo p t i m m i t y n e c e s s a r ya n ds u f f i c i e n t c o n d i t i o n sf o rn o n - l i n e a rp r o g r a m m i n g sw i t h o u tac o n s t r a i n tq u a l i f i c a t i o n ；m i x e d d u a lt h e o r y ；l a g r a n g es a d d l ep o i n tt h e o r y ；n o m n o n o t o n el i n es e a r c hm e t h o d sf o r n o n s m o o t hu n c o n s t r a i n e do p t i m i z a t i o n ；n o n m o n o t o n et r u s tr e g i o nm e t h o d sf o r n o n s m o o t hu n c o n s t r a i n e do p t i m i z a t i o n u s i n gc o n v e x i f i c a t o r sa n di n v e xf u n c t i o n si n t r o d u c e db yj e y a k u m a re ta 1 a n dh a n s o n ，r e s p e c t i v e l y ，t h eg e n e r a l i z e dc o n v e x i t yo fn o n s m o o t hf u n c t i o n sa n d g e n e r a l i z e dm o n o t o n i c i t yo fs e t v a l u e dm a p sa r ef u r t h e re x t e n d e d t h er e l a t i o n s h i p sb e t w e e nt h eg e n e r a l i z e di n v a r i a n tm o n o t o n i c i t yo fc o n v e x i f i c a t o r sa n dt h e g e n e r a l i z e di n v e x i t yo fn o n s m o o t hf u n c t i o n sa r ee s t a b l i s h e d w i t h o u ta n yc o n s t r a i n tq u a l i f i c a t i o n ，w ee s t a b l i s ht h ef i r s t o r d e ro p t i m a l i t y n e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o rn o n s m o o t hs c a l ep r o g r a m m i n g ，m u l t i o b j e c t i v ep r o g r a m m i n ga n dm i n m a xf r a c t i n a lp r o g r a m m i n gi n v o l v i n gp s e u d o i n v e xf u n c t i o n s ，w h i c hg e n e r a h z e st h e e x i s t i n gr e s u l t s o nt h e o t h e rh a n d ，w i t h o u t t h en e e do fac o n s t r a i n tq u a l i f i c a t i o n ，w ee s t a b l i s ht h e n e c e s s a r ya n d s u f f i c i e n to p - t i m a l i t yc o n d i t i o n sf o rg e n e r a l i z e df r a c t i o n a lp r o g r a m m i n gi n v o l v i n gac o m p a c t s e t u s i n gt h e s eo p t i m a l i t yc o n d i t i o n s w ec o n s t r u c t ap a r a m e t r i cd u a lm o d e l a n dap a r a m e t e r f r e em i x e dd u n lm o d e l ，t b i sm i x e dd u a lm o d e lu n i f i e st w od u n l p a r a m e t e r - f r e em o d e l sc o n s t r u c t e db yl a ia n dl i ue ta l s e v e r a ld u a l i t yt h e o - r e m sa r ee s t a b l i s h e d t h en o n m o n o t o n el i n es e a r c hm e t h o d sh a v eb e e ns u c c e s s f l f l l yu s e di ns m o o t h u n c o n s t r a i n e do p t i m i z a t i o na n dc o n s t r a i n e do p t i m i z a t i o n c o m b i n i n gt h ef o r e - i n gf u n c t i o n sw i t ht h en o n m o n o t o n e l i n es e a r c ht e c h n i q u e ，w ep r e s e n tag e n e r a l f r a m e w o r ko fn o n m o n o t o n el i n es e a r d hm e t h o d sf o rt h en o n s m o o t hu n c o n s t r a i n e d o p t i m i z a t i o np r o b l e m sw h e r e t h eo b j e c t i v ef u n c t i o ni sa l o c a l l yl i p s c h i t z i a nf u n c 4 t i o na n de s t a b l i s ht h e g l o b a lc o n v e r g e n c er e s u l t s a ss p e c i a lc a s e s ，w ec a no b t a i t h en o n s m o o t hn o n m o n o t o n e a r m i j or u l e ，g o l d s t e i nr u l ea n dw o l f er u l e c o m b i n i n gt h et r u s tr e g i o na l g o r i t h mo fq ia n ds u nw i t ht h en o n m o n o t o n et e c h n i q u e ，w ep r e s e n tan o n m o n o t o n et r u s tr e g i o n a l g o r i t h mf o rt h ea n c o n s t r a i n e dn o n s m o o t ho p t i m i z a t i o np r o b l e m sw h e r et h eo b j e c t i v ef u n c t i o ni s l o c a l l yl i p s c h i t z i a n ，a n dp r o v et h a to n rn o m n o n o t o n et r u s tr e g i o na l g o r i t h mi s g l o b a l l yc o n v e r g e n t k e y w o r d sc o n v e x i f i c a t o r s l g e n e r a l i z e di n v e x i t y ，g e n e r a l i z e di n v a r i a n t m o n o t o n i c i t y , n o n - s m o o t h0 p t i m i z a t i o n ，m i x e dd u a l i t y , m i n i m a xf r a c t i o n a l p r o g r a m m i n g ，n o n m o n o t o n el i n es e a r c ha l g o r i t h m ，t r u s tr e g i o na l g o r i t h m 本人郑重声明： 学位论文独创性声明 y6d2 3 5 6 】、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表 或撰写过的研究成果。 5 、其他同志对本研究所傲的贡献均已在论文中作了声明并表示了谢意。 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版；有权 将学位论文用手非赢利目的的少量复制并允许论文进入学校图书馆被查阅；有 权将学位论文的内容编入有关数据库进行检索：有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 作者签名： 日期： 碰 趔啤! 丝客 第一章概述 1 1 引论 随着时代的发展，许多科学研究与工程实际中产生的优化问题的变量越来 越多。规模越来越大，常常出现函数不可微( 没有导数) 在这种情形下，一般的 优化方法就显得无能为力尽管由于计算机技术的发展，对于函数性态非常好 的优化问题，已经有处理大规模最优化问题的有效实用的算法和应用软件，但 是当函数的性态不好时( 例如函数不可微) ，只能用逼近或近似的方法，而不能直 接计算非光滑优化问题的计算一直是个难度很大的课题，有效的算法不多事 实上，非光滑问题的优化理论也不是非常系统和完善，因此，研究解非光滑优化 问题的理论与算法就显得十分必要 非光滑问题的优化理论的研究主要集中在函数的各种广义凸性的性质的研 究，各种广义凸性的刻戈，函数的各种广义次梯度的运算，各种广义次微分的结 构，用广义次微分来表示的非光滑优化问题的最优性充分条件和必要条件，非 光滑优化问题的各种对偶问题，l a g r a n g e 乘子条件，鞍点理论，以及各种广义 凸性，各种广义次梯度，非光滑优化问题的最优性，各种对偶问题，l a g r a n g e 乘子条件和鞍点理论这些概念和问题之间复杂的相互关系 众所周知，函数的凸性在数学规划的研究中起着非常重要的作用，但是， 科学研究与工程实际中产生的大量的最优化问题都不是凸规划为了研究非凸 规划，解非凸规划，需要削弱凸性条件。为此，人们定义了各种类型的广义凸 性，例如( 严格) 拟凸，( 严格) 伪凸，( 严格) 广义拟凸，( 严格) 广义伪凸，( 严 格) ( 只p ) 一广义拟凸，( 严格) ( f ，p ) - 广义伪凸，( 严格) 不变拟凸，( 严格) 不变 伪凸，对可微函数和l i p s c h i t z 函数，分别用函数的梯度或函数的广义次梯度， 将各种凸性进行了描述和刻划详见( 【1 】【2 】【3 】【4 】【5 】f s l 7 i s 【9 】 i 0 1 1 】【1 2 】【1 3 ) 尽管各种广义凸函数的研究已经有几十年的历史，但由于广义凸函数在数 学的许多领域有着广泛的应用所以各种广义凸函数的研究和应用仍然是一个 热点。近几年出现的大量的这方面的参考文献就是一个很好的证明 对于非线性规划的对偶问题，m o n d 和w e i r 最早建立了m o n d - w e i r 型 对偶规划，w o l f e 1 4 建立了w o l f e 型对偶规划从此，有大量的文献( 例如。 f 1 5 1 f 1 6 】【1 7 1 1 8 1 【1 9 h 2 0 1 【2 l 】) 分别对于单目标规划，多目标规划，分式规划，极小 南京师范大学博士论文l i p s c h i t z 函数的极小化理论与统一算法 2 极大规划等数学规划，在各种不同条件下研究了这两种对偶模型，在一定的约 束规格下建立了弱对偶定理，强对偶定理，严格逆对偶定理等， 1 9 8 1 年，在没有任何约束规格条件下，b e n - i s r a e l ，b e n 一，工u 和z l o b e c ( | 2 2 1 ) 对单目标凸规划给出了一阶最优性充分必要条件；1 9 9 2 年，e g u d o ，w e i r ，和 m o n d ( 1 2 3 ) 对多目标凸规划给出了一阶最优性充分必要条件；m o n d ，z l o b e c ， w e i r ，和e g u d o 等人( 【2 4 】 2 5 】 2 6 】 2 7 j ) 利用他们给出的这些一阶最优性充分必要 条件，不需任何约束规格，建立了单目标或多目标凸规划的若干对偶问题当 有一定的约束规格条件成立时，他们讨论的问题和得到的结论则退化为一般情 形其中涉及到的目标函数和约束函数或者是不可微的凸函数。或者是可微的 伪凸函数由于该条件的限制，关于不需约束规格的优化问题的研究，近几年没 有什么进展 最近，l 出，l i u 和t a n a k a ( 1 2 8 j ) 利用c r o u z e i x ( 1 2 0 ) ) 和b e n - i s r a e l ( j 2 2 ) 等 人的结果，不需任何约束规格，得到了极小极大分式规划的一阶最优性充分必 要条件，并且建立了极小极大分式规划的一个参数对偶模型和两个无参数的对 偶模型，所涉及到的目标函数和约束函数仍然是不可微的凸函数另外，他们在 文章的最后提出了三个没有解决的问题 非线性规划的算法基本分为两大类，即线搜索方法和信赖域方法线搜索方 法包括精确一维线搜索和不精确一维线搜索精确维线搜索方法往往需要花 费很大的工作量，特别是当迭代点远离问题的最优饵时，精确地求解一个一维子 问题通常不是十分有效因此，在很多最优化算法中经常采用不精确一维线搜 索常用的不精确一维线搜索有三种，即分别采用a r m i j o - 准则，g o l d s t e i n - 准 则和w o l f e - 准则的不精确一维线搜索近几年，非单调线搜索技术已被成功地 应用于连续可微的约束最优化和无约束最优化闻题的算法中( 参见 2 9 ，3 0 ，3 1 ， 3 2 ，3 3 ，3 4 1 ) 最近，孙文瑜，韩继业和s u nj i e 【3 5 和d a iy u h o n g 3 3 各自独立 地提出了光滑无约束极小化问题的一个统一的非单调下降算法，特别地，孙文 瑜，韩继业和s u nj i ef 3 5 把强制函数应用于非单调线搜索技术，给出了一个一 般的线搜索准则( 即f 准则) ，该准则统一了著名的a r m i j o - 准则， g o l d s t e i n - 准则和w o l f e - 准则这有利于讨论线搜索方法的全局收敛性 近年来。迅速发展起来的解最优化问题的信赖域方法( 3 6 1 3 7 1 3 8 3 9 4 。舞( z ，”) 定义2 3 i s l 称函数，：r “一r u 。) 在t r “点有一个j - l 次微分 扩，( 。) ，如果a ，( z ) 既是，在z 点一个上 三次微分，也是，在z 点一个下 j l 次微分 如果，在z 点有一个，一l 次微分，我们总用扩，( z ) 来表示，在这种情况 下，集合扩f ( z ) 被称为，在z 点的( j e y a k u r n a r l u c ) 次微分。筒记为j l 次微分【5 3 】- 定义2 4 p 纠称函数，：册一r u o 。) 在z 舻点有一个上半i f - nj l 次微分a ，( z ) ，如果伊，( z ) cr “是一个闭集，并且对于每一个方向u r “， 都有： 疗( z ， ) ss u p ( z + ， ) ， ? a 。， z j 如果在上面的不等式中等号成立，则称集合扩s ( x ) 是，在z 点的一个正则j l 次微分 下一节我们需要由j e y a k u m a r 和l u c 5 1 】、w a n g 和j e y a k u m a r 【5 3 】给出 的中值定理、最优性必要条件和j l 次微分运算的链式法则， 定理2 1 卢叫设d ，b r ，函数，：兄“一r 是一个连续函数如果 对于每一个x ( o ，6 ) ，0 ，( z ) 和良，( z ) 分别是，在z 点一个上j 一工次 微分和一个下j l 次擞分那么，一定存在c ( o ，b ) 和一个点的序列： ( z ：) cc 0 ( 扩，( c ) ) uc 0 ( a ，( c ) ) 使得t ，( 6 ) 一( a ) = ，1 i 巴( z ：，b o ) 南京师范大学博士论文l i p s c h i t z 函教的极小化理论与纯一算法8 定理2 2 p 假设函数，在z 点有一个l ，一l 次徽分扩f ( x ) 如果，在 。点达到极小值，那么： 0 茚( 矿，( z ) ) 定理2 ，3 芦剐设函数，：只“一只是一个局部l 妇s c h i t z 函数，f ：r t l 一r “ 在z 点是g s t e a u x 可微的如果护，( z ) 是，在z 点的一个j l 次微分，那 么：0 + ，( f 扛) ) v f ( z ) 是复合函数，。f 在z 点，一l 次徽分 2 2 不变拟凸函数和不变拟单调集值映射 在这一节，我们将引进不可微的不变拟凸函数和不变拟单调集值映射，并 且用不可微函数的j l 次微分构成的集值映射的不变拟单调性去刻划它的不 变拟凸性 下面的拟单调集值映射是p e n o t 和s a c h 在 7 】中给出的 定义2 5 俐称集值映射f ：尼一2 舻是一个拟单调集值映射，如果对于 任意的茁，y r ”，z y ，都有： 弓z + f ( z ) ，。4 ，y z ) 0 鲁 v y + f ( 萝) y + ，y 一譬) 三。 现在我们给出不变拟单调集值映射的定义 定义2 6 称集值映射f ：r f 一2 ”是一个与1 有关的不变拟单调集值映 射r 以下简称为不变拟单调集值映射，如果存在函数q ：尼r “一r ”，对于任 意的z ，g 彤，z y ，都有： 3z + f ( 卫) ， ( 正+ ，叩( ，z ) ) 0 茸 s u p c y + ，叮( z ，) ) jy + f ( ) ) 0 对于集值映射f ：即一即，它的凸包集值映射c o f 定义为： c o f ( x ) = c d ( f 0 ) ) 关于集值映射f 的凸包集值映射c o f ，我们有下面的结论： 引理2 1 设f ：碍一只。是一个集值映射，那么，f 是一个与q 有关的不 变拟单调集枉映射，当且仅当c o f 也是一个与q 有关的不变拟单调集值映射 证明；因为 f ( x ) cc o f ( z ) ， vz r ” 第二章广义不变凸函数和广义不变单调集值映射 9 明显地，如果c o f 是一个与1 有关的不变拟单调集值映射，则一定能推出f 是 一个与q 有关的不变拟单调集值映射 反过来，假设f 是一个与q 有关的不变拟单调集值映射，我们要证明c o f 也是一个与1 有关的不变拟单调集值映射用反证法，假如存在点z ；ec o f ( z ) ( z ；，q ( 扒z ) ) 0 ，但是却有 s u p ( y ，q ( z ，) ) ly c o f ( y ) 0 那么一定存在y c o f ( y ) ，使得： ( y ，( 。，9 ) ) 0 由此可知：存在y i f ( ) ，i = 1 ，m ，凡0 ，a 。= 1 使得 y + = a ；酊a 。( 计，q ( z ) ) 0 因此，存在一个下标j 1 2 - ，m ) ，使得 ( 掣；，叩( z ，可) ) o 因为f 是一个与q 有关的不变拟单调集值映射，所以有 s u p ( z ，q ( g ，z ) ) i 。f ( z ) 0 由此可得 ( z + ， ( 9 ，z ) s0 ，vz + f ( z ) y - n 为z ；c o f ( x ) ，所以存在。；f ( 。) ，i = l ，m 和胁0 ，e “= 1 使得 x ；= 雎z ： 因此 m ( z ；，1 ( ，z ) ) = 地( ；，q ( ，z ) ) 0 ， = l 这与( z 玉n ( y ，z ) ) 0 矛盾因此， c o f 是一个与q 有关的不变拟单调集值映 射 下面的不变拟凸函数的概念最早由p i n i 【1 0 】引入，并且m o h a n 【1 1 】和 y a n g l 2 1 等人对不变拟凸函数作了非常深入的研究 南京师范大学博士论文l i p s c h i t z 函数的极小化理论与统一算法1 0 定义2 7 口纠称函数，：彤一r 是一个与q 有关的不变拟凸函数r 以 下简称为不变拟凸函数 如果存在一个函数h ：舻xr “一彤，对于任意的 t ，y r ”，a 0 ，1 ，都有 c 有 s ( y + 加( 。，) ) m a x f ( x ) ，( ) ) ( 2 1 ) 在下面定理的证明中，我们要用到文章 2 】和 1 l 】提出的假设a 和假设 假设a 2 】设，：舻一r 则有 f ( y + q ( z ，g ) ) f ( x ) ， vz ，y r “ 假设c 2 ，1 1 设q ：r “r “一r “则对于任意的。，y r “和a 0 ，1 目( ，y + a q ( z ，g ) ) = 一 q ( 。，y ) 1 ( z ，y + a q ( ，g ) ) = ( 1 一a ) q ( z ，y ) 明显地，当t ( x ，y ) = x y ，时，假设c 成立，容易验证，下面两个q 函数 满足假设c 例2 1 2 】设集合岛= 一2 ，2 l ，函数q 定义为 q ( z ，y ) = z 0 ，y 0 z 0 咖朋= 萎雾 在假设a 和假设e 成立的条件下。我们得到了下面的定理，该定理给出 了与j l 次微分概念有关的非光滑的不变拟凸函数的一个等价描述 当当当当 玑玑y 玑 卜一* 卜 ，j【 第二幸广义不变凸函数和广义不变单调集值映射 1 1 定理2 4 设函数，：口一r 是一个连续函数，并且在彤点有一个上 半正则工l 次微分扩，( ) ，如果存在函数q ：f p 碍1 一即，并且满足假设c 那么，是一个不变枞凸函数，当且仅当对任何一对z ，er “，都有 ，( ) f ( x ) = ： s u p ( z ，q ( z ) ) lz a + ，( z ) ) 兰0 ( 2 2 ) 证明：( 必要性：) 假设，是一个不变拟凸函数，并且有s ( y ) ，( z ) ，根据 定义2 7 ，我们有 ，( z + 蛔( ，z ) ) ，( z ) v 0 ，1 因此 付扛，q ( y ，z ) ) = l i ms u p ，( $ + a q ( 9 ，z ) ) 一，扣) 】a o _ 0 + 因为扩，( z ) 是，在z 点的一个上半正则j l 次微分，所以有 ，乒( z ，q ( p ，z ) ) = s u p ( z 。，q ( ，。) ) = d ，( o ) 由此可以推出 s u p ( z ，砷( y ，z ) ) 1z + a ，( 。) ) so ( 充分性：) 用反证法如果，不是不变拟凸函数，则一定存在一对点。，y 彤，( 。) ，( 口) ，和数a l ( 0 ，1 】，使得 f ( y + a l q ( z ，) ) ，( ) 兰，( 。) 由条件( 22 ) 可得下面两个不等式： s u p ( n ，1 ( ，y + 1 1 ( z ，9 ) ) ) l + a ，( + a 1 q ( t ，g ) ) s0 ， s u p ( d ，q ( z ，+ a l q ( z ，g ) ) ) lo ea ( v + a l q ( z ，) ) 0 因此 ( a ，玎( ，v + a l 叩( z ，) ) ) so ， va ，( 十a t 叼( z ，可) ) ， ( a ，口( 。，v + a l q ( z ，y ) ) ) 墨o ，v8 a + ，( 口+ a l q ( z ，y ) ) 根据假设c ，我们有 一a 1 ( n ，”( z ，) ) s0 ， va a ，( v + , x t r ( z ，口) ) ( 1 一a 1 ) ( d ，目( z ，) ) s0 ，v + 矿，( y + l q ( z ，g ) ) 南京师范大学博士论文l i p s c h i t z 函数的极小化理论与境一算法 1 2 由此立得 ( 口，q ( z ，) ) = 0 ，可a 4 o f ( y + l q ( z ，g ) ) 根据凸包的定义，明显地有 ( a ，q ( z ，) ) = 0 ， va + c o o f ( y + a l q ( 。，) ) 另外，根据，的连续性，我们能够找到数a l 和a 2 ，0 a 2 f ( y ) ， ，( y + a 2 叼( z ，可) ) = ，( 可) ， 由中值定理2 1 知：存在a 3 ( 2 ， 1 ) ，n ：c o o f ( v + 3 v ( x ，) ) ，使得 0 0 s “p ( z ，口( ，z ) ) jz + a + ，( z ) ) 0 f ( y ) ，( z ) 第二幸 广义不变凸函数和广义不变单调集值映射1 3 再由( 2 2 ) 式以及，( z ) o ( ，口( p + a 2 v ( z ，) ，y + a i 口( x ，) ) ) o ， s u p ( 掣+ ，叼( 可+ a l 叩( z ，掣) ，y + a 2 叩( z ，y ) ) ) iy c o o f ( y + a 2 叼( z ，掣) ) 0 ， 这与c o ( 伊f ) 的不变拟单调性矛盾 推论2 1 卢刃设，：月”一r 是一个连续函数，f 在每个点z r ”处都有 有界的上半正则 l 次微分扩，( z ) 如果伊，是不变拟单调映射，那么，是不 变拟凸函数 证明：取q ( z ，y ) = z y ，容易验证假设c 成立，那么，该结论可直接由定 理25 推出 推论2 2 俐设f ：口1 一j r 是一个可擞函数，如果q 满足假设c ，那么， ，是一个与q 有关的不变拟凸函数，当且仅当v ，是一个不变拟单调映射，并 且对任意的z ，y r “，都有 l ( y ) f ( z ) = = ，( p + q ( z ，) ) ，( z ) 证明：医为，是一个可微函数，那么护，( 。) = v ，( ) ) 就是，的一个有界 的上半正则j - l 次微分。那么，该结论可直接由定理2 5 推出 2 3 不变伪凸函数和不变伪单调集值映射 在本节中，我们将引进不可徽的不变伪凸函数和不变伪单调集值映射，并 且用不可微函数的j l 次微分构成的集值映射的不变伪单调性去刻划它的不 变伪凸性，所得到的结果是已有相应结果的推广 下面的伪单调集值映射是p e n o t 和s a c h 在 7 中给出的 第二章广义不变凸函数和广义不变单调寨值映射1 9 推论2 3 肛习设f ：r “一r 是一个连续函数，在每个点。r r 处都有 有界的上半正则 l 次擞分扩，( z ) 如果o s 是不变伪单调映射，那么f 是不 变伪凸函数 证明取1 ( z ，y ) = z y ，容易验证假设c 成立，那么，该结论可直接由定 理2 7 推出 推论2 4 ，2 设f ：r ”一r 是一个可徽函数，如果，和q 分矛】满足假设 a 和假设c ，那么，是一个与q 有关的不变伪凸函数，当且仅当v ，是一个 不变拟伪单调映射。并且对任意的z ，y 冗n ，都有 f ( y ) sf ( x ) = ：= f ( y + q ( z ，) ) ，( z ) 证明t 因为，是一个可微函数。那么护f ( x ) = v f ( x ) 就是，的一个有界的 上半正则j l 次微分，那么，该结论可直接由定理27 推出 2 4 严格不变伪凸函数和严格不变伪单调集值映射 在本节中，我们将引进不可微的严格不变伪凸函数和严格不变伪单调集值 映射，并且用不可微函数的j l 次微分构成的集值映射的严格不变伪单调性去 刻划它的严格不变伪凸性，所得到的结果是已有相应结果的推广 下面我们首先给出严格不变伪凸函数和严格不变伪单调集值映射的定义 定义2 1 1 称集值映射f ：f p 一2 r t 是一个与q 有关的严格不变伪单调集值 映射似下简称为严格不变伪单调集值映射j ，如果存在函数q ：尼r ”一r “， 对于任意的z ，y 舒，z y ，都有 lz f ( z ) ，( z + ，q ( ，z ) ) 0 = = s u p ( y 4 ，口( 。，) ) | y + f ( g ) ) ，( z ) ( 2 2 3 ) 南京师范大学博士诧文l i p s c h i t z 函数的极小化理论与统一算法 2 0 我们给出下面的定理，该定理用函数，的j l 次微分构成的集值映射的严 格不变伪单调性去刻划函数的严格不变伪凸性 定理2 8 设函数，：r t 。一月是一个连续函数，并且在每一点z r ”处 都有有界的上半正则 l 次徽分扩，( z ) ，如果f 和函数q ：r “f p r r 分 别满足假设a 和假设c ，那么，是严格不变伪凸的当且仅当它的 三次微 分扩- 厂是一个严格不变伪单调集值映射 证明：( 必要性：)假设，是一个严格不变伪凸函数，且有z ，g r “t y 和j 扩，( z ) ，满足( 矿，1 ( ，z ) ) 0 ，则有 s u p ( z ，q ( ，z ) ) iz + ea ，( z ) 0( 22 4 ) 根据，的严格不变伪凸性，我们有 f ( y ) ，( z ) 如果有如下不等式 s u p ( y 。，q ( z ，g ) ) iy + ，( ) 20 ， 成立，同样也是根据，的严格不变沩凸性，可以得到：，( z ) ，( ) ，这是一个 矛盾因此一定有 s u p ( ( + ，q ( z ，f ) ) 】y a ，( ) ) ，( z ) 否则，假设有 ，( p ) s ，( z )