第四章共轭梯度法

快来打我* 2022-10-08 13:28 278阅读 0赞

> 内容来自马昌凤编著的《最优化方法及其Matlab程序设计》，文章仅为个人的学习笔记，感兴趣的朋友详见原书。

共轭梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法，具有超线性收敛速度，算法结构简单。同时，与前一章的最速下降法类似，**共轭梯度法只用了目标函数及其梯度值**，避免了求二阶导数，从而降低了计算和储存量。

# 共轭方向法 #

## 共轭的定义 ##

设G是n阶对称正定矩阵，若n维向量组 d 1 , d 2 , . . . , d m ( m < = n ) d\_1,d\_2,...,d\_m(m<=n) d1,d2,...,dm(m<=n)满足：  
 d i T G d j = 0 , i ≠ j d\_i^T G d\_j=0, i≠j diTGdj=0,i=j  
则称 d 1 , d 2 , . . . , d m d\_1,d\_2,...,d\_m d1,d2,...,dm为G共轭的。

**对称正定矩阵 G G G的共轭向量组必然是线性无关的**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70]

## 算法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 1]

# 共轭梯度法 #

## 算法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 2]

## 程序 ##

function [x,val,k]=frcg(fun,gfun,x0)
    % 功能: 用FR共轭梯度法求解无约束问题:  min f(x)
    %输入:  x0是初始点, fun, gfun分别是目标函数和梯度
    %输出:  x, val分别是近似最优点和最优值,  k是迭代次数.
    maxk=5000;   %最大迭代次数
    rho=0.6;sigma=0.4;
    k=0;  epsilon=1e-4; 
    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搜索
            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);
        g0=g;  d0=d; 
        k=k+1;
    end
    x=x0;
    val=feval(fun,x);

## 示例1 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 3]

## 示例2 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70]: /images/20221005/2cf476975ad5426aacd8caa573805047.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 1]: /images/20221005/45d29e9dbe68448da89d29a280d0984a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 2]: /images/20221005/753f44682ac9497fbdf72cfdbc2d8bf7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 3]: /images/20221005/aa26339cbc3b480794390e43ca5ecc1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 4]: /images/20221005/32b80ae8bd444206a1c5d5c5c8ed5029.png