共轭梯度法是利用目标函数的梯度逐步产生共轭方向并将其作为搜索方向的方法。
1. 共轭方向与共轭方向法
定义:设H是n*n方阵且对称正定。
(1)若对n维非零向量p和q,有p^THq = 0,则称p和q是H-共轭的;
(2)若对n维非零向量组d1,...,dm,对任意的i != j,di与dj是H-共轭的,则称d1,...,dm是H-共轭方程组。
当H = I,p^Tq = 0,即p与q相互正交,可见共轭是正交的推广。
定理:设H是n*n方阵且对称正定。若n维非零向量组d1,...,dm是H-共轭方程组,则d1,...,dm也是线性无关方程组。
将一组共轭方向作为搜索方向对无约束非线性规划问题(UNP)进行求解的方法称为共轭方向法。
2. 无约束凸二次规划问题的共轭梯度法
若用一组共轭方向作为搜索方向求解UQP,那么最多迭代n次即可得到其最优解,因此共轭方向法具有二次终止性。
①选定初始数据。给定初始点x,令k = 1。
②最优性判别。若▽f(x) = 0,停止,得到最优解x。否则转3。