广义鞍点问题的改进的类SOR算法

doi:10.12286/jssx.2020.1.39

计算数学 ›› 2020, Vol. 42 ›› Issue (1): 39-50.DOI: 10.12286/jssx.2020.1.39

广义鞍点问题的改进的类SOR算法

张纯^1,2, 贾泽慧³, 蔡邢菊¹

1. 南京师范大学数学科学学院, 南京 210023;
2. 中国人民解放军陆军工程大学基础部, 南京 211101;
3. 南京信息工程大学数学与统计学院, 南京 210044;
4. 北京航空航天大学数学科学学院, 北京 100191

收稿日期:2018-03-07 出版日期:2020-02-15 发布日期:2020-02-15
基金资助:
国家自然科学基金（11625105，11926358，11871279，11571178，11801279），江苏省自然科学基金（BK2018078），南京信息工程大学科研启动基金（2017r059）.

PDF ( 297 ) 引用

张纯, 贾泽慧, 蔡邢菊. 广义鞍点问题的改进的类SOR算法[J]. 计算数学, 2020, 42(1): 39-50.

Zhang Chun, Jia Zehui, Cai Xingju, Han Deren. AN IMPROVED SOR-TYPE ALGORITHM FOR SLOVING GENERALIZED SADDLE-POINT PROBLEMS[J]. Mathematica Numerica Sinica, 2020, 42(1): 39-50.

AN IMPROVED SOR-TYPE ALGORITHM FOR SLOVING GENERALIZED SADDLE-POINT PROBLEMS

Zhang Chun^1,2, Jia Zehui³, Cai Xingju¹, Han Deren⁴

1. School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023, China;
2. Department of Basic Courses, The PLA Army Engineering University, Nanjing 211101, China;
3. School of Mathematics and Statistics, Nanjing University of Information Science&Technology, Nanjing 210044, China;
4. School of Mathematical Sciences, Beihang University, Beijing 100191, China

Received:2018-03-07 Online:2020-02-15 Published:2020-02-15

针对广义鞍点问题，本文提出了一个改进的类逐次超松弛迭代算法，在较弱的条件下，分析了算法的收敛性及线性收敛率.新算法的每步计算量与已有的算法类似，都是需要（近似）求解线性方程组，但新算法有更好的灵活度通过合适地选取参数矩阵，每一步子问题可以容易地求解，甚至可以有闭式解（closed-form solution）.数值实验结果显示了新算法的有效性.

关键词： 鞍点问题, 类SOR算法, 全局收敛性, 收敛率

For the generalized saddle point problem, we develop an improved class of successive over relaxation algorithms. Under mild conditions, we prove its convergence and establish its linear rate of convergence. While, as the classical methods, it needs to solve some linear system of equations approximately to get the next iterate, the flexibility in choosing the involved matrices makes the subproblems easy or even to have closed form solutions, which leads the algorithm to be an efficient one. Preliminary numerical results show the effectiveness of the new method.

Key words: saddle point problem, SOR algorithm, global convergence, convergence rate

MR(2010)主题分类:

65F10
65H10

分享此文:

[1] Bai Z Z, Golub G H, Pan J Y. Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems[J]. Numerische Mathematik, 2004, 98(1):1-32.

[2] Bai Z Z, Parlett B N, Wang Z Q. On generalized successive overrelaxation methods for augmented linear systems[J]. Numerische Mathematik, 2005, 102(1):1-38.

[3] Bai Z Z, Wang Z Q. On parameterized inexact Uzawa methods for generalized saddle point problems[J]. Linear Algebra and its Applications, 2008, 428(11-12):2900-2932.

[4] Bergamaschi L, Gondzio J, Zilli G. Preconditioning indefinite systems in interior point methods for optimization[J]. Computational Optimization and Applications, 2004, 28(2):149-171.

[5] Bergen A R. Power systems analysis[M]. Englewood Cliffs, NJ:Prentice-Hall, 1986.

[6] Betts J T. Practical methods for optimal control using nonlinear programming[M]. Society for Industrial and Applied Mathematics, Philadelphia, 2001.

[7] Björck ?. Numerical methods for least squares problems[M]. Society for Industrial and Applied Mathematics, Philadelphia, 1996.

[8] Cao Y, Jiang M Q, Yao L Q. New choices of preconditioning matrices for generalized inexact parameterized iterative methods[J]. Journal of Computational and Applied Mathematics, 2010, 235(1):263-269.

