投影梯度算法的数值行为研究
定义1.2.2 设C?Rn。若
?x?C，???R,??0,?x?C，
则称C是Rn中的一个“锥”。若C是锥且为凸集，则称它是Rn中的一个“凸锥”。
定义1.2.3 设S?Rn是闭凸集，x?S。若不存在x?1?,x?2??S以及数，???0,1?，使得x??x?1???1???x?2?，则称x是凸集S的一个“顶点”或“极点”即x?S是顶点的充要条件是x不能表示为S中两个不同点的凸组合。
（凸集可以有无限个顶点。如单位圆
S?x?Rnx?1
??的边界上的任意点都是顶点。）
定义1.2.4 设S?Rn是闭凸集，d?Rn为非零向量。若对任意x?S，均有
?x??d??0??S，
则称d是S的一个“方向”。若S的方向d不能表示为S的其他两个不同方向的正线性组合，则称它为S的一个“极方向”。
（由上面的定义易知，有界集合没有方向。）
定理1.2.1 （表示定理）设A?Rm?n,b?Rm，
S??xAx?b,x?0?。
则
（1）凸集S有有限个顶点x?1?,x?2?,?,x?r?。
（2）S有极方向的充要条件是S无界。而且，若S无界，则存在有限个极方向d?1?,?,d?t?。
（3）x?S的充要条件是：存在非负数?i?R,i?1,?,r和非负数
?j?R,j?1,2,?,t，使得
x???ix???jd?j?。
i?1j?1r?i?t11
投影梯度算法的数值行为研究
??i?1ri?1。
1.2.2 凸函数
凸函数的定义如下：
定义1.2.5 设S?Rn是凸集。若函数f:Rn?R满足：
（#） f??x??1???y???f?x???1???f?y?，?x,y?S,????0,1?，
则称f是S上的“凸函数”。若不等式（#）对所有x?y和???0,1?成立严格不等式，则称f是S上的“严格凸函数”。若存在常数m?0，使得不等式
f??x??1???y???f?x???1???f?y??m??1???x?y
2对所有x,y?S以及所有???0,1?成立，则称f是S上的“一致凸函数”（或“强凸函数”）。
（由定义不难看出一致凸函数是严格凸函数，严格凸函数是凸函数。）
凸函数的几何解释为：函数的图像上的任意两点确定的弦在其图像的上方。如图1.2所示。
图1.2 凸函数
Rn中的凸函数有如下性质：
1．设f1,f2:Rn?R是凸函数，则对任意?1?0,?2?0，函数?1f1??2f2是凸函数。
12
投影梯度算法的数值行为研究
2．设fi:Rn?R,i?1,?,m是凸函数，则对任意?i?0,i?1,?,m，函数
??i?1mifi是凸函数。
下面的定理给出了凸函数的几个等价性条件。
定理1.2.2 设函数f:Rn?R二次连续可微。则下面的命题等价： （1）函数f是凸函数。
（2）对任意x,y?Rn，一元函数??t??f?tx??1?t?y?是?0,1?上的凸函数。 （3）对任意的x,y?Rn，下面的不等式成立：
f?x??f?y???f?y??x?y?。
T（4）梯度函数?f单调，即：
??f?x???f?y??T?x?y??0，?x,y?Rn。
（5）对所有x?Rn，?2f?x?半正定。
定义1.2.6 若函数?f是凸函数，则称函数f是“凹函数”。
类似于定理1.2.2，不难建立凹函数相应的等价性定理。
定理1.2.3 设函数f:Rn?R二次连续可微，则下面的命题等价： （1）函数f是凹函数。
（2）对任意x,y?Rn，一元函数??t??f?tx??1?t?y?是?0,1?上的凹函数。 （3）下面的不等式成立：
f?x??f?y???f?y??x?y?，?x,y?Rn。
T（4）下面的不等式成立：
??f?x???f?y??T?x?y??0，?x,y?Rn。
（5）对所有x?Rn，?2f?x?半负定。
定理1.2.4 设S?Rn是凸集，则f:S?R是凸函数的充要条件是f的上图
13
投影梯度算法的数值行为研究
像
?x,??x?S,??R,f?x???? P?f???是Rn?1中的凸集。
定理1.2.5 设S?Rn是凸集，函数f:S?R是凸函数，则对任何??R，水平集
S???x?Sf?x????
是Rn中的凸集。
定理1.2.6 设函数f:Rn?R二次连续可微。若下面的条件之一成立，则f是严格凸函数。
（1）下面的不等式成立：
f?x??f?y???f?y??x?y?，?x?y?Rn。
T（2）对任何x，矩阵?2f?x?正定。
定理1.2.7 设函数f:Rn?R二次连续可微，则它是一致凸函数的充要条件是Hessian阵?2f?x?一致正定，即存在常数a?0，使得
pT?2f?x?p?ap，?x,p?Rn。
2
在结束本章之前，我们引入几个关于收敛性的概念。
所谓算法的局部收敛性指的是：存在点x*的邻域Ux*，使得当初始点
??x?0??Ux*时，算法产生的点列x?k?收敛于x*。
算法的全局收敛性指的是：当初始点x?0?是某个较大的集合中的任意点时，算法产生的点列x?k?收敛于某个点x*。
定义1.2.7 设序列x?k??Rn收敛于点x*。 （1）若存在常数???0,1?，使得当k充分大时，
x?k?1??x*??x?k??x*，
14
????????投影梯度算法的数值行为研究
则称x?k?线性收敛于x*，或称x?k?的收敛速度是线性的。
（2）若
????limk??x?k?1??x*x?k??x*?0，
则称x?k?超线性收敛于x*，或称x?k?的收敛速度是超线性的。一般地，若对某????个常数p?1，存在常数M?0，使得当k充分大时，
x?k?1??x*?Mx?k??x*p，
则称?x?k??的收敛速度是p。
（3）若存在常数M?0，使得当k充分大时，
x?k?1??x*?Mx?k??x*2，
则称?x?k??二次收敛于x*，或称?x?k??的收敛速度是二次的。
（显然，二次收敛必超线性收敛；超线性收敛必线性收敛。） 下面的公式（1.6）称为Sherman-Morrison公式。 定理1.2.8 设矩阵A?Rn?n非奇异。向量u,v?Rn满足
1?vTA?1u?0。
则矩阵A?uvT非奇异，且其逆由下式给出：
1 ?A?uvT??1?1A?uvTA?1?A?1?vTA?1u。
我们再给出如下引理。
引理1.2.1 设I?Rn?n表示单位矩阵，则对任何ui,vi?Rn,i?1,2，det?I?uT?T1v1?1?u1v1，
det?I?uvTT???uTTTT11?u2v2?11v1??1?u2v2???u1v2??v1u2?。
15
1.6）
（