基于KL不等式求解具有锥约束凸优化问题的邻近点方法

任咏红， 熊 英， 许 荻

(辽宁师范大学 数学学院，辽宁 大连 116029)

KL不等式是解决优化分析、动态系统、偏微分方程和其他实际问题的一个重要研究工具，且应用广泛. 像半代数函数、tame函数、零范数等都是KL函数.早在1963年ojasiewicz[1]在实分析函数中，研究一般的最速下降曲线问题解的轨迹是否为有限长度时，提出ojasiewicz不等式：

其中，F:n→的实解析函数，为临界点且并由此推导出最速下降曲线的解的轨迹是有限长度，有界轨迹收敛到临界点.随后，Kurdyka[2]将这一结果扩展到在o-minimal结构中可定义的可微函数中，相应的广义不等式称为Kurdyka-ojasiewicz(KL)不等式.近年来，KL不等式的研究备受国内外学者的关注. Attouch等人[3]将KL不等式应用到非凸非光滑函数中，类型如下：

L(x,y)=f(x)+Q(x,y)+g(y)，

其中，f和g是定义在欧氏空间上的正常下半连续函数，而Q是复合变量x和y的光滑函数.基于KL性质建立交替邻近极小化算法(PALM)的收敛性的框架，并证明PALM算法产生的序列全局收敛到临界点.

在国防、经济、金融、工程等重要领域上有着一大类优化问题可以建模型为下述形式的锥约束优化问题：

本文借助Lagrange函数，将有限维空间上的锥约束优化问题等价转化为无约束优化问题，讨论满足二阶增长条件的正常的下半连续凸函数具有KL性质，进而基于KL不等式分析了求解凸优化问题的邻近点方法的收敛性．

1 预备知识

首先,对本文中用到的KL性质相关内容和锥约束优化的预备知识作出说明.

定义1[3](Kurdyka-ojasiewicz性质) 设f：n→(-∞,+∞]是正常的下半连续函数，对任意x∈domf，若存在常数η∈(0,+∞]，满足如下条件的连续凹函数φ：

(i)φ:[0,η)→+，φ(0)=0且φ在开区间(0,η)上连续可微；

(ii)对∀s∈(0,η)，φ′(s)>0，

定义2[4](次微分) 设f：n→(-∞,+∞]是正常下半连续函数.考虑任意x∈domf，则f在x处的次微分∂f(x)定义为

∂f(x):={u∈n|f(y)≥f(x)+〈u,y-x〉,∀y∈n}.

(1)

注x∈n为f的一个局部极小值点的必要条件是x是f的一个稳定点，即0∈∂f(x)，f的稳定点的集合记作critf．

定义3[4](次水平集) 给定实数α和β，定义f的次水平集如下:

[α≤f≤β]:={x∈n:α≤f(x)≤β}.

定义5[5]设C⊂X,x∈C，定义下述集合：

极锥C-:={x*∈X*:〈x*,x〉≤0,∀x∈C}；

法锥NC(x):={x*∈X*:〈x*,y-x〉≤0,∀y∈C}；

回收锥C∞:={x∈X:x+C⊂C}.

2 锥约束优化问题与KL性质

令X，Y是有限维的Hilbert空间，考虑下述锥约束凸优化问题

(P)

命题1映射G关于-K是凸的，当且仅当G关于(-K)∞是凸的.

证由凸集值函数的定义易知，G关于-K是凸的当且仅当对任意的x1，x2∈X以及t∈[0,1]有

tMG(x1)+(1-t)MG(x2)-K⊂MG(tx1+(1-t)x2)-K，

得到

tG(x1)+(1-t)G(x2)-G(tx1+(1-t)x2)-K⊂-K.

由回收锥的定义

tG(x1)+(1-t)G(x2)-G(tx1+(1-t)x2)∈(-K)∞.

(2)

证毕.

由于回收锥(-K)∞是闭凸锥，那么根据回收锥的定义，得到(-K)∞=-K∞.

问题(P)的Lagrange函数如下:

L(x,λ)=f(x)+〈λ,G(x)〉，(x,λ)∈X×Y*.

