自适应共轭梯度法的研究

Based on the property of Quasi-Newton method and adaptive algorithmic mechanism, we mainly consider some new kinds of conjugate gradient methods which have the properties, including finite-step convergence, adaptive conjugacy condition, adaptive correction, sufficient descent condition and global convergence. With them large-scale and complex in nonlinearization and abnormal state problems can be successfully solved, but also be used the field of Nonnegative Matrix Factorization...This project mainly discusses its algorithm property, convergence analysis and its application on other fields, including: ..1.Based on an eigenvalue analysis, a singular value analysis and floating point arithmetic, we focus on finding an appropriate choice for the parameter in the sense that the condition number in the iteration matrix of the search direction of the adaptive conjugate gradient method and scaling conjugate gradient method are at minimum;..2. Based on the Yabe-Takano conjugate gradient methods, we consider an adaptive truncation strategy such that the modified Yabe-Takano method can be globalized with the non-convex objective functions;..3. Based on quasi Newton method, the modified three-term HS-type conjugate gradient methods are researched, which satisfy the conjugacy condition and sufficient descent conditions;..4. The proposed methods and their properties can be applied to the field of bound constrained optimization and Nonnegative Matrix Factorization...This adative algorithmic mechanism benefits the conjugate gradient method more than theoretically and computationally, and with the passage of time, it will show more meaningful and profound significance.

本项目通过借鉴拟牛顿法的算法性质，以自适应算法机制为主线，以具有二次终止性、自校正性、自适应共轭性、充分下降条件和全局收敛性，以及迭代矩阵的条件数小的共轭梯度算法构造为桥梁，为求解大规模、非线性程度高和病态程度高的实际问题的求解奠定基础，并以此推动非负矩阵分解的研究。..研究内容：.1. 以特征值和奇异值分析、浮点运算为工具，来研究自适应共轭梯度法和谱共轭梯度法中在迭代矩阵条件数最小意义下的最优参数选取；.2. 以YT方法为代表，探索自适应截断策略，研究求解非凸问题时的收敛性分析；.3. 基于BFGS拟牛顿法, 研究以HS方法为基础的三项共轭梯度法,开展具有自行充分下降条件和满足拟牛顿条件的算法构造；.4. 利用上述成果求解界约束优化问题和非负矩阵分解。 ..自适应的算法机制不仅有益于共轭梯度法的理论，而且有效消除舍入误差和加速迭代。随着时间的推移，它将展示出更重要的意义。

一般而言，在共轭梯度法中适当引入某个量，尽量摄取优化所需的非线性性质，从而设计出更为出色的非线性共轭梯度算法(NCG)。戴彧虹(2015)撰文对非线性规划发展综述中指出：(1)对于大规模优化问题，如果要提高收敛速度，改善数值算法，如何以较好方式利用二阶曲率信息非常重要；(2)自适应技术和非单调策略在算法设计中有效使用。.近年来，NCG方法在构造充分下降方向、最优参数选取，及其与拟牛顿法的算法性质的联系等方面仍然存在大量公开问题(罗马尼亚N.Andrei).已有文献中NCG方法中参数选取范围较大或阈值不易调节，以及只对一致凸函数保证全局收敛，会导致算法性质之间顾此失彼，互相掣肘，进一步会影响数值效果.本项目在借鉴BFGS拟牛顿法算法性质和前期研究的基础上，将其中的优秀的算法性质迁移到NCG中，开展算法构造、理论性态分析、迭代矩阵尺度化分析和降低其条件数，以及进行大规模数值实验的验证、比较和分析工作。具体地，通过子空间投影、条件数分析、非单调技术等技巧和工具，在保留NCG原有的存储少、计算快和全局收敛等优点的同时，构造出具有自校正性、充分下降条件、新共轭条件、迭代矩阵的条件数渐进最小等性质上互相融合互为补充的自适应算法，建立补偿机制来减少舍入误差和加速迭代，为提高求解大型问题和病态问题的数值性能提供理论依据。