基于最小二乘修正的混合HS和DY共轭梯度法陈贞晶【期刊名称】《《重庆科技学院学报（自然科学版）》》【年(卷),期】2019(021)005【总页数】6页(P44-49)【关键词】共轭梯度法; Wolfe线搜索; 最小二乘法; 一致凸函数; 全局收敛【作者】陈贞晶【作者单位】重庆师范大学数学科学学院重庆 401331【正文语种】中文【中图分类】O224共轭梯度法是求解大规模无约束优化问题的最有效的方法之一，具有所需存储量小、强收敛性和计算方便等优点。
比如考虑无约束优化问题minf(x), x∈Rn，共轭梯度法的一般迭代格式为：xk+1=xk+αkdk(1)d0=-g0,dk+1=-gk+1+βkdk(2)其中：αk是通过某种线搜索获得的步长，αk>0；dk+1是搜索方向；g(x)是目标函数f(x)的梯度，gk+1=▽f(xk+1)；βk是共轭梯度参数，简称CG参数。
不同的βk值，对应不同的共轭梯度方法。
常用的线搜索有很多，我们在这里只考虑Wolfe线搜索：f(xk+αkdk)-f(xk)≤δαk▽f(xk)Tdk(3)▽f(xk+αkdk)Tdk≥σ▽f(xk)Tdk(4)其中，0<δ<σ<1。
Hestenes-Stiefel(简称“HS”)方法和Dai-Yuan(简称“DY”)方法都是经典的共轭梯度方法，其参数[1]如下：其中：是欧几里得范数；yk-1=gk-gk-1。
HS方法在非精确线搜索下不能保证收敛性，可能无限循环，且不趋近于任何一个解点，但数值计算效果较好。
DY方法具有强收敛性，但由于在计算时会受干扰现象的影响，计算效果不佳[2]。
1 HCG方法的修正1.1 HCG方法2008年，Neculai Andrei基于拟牛顿方向满足割线条件，提出了混合的HS和DY方法[2]，简称HCG方法。
其CG参数如下：其中割线方程为 Bk+1sk=yk。
HCG方法的计算效果不是很好，不如经典的HS方法。
最小二乘法分类最小二乘法（Least Squares Method）是一种常用的参数估计方法，用于寻找一个函数模型的最佳拟合参数，使得模型的预测值与观测值的残差平方和最小化。
这种方法最早由高斯提出，并被广泛应用于统计学和计算机科学等领域。
本文将介绍最小二乘法的基本原理、应用场景以及相关的算法和评估指标。
一、基本原理：最小二乘法用于求解形如y = f(x;θ) 的函数模型的参数θ，其中y是观测值，x是自变量，f是函数模型。
最小二乘法的目标是找到最佳的参数θ，使得模型的预测值与实际观测值之间的残差平方和最小化。
具体步骤如下：1. 定义函数模型：根据具体问题，选择适当的函数模型，如线性模型、多项式模型、指数模型等。
2. 表达目标函数：根据函数模型和参数θ，将目标函数表达为关于θ的函数形式。
3. 定义损失函数：通常采用残差的平方和作为损失函数，即Loss = Σ(y_i - f(x_i;θ))^2 。
4. 求解参数θ：通过最小化损失函数，即求解使得∂Loss/∂θ = 0 的参数θ。
5. 参数估计：根据求解得到的参数θ，即可获得最佳的函数模型。
二、应用场景：最小二乘法在各个领域都有广泛的应用，以下是一些常见的应用场景：1. 线性回归：最小二乘法用于拟合线性回归模型，求解自变量与因变量之间的关系。
2. 特征选择：最小二乘法可用于特征选择，筛选对目标变量影响最大的特征。
3. 数据压缩：通过最小二乘法可以估计出一个低维子空间，将高维数据进行压缩。
4. 图像处理：最小二乘法可用于图像去噪、图像恢复等问题，如使用低秩矩阵模型对图像进行恢复。
5. 信号处理：最小二乘法可用于信号滤波、信号恢复等问题，如基于 DCT 的音频和图像压缩。
三、算法与评估指标：1. 最小二乘法的数值解：在实际应用中，最小二乘法的数值解可以通过各种数值优化算法来求解，包括梯度下降法、牛顿法、共轭梯度法等。
2. 算法评估指标：常用的评估指标包括残差平方和（Residual Sum of Squares, RSS）、均方误差（Mean Square Error, MSE）以及决定系数（Coefficient of Determination, R^2）等。
最小二乘拟合算法最小二乘定义一般情况下，最小二乘问题求的是使某一函数局部最小的向量 x，函数具有平方和的形式，求解可能需要满足一定的约束：信赖域反射最小二乘要理解信赖域优化方法，请考虑无约束最小化问题，最小化 f(x)，该函数接受向量参数并返回标量。
假设您现在位于 n 维空间中的点 x 处，并且您要寻求改进，即移至函数值较低的点。
基本思路是用较简单的函数 q 来逼近 f，该函数需能充分反映函数 f 在点 x 的邻域 N 中的行为。
此邻域是信赖域。
试探步 s 是通过在 N 上进行最小化（或近似最小化）来计算的。
以下是信赖域子问题如果f(x + s) < f(x)，当前点更新为 x + s；否则，当前点保持不变，信赖域 N 缩小，算法再次计算试探步。
在定义特定信赖域方法以最小化 f(x) 的过程中，关键问题是如何选择和计算逼近 q（在当前点 x 上定义）、如何选择和修改信赖域 N，以及如何准确求解信赖域子问题。
在标准信赖域方法中，二次逼近 q 由 F 在 x 处的泰勒逼近的前两项定义；邻域 N 通常是球形或椭圆形。
以数学语言表述，信赖域子问题通常写作公式2其中，g 是 f 在当前点 x 处的梯度，H 是 Hessian 矩阵（二阶导数的对称矩阵），D 是对角缩放矩阵，Δ是正标量，∥ . ∥是 2-范数。
此类算法通常涉及计算 H 的所有特征值，并将牛顿法应用于以下久期方程它们要耗费与 H 的几个分解成比例的时间，因此，对于信赖域问题，需要采取另一种方法。
Optimization Toolbox 求解器采用的逼近方法是将信赖域子问题限制在二维子空间 S 内。
一旦计算出子空间 S，即使需要完整的特征值/特征向量信息，求解的工作量也不大（因为在子空间中，问题只是二维的）。
现在的主要工作已转移到子空间的确定上。
二维子空间 S 是借助下述预条件共轭梯度法确定的。
求解器将 S 定义为由 s1 和 s2 确定的线性空间，其中 s1 是梯度 g 的方向，s2 是近似牛顿方向，即下式的解或是负曲率的方向，以此种方式选择 S 背后的理念是强制全局收敛（通过最陡下降方向或负曲率方向）并实现快速局部收敛（通过牛顿步，如果它存在）。
共轭梯度实验报告共轭梯度实验报告引言：共轭梯度是一种常用的优化算法，广泛应用于数值计算和机器学习等领域。
本实验旨在探究共轭梯度算法的原理和应用，并通过实验验证其在解决线性方程组和最小二乘问题中的有效性和优越性。
一、共轭梯度算法的原理共轭梯度算法是一种迭代法，用于求解对称正定矩阵的线性方程组。
其基本思想是通过选择一组互相共轭的搜索方向，以最小化目标函数的二次型形式。
共轭梯度算法的核心步骤包括初始化、计算搜索方向、计算步长和更新解向量等。
二、共轭梯度算法在线性方程组求解中的应用共轭梯度算法在求解线性方程组方面具有独特的优势。
相比于传统的直接求解方法，共轭梯度算法不需要存储整个矩阵，仅需存储向量和少量中间变量，节省了内存空间。
同时，共轭梯度算法具有较快的收敛速度，能够在有限的迭代次数内得到较精确的解。
三、共轭梯度算法在最小二乘问题中的应用最小二乘问题是一类常见的优化问题，广泛应用于数据拟合和参数估计等领域。
共轭梯度算法在最小二乘问题中的应用主要体现在正规方程法和QR分解法的改进上。
通过共轭梯度算法，可以有效地求解最小二乘问题，得到更准确的拟合结果。
四、实验设计与结果分析本实验选择了一组线性方程组和最小二乘问题进行测试，分别使用共轭梯度算法和传统直接求解方法进行比较。
实验结果表明，共轭梯度算法在求解线性方程组和最小二乘问题时，具有更快的收敛速度和更高的精度。
尤其在大规模问题上，共轭梯度算法的优势更加明显。
结论：共轭梯度算法是一种有效的优化算法，适用于求解对称正定矩阵的线性方程组和最小二乘问题。
通过选择互相共轭的搜索方向，共轭梯度算法能够在有限的迭代次数内得到较精确的解。
在实际应用中，共轭梯度算法具有较快的收敛速度和较高的精度，是一种值得推广和应用的算法。
总结：通过本次实验，我们深入了解了共轭梯度算法的原理和应用，并通过实验验证了其在线性方程组和最小二乘问题中的有效性和优越性。
共轭梯度算法作为一种常用的优化算法，在数值计算和机器学习等领域具有广泛的应用前景。
