共轭梯度法

共轭梯度法

最速下降法和牛顿法都有其自身的局限性，而共轭梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法，它具有超线性收敛速度，而且算法简单。此外，与最速下降法类似，共轭梯度法只用到了目标函数及其梯度值，避免了二阶导数（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等研究并应用于无约束优化问题取得了丰富的成果。

共轭梯度法解最优控制

一、最优控制：咱们先聊聊啥是最优控制

1.大家都知道，生活中每个人都在追求一个“最优解”，对吧？比如说怎么花最少的钱买到最好的东西，或者怎么用最短的时间走到最远的地方。最优控制的核心，就是解决一个问题：如何控制某个系统，才能让系统的表现达到最优。举个简单的例子，假设你是一个赛车手，要控制赛车在赛道上行驶，如何加速、刹车，才能在最短的时间内跑完比赛，这就是最优控制。

2.回到控制的问题上。最优控制的目标，简单来说就是想找到一组操作策略，能够让系统从一个初始状态开始，经过一系列控制操作，最终以最佳的方式到达目标状态。这中间可能会有很多复杂的变量，比如时间、能量、成本等等，而这些都是我们要在最优控制中考虑的因素。如果你想学好最优控制，得有一颗细心的心，因为每个细节都可能影响到最后的结果。

3.最优控制方法可不止一种哦！有些方法直接看控制器的动作，像是线性控制；而有些方法更复杂，需要对控制问题进行数学建模，然后通过一些优化算法来找出最好的控制策略。今天，我们要聊的，就是其中一种非常有趣的优化方法——共轭梯度法。

二、共轭梯度法：它怎么帮忙的？

1.共轭梯度法，听起来像是一个复杂的数学术语对吧？别担心，咱们先从它的名字说起。梯度，大家都知道，就是在一个函数的曲面上，最陡的方向，指向着函数值增加最快的方向。共轭梯度法的“共轭”是什么意思呢？它是一种特别巧妙的技巧，通过选择一组“共轭”方向来迭代求解最优化问题。这就好像你去爬山，不是光看坡度最大的一条路，而是选择一条最“合适”的路径，帮助你更加高效地到达山顶。

2.共轭梯度法怎么具体运作的呢？它的优势就是不需要像其他一些方法那样，存储和处理大量的矩阵数据。它通过逐步调整控制策略，并且巧妙地在梯度方向上进行搜索，最终找到了最优解。想象一下，如果你在玩游戏，控制着角色在一个复杂的迷宫里行走，每走一步，你都会重新计算一下周围的环境，选择一个更合适的方向继续走。共轭梯度法就是帮你做这件事的“导航仪”。

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;

最速下降法 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]