《Franklin Open》:Robust monotone three-term spectral conjugate gradient method for solving convex-constrained system of equations
编辑推荐:
本文提出一种用于求解大规模凸约束单调方程组(convex-constrained monotone system of equations)的稳健三项谱共轭梯度法(robust three-term spectral conjugate gradient, R
本文提出一种用于求解大规模凸约束单调方程组(convex-constrained monotone system of equations)的稳健三项谱共轭梯度法(robust three-term spectral conjugate gradient, RTSCG)。该方案参数通过下降条件(descent condition)和共轭条件(conjugacy condition)导出,是对 Al-Bayati and Abbas (2019) 工作的改进。研究人员将所提方法的性能与文献中若干现有方法进行比较;使用若干基准测试问题(benchmark test problems)开展的数值实验表明,该方法效果令人鼓舞。在适当条件下,研究人员建立了所提算法的全局收敛性(global convergence)。
研究人员关注一类非线性方程组 F(x)=0,x∈E?R
n,其中 F 连续且单调,E 为非空闭凸集。无约束优化已有 Newton 法、Quasi-Newton 法及其变体等较广泛研究,但约束优化问题相对研究较少。共轭梯度(conjugate gradient, CG)法因结构简单、存储需求低而适合大规模问题;将 CG 与超平面投影结合可构造求解约束单调方程的投影方法。单调非线性方程在信号与图像恢复、一般均衡问题和潮流方程等实际场景中有应用,这促使研究人员研究更高效的迭代方法。已有三项 CG 投影方法从不同角度改进搜索方向和参数,但大规模凸约束单调方程组仍需要兼具低存储、稳健数值表现和全局收敛保证的算法。为此,研究人员提出 RTSCG 方法:利用下降条件和 Dai-Liao 共轭条件推导参数,采用单调线搜索与投影步骤,并在适当条件下证明全局收敛性。其意义在于为大规模凸约束单调方程组提供一种新的稳健求解方案,并通过与 MTCGP、DLCG 和 NTCGM 方法的数值比较显示其效率和稳健性。
主要关键技术方法(不超过250字):研究人员构建三项谱共轭梯度方向 d
k=?θ
kF
k+β
ks
k?1?ε
ky
k?1;由下降条件 F
kTd
k=?‖F
k‖
2 推导 β
k,由 Dai and Liao (2001) 共轭条件 y
k?1Td
k=?t s
k?1TF
k 推导 ε
k;采用回溯型单调线搜索(backtracking-type monotone line search)确定步长 α
k,并用 Solodov and Sveiter 超平面投影产生下一迭代;数值实验使用6个基准测试问题(benchmark test problems)和8个初始点,与 MTCGP、DLCG、NTCGM 比较,以迭代次数、函数评价次数、CPU 时间及 Dolan and Moré 性能剖面(performance profiles)评价。研究不涉及样本队列来源。
2. 新算法(The new algorithm):研究人员构造迭代格式 x
k+1=x
k+α
kd
k,并给出求解凸约束单调方程组的投影框架。结论是:在满足 〈F(z
k),x
k?z
k〉>0 时,可通过投影产生下一迭代。2.1 投影法(Projection method):通过投影算子 P
E 将迭代点投影到可行集 E,利用其非扩张性质使投影点不远离解;结论是投影步骤可保持迭代序列的收敛性质。2.2 所提方法的推导(Derivation of the proposed method):研究人员分别推导 β
k 和 ε
k,形成三项谱共轭方向;结论是所提参数由下降条件和共轭条件共同确定。2.2.1 β
k 的推导(Derivation of β
k):由 Birgin and Mertinez 方向出发,结合下降条件 F
kTd
k=?‖F
k‖
2 得到 β
k,并将 θ
k 的分母平方以改善全局收敛性;结论是该 β
k 使方向满足下降性要求。2.2.2 ε
k 的推导(Derivation of ε
k):在三项方向两边左乘 y
k?1T,结合 Dai and Liao (2001) 共轭条件得到 ε
k;结论是三项方向同时包含谱参数与共轭参数。3. 收敛性分析(Convergence analysis):在 F 一致单调(uniformly monotone)、存在解以及 Lipschitz 连续(Lipschitz continuity)等假设下,研究人员证明线搜索良定义、方向满足充分下降条件、α
k‖d
k‖→0、d
k 有界,并证明 lim inf
k→∞‖F
k‖=0;结论是 RTSCG 算法具有全局收敛性。4. 数值结果(Numerical results):研究人员使用 Problem 1 至 Problem 6 的基准测试问题和8个初始点,设置 σ=10
?5,停止准则为迭代次数超过2000或 ‖F(x
k)‖≤10
?5,将 RTSCG 与 MTCGP、DLCG、NTCGM 比较;结果表明 RTSCG 在迭代次数上对54.58%(131/240)的问题表现最优,在函数评价次数上对83.33%(200/240)的问题表现最优,在 CPU 时间上对82.50%(198/240)的问题表现最优,而 MTCGP、DLCG、NTCGM 在函数评价次数上均为0.00%(0/240)最优;性能剖面亦显示 RTSCG 在多数问题上表现最好。结论是 RTSCG 在求解大规模凸约束单调非线性方程组时更稳健、有效和高效。
5. 结论(Conclusion)与讨论总结:论文结论节归纳了 RTSCG 方法、与 MTCGP、DLCG 和 NTCGM 的数值比较以及基于回溯型线搜索(backtracking type line search)的收敛性证明。研究结论翻译如下:本文提出了一种用于求解大规模单调凸约束非线性方程组的稳健三项谱共轭梯度(RTSCG)法,并通过开展若干数值实验,将其性能与 MTCGP、DLCG 和 NTCGM 方法进行了比较。研究人员利用回溯型线搜索证明了所提方法的收敛性,数值结果表明所提方法在精度和稳健性方面更有效,因而具有良好前景。