改进共轭梯度法求解无约束二次凸规划问题

乔熔岩， 赵新国

(1.中国人民解放军装备学院 研究生二队，北京 101416； 2.中国人民解放军装备学院 航天指挥系，北京 101416)

1 引 言

共轭梯度法在构造共轭方向时，初始方向选定为已知点的负梯度方向，有一定的局限性，而且采取边搜索边构造的方式，构造过程比较复杂.本文将对经典共轭梯度法进行改进，即先利用n的任一组正交基，直接构造出一组共轭方向，然后让初始点沿这组方向进行一维最优搜索，求出极小值点.

2 改进共轭梯度法的基础理论

2.1 共轭方向的构造通式

取d1=α1. 因为

(1)

所以取d2=A-1α2. 构造d3=α3+k1d1，令

(2)

(3)

这说明上述构成的d3与d1，d2关于A共轭. 再构造d4=A-1α4+p1d2，令

(4)

(5)

(6)

这说明所构成的d4也与d1，d2，d3关于A共轭.

现将此构造方法进行推广，给出d2m-1和d2m(其中m=1,2,3,…)的构造通式

d2m-1=α2m-1+k1d1+k2d3+…+km-1d2m-3，

(7)

d2m=A-1α2m+p1d2+p2d4+…+pm-1d2m-2.

(8)

令

(9)

由式(9)得

再令

(10)

由式(10)得

由此可根据通式(7)，(8)，构造出一组方向d1,d2,…,dn.

2.2 构造方法的理论证明

(11)

即αi与d2m关于A共轭，根据数学归纳法可知定理1成立.

定理2已知

其中x∈n，A为n阶正定矩阵，b为n维列向量，c为常数，方向d1,d2,…,dn是由一组正交基α1,α2,…,αn，根据通式(7)，(8)构造的，现任取向量αj(其中j为偶数)，则有A-1αj与d1,d3,…，d2m-1关于A共轭，其中2m-1≤n，m=1,2,3,….

(12)

即A-1αj与d2m-1关于A共轭，根据数学归纳法可知定理2成立.

现利用定理1和定理2，来证明由通式(7)和(8)所构造的d1,d2,…,dn是关于A共轭的.

由式(1)～(6)可知，d1，d2，d3和d4是关于A共轭的. 现假设已构造的d1,d2,…,d2m-3,d2m-2关于A共轭，其中2m-2

(13)

(14)

3 改进共轭梯度法的应用

3.1 方法的基本计算过程

第一：确定初始点x0、精度ε和一组正交基α1,α2,…,αn(可取单位坐标基)；

第二：利用式(7)，(8)直接构造出一组方向d1,d2,…,dn关于A共轭；

第三：以x0为起点，首先沿方向d1进行一维最优步长搜索，求出步长λ1和x1=x0+λ1d1.如果‖f(x1)‖≤ε，则停止搜索，求出f(x1)；……