您的位置:

共轭梯度算法python(共轭梯度算法pid)

本文目录一览:

无约束最优化(二) 共轭方向法与共轭梯度法

  之前文章 最速下降法、Newton法、修正Newton法 介绍的最速下降法存在锯齿现象,Newton法需要计算目标函数的二阶导数。接下来介绍的 共轭方向法 是介于最速下降法和Newton法之间的一种方法,它克服了最速下降法的锯齿现象,从而提高了收敛速度;它的迭代公式也比较简单,不必计算目标函数的二阶导数,与Newton法相比,减少了计算量和存储量。它是比较实用而有效的最优化方法。

  我们先将其在正定二次函数 上研究,然后再把算法用到更一般的目标函数上。首先考虑二维的情形。

  任选初始点 ,沿它的某个下降方向,例如向量 的方向,作直线搜索,如上图所示。由下面这个定理:

定理 :设目标函数 具有一阶连续偏导数,若 ,则 。

  知 。如果按照最速下降法选择的就是负梯度方向为搜索方向(也就是 方向),那么将要发生锯齿现象。于是一个设想是,干脆选择下一个迭代的搜索方向 就从 直指极小点 ,也就是找到上图所示的 方向。

  因为 从 直指极小点 ,所以 可以表示为:

  其中 是最优步长因子。显然,当 时, 。到这里,我们还有一个已知条件没用,就是目标函数为二次正定,所以我们对目标函数求导,得到:

  因为 是极小点,所以有:

  将 带入上述方程式,有:

  上式两边同时左乘 ,并注意到 和 ,得到 。这就是为使 直指极小点 , 所必须满足的条件。并且我们将两个向量 和 称为 共轭向量 或称 和 是 共轭方向 。

  由上面共轭梯度法那张图可以设:

  上式两边同时左乘 ,得:

  由此解出:

  代回 得:

  从而求到了 的方向。

  归纳一下,对于正定二元二次函数,从任意初始点 出发,沿任意下降方向 做直线搜索得到 再从 出发,沿 的共轭方向 作直线搜索,所得到的 必是极小点 。到目前为止的共轭梯度法依旧是假设了目标函数是二次正定矩阵。

  上面的结果可以推广到 维空间中,即在 维空间中,可以找出 个互相共轭的方向,对于 元正定二次函数从任意初始点出发,顺次沿着这 个共轭方向最多作 次直线搜索,就可以求到目标函数的极小点。

  对于 元正定二次目标函数,如果从任意初始点出发经过 有限次迭代 就能够求到极小点,那么称这种算法具有 二次终止性 。例如,Newton法对于二次函数只须经过一次迭代就可以求到极小点,因此是二次终止的;而最速下降法就不具有二次终止性。共轭方向法(如共轭梯度法、拟Newton法等)也是二次终止的。

  一般说来,具有二次终止性的算法,在用于一般函数时,收敛速度是较快的。

  定义:设 是 对称正定矩阵。若 维向量空间中的非零向量 满足 , 则称 是 共轭向量或称向量 是 共轭的(简称共轭)。

  当 (单位矩阵)时 变为 , 。即向量 互相正交 。由此看到,“正交”是“共轭”的一种特殊情形,或说,“共轭”是“正交”的推广。

  下面介绍几个定理:

定理 :若非零向量 是 共轭的,则线性无关。

推论 :在 维向量空间中, 非零的共轭向量的个数不超过 。

   定义 设 是 中的线性无关向量, 。那么形式为:

  的向量构成的集合,记为 。称为由点 和向量 所生成的 线性流形 。

  共轭方向法的理论基础是下面的定理。

定理 假设

(1) Q为 对称正定矩阵;

(2) 非零向量 是 共轭向量;

(3) 对二次目标函数 顺次进行 次直线搜索:

其中 是任意选定的初始点,则有:

i) , ;

ii) 是二次函数 在线性流形 上的极小点。

  这个定理看来较繁,但可借用直观的几何图形来帮助理解。 , 的情形为例,如图示。

   和 是Q共轭向量,张成了二维空间 ,这是过坐标原点的一个平面。 现在,过点 沿 方向作直线搜索得到 ,再过点 沿 方向作直线搜索得到 过点 由向量 和 张成的平面就是线性流形 。它是 的平行平面。

  定理的论断是,最后一个迭代点 处的梯度 必与 和 垂直。并且 是三元二次目标函数 在线性流形 (即过 由 和 张成的平面)上的极小点。

   共轭方向法算法的大体流程 就是:选定初始点 和下降方向向量 ,做直线搜索 。提供的梯度方向 使得 , 。提供共轭方向的方法有多种。不同的提供方法将对应不同的共轭方法。每种方法也因产生共轭方向的特点而得名。

  那么这里做直线搜索 中的 是如何确定的呢?这里我们先回顾一下在最速下降法中是如何计算这个 的。最速下降法:

  依据定理 设目标函数 具有一阶连续偏导数,若 ,则 。,我们可以得到 。由此有:

  由此,可求解出 :

  这里还可以采用另外一种种方式计算 ,下面对另外一种方式进行公式推导:

  由 ,用 左乘上式两边,然后再同时加上 ,利用 能够得到:

  左乘 有

  由此解出:

  在最速下降法中 ,在共轭方向法中 。

  在共轭方向法中,如果初始共轭向量 恰好取为初始点 处的负梯度 ,而其余共轭向量 由第 个迭代点 处的负梯度 与已经得到的共轭向量 的线性组合来确定,那么这个共轭方向法就称为 共轭梯度法 。

  针对目标函数是正定二次函数来讨论:

(1) 第一个迭代点的获得 :

  选定初始点 ,设 (否则迭代终止),因此 。取 ,(以下用 表示 )从 出发沿 方向做直线搜索,得到第1个迭代点 ,其中 可由下式确定:

  显然

(2) 第二个迭代点的获得 :

  设 ,因此 。由 知 与 线性无关。取 其中 是使 与 共轭的待定系数,令:

  由此解出

  并代回确定 ,并获得第2个迭代点。

  由公式 可以求得 ,带入公式 可进一步优化得到:

(3) 第三个迭代点的获得 :

  设 ,因此 。由 知 与 线性无关。取 其中 是使 与 共轭的待定系数,令:

  由此解出

  并代回确定 ,并获得第3个迭代点。

  其中

  上述过程仅表明 与 , 与 共轭,现在问, 与 也共轭吗?

(4) 第 个迭代点的获得 :

  由 知 与 线性无关。取 其中 是使 与 共轭的待定系数,令:

  由此解出

  并代回确定 ,并获得第k+1个迭代点。

  其中

  以上就是共轭梯度法得核心内容。

  为使共轭梯度算法也适用于非二次函数,需要消去算法中的 对于正定二次函数,有 代入到 中,得:

  此式中已不再出现矩阵 ,将 两端转置运算,并同时右乘 得:

  将共轭方向法中的定理带入得到 ,由直线搜索的性质有 ,带入上式有 。此外:

  带入 ,得到:

  此式称为Fletcher-Reeves公式(1964年)。

神经网络中rprop是什么算法

对于bp神经网络来说没有固定的标准可以得到最好的bp网络,设计好后只能手动修改参数然后选择最好的。下边是个分类的例子

clc

clear

close all

%---------------------------------------------------

% 产生训练样本与测试样本,每一列为一个样本

P1 = [rand(3,5),rand(3,5)+1,rand(3,5)+2];

T1 = [repmat([1;0;0],1,5),repmat([0;1;0],1,5),repmat([0;0;1],1,5)];

P2 = [rand(3,5),rand(3,5)+1,rand(3,5)+2];

T2 = [repmat([1;0;0],1,5),repmat([0;1;0],1,5),repmat([0;0;1],1,5)];

%---------------------------------------------------

% 归一化

[PN1,minp,maxp] = premnmx(P1);

PN2 = tramnmx(P2,minp,maxp);

%---------------------------------------------------

% 设置网络参数

NodeNum = 10; % 隐层节点数

TypeNum = 3; % 输出维数

TF1 = 'tansig';TF2 = 'purelin'; % 判别函数(缺省值)

%TF1 = 'tansig';TF2 = 'logsig';

%TF1 = 'logsig';TF2 = 'purelin';

%TF1 = 'tansig';TF2 = 'tansig';

%TF1 = 'logsig';TF2 = 'logsig';

%TF1 = 'purelin';TF2 = 'purelin';

net = newff(minmax(PN1),[NodeNum TypeNum],{TF1 TF2});

%---------------------------------------------------

% 指定训练参数

% net.trainFcn = 'traingd'; % 梯度下降算法

% net.trainFcn = 'traingdm'; % 动量梯度下降算法

%

% net.trainFcn = 'traingda'; % 变学习率梯度下降算法

% net.trainFcn = 'traingdx'; % 变学习率动量梯度下降算法

%

% (大型网络的首选算法 - 模式识别)

% net.trainFcn = 'trainrp'; % RPROP(弹性bp)算法,内存需求最小

%

% 共轭梯度算法

% net.trainFcn = 'traincgf'; % Fletcher-Reeves修正算法

% net.trainFcn = 'traincgp'; % Polak-Ribiere修正算法,内存需求比Fletcher-Reeves修正算法略大

% net.trainFcn = 'traincgb'; % Powell-Beal复位算法,内存需求比Polak-Ribiere修正算法略大

% (大型网络的首选算法 - 函数拟合,模式识别)

