526互联

2023-07-11 《数值优化方法》-庞丽萍，肖现涛-无约束最优化（六）

发布时间 2023-07-11 17:29:27作者: XNEF

2023-07-11 《数值优化方法》-庞丽萍，肖现涛-无约束最优化（六）

数值优化方法Matlab共轭梯度法共轭方向法

回顾上节的最速下降法的特征：最速下降法迭代路径呈锯齿状，即. 这一节给出共轭的概念，其是正交性的推广，然后给出共轭方向（梯度）法.

**定义 1.7 ** 设是 对称正定矩阵，是维非零向量. 如果


那么称向量和是共轭的 (或共轭).

自然地, 两个向量的共轭可以推广到个向量共轭. 设是维非零向量组，如果


那么称是共轭的. 即两两共轭.

命题 1.2 设为阶对称正定矩阵，若非零向量组是共轭的，则是线性无关的.

证明只需要假设存在一组常数使得向量组线性相关，然后证得即可.

命题 1.3 设为阶对称正定矩阵，若非零向量组是共轭的. 若与都直交，即, 则.

注意到构成中的一组基（命题 1.2）, 则可由表示，由即得.

下面给出共轭方向法的算法：

Step 1. 取初始点, 搜索方向满足, 精度,

Step 2. 若, 置 则停止, 否则转下步.

Step 3. 线搜索：


Step 4. 选取搜索方向满足


其中是对称正定矩阵.

Step 5. 令, 转 Step 2.

上述算法中，令人疑惑的地方在于的选择和搜索方向的计算，其中搜索方向可以由一个线性方程组给出。

那么共轭方向法在什么情况下收敛到最优解呢，下面的定理将给出答案。

定理 1.8 设是维对称正定矩阵, , 是任意初始点. 若搜索方向是共轭的, 是精确线搜索步长, 是共轭方向法产生的迭代点, 则有
(1) 对每一个

(2) 算法至多次迭代可得无约束优化问题的最优解.

证明：
(1) 由 以及 和


反复带入上式，得到

由于是共轭的，所以

即

由于是精确线搜索的步长 (即)，因此

(2) 由于共轭，再有可知, 即是.

二次终止性 若算法对任意的正定二次函数，从任意初始点出发，都能经过有限步达到其最优点，则称算法具有二次终止性.

正定二次函数中的即可看作是一般可导函数的Hesse矩阵，只不过不被当前迭代点的位置影响.

1. 共轭梯度法

如果在共轭方向发中利用目标函数的梯度来产生共轭方向，那么就称这样的方法维共轭梯度法.

下面给出生成正定二次函数的共轭梯度方向的方法.

给定初始点, . 如果对于第次迭代，是精确线搜索步长，要求与是共轭的且是下降方向，假设


通过选择合适的, 可以使得与之前的 共轭, 因此有

这就确定了下一步的下降方向.

上述公式中每一步的下降方向都与前面所有的下降方向有关，且需要计算当前点的Hesse矩阵，使得算法的复杂性较高. 下面给出一些更简单的下降方向的计算方法.

定理 1.9 设是维对称正定矩阵, , 是任意初始点. 若搜索方向如, 是精确搜索步长，是由共轭梯度法产生的迭代点，则
(1) ;
(2) ;
(3) .

证明: (1) 由于, 因此


又由于共轭方向法都有对：每一个

因此

(2) 由, 有


以及

因此

由 (1) 可知分式上半部分为0, 因此 (2) 成立.

(3)


带入以及定理 1.8 的(1)即得
.

通过上面的证明能够得到几种不同的下降方向迭代格式：


其中在不同取值下有

  1. Fletcher-Reeves公式（FR公式）
  2. Crowder-Wolf 公式
  3. Polak-Ribiere-Polyak 公式
  4. Dixon 公式
  5. Dai-Yuan 公式

上面五个公式虽然形式有所不同，但是都是在定理1.9证明中出现过的等价形式，即目标函数是正定二次函数且采用精确线搜索时，这些公式是等价的. 但是对于一般的优化问题，上述搜索方向并不等价.

由于共轭方向对多能生成个，因此对于一般目标函数当迭代次数大于时需要重置下降方向，如下所示

