王詩云,張慶毅

( 沈陽航空航天大學 理學院,沈陽110136)

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

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的幾何性質,與S和C的幾何性質關系密切。而集合K在k-范數上圖與k-范數函數[1-2]、構建低秩矩陣的逼近[3]中都有廣泛的應用。通過集合S和C的幾何性質推演K的幾何性質是本文的研究動機之一。

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

1 基本概念

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

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)化問題的最優(yōu)解

(4)

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

2 集合S與集合C對偶錐與極錐

對偶錐與極錐在研究投影算子的方向導數以及在求優(yōu)化問題的臨界錐中應用十分廣泛。下面,主要從集合S與C的表達式以及對偶錐與極錐的定義出發(fā),分別推導集合S與C的對偶錐與極錐。

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

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

定理2集合C的對偶錐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。一方面,對任意的(x,t)∈C*,由對偶錐定義,對每一個(y,τ)∈C,都有下式成立

xTy+tτ≥0.

(6)

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

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

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

(7)

即

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

(8)

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

-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*應滿足

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

即

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

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

(12)

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

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

這說明,

eTx+t≥0

(13)

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

eTx+t≤0

(14)

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

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

這說明(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的對偶錐S*={(x,t)∈Rn×R:kx+te≥0,t≥0}.

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

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

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

因此,有S*?B.

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

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

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

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

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

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

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

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

令(y1,τ1)滿足

0

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

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

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

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

3 結論

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