2024年5月19日发(作者：宽带调制解调器是什么东西)

一类多面集投影算子方向导数的研究

刘勇进;李若男

【摘 要】首先刻画了一类多面集的对偶锥和极锥,进而给出了这类多面集上投影算

子方向导数的具体计算方法,研究结果不仅为该类多面集投影算子广义次微分的刻

画提供了技术支持,也为相关优化问题的灵敏度分析和算法收敛性分析奠定了理论

基础.

【期刊名称】《沈阳航空航天大学学报》

【年(卷),期】2017(034)005

【总页数】5页(P81-85)

【关键词】投影算子;多面集;方向导数;对偶锥;极锥

【作 者】刘勇进;李若男

【作者单位】沈阳航空航天大学理学院,110136;沈阳航空航天大学理学院,110136

【正文语种】中 文

闭凸锥上投影算子的性质，尤其是微分性质，在优化问题扰动分析时有着非常重要

的应用，因此引起了学者们的高度重视，并就此展开了深入研究且取得了一系列的

研究成果[1-5]。本文研究一类多面集上投影算子的一种重要的微分性质——方向

导数，给出其方向导数的具体计算表达式，多面集具有如下形式

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

其中0≠ui∈-,+。上述定义的多面集与加权l1、l范数上图锥有着密切的联系，其

中加权l1范数上图锥记为定义为

加权l范数上图锥记为定义为

其中W=diag(w1,w2,…,wn)是对角矩阵，且其对角线元素wi>0，

i=1,2,…,n，‖·‖1表示的是l1范数，‖·‖表示的是l范数，也即，对任意的由此看

出加权l1、l范数上图锥就是这类多面集的特殊形式。

2011年，修乃华[6]等对加权l范数上图锥投影算子进行了研究，并给出其具体表

达式。刘梅娇等[7]于2013年利用闭凸锥上投影算子应满足的条件，分情况讨论

给出了l1范数上图锥的计算公式。刘勇进等[8]在2013年的文章里提出了计算在

半封闭空间和盒子变量上的向量投影的快速算法，最终可以用来计算Ky-Fan k范

数上图锥的投影算子。2014年，丁超等 [9]在他们的文章中给出了l1、l范数上图

锥投影算子的计算方法，并且讨论了其方向导数的具体表达形式。2015年，刘勇

进等[10]详细研究了加权l1/l上图锥投影算子的微分性质，主要包括投影算子的方

向导数、B次微分和Clarke广义Jacobian矩阵等。2016年，刘勇进等[11]又给

出了一类特殊闭凸锥，即非负卦限上投影的l1范数上图锥，较为丰富的理论结果，

着重研究了它的变分和微分性质，详细地描述了其对偶锥、切锥、法锥和临界锥的

表达形式，并刻画了它的方向导数、B次微分和Clarke广义Jacobian矩阵等。

记号说明：如果I是一个集合，则|I|表示集合I的基数。若C是闭凸集，则intC

表示C的内部，bdC表示C的边界。为方便起见，在有限维实Hilbert空间上，

内积均记为〈·,·〉，它诱导的范数记为‖·‖。

设H是有限维实Hilbert空间，令C是H上的闭凸集，则C的对偶锥定义为

C*:=y∈H:〈x,y〉≥0,∀x∈C，

且有C的极锥C°:=-C*。

记ΠC(·)为闭凸锥C上的投影算子，即对任意给定的x∈H，ΠC(x)是如下凸优化问

题的唯一最优解：

min‖y-x‖2

s.t. y∈C。

为了方便后续对上投影算子的方向导数的讨论，我们首先给出多面集的对偶锥和极

锥的结果。

定理1 设的定义如(1)，则是闭凸锥，且的对偶锥形式为

*={(y,τ)∈Rn×R:uiyi=-τ,uiyi≤0}

由此可得的极锥形式为

°={(y,τ)∈Rn×R:uiyi=-τ,uiyi≥0}

证明：为了方便证明，令

首先证明C⊆*。任取(y,τ)∈*，根据对偶锥的定义有