算法 7 FR共轭梯度法
Step 1. 选取初始点, 给定精度.

Step 2. 计算, 置.

Step 3. 做线搜索


得到和.

Step 4. 如果, 则停止算法, ; 否则转下步.

Step 5. 如果, 则令, 转Step 1.; 否则转下步.

Step 6. 计算


置, 转Step 2.

定理 1.10 设无约束优化问题的目标函数连续可微且有下界，梯度是Lipschitz连续. 若采用精确线搜索的FR共轭梯度法产生无穷点列, 则.

定理 1.10 说明FR共轭梯度法对于一般的连续可微有下界函数是可以收敛到局部最优解的，FR最开始提出可能是 Function minimization by conjugate gradients, Fletcher and Reeves. 070149.pdf 3.21 MB

下面是FR共轭梯度法的Matlab实现

  1. % Fletcher-Reeves 共轭梯度法 
  2. function [x xlog] = FRCG(f, x0, epsilon) 
  3. % f 目标函数，函数句柄 
  4. % g 梯度函数 函数句柄 
  5. % epsilon 精度要求 
  6. % method 线搜索方法 
  7. k = 0; 
  8. iter = 0; 
  9. maxIt = 1e4; 
  10. n = length(x0); 
  11. d1 = - My_Gradient(f, x0); 
  12. while iter <= maxIt 
  13. [alpha tx] = SuccFa(f, 1, x0, d1, 1, epsilon, 1e4); 
  14. x1 = x0 + alpha * d1; 
  15. d2 = My_Gradient(f, x1); 
  16. xlog(iter+1) = norm(d2); 
  17. x = x1; 
  18. x0 = x1; 
  19. if norm(d2) < epsilon 
  20. break 
  21. end 
  22. if k+1 == n 
  23. d1 = - My_Gradient(f, x0); 
  24. k = 0; 
  25. else 
  26. d1 = - d2 + d1 * norm(d2)^2/norm(d1)^2; 
  27. k = k+1; 
  28. end 
  29. iter = iter + 1; 
  30. end 
  31. end 
  32.  
  33. function [alphak xlog] = SuccFa(fun, alpha, x0, diff_x, h, epsil, maxIt) 
  34. k = 0; 
  35. xlog = alpha; 
  36. while k <= maxIt 
  37. alphak = alpha + h; 
  38. if fun(x0 + alphak * diff_x) < fun(x0 + alpha * diff_x) 
  39. h = 2 * h; 
  40. alpha = alphak; 
  41. else 
  42. h = - h / 4; 
  43. end 
  44. k = k + 1; 
  45. xlog(k) = alphak; 
  46. if abs(h) < epsil 
  47. break 
  48. end 
  49. end 
  50. end 
  51.  
  52. function [x] = F_alpha(alpha) 
  53. x = f(x0 + alpha * diff_x); 
  54. end 
  55.  
  56.  
  57. function [gd] = My_Gradient(f, x) 
  58. gd = x; 
  59. epsil = 1e-5; 
  60. d = [-2* epsil, -epsil 0 epsil 2*epsil]; 
  61. tx = [x x x x x]; 
  62. fx = [0,0,0,0,0]; 
  63. for i = 1:length(x) 
  64. tx(i,:) = tx(i,:) + d; 
  65. for h = 1:5 
  66. fx(h) = f(tx(:,h)); 
  67. end 
  68. gf = gradient(fx); 
  69. gd(i) = gf(3); 
  70. end 
  71. end 

测试程序

  1. f = @(x) sin(x(1)) + cos(x(2)); 
  2. x0 = [1, 1]'; 
  3. epsilon = 1e-6; 
  4. [x xlog] = FRCG(f, x0, epsilon) 
  5.  
  6. %% 书上的例子 
  7. f = @(x) 2*x(1)^4 - 4 * x(1)^2*x(2) + x(1)^2 + 2* x(2)^2-2*x(1)+5; 
  8. x0 = [0 ,0]'; 
  9. epsilon = 1e-6; 
  10. [x xlog] = FRCG(f, x0, epsilon) 

结果表明我们编写的程序确实收敛到了最优解.