论文部分内容阅读
摘 要：在实际生活中，最优化问题的求解十分普遍，例如大气模拟、自然科学、生产管理等等。所以，最优化问题的求解已经发展为关键问题。本文将就共轭梯度法的改进进行研究。首先论述共轭梯度法的发展概括，然后介绍无约朿最优化问题的基本概念，最后探讨一类求解无约束优化问题的共轭梯度法，本文的研究成果将为优化共轭梯度法解决无约束优化问题过程提供良好借鉴。
关键词：共轭梯度法；无约束；充分下降性
中图分类号：O212 文献标志码：A 文章编号：2095-9214（2015）12-0124-01
引言
因为共轭梯度法具备收敛速度快、存储量少等优点，所以该方法可以解决规模较大的优化问题。即使共轭梯度法从上世纪50年代就已经被提出，但是直至今天，其仍然是一个热门的研究方向，而且其在实际应用以及数学基础理论上具备着重要的研究意义。
一、共轭梯度法的发展概况
共轭梯度法是由几何学家Stiefel与计算数学家Hestenes发明并发展的，其主要是在20世纪50年代初为了求解Ax=bx×Rn此线性方程组提出的，其合作发表的文章至今被认为是共轭梯度法研究的奠基之作。一般地，经典共轭梯度法可以分为HS共轭梯度法、FR共轭梯度法、PRP共轭梯度法、CD共轭梯度法、LS共轭梯度法、DY共轭梯度法统。为了能够构造运算效果更强的共轭梯度算法，对经典共轭梯度法进行进一步的探讨十分重要，只有不断简化解题过程，提高解题效率，才能为数学研究以及实际应用奠定坚实基础。
二、无约朿最优化问题的基本概念
一般地，无约束最优化问题的数学模型为minf（x），x∈Rn，其中决策变量是x∈Rn目标函数为f（x）。以下将给出无约束最优化问题的最优解与极小点定义：
定义1 在无约束最优化问题minf（x），x∈Rn中，如果存在x*∈Rn，能够使任意x∈Rn满足不等式f（x*）≤f（x），那么可以称x*为目标函数f（x）的整体最优解或者整体极小点；如果x≠x*时存在f（x*） 定义2 在无约束最优化问题minf（x），x∈Rn中，如果对于任意的x*∈Rn，均可以找到x*的一个邻域Uδ（x*）={x∈Rn‖x-x*‖<δ，δ>0}（这里‖·‖表示的是欧氏范数）使得对于任意的x∈Uδ（x*）满足f（x*）≤f（x）不等式，那么可以称x*为f（x）的局部最优解或者局部极小点；相反地，x≠x*时，满足f（x*） 整体极小点一定是局部极小点，但是局部极小点却不一定是整体极小点，所以在实际问题中，我们需要求解整体极小点，但是在大多数的无约束最优化问题中却求解局部极小点，这并不是两个矛盾体，在实际问题中求得的目标函数常常是具有单个极值的良性函数，所以可以说它的局部极小点就是整体极小点。
三、一类求解无约束优化问题的共轭梯度法
1.新的共轭梯度算法及公式
改进的求解方法是一种含参数的共轭梯度法βk=λ‖gk‖2μ‖gk-1‖2-gTk-1dk-1，其中0≤λ≤μ≤1，‖·‖表示的是欧式范数，通过推广标准非精确线搜索，便可以发现一种新的线搜索f（xk+akdk）-f（xk）≤-ρa2k‖dk‖2σ1gTkdk≤g（xk+akdk）Tdk≤-σ2gTkdk，其中0<ρ≤σ1<1，σ2≥0且σ1+σ2≤1。第一，取初始点x1∈Rn，d1=-g1，k=1，ε>0；第二，如果‖gk‖<ε那么停止搜索，否则根据线搜索式解得ak，然后由xk+1=xk+akdk，解得xk+1；第三，根据βk=λ‖gk‖2μ‖gk-1‖2-gTk-1dk-1求得βk+1。当k=1时，dk=-gk，当k≥2时，dk=-gk+βkdk-1，由此求得dk+1，并置k=k+1，转回第二步。
2.算法的充分下降性
在研究无约束最优化问题的共轭梯度求解法时，不难发现其进行充分下降的条件为gTkdk≤-c‖gk‖2，k≥1，其中c>0是常数，具有重要作用。但是这个条件并不是所有算法成立的充分条件，其需要在进行非精确线性搜索σ1gTkdk≤g（xk+akdk）Tdk≤-σ2gTkdk以及f（xk+akdk）-f（xk）≤-ρa2k‖dk‖2后仍然满足充分下降性条件gTkdk≤-c‖gk‖2，k≥1才可以。
3.算法的全局收敛性证明
为了能够证明算法的全局收敛性，一般地将给出以下两个假设，并将其充分运用在非线性搜索方法的全局收敛性研究中，使得算法的全局收敛性的证明更为简便。
假设1 f（x）在水平集Ω={x|f（x）≤f（x1）}上有界；
假设2 在水平集Ω中的一个邻域U内，函数f（x）连续可微且梯度向量连续，则存在常数L>0，使得‖g（x）-g（y）‖≤L‖x-y‖，x，y∈U。
根据假设，不难推导出存在常数M>0，能够使得‖g（x）‖≤M，k≥1为建立算法全局收敛性的前提条件：
定理 若两个假设条件均被满足，{x}是算法产生中产生的，如果对于k≥1，存在常数M能够使得‖g（x）‖≤M成立，那么有limk→∞inf‖gk‖=0改进的共轭梯度算法同样具有全局收敛性。
四、结语
总之，只有不断研究与改进共轭梯度算法，才能使其既具备良好的收敛性质，又具备较好的数值表现，使得无约束最优化问题的解题效率大大提高，使得人们的生活随着共轭梯度法的应用范围日渐广泛而增添更多的便捷之处。
参考文献：
[1]崔海娟.改进共轭梯度法求解无约束优化问题[D].渤海大学，2014.
关键词：共轭梯度法；无约束；充分下降性
中图分类号：O212 文献标志码：A 文章编号：2095-9214（2015）12-0124-01
引言
因为共轭梯度法具备收敛速度快、存储量少等优点，所以该方法可以解决规模较大的优化问题。即使共轭梯度法从上世纪50年代就已经被提出，但是直至今天，其仍然是一个热门的研究方向，而且其在实际应用以及数学基础理论上具备着重要的研究意义。
一、共轭梯度法的发展概况
共轭梯度法是由几何学家Stiefel与计算数学家Hestenes发明并发展的，其主要是在20世纪50年代初为了求解Ax=bx×Rn此线性方程组提出的，其合作发表的文章至今被认为是共轭梯度法研究的奠基之作。一般地，经典共轭梯度法可以分为HS共轭梯度法、FR共轭梯度法、PRP共轭梯度法、CD共轭梯度法、LS共轭梯度法、DY共轭梯度法统。为了能够构造运算效果更强的共轭梯度算法，对经典共轭梯度法进行进一步的探讨十分重要，只有不断简化解题过程，提高解题效率，才能为数学研究以及实际应用奠定坚实基础。
二、无约朿最优化问题的基本概念
一般地，无约束最优化问题的数学模型为minf（x），x∈Rn，其中决策变量是x∈Rn目标函数为f（x）。以下将给出无约束最优化问题的最优解与极小点定义：
定义1 在无约束最优化问题minf（x），x∈Rn中，如果存在x*∈Rn，能够使任意x∈Rn满足不等式f（x*）≤f（x），那么可以称x*为目标函数f（x）的整体最优解或者整体极小点；如果x≠x*时存在f（x*）
三、一类求解无约束优化问题的共轭梯度法
1.新的共轭梯度算法及公式
改进的求解方法是一种含参数的共轭梯度法βk=λ‖gk‖2μ‖gk-1‖2-gTk-1dk-1，其中0≤λ≤μ≤1，‖·‖表示的是欧式范数，通过推广标准非精确线搜索，便可以发现一种新的线搜索f（xk+akdk）-f（xk）≤-ρa2k‖dk‖2σ1gTkdk≤g（xk+akdk）Tdk≤-σ2gTkdk，其中0<ρ≤σ1<1，σ2≥0且σ1+σ2≤1。第一，取初始点x1∈Rn，d1=-g1，k=1，ε>0；第二，如果‖gk‖<ε那么停止搜索，否则根据线搜索式解得ak，然后由xk+1=xk+akdk，解得xk+1；第三，根据βk=λ‖gk‖2μ‖gk-1‖2-gTk-1dk-1求得βk+1。当k=1时，dk=-gk，当k≥2时，dk=-gk+βkdk-1，由此求得dk+1，并置k=k+1，转回第二步。
2.算法的充分下降性
在研究无约束最优化问题的共轭梯度求解法时，不难发现其进行充分下降的条件为gTkdk≤-c‖gk‖2，k≥1，其中c>0是常数，具有重要作用。但是这个条件并不是所有算法成立的充分条件，其需要在进行非精确线性搜索σ1gTkdk≤g（xk+akdk）Tdk≤-σ2gTkdk以及f（xk+akdk）-f（xk）≤-ρa2k‖dk‖2后仍然满足充分下降性条件gTkdk≤-c‖gk‖2，k≥1才可以。
3.算法的全局收敛性证明
为了能够证明算法的全局收敛性，一般地将给出以下两个假设，并将其充分运用在非线性搜索方法的全局收敛性研究中，使得算法的全局收敛性的证明更为简便。
假设1 f（x）在水平集Ω={x|f（x）≤f（x1）}上有界；
假设2 在水平集Ω中的一个邻域U内，函数f（x）连续可微且梯度向量连续，则存在常数L>0，使得‖g（x）-g（y）‖≤L‖x-y‖，x，y∈U。
根据假设，不难推导出存在常数M>0，能够使得‖g（x）‖≤M，k≥1为建立算法全局收敛性的前提条件：
定理 若两个假设条件均被满足，{x}是算法产生中产生的，如果对于k≥1，存在常数M能够使得‖g（x）‖≤M成立，那么有limk→∞inf‖gk‖=0改进的共轭梯度算法同样具有全局收敛性。
四、结语
总之，只有不断研究与改进共轭梯度算法，才能使其既具备良好的收敛性质，又具备较好的数值表现，使得无约束最优化问题的解题效率大大提高，使得人们的生活随着共轭梯度法的应用范围日渐广泛而增添更多的便捷之处。
参考文献：
[1]崔海娟.改进共轭梯度法求解无约束优化问题[D].渤海大学，2014.