王詩(shī)云,張慶毅

( 沈陽(yáng)航空航天大學(xué) 理學(xué)院,沈陽(yáng)110136)

閉凸錐的幾何性質(zhì)在優(yōu)化問(wèn)題的理論分析和算法設(shè)計(jì)中有著非常重要的應(yīng)用。本文我們主要研究以下兩個(gè)閉凸錐的幾何性質(zhì):

C={(y,τ)∈Rn×R:y≤τe}

S={(y,τ)∈Rn×R:eTy≤kτ,y≥0}

(1)

(0

其中e表示元素全為“1”的向量。顯然,

S∩C={(y,τ)∈Rn×R:eTy≤kτ,0≤y≤τe} :=K

因而,集合K的幾何性質(zhì),與S和C的幾何性質(zhì)關(guān)系密切。而集合K在k-范數(shù)上圖與k-范數(shù)函數(shù)[1-2]、構(gòu)建低秩矩陣的逼近[3]中都有廣泛的應(yīng)用。通過(guò)集合S和C的幾何性質(zhì)推演K的幾何性質(zhì)是本文的研究動(dòng)機(jī)之一。

本文的另一個(gè)研究動(dòng)機(jī)在于閉凸錐幾何性質(zhì)的廣泛應(yīng)用。對(duì)于線性半定規(guī)劃問(wèn)題,Sun[4]以及 Chan和Sun[5]給出了強(qiáng)二階充分性條件、約束非退化性條件、KKT系統(tǒng)B-次微分的非奇異性,KKT點(diǎn)的強(qiáng)正則性之間的關(guān)系。Hayashi等[6],Liu等[7]研究了二階錐上投影算子的Clarke廣義Jacobian的具體表達(dá)式。對(duì)于一般的對(duì)稱(chēng)錐,Kong等[8-9]等得到了相似的結(jié)論。對(duì)于非對(duì)稱(chēng)錐的情形,也有相應(yīng)的結(jié)論,比如文獻(xiàn)[10-12]。而這些條件的刻畫(huà),離不開(kāi)集合的變分幾何性質(zhì),因此,變分幾何性質(zhì)對(duì)于靈敏性分析是至關(guān)重要的。同時(shí),投影算子的 B-次微分的非奇異性在光滑/半光滑牛頓算法[13]以及增廣拉格朗日算法[14]中都起著重要的作用。

1 基本概念

令E為n+1維歐式空間Rn×R的閉凸錐。我們用int(E)表示E的內(nèi)部。E的對(duì)偶錐和極錐的定義分別為

E*={(y,τ)∈Rn×R:[(x,t),(y,τ)]≥0,?(x,t)∈E}

(2)

和

Eo={(y,τ)∈Rn×R:[(x,t),(y,τ)]≤0,?(x,t)∈E}

(3)

顯然,E*=-Eo。

給定(x,t)∈Rn×R,則其在集合E上的投影,即為下列優(yōu)化問(wèn)題的最優(yōu)解

(4)

這是一個(gè)二次凸優(yōu)化問(wèn)題,因此有且僅有一個(gè)最優(yōu)解,記為ΠE(x,t),稱(chēng)之為點(diǎn)(x,t)在集合E上的投影。

2 集合S與集合C對(duì)偶錐與極錐

對(duì)偶錐與極錐在研究投影算子的方向?qū)?shù)以及在求優(yōu)化問(wèn)題的臨界錐中應(yīng)用十分廣泛。下面,主要從集合S與C的表達(dá)式以及對(duì)偶錐與極錐的定義出發(fā),分別推導(dǎo)集合S與C的對(duì)偶錐與極錐。

定理1集合S與C為閉凸錐。

證明:由S與C的形式,該結(jié)論是顯然的。

定理2集合C的對(duì)偶錐C*={(x,t)∈Rn×R:eTx+t=0,-t≤xi≤0,i=1,2,…,n}.

證明:令

B={(x,t)∈Rn×R:eTx+t=0,-t≤xi≤0,i=1,2,…,n}

(5)

需要證明C*=B。