[9] Elman H C. Preconditioning for the steady-state Navier-Stokes equations with low viscosity[J]. Siam Journal on Scientific Computing, 1999, 20:1299-1316.

[10] Golub G H, Van Loan C F. Matrix computations[M]. Johns Hopkins University Press, Baltimore, 1996.

[11] Haber E, Ascher U M. Preconditioned all-at-once methods for large, sparse parameter estimation problems[J]. Inverse Problems, 2001, 17(6):1847-1864.

[12] Heinkenschloss M, Nguyen H. Neumann-neumann domain decomposition preconditioners for linear-quadratic elliptic optimal control problems[J]. Siam Journal on Scientific Computing, 2006, 28(3):1001-1028.

[13] Jiang M Q, Cao Y. On local Hermitian and skew-Hermitian splitting iteration methods for generalized saddle point problems[J]. Journal of Computational and Applied Mathematics, 2009, 231(2):973-982.

[14] 刘丽华, 马昌凤, 唐嘉. 求解广义鞍点问题的一个新的类SOR算法[J]. 计算数学, 2016, 38(1):83-95.

[15] Martin B, Wolfram M. Numerical approxmation of an SQP-type method for parameter identification[J]. Siam Journal on Numerical Analysis, 2003, 40(5):1775-1797.

[16] Strang G. Introduction to applied mathematics[M]. Wellesley-Cambridge Press, Wellesley, MA, 1986.

[17] Zhang G F, Yang J L, Wang S S. On generalized parameterized inexact Uzawa method for a block two-by-two linear system[J]. Journal of Computational and Applied Mathematics, 2014, 255(285):193-207.

[18] Zheng X Y, Ng K F. Metric subregularity of piecewise linear multifunctions and applications to piecewise linear multiobjective optimization[J]. Siam Journal on Optimization, 2014, 24(1):154-174.

[1]	唐耀宗, 杨庆之. 非线性特征值问题平移对称幂法的收敛率估计[J]. 计算数学, 2021, 43(4): 529-538.
[2]	尹江华, 简金宝, 江羡珍. 凸约束非光滑方程组一个新的谱梯度投影算法[J]. 计算数学, 2020, 42(4): 457-471.
[3]	刘忠祥, 王翠薇, 王增琦. 求解时谐涡流模型鞍点问题的分块交替分裂隐式迭代算法的改进[J]. 计算数学, 2018, 40(3): 271-286.
[4]	王福胜, 张瑞. 不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法[J]. 计算数学, 2018, 40(1): 49-62.
[5]	刘金魁. 解凸约束非线性单调方程组的无导数谱PRP投影算法[J]. 计算数学, 2016, 38(2): 113-124.
[6]	刘丽华, 马昌凤, 唐嘉. 求解广义鞍点问题的一个新的类SOR算法[J]. 计算数学, 2016, 38(1): 83-95.
[7]	刘亚君, 刘新为. 无约束最优化的信赖域BB法[J]. 计算数学, 2016, 38(1): 96-112.
[8]	简金宝, 尹江华, 江羡珍. 一个充分下降的有效共轭梯度法[J]. 计算数学, 2015, 37(4): 415-424.
[9]	黄娜, 马昌凤, 谢亚君. 一类Hermitian鞍点矩阵的特征值估计[J]. 计算数学, 2015, 37(1): 92-102.
[10]	潘春平. 关于Stokes和线性Navier-Stokes方程的广义维数分裂迭代方法[J]. 计算数学, 2014, 36(3): 231-244.
[11]	曹阳, 陶怀仁, 蒋美群. 鞍点问题的广义位移分裂预条件子[J]. 计算数学, 2014, 36(1): 16-26.
[12]	袁敏, 万中. 求解非线性P₀互补问题的非单调磨光算法[J]. 计算数学, 2014, 36(1): 35-50.
[13]	简金宝, 唐菲, 黎健玲, 唐春明. 无约束极大极小问题的广义梯度投影算法[J]. 计算数学, 2013, 35(4): 385-392.
[14]	潘春平. 关于鞍点问题的广义预处理HSS-SOR交替分裂迭代方法[J]. 计算数学, 2013, 35(4): 353-364.
[15]	刘金魁. 两种有效的非线性共轭梯度算法[J]. 计算数学, 2013, 35(3): 286-296.

阅读次数

全文

摘要

广义鞍点问题的改进的类SOR算法

AN IMPROVED SOR-TYPE ALGORITHM FOR SLOVING GENERALIZED SADDLE-POINT PROBLEMS

扫码分享