Stiefel流形約束下矩陣跡函數最小化問題的黎曼共軛梯度算法

秦樹娟， 周學林， 李姣芬

(1.桂林電子科技大學 數學與計算科學學院，廣西 桂林 541004； 2.桂林電子科技大學 教務處，廣西 桂林 541004)

流形約束優化問題作為數值領域的一個活躍研究課題，一直以來備受關注，其基本迭代式為

(1)

問題1給定矩陣X∈Rn×m，F，D∈Rn×n及正則化參數α，給定非凸約束集合

St(m,d)={Q∈Rm×d:QTQ=Id}，

求Q∈St(m,d)，P∈Rd×m，使得

PTQTXTDXQP+αPTP),

s.t.QTQ=I,P∈Rd×m。

(2)

其中可行集

St(m,d)={Q∈Rm×d:QTQ=Id}，

當d≤m時，稱其為Stiefel流形。

令

f(Q,P)=tr(XTDX-2PTQTXTFX+

PTQTXTDXQP+αPTP)，

(3)

1 預備知識

1.1 St(m,d)×的切空間、正交投影及目標函數f(Q,P)的黎曼梯度

TQSt(m,d)={ξ∈Rm×d:ξTQ+QTξ=0};

(4)

(5)

(6)

令在歐式空間Rm×d×Rd×m上賦有如下標準內積：

(X1,Y1),(X2,Y2)∈Rm×d×Rd×m。

〈(ξ1,η1),(ξ2,η2)〉(Q,P)=〈(ξ1,η1),(ξ2,η2)〉,

ΓQξ=ξ-Qsym(QTξ)；

(7)

ΓPη=η。

(8)

Γ(Q,P)(ξ,η)=(ΓQξ,ΓPη)。

(9)

通過f(Q,P)對Q，P分別求導，可得其在Q，P處的歐式梯度：

(XTDTXQPPT+XTDXQPPT)=

XT(DT+D)XQPPT-2XTFXPT；

(QTXTDXQP+QTXTDTXQP)+2αP=

2(αP-QTXTFX)+QTXT(DT+D)XQP。

Gf(Q,P)=(GQf(Q,P),GPf(Q,P))。

gradf(Q,P)=Γ(Q,P)Gf(Q,P)=

(ΓQGQf(Q,P),ΓPGPf(Q,P))。

(10)

1.2 收縮算子和向量轉移算子

命題1令Q∈St(m,d)，W∈Rm×m為反對稱矩陣，若定義集合

ΩQ={ξ∈Rm×d|ξ=WQ}，

則有ΩQ=TQSt(m,d)。

證明令ξ∈TQSt(m,d)，定義反對稱矩陣

Wξ=PQξQT-QξTPQ,

且

由式(4)可知，

ξTQ=-QTξ，

可得

WξQ=PQξ-QξTPQQ=

于是有TQSt(m,d)?ΩQ。令ξ∈ΩQ，存在一個反對稱矩陣W∈Rm×m,使得ξ=WQ，則有

ξTQ+QTξ=(WQ)TQ+QTWQ=

-QTWQ+QTWQ=0，

于是有ΩQ?TQSt(m,d)。綜上可知，

TQSt(m,d)=ΩQ。

對?Q∈St(m,d)，采用擬測地線中的一類由凱萊變換構建的收縮算子：

ξ∈TQSt(m,d)，

(11)

其中：

Wξ=PQξQT-QξTPQ，

且ξ=WξQ由命題1可得。

(12)

R(Q,P)(α(ξ,η))=(RQ(αξ),RP(αη)),

(13)

(14)

采用由微分收縮算子的向量轉移算子

(15)

則Stiefel流形上的向量轉移算子為

(16)

式(16)滿足如下的Ring-Wirth非擴張條件[6]：

〈Ταη(η),Ταη(η)〉R(αη)≤〈η,η〉。

(17)

因式(16)涉及m×m階逆矩陣的計算，當m≥2d時，其計算量較大，故也可采用降階的方法來減少計算量[6]。以下僅給出其降為2d×2d階逆矩陣時的計算式：

(18)

其中：

M1=VΤQ,M2=VΤU,

且當m≤2d時，仍應選用式(16)。

Ταη(η)=η。

(19)

Τα(ξ,η)(ξ,η)=(Ταξ(ξ),Ταη(η)),

(20)

2 求解問題(3)的黎曼共軛梯度法

Dai的非單調共軛梯度法[7]中迭代參數βk+1為

其中yk=gradf(Xk+1)-gradf(Xk), 將其推廣至黎曼流形上，則有

(21)

其中，

Yk+1=〈gradf(Qk+1,Pk+1),Ταk(ξk,ηk)(ξk,ηk)〉-

〈gradf(Qk,Pk),(ξk,ηk)〉。

為保證算法的全局收斂性，采用Armijo型非單調線性搜索條件，其黎曼概括為

f(R(Qk,Pk)(αk(ξk,ηk))≤max{f(Qk,Pk),

f(Qk-1,Pk-1),…,f(Qk-m(k),Pk-m(k))}+

δαk〈gradf(Qk,Pk),(ξk,ηk)〉,

其中m(k)=min{m-1，WK}。

算法11) 給定初值

