解凸约束非线性单调方程组的无导数低存储Broyden族投影法

doi:10.12286/jssx.j2022-0901

计算数学 ›› 2023, Vol. 45 ›› Issue (2): 197-214.DOI: 10.12286/jssx.j2022-0901

解凸约束非线性单调方程组的无导数低存储Broyden族投影法

饶佳运, 黄娜

中国农业大学理学院应用数学系, 北京 100083

收稿日期:2022-01-11 出版日期:2023-05-14 发布日期:2023-05-13
通讯作者: 黄娜, Email:hna@cau.edu.cn

PDF ( 40 ) 引用

饶佳运, 黄娜. 解凸约束非线性单调方程组的无导数低存储Broyden族投影法[J]. 计算数学, 2023, 45(2): 197-214.

Rao Jiayun, Huang Na. A DERIVATIVE-FREE MEMORYLESS BROYDEN FAMILY PROJECTION METHOD FOR SOLVING NONLINEAR MONOTONE SYSTEMS WITH CONVEX CONSTRAINS[J]. Mathematica Numerica Sinica, 2023, 45(2): 197-214.

A DERIVATIVE-FREE MEMORYLESS BROYDEN FAMILY PROJECTION METHOD FOR SOLVING NONLINEAR MONOTONE SYSTEMS WITH CONVEX CONSTRAINS

Rao Jiayun, Huang Na

Department of Applied Mathematics, College of Science, China Agricultural Univeristy, Beijing 100083, China

Received:2022-01-11 Online:2023-05-14 Published:2023-05-13

拟牛顿法是求解非线性方程组的一类有效方法. 相较于经典的牛顿法, 拟牛顿法不需要计算 Jacobian 矩阵且仍具有超线性收敛性. 本文基于 BFGS 和 DFP 的迭代公式, 构造了新的充分下降方向. 将该搜索方向和投影技术相结合, 本文提出了无导数低存储的投影算法求解带凸约束的非线性单调方程组并证明了该算法是全局且 $R$-线性收敛的. 最后, 将该算法用于求解压缩感知问题. 实验结果表明, 本文所提出的算法具有良好的计算效率和稳定性.

关键词： 非线性单调方程组, 凸约束, Broyden族, 投影法, 无导数

Quasi-Newton methods are a class of effective methods for solving nonlinear equations. Compared with the classical Newton method, Quasi-Newton methods do not require computation of the Jacobian matrix and still possess superlinear convergence. Based on the BFGS and DFP iterative schemes, we construct a new sufficient descent direction. Combining this direction with some projection techniques, we propose the derivative-free memoryless projection method for solving nonlinear monotone systems with convex constrains and derive its global R-linear convergence. Finally, we use this method to solve the compressive sensing problems. Numerical results show the efficiency and stability of our new method.

Key words: Monotone nonlinear systems, Convex constrain, Broyden family, Projection method, Derivative-free

MR(2010)主题分类:

分享此文:

[1] Wood A J, Wollenberg B F. Power generations, operations, and control. Wiley, New York, 1996.
[2] Meintjes K, Morgan A.P. A methodology for solving chemical equilibrium systems[J]. Appl. Math. Comput., 1987, 22:333-361.
[3] Prajna S, Parrilo P A, Rantzer A. Nonlinear control synthesis by convex optimization[J]. IEEE Trans. Automat. Control Eng., 2004, 49(2):310-314.
[4] Dirkse S P, Ferris M C. MCPLIB:A collection of nonlinear mixed complementarity problems[J]. Optim. Methods Softw., 2012, 5(4):319-345.
[5] Figueiredo M, Nowak R D, Wright S J. Gradient Projection for Sparse Reconstruction:Application to Compressed Sensing and Other Inverse Problems[J]. IEEE J-STSP, 2008, 1(4):586-597.
[6] Zarantonello E H. Projections on Convex Sets in Hilbert Space and Spectral Theory:Part I. Projections on Convex Sets:Part II. Spectral Theory[J]. Revista de la Unión Matemática Argentina, 1971, 26:237-424.
[7] Xiao Y, Zhu H. A conjugate gradient method to solve convex constrained monotone equations with applications in compressive sensing[J]. J. Math. Anal. Appl., 2013, 405(1):310-319.
[8] Aliyu M A, Kumam P, Auwal B A. A modified conjugate gradient method for monotone nonlinear equations with convex constraints[J]. Appl. Numer. Math., 2019, 145:507-520.
[9] Zheng L, Yang L, Liang Y. A conjugate gradient projection method for solving equations with convex constraints[J]. J. Comput. Appl. Math., 375.
[10] Awwal A M, Kumam P, Sitthithakerngkiet K, Abubakar M B, Abubakar S H. Ibrahim M.S.:Derivative-free method based on DFP updating formula for solving convex constrained nonlinear monotone equations and application[J]. AIMS Math., 2021, 6(8):8792-8814.
[11] Ibrahim A H, Kumam P. Re-modified derivative-free iterative method for nonlinear monotone equations with convex constraints[J]. Ain Shams Eng. J., 2021.
[12] Liu J, Feng Y. A derivative-free iterative method for nonlinear monotone equations with convex constraints[J]. Numer. Algorithms, 2019, 82(1):245-262.
[13] Mahdi M M, Shiker M A K. Three terms of derivative free projection technique for solving nonlinear monotone equations[J]. J. Phys. Conf. Ser., 2020, 1591:012-031.
[14] Solodov M V, Svaiter B F. A hybrid projection-proximal point algorithm[J]. J. Convex Anal., 1999, 6(1):59-70.
[15] Solodov M V, Svaiter B F. A globally convergent inexact Newton method for systems of monotone equations. Reformulation:Nonsmooth, piecewise smooth, semismooth and smoothing methods. Springer, Boston, MA, 1998, 355-369.
[16] Fletcher R, Powell M. A rapidly convergent descent method for minimization[J]. Comput. J., 1963, 6:163-168.
[17] Davidon, William C. Variable metric method for minimization[J]. SIAM J. Optim., 1991, 1(1):1-17.
[18] Ullah N, Sabi'U J., Shah A. A derivati-free scaling memoryless Broyden-Fletcher-Goldfarb-Shanno method for solving a system of monotone nonlinear equations[J]. Numer. Linear Algebra Appl., 2021(2).
[19] Byrd R H, Nocedal J, Schnabel R B. Representations of quasi-Newton matrices and their use in limited memory methods[J]. Math. Program., 1994, 63(1-3):129-156.
[20] Sun W, Yuan Y X. Potimization theory and methods. Nonlinear programming[M]. New York, NY:Springer Science+Business Media, 2006.
[21] Zhang L, Zhou W J. Spectral gradient projection method for solving nonlinear monotone equations[J]. J. Comput. Appl. Math., 2006, 2:478-484.
[22] Broyden C G. Quasi-Newton methods and their application to function minimisation[J]. Math. Comput., 1967, 21(99):368-368.
[23] Sun W, Yuan Y X. Potimization theory and methods. Nonlinear programming[M]. New York, NY:Springer Science+Business Media, 2006.
[24] Ou Y G, Li J Y. A new derivative-free SCG-type projection method for nonlinear monotone equations with convex constraints[J]. J. Appl. Math. Comput., 2018, 56(1-2):195-216.
[25] Sun M, Tian M Y. A Class of Derivative-Free CG Projection Methods for Nonsmooth Equations with an Application to the LASSO Problem[J]. B. IRAN. MATH. SOC. 2020, 46(1), 183-205.
[26] Figueiredo M, Nowak R, Wright S J. Gradient projection for sparse reconstruction, application to compressed sensing and other inverse problems[J]. IEEE J-STSP 2007:586-597.
[27] Pang J S. Inexact Newton methods for the nonlinear complementary problem[J]. Math. Program., 1986, 36:54-71.
[28] Xiao Y, Wang Q, Hu Q. Non-smooth equations based method for ȴ1-norm problems with applications to compressed sensing[J] Nonlinear Anal., 2011, 74(11):3570-3577.
[29] Dolan E D, Moré J J. Benchmarking optimization software with performance profiles[J]. Math. Program., 2002, 91:201-213.

[1]	刘金魁, 孙悦, 赵永祥. 凸约束伪单调方程组的无导数投影算法[J]. 计算数学, 2021, 43(3): 388-400.
[2]	刘金魁. 解凸约束非线性单调方程组的无导数谱PRP投影算法[J]. 计算数学, 2016, 38(2): 113-124.

阅读次数

全文

摘要

解凸约束非线性单调方程组的无导数低存储Broyden族投影法

A DERIVATIVE-FREE MEMORYLESS BROYDEN FAMILY PROJECTION METHOD FOR SOLVING NONLINEAR MONOTONE SYSTEMS WITH CONVEX CONSTRAINS

扫码分享