由于K是闭凸锥,由Lagrange对偶理论，问题(P)具有下述形式：

命题2考虑凸优化问题(P),对任意λ∈NK(G(x)),G(x)∈K，Lagrange函数L(x,λ)是X上的凸函数.

证由于K是闭凸锥，根据文献[4]中练习6.34知

注意到RK(G(x))⊂TK(G(x))，从而由式(2)可得

G(tx1+(1-t)x2)-tG(x1)-(1-t)G(x2)∈TK(G(x))，∀G(x)∈K.

故

〈λ,G(tx1+(1-t)x2)-tG(x1)-(1-t)G(x2)〉≤0,∀λ∈NK(G(x)),

即

〈λ,G(tx1+(1-t)x2)〉≤〈λ,tG(x1)+(1-t)G(x2)〉,∀λ∈NK(G(x))，

因此，∀λ∈NK(G(x)),G(x)∈K,φ(x)=〈λ,G(x)〉是X上的凸函数，又因为f(x)是凸的，则对任意λ∈NK(G(x))，G(x)∈K，Lagrange函数L(x,λ)是X上的凸函数.

证毕.

由于K是闭凸锥，λ∈NK(G(x))等价于G(x)∈K，λ∈K-，且〈λ,G(x)〉=0.记

则g(x)是X上的凸函数.

(3)

证由于g(x)是X上的凸函数.∀x∈U∩[ming≤g≤ming+η],记

由次微分的定义可得

故有

从而

(4)

结合式(3)和式(4)，得到

证毕.

说明：由文献[6]知定理4.6.1知，若在可行点x0∈Φ上二阶充分条件成立，则二阶增长条件在点x0处是成立的.

3 邻近点方法的收敛性分析

给定x0∈X，考虑下述离散的动态系统[7]:

(5)

假设下述条件成立：

(H2)g在domg上连续.

给定一些正参数μ-，μ+，满足0<μ-<μ+<+∞，假设μk∈(μ-,μ+),∀k∈N.记ω(x0)为{xk}的所有聚点的全体.

命题4假设{xk}k∈N是由邻近点算法(5)产生的序列，则下述命题成立：

(i)序列{g(xk)}k∈N是非增的；

(iii)若(H2)成立，则ω(x0)⊂critg={z|0∈∂g(z)}.

如果还有{xk}k∈N是有界的，那么

(iv)ω(x0)是非空紧致连通集，且dist(xk,ω(x0))→0，k→+∞.

证(i)由于

则对任意x∈X，有

取x=xk,有

(6)

故g(xk)是非增的.

求和得

当N→+∞时，

(iii)由算法(5)的最优性条件，存在hk+1∈∂g(xk+1)使得xk+1=xk-μkhk+1，则

由(ii)可知，‖xk-xk+1‖→0，k→+∞.又μk∈(μ-,μ+)，从而有

‖hk+1‖→0，k→+∞.

由于∂g是外半连续的，gph ∂g是闭集，有

即ω(x0)⊂critg.

(iv)当{xk}k∈N有界时，易知ω(x0)非空紧致，从而dist(xk,ω(x0))→0,k→+∞.

证毕.

引理1[7]假设g具有KL性质，则有

(i)若K⊂critg是连通集，那么g在K上取常值；

(ii)若K⊂critg是紧致连通集，则存在实数C>0和θ∈(0，1)使得

令h(s)=-s1-θ，θ∈(0， 1)，易知h(s)是凸函数.在g(xk)与g(xk+1)用凸函数不等式，有

g(xk)1-θ-g(xk+1)1-θ≥(1-θ)g(xk)-θ[g(xk)-g(xk+1)].

(7)

(8)

由命题4(iii)(iv)和引理1，取ω(x0)=K，则存在一个整数N0，实数C和θ∈(0，1)使得

将上式代入式(8)有

(9)

设t∈(0，1)且取k≥N0，若‖xk+1-xk‖≥t‖xk-xk-1‖成立，则式(9)可以表示为

因此，得到

若N>N0，由数学归纳法得

证毕.