首先,證明C*?B。一方面,對(duì)任意的(x,t)∈C*,由對(duì)偶錐定義,對(duì)每一個(gè)(y,τ)∈C,都有下式成立

xTy+tτ≥0.

(6)

特別地,取(y,τ)∈C分別滿足如下條件:

(i)y=τei,τ>0. 由式(6)可知,(x,t)∈C*應(yīng)滿足

xi+t≥0,i=1,2,…,n.

(7)

即

t≥-xi,i=1,2,…,n.

(8)

(ii)y=-τei,τ>0. 由式(6)可知,(x,t)∈C*應(yīng)滿足

-xi+t≥0,i=1,2,…,n.

(9)

即

t≥xi,i=1,2,…,n.

(10)

由式(7)和式(9)可知,

t≥0.

(11)

(iii)yi=-kτ,τ>0,k∈Z+. 由式(6)可知,(x,t)∈C*應(yīng)滿足

-kxi+t≥0,i=1,2,…,n.

即

由k的任意性以及式(11),得到

xi≤0,i=1,2,…,n.

(12)

(iv)y=τe,τ>0. 對(duì)(x,t)∈C*,由式(6)可知,應(yīng)滿足

0≤xTy+tτ=(eTx+t)τ

這說(shuō)明,

eTx+t≥0

(13)

(v)y=τe,τ<0. 對(duì)(x,t)∈C*,由(iv)的推導(dǎo)過(guò)程同理可知

eTx+t≤0

(14)

由式(11)-(14),可知,C*?B。

現(xiàn)在,證明C*?B。對(duì)任意的(x,t)∈B,對(duì)每一個(gè)(y,τ)∈C,都有下式成立

這說(shuō)明(x,t)∈C*,即C*?B。

綜上,證明了C*=B。

定理3集合C的極錐C0={(x,t)∈Rn×R:eTx+t=0,-t≥xi≥0,i=1,2,…,n}.

證明:由定理2與極錐的定義直接可得。

定理4集合S的對(duì)偶錐S*={(x,t)∈Rn×R:kx+te≥0,t≥0}.

證明:令B={(x,t)∈Rn×R:kx+te≥0,t≥0}.要證明S*=B.

首先,對(duì)任意的(x,t)∈S*,對(duì)每一個(gè)(y,τ)∈S,都有式(1)成立。取

(i)y=0,τ>0.顯然(y,τ)∈S,代入式(1),我們得到,t≥0.

因此,有S*?B.

其次,對(duì)任意的(x,t)∈B,對(duì)每一個(gè)(y,τ)∈S,都有

kxTy+ktτ=[kx+te,y]-[te,y]+ktτ≥-[te,y]+ktτ=t(kτ-eTy)≥0.

即xTy+tτ≥0.這說(shuō)明B?S*.即證。

定理5集合S的極錐S0={(x,t)∈Rn×R:kx+t≤0,t≤0,i=1,2,…,n}.

證明:由于S0=-S*,該結(jié)論顯然。

定理6(0,0)∈int(S-C)。

證明:首先,已知(0,0)∈S-C。下面證明(0,0)為內(nèi)點(diǎn)。

設(shè)(Δy,Δτ)為(0,0)的δ鄰域中的任意一點(diǎn),只需證明(Δy,Δτ)∈S-C即可,即要證明:存在(y1,τ1)∈C,使得(y1,τ1)+(Δy,Δτ)∈S。

令(y1,τ1)滿足

0

顯然,(y1,τ1)∈C。

接下來(lái),令(y2,τ2)=(y1,τ1)+(Δy,Δτ)。由y1的定義及性質(zhì),有y2≥0,且

因此,(y2,τ2)∈S。且(Δy,Δτ)=(y2,τ2)-(y1,τ1)∈S-C成立。即證。

注:由定理6的結(jié)論,可以知道K*=C*+S*(見(jiàn)[15,Proposition 1.1.16])。

3 結(jié)論

本文研究了兩類(lèi)閉凸錐的對(duì)偶錐、極錐，為進(jìn)一步研究與這兩類(lèi)集合相關(guān)的優(yōu)化問(wèn)題的靈敏性分析和算法設(shè)計(jì)奠定了理論基礎(chǔ)。