任詠紅， 熊 英， 許 荻

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院，遼寧 大連 116029)

KL不等式是解決優(yōu)化分析、動(dòng)態(tài)系統(tǒng)、偏微分方程和其他實(shí)際問(wèn)題的一個(gè)重要研究工具，且應(yīng)用廣泛. 像半代數(shù)函數(shù)、tame函數(shù)、零范數(shù)等都是KL函數(shù).早在1963年ojasiewicz[1]在實(shí)分析函數(shù)中，研究一般的最速下降曲線問(wèn)題解的軌跡是否為有限長(zhǎng)度時(shí)，提出ojasiewicz不等式：

其中，F(xiàn):n→的實(shí)解析函數(shù)，為臨界點(diǎn)且并由此推導(dǎo)出最速下降曲線的解的軌跡是有限長(zhǎng)度，有界軌跡收斂到臨界點(diǎn).隨后，Kurdyka[2]將這一結(jié)果擴(kuò)展到在o-minimal結(jié)構(gòu)中可定義的可微函數(shù)中，相應(yīng)的廣義不等式稱為Kurdyka-ojasiewicz(KL)不等式.近年來(lái)，KL不等式的研究備受國(guó)內(nèi)外學(xué)者的關(guān)注. Attouch等人[3]將KL不等式應(yīng)用到非凸非光滑函數(shù)中，類型如下：

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

其中，f和g是定義在歐氏空間上的正常下半連續(xù)函數(shù)，而Q是復(fù)合變量x和y的光滑函數(shù).基于KL性質(zhì)建立交替鄰近極小化算法(PALM)的收斂性的框架，并證明PALM算法產(chǎn)生的序列全局收斂到臨界點(diǎn).

在國(guó)防、經(jīng)濟(jì)、金融、工程等重要領(lǐng)域上有著一大類優(yōu)化問(wèn)題可以建模型為下述形式的錐約束優(yōu)化問(wèn)題：

本文借助Lagrange函數(shù)，將有限維空間上的錐約束優(yōu)化問(wèn)題等價(jià)轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，討論滿足二階增長(zhǎng)條件的正常的下半連續(xù)凸函數(shù)具有KL性質(zhì)，進(jìn)而基于KL不等式分析了求解凸優(yōu)化問(wèn)題的鄰近點(diǎn)方法的收斂性．

1 預(yù)備知識(shí)

首先,對(duì)本文中用到的KL性質(zhì)相關(guān)內(nèi)容和錐約束優(yōu)化的預(yù)備知識(shí)作出說(shuō)明.

定義1[3](Kurdyka-ojasiewicz性質(zhì)) 設(shè)f：n→(-∞,+∞]是正常的下半連續(xù)函數(shù)，對(duì)任意x∈domf，若存在常數(shù)η∈(0,+∞]，滿足如下條件的連續(xù)凹函數(shù)φ：

(i)φ:[0,η)→+，φ(0)=0且φ在開區(qū)間(0,η)上連續(xù)可微；

(ii)對(duì)?s∈(0,η)，φ′(s)>0，

定義2[4](次微分) 設(shè)f：n→(-∞,+∞]是正常下半連續(xù)函數(shù).考慮任意x∈domf，則f在x處的次微分?f(x)定義為

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

(1)

注x∈n為f的一個(gè)局部極小值點(diǎn)的必要條件是x是f的一個(gè)穩(wěn)定點(diǎn)，即0∈?f(x)，f的穩(wěn)定點(diǎn)的集合記作critf．

定義3[4](次水平集) 給定實(shí)數(shù)α和β，定義f的次水平集如下:

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

定義5[5]設(shè)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 錐約束優(yōu)化問(wèn)題與KL性質(zhì)

令X，Y是有限維的Hilbert空間，考慮下述錐約束凸優(yōu)化問(wèn)題

(P)

命題1映射G關(guān)于-K是凸的，當(dāng)且僅當(dāng)G關(guān)于(-K)∞是凸的.

證由凸集值函數(shù)的定義易知，G關(guān)于-K是凸的當(dāng)且僅當(dāng)對(duì)任意的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)∞是閉凸錐，那么根據(jù)回收錐的定義，得到(-K)∞=-K∞.

問(wèn)題(P)的Lagrange函數(shù)如下:

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

由于K是閉凸錐,由Lagrange對(duì)偶理論，問(wèn)題(P)具有下述形式：

命題2考慮凸優(yōu)化問(wèn)題(P),對(duì)任意λ∈NK(G(x)),G(x)∈K，Lagrange函數(shù)L(x,λ)是X上的凸函數(shù).

證由于K是閉凸錐，根據(jù)文獻(xiàn)[4]中練習(xí)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上的凸函數(shù)，又因?yàn)閒(x)是凸的，則對(duì)任意λ∈NK(G(x))，G(x)∈K，Lagrange函數(shù)L(x,λ)是X上的凸函數(shù).

證畢.

由于K是閉凸錐，λ∈NK(G(x))等價(jià)于G(x)∈K，λ∈K-，且〈λ,G(x)〉=0.記

則g(x)是X上的凸函數(shù).

(3)

證由于g(x)是X上的凸函數(shù).?x∈U∩[ming≤g≤ming+η],記

由次微分的定義可得

故有

從而

(4)

結(jié)合式(3)和式(4)，得到

證畢.

說(shuō)明：由文獻(xiàn)[6]知定理4.6.1知，若在可行點(diǎn)x0∈Φ上二階充分條件成立，則二階增長(zhǎng)條件在點(diǎn)x0處是成立的.

3 鄰近點(diǎn)方法的收斂性分析

給定x0∈X，考慮下述離散的動(dòng)態(tài)系統(tǒng)[7]:

(5)

假設(shè)下述條件成立：

(H2)g在domg上連續(xù).

給定一些正參數(shù)μ-，μ+，滿足0<μ-<μ+<+∞，假設(shè)μk∈(μ-,μ+),?k∈N.記ω(x0)為{xk}的所有聚點(diǎn)的全體.

命題4假設(shè){xk}k∈N是由鄰近點(diǎn)算法(5)產(chǎn)生的序列，則下述命題成立：

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

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

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

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

證(i)由于

則對(duì)任意x∈X，有

取x=xk,有

(6)

故g(xk)是非增的.

求和得

當(dāng)N→+∞時(shí)，

(iii)由算法(5)的最優(yōu)性條件，存在hk+1∈?g(xk+1)使得xk+1=xk-μkhk+1，則

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

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

由于?g是外半連續(xù)的，gph ?g是閉集，有

即ω(x0)?critg.

(iv)當(dāng){xk}k∈N有界時(shí)，易知ω(x0)非空緊致，從而dist(xk,ω(x0))→0,k→+∞.

證畢.

引理1[7]假設(shè)g具有KL性質(zhì)，則有

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

(ii)若K?critg是緊致連通集，則存在實(shí)數(shù)C>0和θ∈(0，1)使得

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

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

(7)

(8)

由命題4(iii)(iv)和引理1，取ω(x0)=K，則存在一個(gè)整數(shù)N0，實(shí)數(shù)C和θ∈(0，1)使得

將上式代入式(8)有

(9)

設(shè)t∈(0，1)且取k≥N0，若‖xk+1-xk‖≥t‖xk-xk-1‖成立，則式(9)可以表示為

因此，得到

若N>N0，由數(shù)學(xué)歸納法得

證畢.