利用共轭梯度算法求解n元正定二次函数的极小点
利用共轭梯度算法求解n 元正定二次函数的极小点
我利用共轭梯度算法来解决n 元正定二次函数的极小点问题，并通过一个简单的函数模型来测试基于该算法的程序的正确性。通过分析该算法后，我采用MATLAB7.0中的设计语言来编写程序。MA TLAB 是集数学计算、图形处理和程序设计与以设计与一体的著名数学软件，在许多科学领域成为计算机辅助设计和分析、算法研究和应用开发的基本工具和首选平台。
一．算法条件及特点：
适合条件：无约束n 元正定二次函数f (X ) =1TX AX +B T+c 2
n 式中Ａ为n ⨯n 对称正定阵；Ｘ，Ｂ∈E ；c 为常数。
算法特点：已知P (i ) (i =0,..., n -1) 关于Ａ共轭，以任给X (0) 出发，依次以
P (0) , P (1) ,..., P (n -1) 为搜索方向的下述算法：
min f (X (k ) +λP (k ) ) ＝f (X (k ) +λk P (k ) ) λ
（k +1）（k ）（k ） X ，k =0, 1,..., n -1 =X +λk P
二．算法步骤：
（1）选择初始值近似X
（2）计算
（0）(0) P =-∇f (X ) (0) ，给出允许误差ε>0，k =0。
并用X （1）=X （0）+λ0P （0）∇f (X (0) ) TP (0) (1) 和λ0=-算出X 。 (0) T(0) (P ) AP
(k ) （3）一般地，假定已得出X
X
（4）||f (X (k +1) 和P （k ），则可计算第k +1次近似X (k +1) ： （k +1）（k ）（k ） =X +λk P λk ：min f (X (k ) +λP (k ) ) ) ||2≤ε， 停止计算，X (k +1) 即为要求的近似解。
否则，若k
P （k +1）=-∇f (X (k ) （k ） ) +βk P
∇f (X (k +1) ) T∇f (X (k +1) ) βk = ∇f (X (k ) ) T∇f (X (k ) )
k =k +1
计算出βk 和P （k +1），并转向第三步。
三．详细算法中变量说明：
Gradf ：函数的梯度。e ：终止条件ε
四．模型求解：
已知一个二维正定二次函数f (X ) =3212x 1+x 2-x 1x 2-2x 1 22
1312-x 1x 2-2x 1化成f (X ) =X TAX +B T+c 形式，得 ∙将f (X ) =x 12+x 2222
A = ⎛3-1⎫⎛-2⎫⎪ ⎪, B =⎪ ⎪⎝-11⎭⎝0⎭
∙初始条件X (0) ⎛-2⎫= 4⎪⎪，ε=0。
⎝⎭
∙将A , B ，X (0) 和ε=0输入算法求解。（具体算法及运行过程见附录）
⎛1⎫∙结果X *= 1⎪⎪ ⎝⎭
∙初始条件，即分别取
⎛2⎫(0) ⎛12⎫(0) ⎛2⎫(0) ⎛-2⎫(0) ⎛0. 2⎫(0) ⎛82⎫X (0) = 4⎪⎪, X = 4⎪⎪, X = 14⎪⎪, X = -4⎪⎪, X = 4⎪⎪, X = 224⎪⎪ ⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭
⎛1⎫ 均得结果X = 1⎪⎪ ⎝⎭*
五．根据上述结果进行必要分析：
由结果可知不管初始条件如何变化，均得出相同的结果，因为对于二次函数的情形，从理论上说，进行n 次迭代后即可到达极小点，所以对于简单的模型，与理论结果一致。
但是，在实际计算中，由于数据的舍入以及计算误差的积累，往往做不到这一点。此外，由于n 维问题的共轭方向最多只有n 个，在n 步以后继续如上进行是没有意义的。因此，在实际应用时，如迭代到n 步还不收敛，就将X (n ) 作为新的初始近似，重新开始迭代。根据实际经验，采用这种在开始的办法，一般都可得到较好的效果。
六．附录：
%正定二次型函数(n元) 极小点的共轭梯度算法
clc
%f(X)=(1/2)X'AX+BX+c
A=[3 -1;-1 1];
B=[-2 0]';
%初始点X(0)
X=[-2 4]';
%f(X)的梯度
Gradf=A*X+B;
%共轭梯度法终止条件
e=0;
%共轭梯度法初始搜索方向
P=-Gradf;
while(Gradf'*Gradf )>e
a=P'*A*P;
b=-(Gradf'*P)/a;
%X(k+1)=X(k)+bP(k),k=0,1,...,n
X=X+b*P;
%f(X)在点X(k+1)处的梯度,k=0,1,...,n
Gradf=A*X+B;
c=(Gradf'*A*P)/a;
%f(X)在点X(k+1)处的搜索方向P(k+1),k=0,1,...,n P=-Gradf+c*P;
end
%f(X)的极小点X(*)
X
运行过程如下（部分）：
1.
⎛82⎫X (0) = 244⎪⎪ ⎝⎭
A =
3 -1
-1 1
B =
-2
X =
82
244
Gradf =
162
e =
P =
-162
b =
1
X =
82
82
Gradf =
162 0
c =
1
P =
-162 -162
b =
0.5000
X =
1 1
Gradf =
0 0
c =
P =
X =
1 1
2.
⎛-2⎫X (0) = 4⎪⎪ ⎝⎭
A =
3 -1 -1 1
B =
-2 0
X =
-2 4
Gradf =
-12 6
e =
P =
12
b =
0.2941
X =
1.5294
2.2353
Gradf =
0.3529 0.7059
c =
0.0035
P =
-0.3114 -0.7266
b =
1.7000
X =
1.0000 1.0000
Gradf =
1.0e-015 *
-0.4441 0.1110
c =
1.2583e-016
P =
1.0e-015 *
0.4049 -0.2025
b =
0.2903
X =
1.0000 1.0000
Gradf =
1.0e-015 *
0 -0.1110
c =
0.0968
P =
1.0e-016 *
0.3918 0.9143
b =
1.7500
X =
1 1
Gradf =
0 0
c =
P =
0 0
X =
1 1
>>