NewtonPCG算法的效率的理论分析.pdf

1 695 中国科学A辑数学2005，35(6)：695—71 邓乃扬1张建中2料钟萍1 (1．中国农业大学理学院数学系，北京100083；2．香港城市大学数学系，香港) 摘要 为了从理论上研究在标准条件下光滑无约束问题的不精确Newton类型 算法的效率，对一个具体的Newton．PCG算法进行了讨论．为了比较该算法与 Newton法的效率，引入了两者的近似效率之比值．在很弱的条件下证明了该比 的维数n_。。时，该比值至少以ln佗／In2的速度增加，因而从理论上证明了 Newton．PCG算法对大中型问题更有效．数值实验也支持了上述理论结果． 关键词 无约束最优化 Newton法条件预优共轭梯度法 效率 1引言 考虑大中型无约束最优化问题 min，(z)，z∈酞” 法，该类方法只近似求解Newton方程．选择线性共轭梯度或条件预优共轭梯度 年里，这方面的研究取得了重大的成果：建立了许多有效的算法和可靠的收敛 理论．例如文献[1,-一91．然而，至今几乎没有对该算法的效率的理论分析，甚至 没有明晰的理论分析来说明它比Newton法更为有效． 有效．事实上，那里从以下两个方面把它和Newton法进行了比较： 2004—04．19收稿，2005—01-30收修改稿 ”E—mail：mazhang@ciWu．edu．hk SCⅡiNCEINCHINASer．AMathematics 中国科学A辑数学 第35卷 的平均计算量比Newton法的相应部分要少，而第1部分的计算量相同． 的方法也是恰二阶收敛的． 个限制条件下证明的： 以忽略． (ii)假设Newton法恰好二阶收敛． 同时，没有对文献[10】中的方法进行任何数值实验． 算法的有效性． 要去除第1个限制条件，意味着要减少导数信息的计算量．这可以用以下 的乘积V2f·q可以由V，沿口方向的差商来近似．这样只需要额外再计算一个 梯度的工作量．然而，由于差商提供的仅仅是V2f·q的近似值，所以需要进行 理论分析与数值实验来支持这种修改方法． 要去除第2个限制条件，意味着要在标准条件下求解问题(1．1)．在标准条 件下，Newton法的局部收敛速度是至少二阶的，因此必须考察条件预优共轭梯 度子迭代的进展，以及该进展是如何受条件预优阵和子迭代影响的．对此我们 是通过引进“进度指标”概念和细致的理论分析完成的． 型．依据文献[12】，一个算法的效率依赖于其局部收敛速度，所以它是一个局部性 质，和算法的全局表现不相关，因此为了简洁，我们的算法模型是一个没有全局 策略的局部算法．通过扩展文献[121中的效率度量的定义以及引进“进展指标”， 得到了该算法模型的效率下界．这个下界依赖于算法模型中的参数．最大化这 个下界可导出算法模型的一个具体实现．我们证明了该具体实现在大中型问题 与文献[10]相比，本文不仅可以处理无以上两个限制条件的一般问题(1．1)， 而且对满足这两个限制条件的特殊问题(1．1)也得到了较文献[10]更强的结论． 此外，与文献[10]不同，本文的理论结论有数值实验的支撑． 2算法模型 SCⅢNCEINCHINASenAMathematics 第6期 邓乃扬等：Newton．PCG算法的效率的理论分析 697 包括以下两类步骤： (1)CF步．用Cholesky分解求解Newton方程 V2f(x)·s=Vf(x) (2．1) 积V2f(x)q由下列差商近似： V2f(z)g≈旦堕粤咝． 解夏其中c是条件预优阵，z是当前点，2。是子迭代的最大次数，九是步长，e 是终止准则中用到的参数．该终止准则出于以下的考虑：假设{z％]．是由Xk+l= 了我们在以下(2．2)式中使用e． 2．1算法PCGd(C，∞，1