《武汉工程大学学报》 2008年04期
118-119
出版日期：2008-04-30
ISSN:1674-2869
CN:42-1779/TQ
扩张子空间定理的完整证明
0引言扩张子空间定理是应用共轭方向法极小化正定二次函数时获得的一个重要理论成果［１～２］，但在众多的文献中都只给出了这一定理的一个极其粗略的证明.本文将扩张子空间定理的证明过程分解为四个命题的证明，利用线性流形的性质、凸规划的性质及K—T条件，在理论上完整地证明了扩张子空间定理.约定：以下讨论过程中所涉及到的数皆为实数，所涉及到的向量皆为实向量.1四个命题及其证明定义设x(1)∈Rn是一个n维向量，d1，d2，…，dk是Rn中k个线性无关的向量，称集合
L=x∈Rn|x=x(1)+∑ki=1λidi,λi∈（-∞，∞）
为Rn中的一个线性流形.命题1线性流形L={x∈Rn|x=x(1)+∑ki=1λidi,λi∈（-∞，∞）}是一个凸集.证明任取x∈L，y∈L，记x=x(1)+∑ki=1kidi，y=x(1)+∑ki=1lidi.
对于α∈（0，1），有αx+（1-α）y=αx(1)+∑ki=1αkidi+
（1-α）x(1)+∑ki=1（1-α）lidi=
x(1)+∑ki=1［αki+(1-α)li］di∈L,
故L是一个凸集.证毕.命题2设A是一个n阶对称正定矩阵，则规划问题minf（x）=12xTAx+bTx+c
s.t. x∈L=x∈Rn|x=x(1)
+∑ki=1λidi,λi∈（-∞,+∞）（1）
是一个严格凸规划.其中b是一个n维列向量，c是一个常数.证明因A是一个n阶对称正定矩阵，故f(x)=12xTAx+bTx+c是Rn上的严格凸函数.由命题1知可行域LRn是一个凸集，所以规划问题（1）是一个严格凸规划.证毕.命题3线性流形L=x∈Rn|x=x(1)+∑ki=1λidi,λi∈（-∞,+∞）是线性方程组PTx=PTx(1)
的解集.其中P=(p1,p2,…,pn-k)，p1,p2,…,pn-k是齐次线性方程组DTx=dT1
dT2
dTkx=0
的基础解系.证明因p1,p2,…,pn-k是齐次线性方程组DTx=0的基础解系，故d1,d2,…,dk是齐次线性方程组PTx=0的基础解系.又x(1)是线性方程组PTx=PTx(1)的解，所以线性流形L是线性方程组PTx=PTx(1)的解集.证毕.命题3刻画了线性流形L=x∈Rn|x=x(1)+∑ki=1λidi,λi∈（-∞,+∞）的代数性质.根据命题3，规划问题（1）可转化为如下形式minf(x)=12xTAx+bTx+c
s.t. PTx-PTx(1)=0(2)命题4设d1,d2，…,dk是A共轭的非零向量，对于规划问题（2），以任意x(1)∈Rn为初始点，依次沿d1,d2，…,dk进行一维精确线性搜索，得到点x(2),x(3),…,x(k+1)，则x(k+1)是规划问题（2）的可行K—T点.证明因d1,d2，…,dk是A共轭的非零向量，故d1,d2，…,dk线性无关.由规划问题（1）与（2）的等价性及一维线性搜索的定义知，点x(2),x(3),…,x(k+1)是规划问题（2）的可行点.要证x(k+1)是规划问题（2）的K—T点，只需证明存在数λ*1，λ*1，…,λ*n-k，使f(x(k+1))=Ax(k+1)+b=λ*1p1+λ*2p2+…+λ*n-kpn-k，
注意到p1,p2,…,pn-k是齐次线性方程组DTx=0的基础解系，即要证Ax(k+1)+b是齐次线性方程组第4期罗进：扩张子空间定理的完整证明
武汉工程大学学报第30卷
DTx=dT1
dT2
dTkx=0
的解，也就是要证明dTi(Ax(k+1)+b)=0，i=1，2，…，k.事实上，当i=k时，由一维精确线性搜索得dTk（Ax(k+1)+b）=0.当i<k时，dTi（Ax(k+1)+b）=dTi（Ax(i+1)+b）+∑kj=i+1dTi［（Ax(j+1)+b）-（Ax(j)+b）］=0+∑kj=i+1dTiA（x(j+1)-x(j)）=∑kj=i+1αjdTiAdj（αj为步长）=0（因d1，d2，…，dk是A共轭的）证毕.2扩张子空间定理的证明利用上述结论可以完整地证明扩张子空间定理［1］.定理（扩张子空间定理）设有函数f(x)=12xTAx+bTx+c，
其中A是n阶对称正定矩阵，d1，d2，…，dk是A共轭的非零向量，以任意x(1)∈Rn为初始点，依次沿d1，d2，…，dk进行一维精确线性搜索，得到点x(2)，x（3），…，x(k+1)，则x(k+1)是函数f(x)在线性流形
L=x∈Rn|x=x(1)+∑ki=1λidi,λi∈（-∞,+∞）
上的唯一极小点.特别地，当k=n时，x(n+1)是f(x)在Rn上的唯一极小点.证明由命题4知，x(k+1)是规划问题（1）的可行K—T点.由命题2知，规划问题（1）是一个严格凸规划，故x(k+1)是规划问题（1）的唯一全局极小点.特别地，当k=n时，L=Rn，从而x(n+1)是f(x)在Rn上的唯一全局极小点.证毕.