選取參數ε,δ,λ∈(0,1)，m∈N+，步長αmax>α0>αmin>0，令

(ξ0,η0)=-gradf(Q0,P0)，k=0。

2) 當‖gradf(Qk,Pk)‖>ε時，進行下一步。

3) 若步長αk滿足

f(R(Qk,Pk)(αk(ξk,ηk)))≤max{f(Qk,Pk),

f(Qk-1,Pk-1),…,f(Qk-m(k),Pk-m(k))}+

δαk〈gradf(Qk,Pk),(ξk,ηk)〉，

(22)

則轉步驟4)，否則，轉步驟5)。

4)令(Qk+1,Pk+1)=R(Qk,Pk)(αk(ξk,ηk))，R由式(11)定義，若m≥2d則由式(14)定義。

5) 令αk=λαk，轉步驟3)。

6) 計算

(ξk+1,ηk+1)=-gradf(Qk+1,Pk+1)+

βk+1Ταk(ξk,ηk)(ξk,ηk)，

(23)

7) 更新αk+1∈[αmin,αmax]，并令k=k+1。

3 收斂性分析

Ψ:=

{(Q,P)∈St(m,d)×Ρ|f(Q,P)≤f(Q0,P0)}

(24)

是緊集。

T(Q,P)St(m,d)×?Rm×d×Rd×m，

故gradf(Q,P)可看作

的連續映射。因此，對任意點，

gradf(Q2,P2)-gradf(Q1,P1)

是存在的。由引理2可知， gradf(Q,P)在Ψ上是Lipschitzian連續的，即

?(Q1,P1),(Q2,P2)∈Ψ，

存在一個Lipschitzian常數L>0,使得

‖gradf(Q1,P1)-gradf(Q2,P2)‖≤

Ldist((Q1,P1)-(Q2,P2)),

(25)

引理3[6]假設算法1未在有限步迭代后終止，則對任意的k，有

〈gradf(Qk,Pk),ηk〉<0。

(26)

〈gradf(Qk+1,Pk+1),(ξk+1,ηk+1)〉=

‖gradf(Qk+1,Pk+1)‖2。

(27)

若令

〈gradf(Qk+1,Pk+1),Ταk(ξk,ηk)(ξk,ηk)〉≥0，

則由歸納假設知

Yk+1=〈gradf(Qk+1,Pk+1),Ταk(ξk,ηk)(ξk,ηk)〉-

〈gradf(Qk,Pk),(ξk,ηk)〉>0，

則有

〈gradf(Qk+1,Pk+1),(ξk+1,ηk+1)〉=

‖gradf(Qk+1,Pk+1)‖2，

于是

〈gradf(Qk+1,Pk+1),(ξk+1,ηk+1)〉<0。

若令

〈gradf(Qk+1,Pk+1),Ταk(ξk,ηk)(ξk,ηk)〉<0，

則有

〈gradf(Qk+1,Pk+1),(ξk+1,ηk+1)〉=

‖gradf(Qk+1,Pk+1)‖2，

于是同樣有

〈gradf(Qk+1,Pk+1),(ξk+1,ηk+1)〉<0，

故對k+1而言，式(26)也成立。因此，對任意的k，式(26)都成立。

引理4[9]對算法 1，存在一個正常數μ>0,使得對任意的k都有

(28)

(29)

定理1假設算法 1在有限步迭代后未終止，則由該算法產生的序列在以下條件下收斂：

(30)

因此至少存在一個一階臨界點的聚點。.

‖gradf(Qk,Pk)‖≥γ,?k,

(31)

其中，

Δk+1=(1-rk+1)〈gradf(Qk+1,Pk+1),

Ταk(ξk,ηk)(ξk,ηk)〉,-rk+1×

〈gradf(Qk+1,Pk+1),Ταk(ξk,ηk)(ξk,ηk)〉，

結合引理3有

(32)

由式(23)可知,

‖(ξk+1,ηk+1)‖2=-2〈gradf(Qk+1,Pk+1),

(ξk+1,ηk+1)〉-‖gradf(Qk+1,Pk+1)‖2+

(33)

式 (33)兩邊同除

〈gradf(Qk+1,Pk+1),(ξk+1,ηk+1)〉2,

并結合式(32)、(17)可得，

(34)

由式(34)、式(31)可知，

(35)

于是

(36)

另一方面，由式(34)、(35)可知，

于是

(ξk,ηk)〉+‖gradf(Qk,Pk)‖2。

(37)

若

則根據式(37)有

因此，由引理3和式(31)知，

(38)

〈gradf(Qmj+i-2,Pmj+i-2),(ξmj+i-2,ηmj+i-2)〉,μ×

而這與式(29)相矛盾，因此式(31)不成立，從而可知式 (30)成立。

4 結束語

針對機器學習特征提取中的一類Stiefel流形約束下矩陣跡函數問題，先將其轉化為乘積流形約束下的最小化問題，再采用帶有Armijo型非單調線性搜索的黎曼共軛梯度算法對其進行求解，并給出了該方法的全局收斂性證明。