精华内容
下载资源
问答
  • 共轭梯度法
    2022-02-14 17:32:07

    共轭梯度法

    最速下降法以及牛顿法都具有其自身的局限性。本文将要介绍的共轭梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法,它具有超线性的收敛速度,而且算法结构简单,容易编程实现。此外,根最速下降法相类似,共轭梯度法只用到了目标函数及其梯度值,避免了二阶导数的计算,从而降低了计算量和存储量,因此它是求解无约束优化问题的一种比较有效而使用的算法。

    一、共轭方向发
    共轭方向法的基本思想是在求解 n n n维正定二次目标函数极小点时产生一组共轭方向作为搜索方向,在线搜索条件下算法之多迭代 n n n步即能求得极小点。京故宫适当修正后共轭方向法可以推广到求解一般非二次目标函数情形。下面先介绍共轭方向的概念。
    定义1:设 G G G n n n阶对称正定矩阵,若 n n n维向量组 d 1 , d 2 , ⋯   , d m ( m ≤ n ) 满 足 d_1,d_2,\cdots,d_m(m\le n)满足 d1,d2,,dm(mn) d i T G d j = 0 , i ≠ j d_i^TGd_j=0,i\neq j diTGdj=0,i=j,则乘 d 1 , d 2 , ⋯   , d m d_1,d_2,\cdots,d_m d1,d2,,dm G G G共轭的。
    显然,向量组的共轭是正交的推广,即当 G = I G=I G=I(单位阵)时,上述定义变成了向量组正交的定义。此外,不难证明,对称正定矩阵 G G G的共轭向量组必然是线性无关的。
    下面我们考虑求解正定二次目标函数极小点的共轭方向法。设
    min ⁡ f ( x ) = 1 2 x T G x + b T x + c (1) \min f(x)=\frac{1}{2}x^TGx+b^Tx+c\tag{1} minf(x)=21xTGx+bTx+c(1)
    其中 G G G n n n阶对称正定阵, b b b n n n为常向量, c c c为常数。我们有下面的算法:


    算法1:共轭方向法
    0. 给定迭代精度 0 ≤ ϵ ≤ 1 0\le\epsilon\le 1 0ϵ1和初始点 x 0 x_0 x0。计算 g 0 = ∇ f ( x 0 ) g_0=\nabla f(x_0) g0=f(x0)。选取初始方向 d 0 d_0 d0使得 d 0 T g 0 < 0 d_0^Tg_0\lt 0 d0Tg0<0。令 k = 0 k=0 k=0.

    1. ∣ ∣ g k ∣ ∣ ≤ ϵ ||g_k||\le\epsilon gkϵ,停算,输出 x ∗ ≈ x k x^*\approx x_k xxk.
    2. 利用线搜索方法确定步长 α k \alpha_k αk
    3. x k + 1 = x k + α k d k x_{k+1}=x_k+\alpha_kd_k xk+1=xk+αkdk,并计算 g k + 1 = ∇ f ( x k + 1 ) g_{k+1}=\nabla f(x_{k+1}) gk+1=f(xk+1).
    4. 选取 d k + 1 d_{k+1} dk+1满足下降性和共轭性条件: d k + 1 T g k + 1 < 0 , d k + 1 T G d i = 0 , , i = 0 , 1 , ⋯   , k d_{k+1}^Tg_{k+1}\lt 0,d_{k+1}^TGd_i=0,\quad,i=0,1,\cdots,k dk+1Tgk+1<0,dk+1TGdi=0,,i=0,1,,k.
    5. k = k + 1 k=k+1 k=k+1,转步1

    该算法的收敛性证明略过,如果感兴趣,可以去查找相应的数值优化专著。这里直接给出结论,在精确线搜索下,算法1求解正定二次目标函数极小化问题,之多在 n n n步内即可求得其唯一极小点。这种能在有限步内求得二次函数极小点的性质通常称为二次终止性。

    二、共轭梯度法
    共轭梯度法是在每一步迭代利用当前点处的最速下降方向来生成关于凸二次函数 f f f的海塞阵 G G G的共轭方向,并建立求 f f f R n \mathbb{R^n} Rn上的极小点的方法。这一方法最早是由Hesteness和Stiefel于1952年为求解正定线性方程组而提出来的,后经Fletcher等人研究并应用于无约束优化问题取得了丰富的成果,共轭梯度法也因此成为当前求解无约束优化问题的重要算法类。
    设函数如(1)式所定义,则 f f f的梯度和海塞矩阵为
    g ( x ) = ∇ f ( x ) = G x + b , G ( x ) = ∇ 2 f ( x ) = G (2) g(x)=\nabla f(x)=Gx+b,\quad G(x)=\nabla^2 f(x)=G\tag{2} g(x)=f(x)=Gx+b,G(x)=2f(x)=G(2)
    下面我们讨论算法(1)中共轭方向的构造。我们取初始方向 d 0 d_0 d0为初始点 x 0 x_0 x0处的负梯度方向,即
    d 0 = − ∇ f ( x 0 ) = − g 0 (3) d_0=-\nabla f(x_0)=-g_0 \tag{3} d0=f(x0)=g0(3)
    x 0 x_0 x0出发沿 d 0 d_0 d0方向进行线搜索得到步长 α 0 \alpha_0 α0,令
    x 1 = x 0 + α 0 d 0 x_1=x_0+\alpha_0d_0 x1=x0+α0d0
    其中 α 0 \alpha_0 α0满足条件
    ∇ f ( x 1 ) T d 0 = g 1 T d 0 (4) \nabla f(x_1)^Td_0=g_1^Td_0 \tag{4} f(x1)Td0=g1Td0(4)
    x 1 x_1 x1处,用 f f f x 1 x_1 x1的负梯度方向 − g 1 -g_1 g1 d 0 d_0 d0的组合来生成 d 1 d_1 d1,即
    d 1 = − g 1 + β 0 d 0 (5) d_1=-g_1+\beta_0d_0 \tag{5} d1=g1+β0d0(5)
    然后选取系数 β 0 \beta_0 β0使 d 1 d_1 d1 d 0 d_0 d0关于G共轭,即令
    d 1 T G d 0 = 0 (6) d_1^TGd_0 = 0 \tag{6} d1TGd0=0(6)
    来确定 β 0 \beta_0 β0,将(6)代入(5)得
    β 0 = g 1 T G d 0 d 0 T G d 0 (7) \beta_0 = \frac{g_1^TGd_0}{d_0^TGd_0} \tag{7} β0=d0TGd0g1TGd0(7)
    由(2)得
    g 1 − g 0 = G ( x 1 − x 0 ) = α 0 G d 0 (8) g_1-g_0=G(x_1-x_0)=\alpha_0Gd_0 \tag{8} g1g0=G(x1x0)=α0Gd0(8)
    故由(3)~(5)可得
    g 2 T g 0 = 0 , g 2 T g 1 = 0 , d 0 T g 0 = − g 0 T g 0 , d 1 T g 1 = − g 1 T g 1 g_2^Tg_0=0,g_2^Tg_1=0,d_0^Tg_0=-g_0^Tg_0,d_1^Tg_1=-g_1^Tg_1 g2Tg0=0,g2Tg1=0,d0Tg0=g0Tg0,d1Tg1=g1Tg1
    现假设已得到互相共轭得搜索方向 d 1 , d 2 , ⋯   , d k − 1 d_1,d_2,\cdots,d_{k-1} d1,d2,,dk1,精确线搜索得到得步长为 α 0 , α 1 , ⋯   , α k − 1 \alpha_0,\alpha_1,\cdots,\alpha_{k-1} α0,α1,,αk1,且满足
    { d k − 1 T G d i = 0 , i = 0 , 1 , ⋯   , k − 2 , d i T g i = − g i T g i , i = 0 , 1 , ⋯   , k − 1 , g k T g i = 0 , g k T d i = 0 , i = 0 , 1 , ⋯   , k − 1. (9) \left\{ \begin{array}{rcl} d_{k-1}^TGd_i=0, &i=0,1,\cdots,k-2,\\ d_i^Tg_i=-g_i^Tg_i,&i=0,1,\cdots,k-1,\\ g_k^Tg_i=0,g_k^Td_i=0,&i=0,1,\cdots,k-1. \end{array} \right. \tag{9} dk1TGdi=0,diTgi=giTgi,gkTgi=0,gkTdi=0,i=0,1,,k2,i=0,1,,k1,i=0,1,,k1.(9)
    现令
    d k = − g k + β k − 1 d k − 1 + ∑ i = 0 k − 1 β k ( i ) d i (10) d_k=-g_k+\beta_{k-1}d_{k-1}+\sum_{i=0}^{k-1}\beta_{k}^{(i)}d_i\tag{10} dk=gk+βk1dk1+i=0k1βk(i)di(10)
    其中 β k − 1 , β k ( i ) ( i = 0 , 1 , ⋯   , k − 2 ) \beta_{k-1},\beta_k^{(i)}(i=0,1,\cdots,k-2) βk1,βk(i)(i=0,1,,k2)得选择要满足
    d k T G d i = 0 , i = 0 , 1 , ⋯   , k − 1 (11) d_k^TGd_i=0,i=0,1,\cdots,k-1\tag{11} dkTGdi=0,i=0,1,,k1(11)
    d i T G ( i = 0 , 1 , ⋯   , k − 1 ) d_i^TG(i=0,1,\cdots,k-1) diTG(i=0,1,,k1)左乘(10)得
    β k − 1 = g k T G d k − 1 d k − 1 T G d k − 1 , β k ( 1 ) = g k T G d i d i T G d i , i = 0 , 1 , ⋯   , k − 2 (12) \beta_{k-1}=\frac{g_k^TGd_{k-1}}{d_{k-1}^TGd_{k-1}},\beta_k^{(1)}=\frac{g_k^TGd_i}{d_i^TGd_i},i=0,1,\cdots,k-2\tag{12} βk1=dk1TGdk1gkTGdk1,βk(1)=diTGdigkTGdi,i=0,1,,k2(12)
    类似于(8),我们有
    g i + 1 − g i = G ( x i + 1 − x i ) = α i G d i , i = 0 , 1 , ⋯   , k − 1 g_{i+1}-g_i=G(x_{i+1}-x_i)=\alpha_iGd_i,i=0,1,\cdots,k-1 gi+1gi=G(xi+1xi)=αiGdi,i=0,1,,k1

    α i G d i = g i + 1 − g i , i = 0 , 1 , ⋯   , k − 1 (13) \alpha_iGd_i=g_{i+1}-g_i,i=0,1,\cdots,k-1\tag{13} αiGdi=gi+1gi,i=0,1,,k1(13)
    于是由归纳法假设(9)可得
    β k ( i ) = g k T G d i d i T G d i = g k T ( g i + 1 − g i ) d i T ( g i + 1 − g i ) = 0 , i = 0 , 1 , ⋯   , k − 2. \beta_k^{(i)}=\frac{g_k^TGd_i}{d_i^TGd_i}=\frac{g_k^T(g_{i+1}-g_i)}{d_i^T(g_{i+1}-g_i)}=0,i=0,1,\cdots,k-2. βk(i)=diTGdigkTGdi=diT(gi+1gi)gkT(gi+1gi)=0,i=0,1,,k2.
    于是,第k步得搜索方向为
    d k = − g k + β k − 1 d k − 1 , (14) d_k=-g_k+\beta_{k-1}d_{k-1},\tag{14} dk=gk+βk1dk1,(14)
    其中 β k − 1 \beta_{k-1} βk1由(12)确定,即
    β k − 1 = g k T G d k − 1 d k − 1 T G d k − 1 (15) \beta_{k-1}=\frac{g_k^TGd_{k-1}}{d_{k-1}^TGd_{k-1}}\tag{15} βk1=dk1TGdk1gkTGdk1(15)
    同时有 d k T g k = − g k T g k d_k^Tg_k=-g_k^Tg_k dkTgk=gkTgk。这样确定了一组由负梯度方向形成得共轭方向,而把沿着这组方向进行迭代得方向称为共轭梯度法。其证明过程这里略过。
    下面我们给出共轭梯度法求解无约束优化问题(1)极小点得算法步骤


    算法2:共轭梯度法
    0. 给定迭代精度 0 ≤ ϵ < 1 0\le\epsilon\lt 1 0ϵ<1和初始点 x 0 x_0 x0。计算 g 0 = ∇ f ( x 0 ) g_0=\nabla f(x_0) g0=f(x0)。令 k = 0 k=0 k=0

    1. ∣ ∣ g k ∣ ∣ ≤ ϵ ||g_k||\le\epsilon gkϵ,停算,输出 x ) ≈ x k x^)\approx x_k x)xk
    2. 计算搜索方向 d k d_k dk:
      KaTeX parse error: Unknown column alignment: s at position 29: …\begin{array}{ls̲c} -g_k,&k=0,\\…
      其中当 k ≥ 1 k\ge 1 k1时, β k − 1 \beta_{k-1} βk1由(15)确定
    3. 利用线搜索方法确定搜索步长 α k \alpha_k αk
    4. x k + 1 = x k + α k d k x_{k+1}=x_k+\alpha_kd_k xk+1=xk+αkdk,并计算 g k + 1 = ∇ f ( x k + 1 ) g_{k+1}=\nabla f(x_{k+1}) gk+1=f(xk+1)
    5. k = k + 1 k=k+1 k=k+1,转步1

    计算公式(15)是由Fletcher和Reeves给出得,故称之为FR公式,算法2也称之为FR共轭梯度法。除FR工诗外,尚有下列著名公式:
    β k = g k + 1 T g k + 1 − d k T g k , ( D i x o n 公 式 ) β k = g k + 1 T g k + 1 d k T ( g k + 1 − g k ) , ( D a i − Y u a n 公 式 ) β k = g k + 1 T ( g k + 1 − g k ) d k T ( g k + 1 − g k ) , ( C r o w d e r − W o l f e 公 式 ) β k = g k + 1 T ( g k + 1 − g k ) g k T g k , ( P o l a k , R i b i e r e , P l o y a k , P R P 公 式 ) \begin{aligned} \beta_k&=\frac{g_{k+1}^Tg_{k+1}}{-d_k^Tg_k}, (Dixon公式) \\ \beta_k&=\frac{g_{k+1}^Tg_{k+1}}{d_k^T(g_{k+1}-g_k)}, (Dai-Yuan公式) \\ \beta_k&=\frac{g_{k+1}^T(g_{k+1}-g_k)}{d_k^T(g_{k+1}-g_k)}, (Crowder-Wolfe公式) \\ \beta_k&=\frac{g_{k+1}^T(g_{k+1}-g_k)}{g_k^Tg_k}, (Polak,Ribiere,Ployak,PRP公式) \\ \end{aligned} βkβkβkβk=dkTgkgk+1Tgk+1,(Dixon)=dkT(gk+1gk)gk+1Tgk+1,(DaiYuan)=dkT(gk+1gk)gk+1T(gk+1gk),(CrowderWolfe)=gkTgkgk+1T(gk+1gk),(Polak,Ribiere,Ployak,PRP)

    三、共轭梯度法得matlab实现
    在共轭梯度法得实际使用中,通常在迭代n步或n+1步之后,重新选取负梯度方向作为搜索方向,我们称之为再开始共轭梯度法。这是因为对于一般非二次函数而言,n步迭代后共轭梯度法产生得搜索方向往往不再具有共轭性。而对于大规模问题,常常每 m ( m < n 或 m ≪ n ) m (m<n或m\ll n) m(m<nmn)步就进行再开始。此外,当搜索方向不是下降方向时,也插入负梯度方向所作为搜索方向。
    这里给出基于Armijo-rule非精确线搜索得再开始FR共轭梯度法得matlab程序。

    function [fmin, xmin] = frcg(fun, gfun, x0, epsilon)
    
    maxk = 5000;
    rho = 0.6;
    sigma = 0.4;
    k = 0;
    n = length(x0);
     
     while k < maxk
         g = feval(gfun, x0);
         itern = k - (n+1) * floor(k / (n + 1));
         itern = itern + 1;
         
         if (itern == 1)
             d = -g;
         else
             beta = (g' * g) / (g0' * g0);
             d = -g + beta * d0; gd = g' * d;
             if (gd >= 0.0)
                 d = -g;
             end
         end
         
         if (norm(g) < epsilon), break; end
         
         m = 0; mk = 0;
         
         while (m < 20)  % armijo-rule 
             if (feval(fun, x0 + rho^m*d) < feval(fun, x0) + sigma * rho^m*g'*d)
                 mk = m; break;
             end
             m = m + 1;
         end
         
         x0 = x0 + rho^mk*d;
         val = feval(fun, x0);
         fprintf('kIter = %d, fmin = %f\n', k, val);
         
         g0 = g; d0 = d;
         k = k+1;
     end
     x = x0;
     val = feval(fun, x);
     xmin = x;
     fmin = val;
    
    
    end
    

    利用程序求解无约束优化问题
    min ⁡ x ∈ R 2 f ( x ) = 100 ( x 1 2 − x 2 ) 2 + ( x 1 − 1 ) 2 \min_{x\in\mathbb{R^2}}\quad f(x)=100(x_1^2-x_2)^2+(x_1-1)^2 xR2minf(x)=100(x12x2)2+(x11)2
    该问题由精确解 x ∗ = ( 1 , 1 ) T , f ( x ∗ ) = 0 x^*=(1,1)^T,f(x^*)=0 x=(1,1)T,f(x)=0

    求解main函数

    x0 = [0, 0]';
    epsilon = 1e-4;
    
    [fmin, xmin] = frcg('func', 'gfunc', x0, epsilon);
    fprintf('frcg: fmin = %f, xmin = (%f, %f)\n', fmin, xmin(1), xmin(2));
    
    [x, f] = fminsearch('func', x0);
    fprintf('build-in search: fmin = %f, xmin = (%f, %f)\n', f, x(1), x(2));
    
    

    函数定义以及梯度求解

    function f = func(x)
    
    f = 100 * (x(1)^2 - x(2))^2 + (x(1) - 1)^2;
    
    end
    
    function grad = gfunc(x)
    
    grad = [400 * x(1) * (x(1)^2-x(2))+2*(x(1)-1); ...
        -200 * (x(1)^2-x(2))];
    
    end
    

    求解结果为:

    frcg: fmin = 0.000000, xmin = (0.999921, 0.999841)
    build-in search: fmin = 0.000000, xmin = (1.000004, 1.000011)
    
    更多相关内容
  • 共轭梯度法实现求解线性方程组。 可以用来求解一般的线性方程组方程,程序清晰易懂。
  • 共轭梯度法学习笔记

    千次阅读 2019-06-27 20:07:28
    共轭梯度法的基本思想是把共轭性与最速下降法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点。根据共轭方向的基本性质,这种方法具有二次终止性。 用共轭梯度法求解简单...

    共轭梯度法是介于最速下降法与牛顿法之间的一个方法,它仅需一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点。共轭梯度法的基本思想是把共轭性与最速下降法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点。根据共轭方向的基本性质,这种方法具有二次终止性。

    用共轭梯度法求解简单多元函数问题:

    引入泰勒展开式概念:

    f(x)=f\left(x_{0}\right)+f^{\prime}\left(x_{0}\right)\left(x-x_{0}\right)+\frac{f^{(2)}\left(x_{0}\right)}{2 !}\left(x-x_{0}\right)^{2}+\cdots+\frac{f^{(n)}\left(x_{0}\right)}{n !}\left(x-x_{0}\right)^{n}

    则对x_{1}x_{2}求一阶偏导得到在x^{(0)}点的梯度方向g_{0}=\nabla f\left(x^{(0)}\right)。那么$g_{0}$$p_{0}$是什么关系呢?注意这道题是求最小值问题,梯度方向是函数局部上升最快方向,则反方向为局部下降最快方向。

    题目中\beta有以下几种常见形式

    \beta_{j}=\frac{\left\|\nabla f\left(y^{(j+1)}\right)\right\|^{2}}{\left\|\nabla f\left(y^{(j)}\right)\right\|^{2}}

    \beta_{j}=\frac{\boldsymbol{g}_{j+1}^{\mathrm{T}}\left(\boldsymbol{g}_{i+1}-\boldsymbol{g}_{j}\right)}{\boldsymbol{g}_{j}^{\mathrm{T}} \boldsymbol{g}_{j}}

    \beta_{j}=\frac{\boldsymbol{g}_{i+1}^{\mathrm{T}}\left(\boldsymbol{g}_{i+1}-\boldsymbol{g}_{i}\right)}{\boldsymbol{d}^{(j) \mathrm{T}}\left(\boldsymbol{g}_{j+1}-\boldsymbol{g}_{j}\right)}

    \beta_{j}=\frac{\boldsymbol{d}^{(j) T} \nabla^{2} f\left(\boldsymbol{x}^{(j+1)}\right) \boldsymbol{g}_{j+1}}{\boldsymbol{d}^{(j) T} \nabla^{2} f\left(\boldsymbol{x}^{(j+1)}\right) \boldsymbol{d}^{(j)}}

    参考网址:

    1、数学优化入门:梯度下降法、牛顿法、共轭梯度法

    展开全文
  • FR共轭梯度法

    2022-04-25 18:19:58
    共轭梯度法的基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜素,求出目标函数的极小点。根据共轭方向基本性质,这种方法具有二次终止性。 对于二次凸函数的共轭...

    Fletcher-Reeves共轭梯度法,简称FR法。

    共轭梯度法的基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜素,求出目标函数的极小点。根据共轭方向基本性质,这种方法具有二次终止性。

    对于二次凸函数的共轭梯度法:

    min f(x) = 1/2 xTAx + bTx + c,

    其中x∈ Rn,A是对称正定矩阵,c是常数。

    具体求解方法如下:

    首先,任意给定一个初始点x(1),计算出目标函数f(x)在这点的梯度,若||g1|| = 0,则停止计算;否则,令

    d(1) = -▽f(x(1)) = -g1。

    沿方向d(1)搜索,得到点x(2)。计算在x(2)处的梯度,若||g2|| ≠ 0,则利用-g2和d(1)构造第2个搜索方向d(2),在沿d(2)搜索。

    一般地,若已知点x(k)和搜索方向d(k),则从x(k)出发,沿d(k)进行搜索,得到

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

    其中步长λk满足

    f(x(k) + λkd(k)) = min f(x(k)+λd(k))。

    此时可求出λk的显示表达

     

    计算f(x)在x(k+1)处的梯度。若||gk+1|| = 0,则停止计算;否则,用-gk+1和d(k)构造下一个搜索方向d(k+1),并使d(k+1)和d(k)关于A共轭。按此设想,令

    d(k+1) = -gk+1 + βkd(k),

    上式两端左乘d(k)TA,并令

    d(k)TAd(k+1) = -d(k)TAgk+1 + βkd(k)TAd(k) = 0,

    由此得到

    βk = d(k)TAgk+1 / d(k)TAd(k)。

    再从x(k+1)出发,沿方向d(k+1)搜索。

    在FR法中,初始搜索方向必须取最速下降方向,这一点决不可忽视。因子βk可以简化为:βk = ||gk+1||2 / ||gk||2。

    实现算法如下:

     

    主函数

    clear

    clc

    close all

    %%

    F=@(x) 3/2*x(1)^2+1/2*x(2)^2-x(1)*x(2)-2*x(1);

    gradF=@(x) [3*x(1)-x(2)-2; -x(1)+x(2)];

    x0=[-2 4]';%初始点

    TolGrad=1e-5; %容忍误差

    MaxIter=5e5;%最大迭代次数

    [x,f1,k,diedai,var,ff]=ConjGrad(F,gradF,x0,TolGrad,MaxIter);

    x

    f1

    k

    figure(1)

    plot(1:k,diedai,'linewidth',2)

    xlabel 迭代次数

    ylabel 误差

    title 目标函数迭代曲线

    set(gcf,'color','w')

    %% 验证结果有效性 暴力求解极小值

    xx=linspace(-10,10,500);

    yy=linspace(-10,10,500);

    [x,y]=meshgrid(xx,yy);

    z=3/2*x.^2+1/2*y.^2-x.*y-2*x;

    figure(2)

    surf(x,y,z)

    min(min(z))

    set(gcf,'color','w')

    子函数

    function [x,f1,iter,diedai,var,ff]=ConjGrad(F,gradF,x0,TolGrad,MaxIter)

    %功能:用FR共轭梯度法求解无约束问题minf(x)

    %输入:F原函数,grad F函数梯度,x0是初始点,TolGrad....容忍误差,MaxIter....最大迭代次数

    %输出:x,f1,iter分别是取得极小值的x,近似最优点和迭代次数,diedai迭代信息

    iter = 0;

    f0   = F(x0);

    c    = gradF(x0);

    Converged = norm(c) < TolGrad;

    alpha = 1e-6*norm(c);

    while iter<MaxIter && ~Converged

       iter = iter + 1;

       d = -c;

       f = @(alpha) F(x0+alpha*d);

       alphaUpper = bracket( f, 0, 0.1*alpha );

       [alpha,f1] = fminbnd( f, 0, alphaUpper );

       x = x0 + alpha*d;

       var(iter,1:2) = x;

       ff (iter) = f1;

       c = gradF(x);

       diedai(iter) = norm(c);

       Converged = (norm(c) < TolGrad);

       x0 = x;

    end

    end

    结果:

    迭代次数

    设计变量

    目标函数值

    x1

    x2

    1

    1.52941176

    2.235294118

    -0.47059

    2

    0.94117647

    1.058823529

    -0.98962

    3

    1.01038062

    1.024221453

    -0.9998

    4

    0.9988466

    1.001153403

    -1

    5

    1.00020354

    1.00047493

    -1

    6

    0.99997739

    1.000022634

    -1

    7

    1.000004

    1.000009328

    -1

    x =

        1.0000

        1.0000

    f1 =

       -1.0000

    k =

         7

    ans 

       -0.9997

     

    查看迭代曲线误差,在第三步的时候,结果就基本收敛,收敛速度较快,通过求解列举法,求出了该函数的极小值,与我们的FR算法对比,可以发现结果一样,验证了FR算法的有效性,

    展开全文
  • 提出了一种分析频谱的新方法,其主要思想是采用共轭梯度法训练傅里叶基神经网络权值,根据权值获得信号的幅度谱和相位谱,并给出了基于Matlab语言的频谱分析应用实例。仿真结果表明,与FFT相比,该方法具有计算精度...
  • 预处理共轭梯度法(2)

    千次阅读 2019-12-08 11:24:38
    预处理共轭梯度法(2) 关于预处理矩阵M的选取 1.回顾算法 共轭梯度毒发的基本性质:共轭梯度法生成的剩余向量相互正交,其下降的方向关于A互为共轭 由此,我们可以得出: 2.预处理阵M选取的前提条件 3.一种观点...

    预处理共轭梯度法(2)

    关于预处理矩阵M的选取

    1.回顾算法

    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    共轭梯度毒发的基本性质:共轭梯度法生成的剩余向量相互正交,其下降的方向关于A互为共轭

    由此,我们可以得出:
    在这里插入图片描述

    2.预处理阵M选取的前提条件

    在这里插入图片描述

    3.一种观点

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    4.广义共轭梯度法

    在这里插入图片描述
    在这里插入图片描述

    5.不完全Cholesky分解

    回顾在矩阵的三角分解法中的平方根法

    定理(Cholesky分解):如果A为n阶对称正定矩阵,则存在一个实的非奇异下三角矩阵L使 A = L L T A = LL^T A=LLT ,当限定L的对角元素为正时,这种分解是唯一的

    为了避免开平方,我们也可以使用分解式 A = L D L T A = LDL^T A=LDLT

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    其核心思想在于保证分解后的矩阵的稀疏性,使其易于求解
    在这里插入图片描述
    在这里插入图片描述

    6.分块不完全Cholesky分解

    在这里插入图片描述
    对分块三对角矩阵A在这里插入图片描述
    我们令
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    对于第二个途径在这里插入图片描述

    展开全文
  • 19.90 积分实验的题目和要求 1、所属课程名称:最优化方法2、实验日期:2010 年 5 月 10 日~2010 年 5 月 15 日3、实验目的掌握最速下降法,牛顿法和共轭梯度法的算法思想,并能上机编程实现相应的算法。二、实验...
  • 数值最优化—无约束问题共轭梯度法
  • 实验目的:掌握最速下降法,牛顿法和共轭梯度法的算法思想,并能上机编程实现相应的算法。四.实验要求:用MATLAB实现最速下降法,牛顿法和共轭梯度法求解实例。五.实验原理:最速下降法是以...
  • 共轭梯度法推导

    2020-03-24 17:10:21
     在介绍共轭梯度法前,首先介绍一下共轭向量的概念。对于向量e1\boldsymbol{e_1}e1​,e2\boldsymbol{e_2}e2​,如果两个向量正交,则有e1Te2=0\boldsymbol{e_1}^\mathrm{T}\boldsymbol{e_2}=0e1​Te2​=0,那么...
  • 优化算法-共轭梯度法

    千次阅读 2014-09-22 20:27:01
    优化算法-共轭梯度法 (2012-04-20 08:57:05) 转载▼ 标签: 杂谈   最速下降法 1.最速下降方向 函数f(x)在点x处沿方向d的变化率可用方向导数来表示。对于可微函数,...
  • 在一般问题的优化中,最速下降法和共轭梯度法都是非常有用的经典方法,但最速下降法往往以”之”字形下降,速度较慢,不能很快的达到最优值,共轭梯度法则优于最速下降法,在前面的某个文章中,我们给出了牛顿法和最...
  • 共轭梯度法详细推导分析

    万次阅读 多人点赞 2018-11-29 21:10:57
    共轭梯度法是一种经典的优化算法。算法求解速度较快,虽然比梯度下降法复杂,但是比二阶方法简单。 一、引入 1. 优化模型建立 假定待优化的问题如下所示: min⁡xf(x)=12xTAx−bTx \min_{x} f(x)=\frac{1}{2}x^TAx -...
  • 共轭梯度法也是解决无约束优化问题的常用迭代算法,它结合了最速下降法矩阵共轭梯度的性质,可以加快算法的迭代过程。且如果初始点选取后的最终优化中不满足精度条件,还可保存上一步得到的迭代点进行再次迭代直到...
  • 预处理共轭梯度法(1)

    千次阅读 2019-12-07 17:16:00
    预处理共轭梯度法 对问题的描述 共轭梯度法的收敛性分析 定理:设A为n x n对称正定矩阵,其最大与最小特征值分别为λ1\lambda _{1}λ1​和λn\lambda _{n}λn​,Ax=bAx = bAx=b的精确解为x∗x^{*}x∗,则对任意...
  • 共轭梯度法误差分析所用范数为 注4.设 x* 是方程组Ax = b的解,A的特征值为: ?1≥?2 ≥ …≥?n> 0 共轭梯度法迭代向量xk 误差估计结果为 注2. 共轭梯度法适用于求解对称正定矩阵方程组。 * 参考文献: An ...
  • 最优化方法-共轭梯度法

    千次阅读 2019-03-31 17:16:23
    最优化方法-共轭梯度法 1.简介 共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出的。其基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜素,求...
  • 共轭梯度法的推导与完整算法

    万次阅读 多人点赞 2017-10-09 19:51:17
    共轭梯度法学习自知乎:https://www.zhihu.com/question/27157047和非线性规划课程简介在数值线性代数中,共轭梯度法是一种求解对称正定线性方程组Ax=b的迭代方法。事实上,求解Ax=b等价于求解: min||Ax−b||22min|...
  • Newton算法基本思想牛顿梯度下降的效率对比 1. 一维搜索 最优化问题一般选择某一组变量,然后在满足一定的限制条件下,求出使目标值达到最优(最大或最小)的变量值。大部分时候,最优化问题都采用迭代计算...
  • 事实上这个方法(思想)在实际中是被用于求解线性方程的,当然单纯的梯度下降形式并没有被直接采用,被广泛用于求解对称、正系数矩阵方程组的方法是,基于梯度下降原理实现的共轭梯度法,这一方法在大...
  • 1 梯度下降 函数在某一点的梯度是,在该方向单位步长上升最快的向量。梯度下降是利用待优化变量,沿着负梯度方向不断迭代寻找最优值。 直观理解: 梯度下降算法流程: (PPT画个图可真难) 梯度...
  • 共轭方向法和共轭梯度法

    万次阅读 多人点赞 2017-11-16 15:18:46
    共轭方向是介于最速下降和Newton之间的一种方法。克服了最速下降的锯齿现象,从而提高了收敛速度;同时,共轭方向的迭代公式比较简单,不必求目标函数的Hesse矩阵,比Newton减少了计算量和存储量。是一...
  • 共轭梯度法原理与实现

    万次阅读 多人点赞 2015-05-29 23:24:47
    作者:金良(golden1314521@gmail.com) csdn博客: 共轭...定义 共轭方向的性质 共轭方向法 算法描述 算法的收敛性 搜索步长kalpha_k的确定 共轭梯度法 共轭梯度法的原理 共轭梯度算法描述 共轭梯度算法Python实现 r
  • 最优化理论——共轭梯度法算法思想共轭方向法:共轭梯度法:算法步骤共轭方向法:共轭梯度法:代码示例 算法思想 共轭方向法: 共轭梯度法: 算法步骤 共轭方向法: 共轭梯度法: 代码 Matlab代码如下: ...
  • 数学优化入门:梯度下降法、牛顿法、共轭梯度法

    万次阅读 多人点赞 2016-10-13 19:45:43
    1、基本概念 1.1 方向导数 1.2 梯度的概念 ...那么,某一点的梯度方向是在该点坡度最陡的方向,而梯度的大小告诉我们坡度到底有多陡。 对于含有n个变量的标量函数,其梯度表示为 1.3 梯度与方...
  • 最优化方法——最速下降法,阻尼牛顿法,共轭梯度法 目录 最优化方法——最速下降法,阻尼牛顿法,共轭梯度法 1、不精确一维搜素 1.1 Wolfe-Powell 准则 2、不精确一维搜索算法计算步骤 3、最速下降法 3.1 ...
  • 如何理解共轭梯度法
  • \qquad共轭方向的意义在于加快最速下降的收敛速度,避免牛顿方法的大量计算。最初是为了解决 minimizef(x)=12x′Qx−b′xsubject to x∈ℜn minimize\quad f(x)=\frac{1}{2}x^{&#x27;}Qx-b^{&....
  • 最近小编复习了一下无约束问题最优化算法中的共轭梯度法。无约束问题最优化方法包括最速下降法、牛顿法、共轭梯度法、拟牛顿法等等。借用书中的一句话: 无约束优化问题的求解通过一系列一维搜索来实现。因此怎样...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,074
精华内容 829
关键字:

共轭梯度法思想