两类闭凸锥的变分几何性质

王诗云,张庆毅

( 沈阳航空航天大学 理学院,沈阳110136)

闭凸锥的几何性质在优化问题的理论分析和算法设计中有着非常重要的应用。本文我们主要研究以下两个闭凸锥的几何性质:

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的几何性质是本文的研究动机之一。

本文的另一个研究动机在于闭凸锥几何性质的广泛应用。对于线性半定规划问题,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上的投影,即为下列优化问题的最优解

(4)

这是一个二次凸优化问题,因此有且仅有一个最优解,记为ΠE(x,t),称之为点(x,t)在集合E上的投影。

2 集合S与集合C对偶锥与极锥

对偶锥与极锥在研究投影算子的方向导数以及在求优化问题的临界锥中应用十分广泛。下面,主要从集合S与C的表达式以及对偶锥与极锥的定义出发,分别推导集合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 结论

本文研究了两类闭凸锥的对偶锥、极锥，为进一步研究与这两类集合相关的优化问题的灵敏性分析和算法设计奠定了理论基础。