Newton-PCG算法的效率的理论分析

作者：邓乃扬; 张建中; 钟萍

来源：中国科学A辑:数学 , 2005, 35(06): 695-711.

DOI：10.3969/j.issn.1674-7216.2005.06.008

• 无约束最优化
• Newton法
• 条件预优共轭梯度法
• 效率

为了从理论上研究在标准条件下光滑无约束问题的不精确Newton类型算法的效率,对一个具体的Newton—PCG算法进行了讨论.为了比较该算法与Newton法的效率,引入了两者的近似效率之比值.在很弱的条件下证明了该比值大于1,这表明Newton-PCG算法比Newton法的效率高.同时,当无约束问题的维数n→∞时,该比值至少以lnn/1n2的速度增加,因而从理论上证明了Newton-PCG算法对大中型问题更有效.数值实验也支持了上述理论结果.

• 单位
  香港城市大学; 中国农业大学