凸约束伪单调方程组的无导数投影算法

doi:10.12286/jssx.j2020-0659

计算数学 ›› 2021, Vol. 43 ›› Issue (3): 388-400.DOI: 10.12286/jssx.j2020-0659

凸约束伪单调方程组的无导数投影算法

刘金魁, 孙悦, 赵永祥

重庆三峡学院数学与统计学院, 万州 404100

收稿日期:2020-01-05 出版日期:2021-08-15 发布日期:2021-08-20
基金资助:
重庆市教育委员会科学技术研究计划青年项目（KJQN202001201），重庆三峡学院重大培育项目（16PY12），重庆市高等学校重点实验室（（2017）3）资助.

PDF ( 255 ) 引用

刘金魁, 孙悦, 赵永祥. 凸约束伪单调方程组的无导数投影算法[J]. 计算数学, 2021, 43(3): 388-400.

Liu Jinkui, Sun Yue, Zhao Yongxiang. A DERIVATIVE-FREE PROJECTION ALGORITHM FOR SOLVING PSEUDO-MONOTONE EQUATIONS WITH CONVEX CONSTRAINTS[J]. Mathematica Numerica Sinica, 2021, 43(3): 388-400.

A DERIVATIVE-FREE PROJECTION ALGORITHM FOR SOLVING PSEUDO-MONOTONE EQUATIONS WITH CONVEX CONSTRAINTS

Liu Jinkui, Sun Yue, Zhao Yongxiang

School of Mathematics and Statistics, Chongqing Three Gorges University, Wanzhou 404100, China

Received:2020-01-05 Online:2021-08-15 Published:2021-08-20

基于HS共轭梯度法的结构，本文在弱假设条件下建立了一种求解凸约束伪单调方程组问题的迭代投影算法.该算法不需要利用方程组的任何梯度或Jacobian矩阵信息，因此它适合求解大规模问题.算法在每一次迭代中都能产生充分下降方向，且不依赖于任何线搜索条件.特别是，我们在不需要假设方程组满足Lipschitz条件下建立了算法的全局收敛性和R-线收敛速度.数值结果表明，该算法对于给定的大规模方程组问题是稳定和有效的.

关键词： 非线性方程组, 无导数投影法, 共轭梯度法, 全局收敛, R-线收敛速度

Based on the structure of the HS conjugate gradient method, we propose an iterative projection algorithm for solving nonlinear pseudo-monotone equations with convex constraints under one weak assumption. Since the proposed method does not need any gradient or Jacobian matrix information of equations, it is suitable to solve large-scale problems. The proposed algorithm generates a sufficient descent direction in per-iteration, which is independent of any line search. Moreover, the global convergence and R-linear convergence rate of the proposed method are proved without the assumption that nonlinear equations satisfies Lipschitz condition.The numerical results show that the proposed method is stable and effective for the given large-scale nonlinear equations with convex constraints.

Key words: Nonlinear equations, Derivative-free projection method, Conjugate gradient method, Global convergence, R-linear convergence rate

MR(2010)主题分类:

65H10
90C30

分享此文:

[1] Meintjes K, Morgan A P. A methodology for solving chemical equilibrium systems[J]. Applied Mathematics and Computation, 1987, 22:333-361.
[2] Dirkse S P, Ferris M C. MCPLIB:A collection of nonlinear mixed complementarity problems[J]. Optimization Methods and Software, 1995, 5:319-345.
[3] Dennis J E, More J J. A characterization of superlinear convergence and its application to quasiNewton methods[J]. Mathematics of Computation, 1974, 28:549-560.
[4] Iusem A N, Solodov M V. Newton-type methods with generalized distances for constrained optimization[J]. Optimization, 1997, 44:257-278.
[5] Zhao Y B, Li D. Monotonicity of fixed point and normal mapping associated with variational inequality and its application[J]. SIAM Journal on Optimization, 2001, 4:962-973.
[6] Solodov M V, Svaiter B F. A Globally Convergent Inexact Newton Method for Systems of Monotone Equations[M]. Kluwer:Kluwer Academic Publisher, 1988, 355-369.
[7] Kanzow C, Yamashita N, Fukushima M. Levenberg-Marquardt methods for constrained nonlinear equations with strong local convergence properties[J]. Journal of Computational and Applied Mathematics, 2004, 172:375-397.
[8] Tong X J, Qi L, Yang Y F. The Lagrangian globalization method for nonsmooth constrained equations[J]. Computational Optimization and Applications, 2006, 33:89-109.
[9] Zhou W J, Li D H. A globally convergent BFGS method for nonlinear monotone equations without any merit functions[J]. Mathematics of Computation, 2008, 77:2231-2240.
[10] Zhou G, Toh K C. Superline convergence of a Newton-type algorithm for monotone equations[J]. Journal of Optimization Theory with Applications, 2005, 125:205-221.
[11] Zhang L, Zhou W J. Spectral gradient projection method for solving nonlinear monotone equations[J]. Journal of Computation and Applied Mathematics, 2006, 196:478-484.
[12] Cheng W Y. A PRP type method for systems of monotone equations[J]. Mathematical and Computer Modelling, 2009, 50:15-20.
[13] 刘金魁. 解凸约束非线性单调方程组的无导数谱PRP投影算法[J]. 计算数学, 2016, 38:113-124.
[14] Zhou W J, Li D H. On the Q-linear convergence rate of a class of methods for monotone nonlinear equations[J]. Pacific Journal of Optimization, 2018, 14:723-737.
[15] Xiao Y H, Zhu H. A conjugate gradient method to solve convex constrained monotone equations with applications in compressive sensing[J]. Journal of Mathematical Analysis and Applications, 2013, 405:310-319.
[16] Dai Z F, Chen X H, Wen F H. A modfied Perry's conjugate gradient method-based derivativefree method for solving large-scale nonlinear monotone equations[J]. Applied Mathematics and Computations, 2015, 270:378-386.
[17] Gao P T, He C J. An efficient three-term conjugate gradient method for nonlinear monotone equations with convex constraints[J]. Calcolo, 2018, 55:53.
[18] Hestenes M R, Stiefel E L. Methods of conjugate gradients for solving linear systems[J]. Journal of Research of the National Bureau of Standards, 1952, 49:409-436.
[19] Conn A R, Gould N I M, Toint Ph L. CUTEr:constrained and unconstrained testing enviroment[J]. ACM Transactions on Mathematical Software, 1995, 21:123-160.
[20] Gomez-Ruggiero M, Martínez J M, Moretti A. Comparing Algorithms for solving sparse nonlinear systems of equations[J]. SIAM Journal on Scientific Computing, 1992, 23:459-483.
[21] Móre J J, Garbow B S, Hillström K E. Testing uncosntrained optimization software[J]. ACM Transactions on Mathematical Software, 1981, 7:17-41.
[22] Dolan E D, Moré J J. Benchmarking optimization software with performance profiles[J]. Mathematical Programming, 2002, 91:201-213.

[1]	孔令畅, 魏科洋, 周学林, 李姣芬. 广义特征值极小扰动问题的一类黎曼共轭梯度法[J]. 计算数学, 2022, 44(4): 508-533.
[2]	郭洁, 万中. 求解大规模极大极小问题的光滑化三项共轭梯度算法[J]. 计算数学, 2022, 44(3): 324-338.
[3]	马玉敏, 蔡邢菊. 求解带线性约束的凸优化的一类自适应不定线性化增广拉格朗日方法[J]. 计算数学, 2022, 44(2): 272-288.
[4]	米玲, 薛文娟, 沈春根. 球面上$\ell_1$正则优化的随机临近梯度方法[J]. 计算数学, 2022, 44(1): 34-62.
[5]	马积瑞, 范金燕. 信赖域方法在Hölderian局部误差界下的收敛性质[J]. 计算数学, 2021, 43(4): 484-492.
[6]	尹江华, 简金宝, 江羡珍. 凸约束非光滑方程组一个新的谱梯度投影算法[J]. 计算数学, 2020, 42(4): 457-471.
[7]	吴敏华, 李郴良. 求解带Toeplitz矩阵的线性互补问题的一类预处理模系矩阵分裂迭代法[J]. 计算数学, 2020, 42(2): 223-236.
[8]	张纯, 贾泽慧, 蔡邢菊. 广义鞍点问题的改进的类SOR算法[J]. 计算数学, 2020, 42(1): 39-50.
[9]	姜帆, 刘雅梅, 蔡邢菊. 一类自适应广义交替方向乘子法[J]. 计算数学, 2018, 40(4): 367-386.
[10]	王福胜, 张瑞. 不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法[J]. 计算数学, 2018, 40(1): 49-62.
[11]	裕静静, 江平, 刘植. 两类五阶解非线性方程组的迭代算法[J]. 计算数学, 2017, 39(2): 151-166.
[12]	张旭, 檀结庆, 艾列富. 一种求解非线性方程组的3p阶迭代方法[J]. 计算数学, 2017, 39(1): 14-22.
[13]	郭俊, 吴开腾, 张莉, 夏林林. 一种新的求非线性方程组的数值延拓法[J]. 计算数学, 2017, 39(1): 33-41.
[14]	刘金魁. 解凸约束非线性单调方程组的无导数谱PRP投影算法[J]. 计算数学, 2016, 38(2): 113-124.
[15]	刘亚君, 刘新为. 无约束最优化的信赖域BB法[J]. 计算数学, 2016, 38(1): 96-112.

阅读次数

全文

摘要

凸约束伪单调方程组的无导数投影算法

A DERIVATIVE-FREE PROJECTION ALGORITHM FOR SOLVING PSEUDO-MONOTONE EQUATIONS WITH CONVEX CONSTRAINTS

扫码分享