当前位置：文档之家 › 共轭梯度法

共轭梯度法

  • 格式：doc
  • 大小：120.50 KB
  • 文档页数：2

共轭梯度法：

设w为n维矢量，假设优化准则函数为二次函数：ttJcwwHwuw，其中H为nn的正定对称矩阵。

如果两个矢量,ijdd满足0tijdHd，则称它们关于矩阵H互为共轭。在n为空间中存在互为共轭的n个矢量01,,ndd，并且它们是线性无关的。

 证明沿共轭方向可以在n步之内收敛于极值点

共轭方向算法：

1、 初始化起始点0w，一组共轭矢量01,,ndd，0k；

2、 计算k和1kw，使得：

minkkkkkJJwdwd

1kkkkwwd

3、 转到2，直到k=n-1为止。

定理：对于正定二次优化函数Jw，如果按照共轭方向进行搜索，至多经过n步精确的线性搜索可以终止；并且每一个1iw都是在0w和方向0,,idd所张成的线性流形00ijjjwwwd中的极值点。

证明：令ig为第i步的梯度，即：iiJwwgw，上述定理实际上只需证明对ji，10tijgd即可，因为1ig正交于0,,idd，则1ig正交于它们所张成的线性流形，100iijjjwwd包含在此线性流形中，因此在此线性流形中Jw的梯度为0，即1iw为在线性流形上的极值点。当1in时，01,,ndd所张成的线性流形即为整个n维空间nR，只有当ng0时，才有0tnjgd成立，因此nw为极值点。

梯度JgwHwu，因此两次迭代之间梯度的差值矢量为：

11kkkkkkkyggHwwHd 对于ji:

111111111tttttttijijijijijijjjittjjkkjkjittjjkkjkjgdgdgdgdgdgdgdgdggdgddHd

因为1kw是沿着jd方向搜索的极值点，因此10tjjgd，而0,,idd互为共轭，所以有10itkkjkjdHd，因此：

10tijgd

上述定理得证。

合集下载

共轭梯度法

共轭梯度法

共轭梯度法

最速下降法和牛顿法都有其自身的局限性，而共轭梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法，它具有超线性收敛速度，而且算法简单。此外，与最速下降法类似，共轭梯度法只用到了目标函数及其梯度值，避免了二阶导数（Hess矩阵）的计算，从而降低了计算量和存储量。

共轭方向法

共轭方向法的基本思想是在求解n维正定二次目标函数极小点时产生的一组共轭方向作为搜索方向，在精确线搜索条件下算法至多迭代n步就能求得极小点。经过适当的修正后，共轭方向法可以推广到求解一般非二次目标函数情形。下面先介绍共轭方向的概念。

设G是n接对称正定矩阵，若n维向量组12,,...,()mdddmn满足0,TijdGdij，则称12,,...,mddd为G共轭的。显然，向量组的共轭是正交的推广，即当G=I（单位矩阵）时，上述定义变成向量组正交的定义。此外，对称正定矩阵G的共轭向量组必然是线性无关的。

下面考虑求解正定二次目标函数极小点的共轭方向法。设

1min()2TTfxxGxbxc (1)

其中，G为n阶对称正定矩阵，b为n维常向量，c为常数。于是有下面的算法。

共轭方向法

0. 给定迭代精度01和初始点0x，计算00()gfx。选取初始方向0d，使得000Tdg。令0k

1. 若||||kg，停止运算，输出*kxx

2. 利用精确线搜索方向确定搜索步长k

3. 令1kkkkxxd，并计算11()kkgfx

4. 选取1kd满足如下下降性和共轭条件：1110,0,0,1,...,,TTkkkidgdGdik

5. 令k=k+1，转步1. 共轭梯度法

共轭梯度法是在每一次迭代步中利用当前点所处的最速下降方向来生成关于凸二次函数f的Hess矩阵G的共轭方向，并建立求f在Rn上的极小点的方法。这一方法最早是由Hesteness和Stiefel于1952年为求解对称正定线性方程组而提出来的，后经Fletcher等研究并应用于无约束优化问题取得了丰富的成果。

共轭梯度法matlab实例

共轭梯度法matlab实例

clear all;close all;clc;

syms x1 x2 t;

f=2*x1^2+x2^2-x1*x2;

f_grad=[diff(f,x1);diff(f,x2)];

X0=[1;1];

n=10;

epsonal=0.01;

fx=inline(f);

fx_grad=inline(f_grad);

X=X0;

fx0=fx(X(1),X(2));

fx0_grad=fx_grad(X(1),X(2));

