【作者】 张海斌；

【导师】 邓乃扬；

【作者基本信息】 中国农业大学 ， 管理科学与工程， 2002， 博士

【摘要】 非线性最优化在科学计算和工程分析等领域中起着非常重要的作用。在非线性最优化的研究中，牛顿法是二阶算法，对牛顿法的改进，一直是人们关注的问题，近年来，用共轭梯度法对它进行改进，即研究牛顿-PCG型方法是国内外的一个研究热点。自动微分是一种新的能精确而有效地计算导数的方法，它优越于传统的微分方法，例如它比符号微分和差分方法的计算成本低，又比差分方法计算精确，自动微分在近几年发展迅速，应用广泛。 论文首次将自动微分应用于牛顿-PCG型算法，构造了新算法，并从理论上比较了新算法与牛顿法的效率，证明了新算法的效率严格大于牛顿法的效率，而且新算法与牛顿法的效率比分别是问题维数n和目标函数复杂性的严格单调递增函数，当n趋于无穷大时，这个效率比的下界以ln(n)／ln2的速率趋于无穷大。需要说明的是，在已有的文献中，牛顿-PCG算法与牛顿法的效率比是在目标函数复杂性很小的假设条件下讨论的，本文去掉了这一限制。本文也对不同的微分方法下牛顿-PCG算法与牛顿法的效率比进行了比较，得出：在一般的假设下，使用自动微分下的效率比严格大于使用符号微分下的效率比，而且它们的比值随问题维数n趋于无穷，即应用自动微分的牛顿-PCG算法对牛顿法有进一步的改进。 在科学计算及其应用领域中，Improved Method of Tangent Hyperbolas方法(简称为IMTH方法)是常用的三阶最优化算法。论文在IMTH方法的基础上，结合自动微分和Newton-PCG算法的思想，论文首次提出了广义的Newton-PCG算法模型。通过具体化模型参数，得到了算法ECFPCG1和算法ECFPCG2。理论分析结果表明：这两个算法比IMTH方法具有更高的效率，而且，算法ECFPCG1的效率高于算法ECFPCG2的效率。进一步地，算法ECFPCG2与IMTH方法的效率比分别为问题维数n和目标函数复杂性严格递增函数，而且这个效率比的下界随问题维数n的增大以ln(n)／ln3的速率趋于无穷大。数值试验结果验证了理论分析的正确性。更多还原

【Abstract】 Nonliuear optiInization plays an important role in many fields such as science computationand engineering analysis. For solving nonlinear optimization problems, Newton method is oneof the most efficient methods. As modification to Newton method, inexact Newton methodsare popular for solving the middle and large scale nonIinear optimization problems. Amongthem, CF-PCG (Newton-PCG) method is an efficient improvement to Newton method. It isproposed on the basis of the analysis on Newton method and the preconditioned conjugategradient method (PCG method). Numerical derivatives can be evaluated by symbolic differ-entiation (SD), finite difference approximation and automatic differelltiation (AD). AD hassignificant advantages over other two approaches. One of its most important applicationsis to improve the optimization algorithms by evaluating the relevant derivatives informationefficientlyThe aim of the work includes: to establish and study new algorithms--CF-PCG algorithrnswith AD; to establish and study the extended CF-PCG algorithm (ECFPCG).CF-PCG algorithms with AD is proposed on the basis of CF-PCG algorithms with SD,in addition to replace SD with AD, there are other significant modification to the algorithms.The results by theoretical analysis and numerical experiments implicate that CF-PCG algo-rithm with AD is an improvement to Newton method with AD. The improvement can beachieved under the mild conditiolls. For the same dimension problems, the larger the costto evaluate the objective function, the more the improvement of the new algorithm versusNewton method with AD. So, as the worst case when the computation cost of the objectivefunction is negligible, the improvement is strictly increasing with respect to n and tends to+oc approximately at a rate lnn/ ln2 when n - +oo. The results also show that the im-provement of CF-PCG algorithIn with AD over Newton method with AD is much greaterthan the improvement of CF-PCG algorithm witll SD over Newton method with SD.The methods which convergence order is greater than 2 are named as high-order methods.The improved method of tangent hyperbolas (IMTH method) is a popular method amongthe high--order methods. In this thesis, combining AD techniques and the thoughts of theCF-PCG algorithms, extended CF-PCG algorithm model is derived. Theoretical analysisand experimental results indicate that Algorithm ECFPCG1 and Algorithm ECFPCG2 es-tablished by specifying parameters are much more efficient than the IMTH method, androughly speaking, the relative efficiency of the algorithms versus the IMTH method tends to +00 at the asymptotic formula Inn/In3 when n tends to +00.更多还原