〈(x,t),(y,τ)〉=〈x,y〉+tτ≥0, ∀(x,t)∈

特别地，取则由(3)可推出τ≥0。再分别取和(x,t)由(3)可以推出

再对所有i=1,…,n，令xi=0,xj=uj,j≠i,j=1,…,n，t=1，可以验证这些且由(3)式可以

推出

结合式(4)和(5)可得uiyi≤0，i=1,2,…,n，且由(4)可知uiyi≤0意味着τ≥0。由于

(y,τ)∈*，即可推知*⊆C。

反过来，我们欲证C⊆*。任取(y,τ)∈C，对任意的有

〈(x,t),(y,τ)〉=〈x,y〉+tτ=xiuiyi+tτ=(xi-t) uiyi≥0

其中第三个等式成立是因为(y,τ)∈C满足这意味着(y,τ)∈*，即C⊆*。

综上所述可得*=C。再由°=-*可知(2)成立。

现定义闭凸锥为

={(x,t)∈Rn×R:xi=t,i∈I1;t,i∈I2}

其中I1,I2是集合{1,2,…,n}的两个互不相交的子集，ui≠0,i∈I1∪I2。关于上的投影

算子的计算结果，我们有以下结论[12]：

引理1 假设给定(x,t)∈Rn×R和u∈Rn。令π是{1,2,…,I2}的一个排序使得

定义和。设为k∈{0,1,2,…,|I2|}满足下述条件的最小非负整数

定义

且对于i=1,2,…,n有

则有

根据引理1，我们可以得到以下两种特殊形式的上投影算子的具体表达式。

推论1假设给定(x,t)∈Rn×R和u∈Rn，我们有以下结论：

(1)当I1=∅，I2={1,2,…,n}时，此时则上的投影算子可以计算为

其中

且为k∈{0,1,2,…,n}满足下述条件的最小非负整数

(2)当I1=∅,I2=∅，此时这种情况下有

这一节给出上投影算子方向导数的计算公式以及详细推演过程。由于方向导数的研

究涉及在处的切锥，我们首先讨论切锥的计算。下面给出正则齐次凸函数上图切锥

的刻画定理，Clarke[13]给出了该定理的具体证明。

引理2 设f:Rn→R是一正则齐次凸函数。定义C:={(x,t)∈Rn×R:f(x)≤t}，则C是

一闭凸锥。且对任意在的切锥可以计算为

TC(,)={(d,ξ)∈Rn×R:f ′(;d)≤ξ}

其中表示函数f在处沿着方向d的方向导数。

由以上引理可以推导出的具体表达式，在下述定理中，我们给出的刻画公式及其详

细证明。

定理2 假设给定(x,t)∈Rn×R和u∈Rn，且则在的切锥的表达形式为

其中

证明：当时，由引理1及凸集上投影算子的定义可知再根据切锥的定义可知；当

(x,t)∈°时，根据投影算子的定义可知此时

现在考虑其他情况下切锥的计算，令则可知f是正则齐次函数且进一步，对任意的

d∈Rn，函数f在处沿着方向d的方向导数具有如下形式：

定义则有因此，由引理2可知，当(x,t)∉或(x,t)∉°时，有

综上所述在的切锥的表达形式为定理所示。

下述引理给出了用来计算上投影算子方向导数的一个重要结论，Haraux[14]和

Pang[15]在他们的文章中分别给出了该引理的详细证明过程。

引理3 设C⊆Rn×R是多面集。对任意的(x,t)∈Rn×R，令则对任意(h,η)∈Rn×R，

ΠC(·,·)在(x,t)处沿方向(h,η)的方向导数可通过下式得到。

其中是C在(x,t)的临界锥。

根据推论1，对给定的(x,t)∈Rn×R和u∈Rn，定义指标集α,β和γ为

α:={i:xi>},β:={i:xi=},γ:={i:xi<}

由定理1、定理2 以及引理3，我们得到以下刻画上投影算子方向导数的定理。

定理3 假设给定(x,t)∈Rn×R和u∈Rn，对任意的在(x,t)处沿方向(h,η)的方向导数

