基于KL不等式求解具有錐約束凸優(yōu)化問題的鄰近點方法

任詠紅， 熊 英， 許 荻

(遼寧師范大學 數學學院，遼寧 大連 116029)

KL不等式是解決優(yōu)化分析、動態(tài)系統、偏微分方程和其他實際問題的一個重要研究工具，且應用廣泛. 像半代數函數、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是定義在歐氏空間上的正常下半連續(xù)函數，而Q是復合變量x和y的光滑函數.基于KL性質建立交替鄰近極小化算法(PALM)的收斂性的框架，并證明PALM算法產生的序列全局收斂到臨界點.

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

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

1 預備知識

首先,對本文中用到的KL性質相關內容和錐約束優(yōu)化的預備知識作出說明.

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

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

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

定義2[4](次微分) 設f：n→(-∞,+∞]是正常下半連續(xù)函數.考慮任意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的一個穩(wěn)定點，即0∈?f(x)，f的穩(wěn)定點的集合記作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 錐約束優(yōu)化問題與KL性質

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

(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考慮凸優(yōu)化問題(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，考慮下述離散的動態(tài)系統[7]:

(5)

假設下述條件成立：

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

給定一些正參數μ-，μ+，滿足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)的最優(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)當{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，由數學歸納法得

證畢.