while 1

if fx0_grad.'*fx0_grad<=epsonal

break;

end

P0=-fx0_grad;

k=0;

while 1

Xk=X+t*P0;

fx1=fx(Xk(1),Xk(2));

[tk,y]=equation_extremum(fx1,t,-1,5,epsonal);

Xk=X+tk*P0;

fx0_k=fx(Xk(1),Xk(2));

fx0_grad_k=fx_grad(Xk(1),Xk(2));

if fx0_grad_k.'*fx0_grad_k<=epsonal

fx0_grad=fx0_grad_k;

break;

end

if k+1==n

X=X;

else

lamdak=fx0_grad_k.'*fx0_grad_k/(fx_grad(X(1),X(2)).'*fx_grad(X(1),X(2)));

P0=-fx0_grad_k+lamdak*P0;

X=Xk;

共轭梯度法 2

共轭梯度法 2

最速下降法 and 共轭梯度法

分类： matlab 2011-04-17 17:02 961人阅读 评论(2) 收藏 举报

算法出版优化

注明：程序中调用的函数jintuifa.m golddiv.m我在之前的笔记中已贴出

最速下降法

%最速下降法求解f = 1/2*x1*x1+9/2*x2*x2的最小值，起始点为x0=[9 1]

%算法根据最优化方法（天津大学出版社）97页算法3.2.1编写

%v1.0 author: liuxi BIT

%format long

syms x1 x2 alpha;

f = 1/2*x1*x1+9/2*x2*x2;%要最小化的函数

df=jacobian(f,[x1 x2]);%函数f的偏导

epsilon=1e-6;%0.000001k=0;

x0=[9 1];%起始点

xk=x0;

gk=subs(df,[x1 x2],xk);%起始点的梯度

gk=double(gk);

while(norm(gk)>epsilon)%迭代终止条件||gk||<=epsilon

pk=-gk;%负梯度方向

f_alpha=subs(f,[x1 x2],xk+alpha*pk);%关于alpha的函数

[left right] = jintuifa(f_alpha,alpha);%进退法求下单峰区间

[best_alpha best_f_alpha]=golddiv(f_alpha,alpha,left,right);%黄金分割法求最优步长

xk=xk+best_alpha*pk;

k=k+1;

gk=subs(df,[x1 x2],xk);

gk=double(gk);

end

best_x=xk;%最优点

best_fx=subs(f,[x1 x2],best_x);%最优值

共轭梯度法 %共轭梯度法求解f = 3/2*x1*x1+1/2*x2*x2-x1*x2-2*x1的最小值，起始点为x0=[0 0]

共轭梯度法 3

共轭梯度法 3

1 / 28 最速下降法

1.最速下降方向

函数f(x)在点x处沿方向d的变化率可用方向导数来表示。对于可微函数，方向导数等于梯度与方向的内积，即：

Df(x;d) = ▽f(x)Td,

因此，求函数f(x)在点x处的下降最快的方向，可归结为求解下列非线性规划：

min ▽f(x)Td

s.t. ||d|| ≤ 1

当 d = -▽f(x) / ||▽f(x)||

时等号成立。因此，在点x处沿上式所定义的方向变化率最小，即负梯度方向为最速下降方向。

2.最速下降算法

最速下降法的迭代公式是

x(k+1) = x(k) + λkd(k) ,

其中d(k)是从x(k)出发的搜索方向，这里取在x(k)处的最速下降方向，即

d = -▽f(x(k)).

λk是从x(k)出发沿方向d(k)进行一维搜索的步长，即λk满足

f(x(k) + λkd(k)) = min f(x(k)+λd(k)) (λ≥0).

计算步骤如下：

(1)给定初点x(1) ∈ Rn，允许误差ε> 0， 置k = 1。

(2)计算搜索方向d = -▽f(x(k))。

(3)若||d(k)|| ≤ ε，则停止计算；否则，从x(k)出发，沿d(k)进行一维搜索，求λk，使

f(x(k) + λkd(k)) = min f(x(k)+λd(k)) (λ≥0).

(4)令x(k+1) = x(k) + λkd(k) ，置k = k + 1，转步骤(2)。

共轭梯度法

1.共轭方向

无约束问题最优化方法的核心问题是选择搜索方向。

以正定二次函数为例，来观察两个方向关于矩阵Ａ共轭的几何意义。

设有二次函数：

f(x) = 1/2 (x - x*)TA(x - x*) ,

其中A是n×n对称正定矩阵，x*是一个定点，函数f(x)的等值面

1/2 (x - x*)TA(x - x*) = c