可以通过下式计算：

证明：令由于是一多面集，根据引理2可知

其中接下来，我们分如下四种情况讨论方向导数的结果：

在这种情况下有可得⊥=Rn×R。又由定理2知因此，根据(6)可得

此时且由可知，α=∅,β=∅,γ={1,2,…,n}

在这种情况下有于是有⊥=Rn×R，因此再由定理2可知

C=(,)={(d,ξ)∈Rn×R:di≤ξ,i∈I()}，

其中于是得到

进一步可知且因此有α=∅

(3)(x,t)∉且(x,t)∉在这种情况下，且有

其中第二个等式成立是由推论1中的刻画得到，第三个等式成立是因为对任一均

有又对每一个有也即

由此可得

C={(d,ξ)∈Rn×R:di=ξ,i∈α,di≤ξ,i∈β}，

则由(6)可得

进一步有

(4)(x,t)∈°。在这种情况下且由定理1可知当(x,t)∈°时，(x,t)∈Rn×R满足

且uixi≥0，

则有

由此推得

由(6)可以推知

再由可得α∪β={1,2,…,n},γ=∅。

综上所述在(x,t)处沿方向(h,η)的方向导数即为定理所示。

本文给出了一类多面集上投影算子方向导数的显示表达式，在此基础上可以进一步

研究其广义次微分的性质。此外，由于本文中提出的多面集更具有普遍性，它的投

影算子应用范围更加广泛，其中l范数上图锥和加权l范数上图锥都是它的特殊形

式，且这类多面集投影算子的次微分可以运用到加权l1、l范数上图投影算子广义

Jacobian阵的研究中。在后续的研究中，我们将考虑进一步研究这些问题。

【相关文献】

[1] BONNANS J F,SHAPIRO bation analysis of optimization problems

[M].Springer,New York,2000.

[2] 张立卫,吴佳,张艺.变分分析与优化 [M].北京:科学出版社,2013.

[3] BONNANS J F,RAMIREZ C bation analysis of second-order cone programming

problems[J].Mathematical Programming,2005,104(2):205-227.

[4] WANG Y,ZHANG L ties of equation reformulation of the Karush-Kuhn-Tucker

condition for nonlinear second order cone optimization problems[J].Mathematical

Methods of Operations Research 2009,70(2):195-218.

[5] SUN D strong second order sufficient condition and constraint nondegeneracy in

nonlinear semidefinite programming and their implications[J].Mathematics of Operations

Research,2006,31(4):761-766.

[6] 王英楠,修乃华.几类非对称矩阵锥分析 [D].北京:北京交通大学,2011.

[7] 刘梅娇,单锋,姜永.范数锥投影算子的计算[J].数学进展,2013,42(4):563-568.

[8] LIU Y J,WANG S Y,SUN J g the projection onto the projection onto the

intersection of a closed half-space and a variable box[J].Operations Research

Letters,2013,41(3):259-264.

[9] DING C,SUN D F,TOH K introduction to a class of matrix cone

programming[J].Mathematical Programming,2014,144(1-2):141-179.

[10]LIU Y J,HAN N,WANG S Y,ential properties of the metric projectors over the

epigraph of the weighted and norm[J].Pacific Journal of Optimization,2015,11(4):737-749.

[11]LIU Y J,WANG ties associated with the epigraph of the l1 norm function of

projection onto the nonnegative orthant[J].Mathematical Methods of Operations

Research,2016,84(1):205-211.

[12]韩宁,刘勇进,刘梅娇.一类闭凸锥上投影算子的计算[J].沈阳航空航天大学学报,2013,30(5):88-91.

[13]CLARKE,F zation and nonsmooth analysis [M].New York:John Wiley &

Sons,1983.

[14]HARAUX P to differentiate the projection on a convex set in Hilbert

space[J].Journal of the Mathematical Society of Japan,1977,29:615-631.

[15]PANG J ′s method for B-differentiable equation[J].Mathematics of

Operations Research,1990,15(1-3):149-160.