1. 引言
Tilt扰动下局部极小值的稳定性研究起源于Poliquin和Rockafellar的开创性工作 [1],并在近二十年受到众多学者的广泛关注。特别的,在2008年,Artacho和Geoffroy在Hilbert空间中首次证明了凸函数f在某点有稳定二阶强局部极小值当且仅当
在该点是强度量正则的 [2]。随后,在目标函数是次微分连续且prox-正则的非凸假定下,Drusvyatskiy和Lewis在有限维空间中证明了f在某点有稳定二阶强局部极小值等价于f在该点有tilt-稳定局部极小值等价于
在该点是强度量正则的 [3]。最近,有限维空间中的结果被拓展到无限维的Banach空间或Asplund空间中 [4] [5]。最初考虑的二阶问题也被郑喜印等人拓展至q阶以及所谓的
阶情形 [6] [7] [8] [9],此处
是admissible函数。回顾函数
被称为admissible的,若它是非减函数,满足
且有
。以上工作研究了目标函数受tilt扰动后局部极小值点的不同稳定性行为,并已经形成了较为完备的结果。这些稳定性行为的研究对于算法的调整,特别是停机准则和收敛性分析有重要意义 [1] [4] [5]。直至2021年,文献 [10] 首次考虑了集值映射的全局度量正则性和稳定的全局极小值,并将一系列局部定义拓展至如下的全局定义。
定义1.1:设
均是Banach空间,
均是admissible函数,F是X到Y的集值映射,
是真下半连续函数。
1) F在
处被称为全局
-度量正则的(全局
-pseudo-度量正则的),若存在
使得
如果额外有
是单值,则F在
处被称为全局强
-度量正则的(全局强
-pseudo-度量正则的)。
2) f被称为有稳定全局
-适定性,如果存在
以及单值映射
使得
3) f被称为有
-tilt-稳定全局极小值,如果存在
使得对于任意的
,
是单值且满足
其中
表示扰动后的函数
的全局解集映射,即
文献 [10] 研究了稳定全局适定性、tilt-稳定全局极小值和次微分
的两种全局度量正则性之间的联系。在目标函数f是凸的假定下,其得到如下结果(参考文献 [10],定理3.4和3.5):
定理A 设
是admissible函数,
,
,
,则f有稳定全局
-适定性当且仅当
在0处是全局强
-度量正则的。
定理B 设
是严格递增的admissible函数,
,
,
,则f有稳定全局
-tilt-稳定全局极小值当且仅当
在0处是全局强
-pseudo-度量正则的。
但相较于局部情形下丰富的研究成果,文献 [10] 中的工作还存在着一些留白。一方面,文献 [10] 仅在目标函数为凸的假定下探究了稳定全局极小值和次微分的全局度量正则性的联系。另一方面,它并没有考虑与次微分相结合的一致增长条件——极小值的另一种稳定性行为(参考文献 [7],定义3.2)。在局部情形时,姚等人 [8] 在2017年将函数的prox-正则性定义扩充至
-正则性,并把 [9] 中的相关凸性结果推广至目标函数f是
-正则的非凸情形。受此启发,我们把函数的
-正则性定义拓展至了全局情形,提出连续全局
-正则函数的定义,并把定理A拓展至目标函数是连续全局
-正则的非凸情形。同时,我们把一致增长条件的定义也拓展至全局情形。类比局部视角下的相关结果 [4] [7],我们探究了全局一致增长条件和次微分的度量正则性以及其它稳定全局极小值之间的联系。对于那些在局部情形向全局情形拓展中丢失的性质,我们给出了反例进行证伪。
本文的剩余部分结构如下。在第二章,我们回顾了我们用到的变分分析中的一些定义和定理。在第三章,我们把集值映射线性开性的定义拓展到全局
-开性,并建立了全局
-开性和全局
-度量正则性之间的等价关系。该结果补充了( [10],命题2.5)所建立的等价关系,同时也可看做( [11],定理5A.3)在全局和高阶情形的拓展。在第四章,我们给出了连续全局
-正则函数的定义,并证明了定义在X上的
-仿凸函具有连续全局
-正则性。在目标函数是连续全局
-正则的或
-仿凸的假定下,我们将定理A推广至非凸情形。在第五章,我们给出了函数f有一致全局增长条件的定义,并讨论了它和稳定全局适定性之间的联系。同时,我们发现若扰动后的函数是invex的,定理B的等价性依旧存在。
2. 预备知识
设
是Banach空间,我们用
和
分别表示X中以点x为圆心,
为半径的开球和闭球,用
和
分别表示X中的单位开球和单位闭球。设F是X到Y的集值映射,用
表示F的图像,即
设
是下半连续函数,我们用
表示f的可行域,即
若
且
,我们称函数是真的。设
,我们用
表示Clarke-Rockafellar广义方向导数,即
表示f在点
的Clarke-Rockafellar次微分,即
若
,则
。关于Clarke-Rockafellar次微分,我们还需要如下的计算法则 [12]。
引理2.1 设
,
在点x是局部Lipschitz的,则有
和
若额外有
在点x均是regular的(参考文献 [12],定义2.4.10),则
。
接下来的Ekeland变分原理对于我们主要定理的证明至关重要 [13]。
引理2.2 设X是完备的度量空间,f是真下半连续函数。设
,
使得
成立。于是,对于任意的
都存在
使得
1)
。
2)
。
3)
。
接下来的引理给出了相关于admissible函数的一些有用性质。
引理2.3 设
是admissible函数,
,则接下来的命题成立:
1)
且
2)
证明1) 根据admissible函数的定义,我们只需证明
事实上,根据
的定义和admissible函数的非减性,我们有
2) 同样根据
的定义和admissible函数的非减性,我们有
3. 全局开性和全局度量正则性
在接下来的文章中,若无额外说明,我们总假定
是Banach空间,f是真下半连续函数。
众所周知,集值映射
的度量正则性,线性开性,以及逆映射
的Aubin性质三者之间存在等价性(参考文献 [11],定理5A.3)。文献 [10] 给出了两种全局度量正则性的定义并建立了它们和其逆映射Lipschitz性之间的等价关系。为了进一步完善 [10] 中的等价关系,我们将文献 [11] 中集值映射线性开性的定义作如下拓展。
定义3.1 设
是admissible函数,F是X到Y的集值映射,
。我们称
1) F在
处是全局
-开的,若存在
使得
2) F在
处是全局
-pseudo-开的,若存在
使得
全局
-开性或全局
-pseudo-开性刻划了集值映射在参考点附近的全局开性所具有的“
-阶”比例关系。根据定义中集合的包含关系,若F在
处是全局
-开的则在
处必是全局
-pseudo-开的。接下来的等价关系表明了这个命题的逆不成立,因为集值映射的全局
-度量正则性和全局
-pseudo-度量正则性不等价(参考文献 [10],例2.3)。
定理3.1 设F是X到Y的集值映射,
是严格递增的admissible函数,
,则F在
处是全局
-开的当且仅当F在
处是全局
-度量正则的。
证明充分性:设F在
处是全局
-度量正则的,则存在
使得
(1)
任取
,
。假定
,于是存在
有
,即等价于
于是存在足够小的
使得
(2)
另一方面,根据(1)式有
因此存在
使得
此时,再结合(2)式有
必要性:因为F在
处是全局
-开的,于是存在
使得
(3)
任取
,设
,于是存在
,使得
。
于是对于任意的
,有
此时令
,即等价于
根据(3)式,有
于是存在
满足
即有
令
,于是就有
定理证毕!
相似于定理3.1的证明,对于集值映射的全局
-pseudo-开性我们有如下结果。
定理3.2 设F是X到Y的集值映射,
是严格递增的admissible函数,
,则F在
处是全局
-pseudo-开的当且仅当F在
处是全局
-pseudo-度量正则的。
4. 连续全局正则函数及稳定全局适定性
在2017年,姚等人将函数的prox-正则性定义推广到
-正则性和
-次正则性 [8],并在目标函数f是
-正则且次微分连续的假定下,将文献 [9] 中的相关凸性结果推广至非凸情形。受此启发,我们将 [8] 中的局部定义拓展成如下的全局定义。
定义4.1 设
是admissible函数,
,
,我们称
1) f在
处是连续全局
正则的,如果存在
使得
对于任意的
都成立。
2) f在
处是连续全局
正则的,如果存在
使得
对于任意的
都成立。
我们称f在
处是连续全局
-正则(
正则)的,如果存在
使得f在
处是连续全局
正则(
正则)的。
受参考文献( [8],命题3.2)和( [14],定理4.1)的启示,我们证明了X上的
-仿凸函数是连续全局
-正则函数。设
,回顾X上的真下半连续函数f被称为
-仿凸的,若
我们称f在X上是
-仿凸的,若存在
使得f在X是上
-仿凸的。特别的,当
时,
-仿凸函数退化成经典的弱凸函数。
命题4.1 设
是admissible函数,
,f是X上的
-仿凸函数,则
对于所有的
成立,故f在任意的
都是连续全局
-正则的。
证明设
,
,取
。根据假定有
于是有
注意
,于是有
根据f的下半连续性,有
因此,有
所以对于任意的
,有
。另一方面当
时,
,命题成立。定理证毕!
我们发现 [4] [5] [8] 中通过Ekeland变分原理不断迭代去寻找稳定极小值点的方法在全局情形仍然适
用。设
是admissible函数,
。假定
,设
及
根据引理2.3,易证
及
(4)
设
是任一单值映射,为方便我们作如下约定:
及
接下来的引理来自于( [8],定理4.2)。
引理4.1 假定
,
。设
定义如下函数
则有
且接下来的命题成立:
1) 若
,则
。
2) 若
,则存在唯一正整数使得
使得
且
。
接下来的定理证明思路来自于( [8],引理4.1),可看成其在全局下的推广。
定理4.1 设
是连续的admissible函数,
。假定
,
,
。若存在
以及
使得
(5)
以及
(6)
则有
(7)
证明
时。如果
,则有
,即有
。根据引理4.1有
此时,(7)式可由(6)式直接得到。如果
,采取反证法。假定(7)式不成立,则存在
使得
定义如下函数
,
则上式等价于
根据(6)式有
,则有
于是存在
使得
根据Ekeland变分原理,即引理2.2,存在
使得
和
故有
(8)
根据
的定义有
于是u是不等式右边函数的全局极小值点,根据广义费马法则以及引理2.1有
注意最后复合函数的包含关系参考文献( [15],命题2.1)。于是就有
根据(4)式以及(8)式有
根据(5)式有
于是就有
变形后有
此时与
的选择矛盾,故有(7)式成立。
另一方面,假设
时(7)式成立。根据引理4.1的(1)式,有
。此时用
代替
,则通过上述证明有
根据数学归纳法,定理证毕!
当目标函数是连续全局
正则时,借助上述命题我们发现定理A的充分性部分的
的全局强
-度量正则性的假定可以弱化为全局
-度量正则性。
定理4.2 设
,
,
,
。假定
是严格递增的连续admissible函数,
,f在0处是连续全局
正则的,
在0处是全局
-度量正则的,即存在
使得
则f有稳定全局
-适定性。
证明因为f在0处是连续全局
正则的,不失一般性,有
对于任意的
都成立。任取
,应用定理
4.1有
对于任意的
,根据引理4.1的(2)式,当n足够大时有,
,于是就有
(9)
此时,我们声明对于任意的
,有
如若不然则存在
和
满足
且
。此时有
于是有
,这与
的严格递增性矛盾。于是声明成立,故此时存在
使得对于任意的
有
。再结合(9)式,对于
,任意的
都是扰动后的函数
的全局极小值,即有
另一方面,根据广义费马法则,有
于是就有
根据(9)式,此时要证f有稳定全局
-适定性,只需证明对于任意的
,
是单值。
此时,对于真下半连续函数f,其共轭函数如下
注意到
是凸函数,故
且
是单调的集值映射。于是就有
是
上单调的集值映射。另一方面,由
的度量正则性以及( [10],命题2.5),我们有
在0处是半局部
-Lipschitz的,故
在0处是下半连续的。参考文献( [16],命题2.6),单值性得证,
定理证毕!
受参考文献( [8],定理5.3)的启发,用带有模量限制的
-仿凸性取代目标函数f的凸性后,我们推广了定理A的必要性部分,即此时稳定全局
-适定性能推出
的全局强
-度量正则性。
定理4.3 设
是admissible函数,
。假定f是
-仿凸的,有稳定全局
-适定性,且有
,则f在0处是全局强
-度量正则的。
证明因为f有稳定全局
-适定性,于是存在
以及单值映射
使得
另一方面因为f是
-仿凸的,根据命题4.1有
对于所有的
成立。取
代替y有
对于所有的
成立。两式相加有
对所有的
,
成立。于是有
对于所有的
,
成立。根据引理2.3,我们有
对于
成立,因为当
时,
,不等式右边恒为正无穷。事实上此时必有
,其证明可从后文的定理5.1所得。故f在0处是全局强
-度量正则的,定理证毕!
注:不同于参考文献( [8],定理5.3),我们把函数的正则性假定加强到了仿凸假定。若函数是连续全局
-正则的,根据推论5.1,我们只能得到f在0处是全局强
-pseudo-度量正则的。
5. 全局一致增长条件及Tilt-稳定全局极小值
参考文献 [4] [5] [7] [17],我们提出如下的和次微分结合的全局一致
-增长条件的定义。设
是admissible函数,
,
,我们称f满足全局一致
-增长条件,若存在
使得
(10)
对于任意的
都成立。称f满足全局一致
-增长条件,如果存在
使得f满足全局一致
-增长条件。注意全局一致
-增长条件和稳定全局
-适定性之间
存在如下区别:
1) 全局一致
-增长条件的(10)式只需对
成立,而稳定全局
-适定性的对应式需要对所有的
都成立。
2) 给定
,全局一致
-增长条件的(10)式需要对所有的
都成立,而稳定全局
-适定性的对应式只需要对某个
成立。
因此,如果f有稳定全局
-适定性,则存
使得
,如果f满足全局一致
-增长条件,则存在
使得对于所有的
,
是单值。但文献 [10] 的定理3.4后的remark所给例子却说明,即使f满足稳定全局
-适定性时,
也可能不为单值,这样的可能
在局部情形下依旧会出现(参考文献 [7],例子3.1),这说明全局一致
-增长条件和稳定全局
-适定性有实质性的不同。根据以上分析,我们给出如下两个命题:
命题A 假设存在
使得对所有的
有
是单值,则f满足稳定全局
-适定性时,f满足全局一致
-增长条件。
命题B 假设存在
使得
,则f满足全局一致
-增长条件时,f满足稳定全局
-适定性。
为便利,我们称满足命题A (命题B)的假设为条件A (条件B)。受参考文献( [7],命题3.3)的启发,我们给出了条件A成立的一个充分条件。
定理5.1 设
是admissible函数,
,
。假定f在0处是连续全局
-正则的且有稳定全局
-适定性,则条件A成立,f有一致
-增长条件。
证明 因为f有稳定全局
-适定性,于是存在
以及单值映射
使得
(11)
又因为f在0处是连续全局
-正则,不失一般性有,
(12)
对于任意的
都成立。注意此时
,任取
,
,将(11)式中的x取值为u,(12)式中的x取值为
,即有
和
两式相加有
故有
,于是条件A成立,f有一致
-增长条件,定理证毕!
受参考文献( [4],定理3.1)和( [17],定理3.3)的启发,我们讨论了全局一致
-增长条件和全局强
-pseudo-度量正则性之间的联系,得到如下定理。
定理5.2 设
是严格递增的admissible函数,
,
。假定f满足全局一致
-增长条件,则条件B成立,
在0处是全局强
-pseudo-度量正则的。
证明 因为f满足全局一致
-增长条件,于是存在
使得
(13)
对于任意的
都成立。任取
,于是有
以及
两式相加有
于是根据引理2.3有
又因为
是严格递增,于是有
(14)
根据( [10],命题2.5),此时仅需证明
。任取
,
。因为f是真下半连续函数,所以存在a的某个邻域使得f有下界。注意到
也是下半连续的,于是存在
使得
在
上有下界。于是对于任意的存在
,都存在
使得
于是根据Ekeland变分原理,存在
使得
和
(15)
此时取
,移项后再结合(13)式便有
整理后有
根据引理2.3的(2)式有
即有
因为
是严格递增的admissible函数,有
,于是有
。当n足够大时,可选取足够小的
使得
另一方面,根据(15)式有
是不等式右式函数在
的局部极小值。根据广义费马法则有
即存在
满足
。于是当n充分大时,有
。根据(14)式,当n充分大时,
我们有
因为
,故
是Cauchy列。又因为X是完备的,所以
必收敛于某点
。因为
,f满足全局一致
-增长条件,于是有
根据f的下半连续性和
的连续性有
即有b是
的全局极小值点,根据广义费马法则,有
于是条件B成立,同时定理得证!
不同于局部情况下的( [4],定理3.1),接下来的例子表明,即使当目标函数f是欧式空间中连续可微的凸函数时,定理5.2的逆也不一定能成立。
例1 设
,取
。此时
。根据参考文献 [10] 中的例2.3,我们有
在0处是全局
-pseudo-度量正则的。对于任意的
,取
,
。此时有
因此f不满足全局一致
-增长条件。
结合定理4.1和定理4.2我们有如下推论。
推论5.1 设
是严格递增的admissible函数,
,
,
,
。假定f在0处是连续全局
-正则的且有稳定全局
-适定性,则
在0处是全局强
-pseudo-度量正则的。
接下来我们考虑非凸情形的tilt-稳定全局极小值和全局强
-pseudo-度量正则性。参考文献 [1] [3] [4] [5] [6] [7],我们发现tilt-稳定局部极小值的非凸扩展总是在自共轭的Hilbert空间内进行。此时,目标函数总是被假定为prox-正则的,以使得其函数的次微分具有hypo-单调性。再利用凸包函数次微分所具有的的极大单调性,运用Hilbert空间中集值映射极大单调性的相关理论去处理问题。但接下来的例子表明,即使我们把目标函数加强到弱凸的,这种处理方式在全局情形下仍不可行。
例2 定义
如下
于是有
,参考文献( [18],命题4.3),知
是弱凸的,其中
是如下定义的凸函数,
取
,对于任意的
,易证
有唯一极小值点
于是就有对于任意的
,
即f有
-tilt-稳定全局极小值点,其中
。但另一方面
,所以
在0处不是全局强
-pseudo-度量正则的。
但我们发现目标函数的次微分
在0处是全局强
-pseudo-度量正则的意味着函数的另一种非凸性,invex性。回顾( [19],定义3.2),真下半连续函数f被称为是invex的,若[
是f的全局极小值]。接下来的定理表明,扰动后的函数若是invex的,定理B的等价关系仍旧存在。
定理5.3 设
是严格递增的admissible函数,f在X上是regular的。假定
,
,
则接下来的命题等价:
1)
在0处是全局强
-pseudo-度量正则的。
2) f有
-tilt-稳定全局极小值且存在
使得对于任意的
,
是invex的。
证明(1)
(2)因为
在
处是全局强
-pseudo-度量正则的,于是存在
使得对于任意的
,
是单值。根据参考文献( [10],定理3.5),f有
-tilt-稳定全局极小值且存在
使得
假设
满足
,根据引理2.1有
。于是有
,
是invex的。
(2)
(1)因为f有
-tilt-稳定全局极小值,不失一般性,有
任取
,等价于
。根据引理2.1,则有
。又因为
是invex的且
是单值,于是有
,根据( [10],命题2.5)有
在0处是全局强
-pseudo-度量正则的。定理证毕!
基金项目
贵大人基合字(2017)60号。