% net.trainFcn = 'trainscg'; % Scaled Conjugate Gradient算法,内存需求与Fletcher-Reeves修正算法相同,计算量比上面三种算法都小很多

%

% net.trainFcn = 'trainbfg'; % Quasi-Newton Algorithms - BFGS Algorithm,计算量和内存需求均比共轭梯度算法大,但收敛比较快

% net.trainFcn = 'trainoss'; % One Step Secant Algorithm,计算量和内存需求均比BFGS算法小,比共轭梯度算法略大

%

% (中小型网络的首选算法 - 函数拟合,模式识别)

net.trainFcn = 'trainlm'; % Levenberg-Marquardt算法,内存需求最大,收敛速度最快

%

% net.trainFcn = 'trainbr'; % 贝叶斯正则化算法

%

% 有代表性的五种算法为:'traingdx','trainrp','trainscg','trainoss', 'trainlm'

%---------------------%

net.trainParam.show = 1; % 训练显示间隔

net.trainParam.lr = 0.3; % 学习步长 - traingd,traingdm

net.trainParam.mc = 0.95; % 动量项系数 - traingdm,traingdx

net.trainParam.mem_reduc = 10; % 分块计算Hessian矩阵(仅对Levenberg-Marquardt算法有效)

net.trainParam.epochs = 1000; % 最大训练次数

net.trainParam.goal = 1e-8; % 最小均方误差

net.trainParam.min_grad = 1e-20; % 最小梯度

net.trainParam.time = inf; % 最大训练时间

%---------------------------------------------------

% 训练与测试

net = train(net,PN1,T1); % 训练

%---------------------------------------------------

% 测试

Y1 = sim(net,PN1); % 训练样本实际输出

Y2 = sim(net,PN2); % 测试样本实际输出

Y1 = full(compet(Y1)); % 竞争输出

Y2 = full(compet(Y2));

%---------------------------------------------------

% 结果统计

Result = ~sum(abs(T1-Y1)) % 正确分类显示为1

Percent1 = sum(Result)/length(Result) % 训练样本正确分类率

Result = ~sum(abs(T2-Y2)) % 正确分类显示为1

Percent2 = sum(Result)/length(Result) % 测试样本正确分类率

Python怎么做最优化

一、概观scipy中的optimize子包中提供了常用的最优化算法函数实现。我们可以直接调用这些函数完成我们的优化问题。optimize中函数最典型的特点就是能够从函数名称上看出是使用了什么算法。下面optimize包中函数的概览:1.非线性最优化fmin -- 简单Nelder-Mead算法fmin_powell -- 改进型Powell法fmin_bfgs -- 拟Newton法fmin_cg -- 非线性共轭梯度法fmin_ncg -- 线性搜索Newton共轭梯度法leastsq -- 最小二乘2.有约束的多元函数问题fmin_l_bfgs_b ---使用L-BFGS-B算法fmin_tnc ---梯度信息fmin_cobyla ---线性逼近fmin_slsqp ---序列最小二乘法nnls ---解|| Ax - b ||_2 for x=03.全局优化anneal ---模拟退火算法brute --强力法4.标量函数fminboundbrentgoldenbracket5.拟合curve_fit-- 使用非线性最小二乘法拟合6.标量函数求根brentq ---classic Brent (1973)brenth ---A variation on the classic Brent(1980)ridder ---Ridder是提出这个算法的人名bisect ---二分法newton ---牛顿法fixed_point7.多维函数求根fsolve ---通用broyden1 ---Broyden’s first Jacobian approximation.broyden2 ---Broyden’s second Jacobian approximationnewton_krylov ---Krylov approximation for inverse Jacobiananderson ---extended Anderson mixingexcitingmixing ---tuned diagonal Jacobian approximationlinearmixing ---scalar Jacobian approximationdiagbroyden ---diagonal Broyden Jacobian approximation8.实用函数line_search ---找到满足强Wolfe的alpha值check_grad ---通过和前向有限差分逼近比较检查梯度函数的正确性二、实战非线性最优化fmin完整的调用形式是:fmin(func, x0, args=(), xtol=0.0001, ftol=0.0001, maxiter=None, maxfun=None, full_output=0, disp=1, retall=0, callback=None)不过我们最常使用的就是前两个参数。一个描述优化问题的函数以及初值。后面的那些参数我们也很容易理解。如果您能用到,请自己研究。下面研究一个最简单的问题,来感受这个函数的使用方法:f(x)=x**2-4*x+8,我们知道,这个函数的最小值是4,在x=2的时候取到。from scipy.optimize import fmin #引入优化包def myfunc(x):return x**2-4*x+8 #定义函数x0 = [1.3] #猜一个初值xopt = fmin(myfunc, x0) #求解print xopt #打印结果运行之后,给出的结果是:Optimization terminated successfully.Current function value: 4.000000Iterations: 16Function evaluations: 32[ 2.00001953]程序准确的计算得出了最小值,不过最小值点并不是严格的2,这应该是由二进制机器编码误差造成的。除了fmin_ncg必须提供梯度信息外,其他几个函数的调用大同小异,完全类似。我们不妨做一个对比:from scipy.optimize import fmin,fmin_powell,fmin_bfgs,fmin_cgdef myfunc(x):return x**2-4*x+8x0 = [1.3]xopt1 = fmin(myfunc, x0)print xopt1printxopt2 = fmin_powell(myfunc, x0)print xopt2printxopt3 = fmin_bfgs(myfunc, x0)print xopt3printxopt4 = fmin_cg(myfunc,x0)print xopt4给出的结果是:Optimization terminated successfully.Current function value: 4.000000Iterations: 16Function evaluations: 32[ 2.00001953]Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 531.99999999997Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 12Gradient evaluations: 4[ 2.00000001]Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 15Gradient evaluations: 5[ 2.]我们可以根据给出的消息直观的判断算法的执行情况。每一种算法数学上的问题,请自己看书学习。个人感觉,如果不是纯研究数学的工作,没必要搞清楚那些推导以及定理云云。不过,必须了解每一种算法的优劣以及能力所及。在使用的时候,不妨多种算法都使用一下,看看效果分别如何,同时,还可以互相印证算法失效的问题。在from scipy.optimize import fmin之后,就可以使用help(fmin)来查看fmin的帮助信息了。帮助信息中没有例子,但是给出了每一个参数的含义说明,这是调用函数时候的最有价值参考。有源码研究癖好的,或者当你需要改进这些已经实现的算法的时候,可能需要查看optimize中的每种算法的源代码。在这里:https:/ / github. com/scipy/scipy/blob/master/scipy/optimize/optimize.py聪明的你肯定发现了,顺着这个链接往上一级、再往上一级,你会找到scipy的几乎所有源码!

