凸集上投影算子的一个单调性质

本文证明了投影算子的一个新的单调性质,并简要讨论了与其它单调性质的关系

第18卷第4期

1998年11月数学研究与评论JOURNALOFMATHEMATICALRESEARCHANDEXPOSITION.18No.4Vol

Nov.1998

凸集上投影算子的一个单调性质

戚　厚　铎

(中国科学院计算数学与科学工程计算研究所,北京100080)Ξ

摘　要　本文证明了投影算子的一个新的单调性质,并简要讨论了与其它单调性质

的关系.

关键词　单调性,投影算子,凸集.

分类号　AMS(1991)90C33 CCLO221

n设8为R中的闭凸集,记P(x)为到8上的投影算子,即

P(x)=argmin{ z-x :z∈8}.

投影算子P的性质在与投影梯度法有关的算法中起着至关重要的作用,参见[1-4].首先介绍一些已知的性质,下述性质的前三个可见[2]中引理2.1,性质(d)可见[2]中引理2.2,(e)可见[4]中引理3,(f)是(a)的一个简单推论.

n引理1　(a)　〈P(x)-x,z-P(x)〉≥0,Πx∈R,z∈8;

n(b)　〈P(y)-P(x),y-x〉≥0,Πx,y∈R,若P(x)≠P(y),则严格不等式成立;

(c)　 P(y)-P(x) ≤ y-x ,Πx,y∈Rn;

(d)　给定x∈8及d∈Rn,函数 (Α)=,Α>0是关于Α的不增函数;

,Α>0是关于Α的不增函数;2n(f)　给定x∈8,d∈R及Α>0,有〈d,x-P(x-Α≥d)〉Α

　　现在证明算子P的另外一个单调性质.

()n)=定理2　给定x∈8及d∈R,函数5(Α,Α>0是关于Α的不增函数. x-P(x-Αd)

证明(反证法)　设存在两个正常数Α,Β且Β>Α使得

(1)< x-P(x-Αd) x-P(x-Βd)

从关系(1)得到矛盾,从而证明定理的结论.令

)=P(x-Βd)+Κ(x-P(x-Βd)),Κ∈Rz(Κ(e)　给定x∈8及d∈Rn,函数#(Α)=Α

及λ):Κ∈[0,1]}.I={z(Κ

由于x∈8,P(x-Βd)∈8及8为凸集,λIΑ8.令

Ξ1996年1月30日收到.1998年5月28日收到修改稿

.

—580—

© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

本文证明了投影算子的一个新的单调性质,并简要讨论了与其它单调性质的关系

)= (x-Α) 2,Κ∈R.Χ(Κd)-z(Κ

)为Κ的凸函数,Χ(Κ)的导数为Χ(Κ

Χ′(Κ)=2〈x-Αd-z(Κ),x-P(x-Βd)〉.

设Κ3满足Χ′(Κ3)=0,得到

Κ3= x-P(x-Βd) 2=1- x-P(x-Βd) 2从引理1(f)知

〈d,x-P(x-Βd)〉≥Β2将上式代入(2)有Κ3≤1-Β<1.

考虑两种情况

情况1　Κ3≥0.

由于Χ(Κ)为凸函数且Κ3∈[0,1],所以Χ(Κ3)≤Χ(Κ),Κ∈[0,1].令

　　　　　　　z3=P(x-Βd)+Κ3(x-P(x-Βd))

=P(x-Βd)+(1-Α x-P(x-Βd) 2)(x-P(x-Βd)),

显然z3∈8,现在证明

x-Αd-z3 < x-Αd-P(x-Αd) .

上式就与P(x-Αd)的定义矛盾.事实上,

x-Αd-z3 2= x-Αd-x+ ) x-P(x-Βd2(x-P(x-Βd)) 2

=Α2 d 2-Α2( x-P(x-Βd) )2,

所以

　　 x-Αd-P(x-Αd) 2- x-Αd-z3 2

　= x-P(x-Αd) 2-2〈Αd,x-P(x-Αd)〉+Α2( x-P(x-Βd) )2

(　1)

> x-P(x-Αd) 2-2〈Αd,x-P(x-Αd)〉+Α2( ()x-P(x-Αd) )2

　= x-P(x-Αd)-Α2

x-P(x-Αd) 2(x-P(x-Αd)) ≥0.

这就证明了(3)式.

情形2　Κ3<0,即1- x-P(x-Βd) 2<0.从而

〈d,x-P(x-Βd)〉>Α2现在证明

x-Αd-P(x-Βd) < x-Αd-P(x-Αd) .

由(1)及(4)知

　　 x-Αd-P(x-Αd) 2- x-Αd-P(x-Βd) 2

　= x-P(x-Αd) 2-2d〈d,x-P(x-2d)〉-

—5

81—

© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.(2)(3)(4)(5)

本文证明了投影算子的一个新的单调性质,并简要讨论了与其它单调性质的关系

2　　 x-P(x-Βd) +2Α〈d,x-P(x-Βd)〉

2　> x-P(x-Αd,x-P(x-Βd)〉-d) -2Α x-P(x-Βd) 2　　 x-P(x-Βd) +2Α〈d,x-P(x-Βd)〉

22)　> x-P(x-Α-d) +2Α(1- x-P(x-Βd) Α

　　 x-P(x-Βd)

2　= x-P(x-Αd) -2 x-P(x-Αd) x-P(x-Βd) +

2　　 x-P(x-Βd)

2　=( x-P(x-Αd) - x-P(x-Βd) )≥0.

这就证明了(5)式,从而与P(x-Α.综合情形1及2就证明了结论.d)的定义矛盾

最后指出定理要求 x-P(x-Α>0,如果它等于零,定理就成为最简单的情形.d) ≠0,Α

即投影方法就不必考虑这些单调性质.注意到

=, x-P(x-Αd)

)是关于Α的不增函数由引理1(d)及定理2就得到#(Α.

感谢曲阜师范大学王长珏教授对本文的指导.

参　考　文　献

1　BertsekasDP.Projectednewtonmethodsforoptimizationproblemswithsimpleconstraints.SIAMJ.Con2

tr.Option,1982,20:221-246

2　BurkeJVandMoréJJ.Projectedgradientmethodsforlinearlyconstrainedproblems.Math.Program2

ming,1987,39:93-116

3　DunnJC.Ontheconvergenceofprojectedgradientprocessestosingularcriticalpoints.JOTA,1987,55:

203-216

4　WangCYandZhaoF.Optimalvaluefunctionismathematicalprogrammingandconvergenceforgradi2

entprojectionmethod.SystemSciencesandMathematicalSciences,1994,7:261-269

AMonotonicPropertyoftheProjectOperator

ontoaClosedConvexSet

QiHuoduo

(InstituteofComputationalMathematicsandScientific EngineeringComputing,

ChineseAcademyofSciences,Beijing100080)

Abstract

Thispaperprovesanewmonotonicpropertyformonotoneoperater,andstudiesthere2

.lationshipbetweenthispropertyandothermonotonicproperties

Keywords　monotoneproperty,projectionoperator,convexset.

—5

82—

© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.