共轭梯度法是什么?

共轭梯度法(Conjugate Gradient)是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息。

但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。

在各种优化算法中:

共轭梯度法是非常重要的一种。其优点是所需存储量小,具有步收敛性,稳定性高,而且不需要任何外来参数。

共轭梯度法是一个典型的共轭方向法,它的每一个搜索方向是互相共轭的,而这些搜索方向d仅仅是负梯度方向与上一次迭代的搜索方向的组合,因此,存储量少,计算方便。

共轭梯度法的算法介绍

又称共轭斜量法,是解线性代数方程组和非线性方程组的一种数值方法,例如对线性代数方程组 Ax=ƒ, (1)式中A为n阶矩阵,x和ƒ为n维列向量,当A对称正定时,可以证明求(1)的解X*和求二次泛函

的极小值问题是等价的。此处(x,у)表示向量x和у的内积。由此,给定了初始向量x(0),按某一方向去求(2)式取极小值的点x(1),就得到下一个迭代值x(2),再由x(2)出发,求x(3)等等,这样来逼近x*。若取求极小值的方向为F在 x(k=1,2,…)处的负梯度方向就是所谓最速下降法,然而理论和实际计算表明这个方法的收敛速度较慢,共轭梯度法则是在 x(k-1)处的梯度方向r(k-1)和这一步的修正方向p(k-1)所构成的二维平面内,寻找使F减小最快的方向作为下一步的修正方向p(k),即求极小值的方向p(其第一步仍取负梯度方向)。计算公式为

再逐次计算(k=1,2,…)。可以证明当i≠j时,

从而平p(1),p(2)形成一共轭向量组;r(0),r(1),…形成一正交向量组。后者说明若没有舍入误差的话,至多 n次迭代就可得到(1)的精确解。然而在实际计算中,一般都有舍入误差,所以r(0),r(1),…并不真正互相正交,而尣(0)尣(1),…等也只是逐步逼近(1)的真解,故一般将共轭梯度法作为迭代法来使用。

近来在解方程组(1)时,常将共轭梯度法同其他一些迭代法结合作用。特别是对病态方程组这种方法往往能收到比较显著的效果。其方法是选取一对称正定矩阵B并进行三角分解,得B=LLT。将方程组(1)化为 hу=b, (3)

此处y=lTx,b=l-1ƒ,h=l-1Al-T,而

再对(3)用共轭梯度法,计算公式为

k=0,1,2,…)适当选取B,当B很接近A时,h的条件数较之A大大减小,从而可使共轭梯度法的收敛速度大为加快,由一些迭代法的矩阵分裂A=M -N,可选取M 为这里的B,例如对称超松弛迭代(SSOR),强隐式迭代(SIP)等,这类方法常称为广义共轭梯度法或预条件共轭梯度法,它也可用于解代数特征值问题。