计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  重点论文 |  在线办公 | 
计算数学  2018, Vol. 40 Issue (4): 418-435    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
单调算子理论与分裂算法
郭科1, 韩德仁2
1. 西华师范大学数学与信息学院, 南充 637000;
2. 北京航空航天大学数学与系统科学学院, 北京 100191
MONOTONE OPERATOR THEORY AND SPLITTING METHODS
Guo Ke1, Han Deren2
1. School of Mathematics and Information, China West Normal University, Nanchong 637000 China;
2. School of Mathematics and System Sciences Beihang University, Beijing 100191, China
 全文: PDF (418 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 文主要回顾了单调算子理论与分裂算法的基本概念和结果,重点介绍Forward-Backward分裂算法和Douglas-Rachford分裂算法的收敛性理论及应用.同时,也介绍了这些方法处理非凸优化问题的最新进展以及一些前沿和热点问题.最后提出了几个未来可以继续研究的方向.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词Forward-Backward分裂算法   Douglas-Rachford分裂算法   交替方向法   邻近梯度法   凸优化   非凸优化   单调算子   非扩张算子   可行问题     
Abstract: In this paper, we revisit the basic notations and results of monotone operator theory and splitting methods, especially for the convergence theory and its applications of the ForwardBackward splitting method and the Douglas-Rachford splitting method. Meanwhile, we present the recent advances of these methods for solving nonconvex optimization problems and some heated research areas. Last, we list several research directions for the future work.
Key wordsForward-Backward Splitting Method   Douglas-Rachford Splitting Method   Alternating Direction Method of Multipliers   Proximal Gradient Method   Convex Optimization   Nonconvex Optimization   Monotone Operator   Nonexpansive Operator   Feasible Problem   
收稿日期: 2017-12-15;
基金资助:

国家杰出青年科学基金(No.11625105),国家自然科学基金项目(Nos.11801455,11571178,11431002),西华师范大学博士科研启动基金(No.17E084).

引用本文:   
. 单调算子理论与分裂算法[J]. 计算数学, 2018, 40(4): 418-435.
. MONOTONE OPERATOR THEORY AND SPLITTING METHODS[J]. Mathematica Numerica Sinica, 2018, 40(4): 418-435.
 
[1] Aragón Artacho F and Borwein J. Global convergence of a non-convex Douglas-Rachford iteration[J]. Journal of Global Optimization., 2013, 57(3):753-769.
[2] Attouch H, Briceño-Arias L M and Combettes P L. A parallel splitting method for coupled monotone inclusions[J]. SIAM Journal on Control optimization., 2010, 48(5):3246-3270.
[3] Attouch H, Briceño-Arias L M and Combettes P L. A strongly convergent primal-dual method for nonoverlapping domain decomposition[J]. Numerische Mathematik., 2016, 133(3):443-470.
[4] Attouch H, Bolte J and Svaiter B F. Convergence of descent methods for semi-algebraic and tame problems:proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods[J]. Mathematical Programming., 2013, 137:91-129.
[5] Attouch H, Peypouquet J and Redont P. Backward-forward algorithms for structured monotone inclusions in Hilbet spaces[J]. Journal of Mathematical Analysis and Applications., 2018, 457:1095-1117.
[6] Attouch H, Redont P and Soubeyran A. A new class of alternating proximal minimization algorithms with costs-to-move[J]. SIAM Journal on Optimization., 2007, 18:1061-1081.
[7] Attouch H and Thera M. A general duality principle for the sum of two operators[J]. Journal of Convex Analysis., 1996, 3:1-24.
[8] Baillon J B and Haddad G. Quelques propriétés des opérateurs angle-bornés et n-cycliquement monotones[J]. Israel Journal of Mathematics., 1977, 26:137-150.
[9] Bauschke H and Borwein J. Dykstra's alternating projection algorithm for two sets[J]. Journal of Approximation Theory., 1994, 79(3):418-443.
[10] Bauschke H and Browein J. On projection algorithms for solving convex feasibility problems[J]. SIAM Review., 1996, 38(3):367-426.
[11] Bauschke H and Borwein J. On the convergence of von Neumann's alternating projection algorithm for two sets[J]. Set-Valued Analysis., 1993, 1(2):185-212.
[12] Bauschke H H and Combettes P. Convex analysis and Monotone operator Theory in Hilbert spaces[M]. (2011).
[13] Bauschke H, Combettes P and Luke D. Hybrid projection-reflection method for phase retrieval[J]. Journal of the Optical Society of America A., 2003, 20(6):1025-1034.
[14] Bauschke H, Combettes P and Luke D. Phase retrieval, error reduction algorithm, and Fienup variants:a view from convex optimization[J]. Journal of the Optical Society of America A., 2002, 19(7):1334-1345.
[15] Beck A and Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problem[J]. SIAM Journal on Imaging Sciences., 2009, 2(1):183-202.
[16] Bot R I and Hendrich C. A Douglas-Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators[J]. SIAM Journal on Optimization., 2013, 23(4):2541-2565.
[17] Boyd S, Parikh N, Chu E, Peleato B and Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning., 2011, 3:1-122.
[18] Bregman L. The method of successive projection for finding a common point of convex sets. Dokl. Akad. Nauk SSSR., 1965, 6:688-692.
[19] Browder F E. Nonlinear elliptic boundary value problems[J]. Bulletin of the American Mathematical Society., 1963, 69(6):862-874.
[20] Browder F E. The solvability of non-linear function equations[J]. Duke Mathematical Journal., 1963, 30(4):557-566.
[21] Browder F E. Variational boundary value problems for quasi-linear ellptic equations of arbitrary order[J]. Proceedings of the National Academy of Sciences of the United States of America., 1963, 50(1):31-37.
[22] Browein J and Sims B. The Douglas-Rachford algorithm in absence of convexity[M]. In:FixedPoint Algorithms for Inverse Problems in Science and Engineering., 2011, 93-109.
[23] Chambolle A and Pock T. A first-order primal-dual algorithm for convex problems with applications to imaging[J]. Journal of Mathematical Imaging and Vision., 2011, 40:120-145.
[24] Chen L, Sun D F and Toh K C. A note on the convergence of ADMM for linearly constrained convex optimization problems[J]. Computational Optimization and Applications., 2017, 66(2):327-343.
[25] Combettes P L. Solving monotone inclusions via compositions of nonexpansive averaged operators[J]. Optimization., 2004, 53:475-504.
[26] Combettes P L and Briceño-Arias L M. A monotone + skew splitting model for composite monotone inclusion in duality[J]. SIAM Journal on Optimization., 2010, 21(4):1230-1250.
[27] Combettes P L and Pesquet J C. Proximal splitting methods in signal processing[M]. In:FixedPoint Algorithms for Inverse problems in Science and Engineering., 2011, 185-212.
[28] Combettes P L and Vu B C. Variable metric forward-backward splitting with applications to monotone inclusions in duality[J]. Optimization., 2014, 63:1289-1318.
[29] Combettes P L and Vu B C. Variable metric quasi-Fejer monotonicity[J]. Nonlinear Analysis., 2013, 78:17-31.
[30] Combettes P L and Wajs V R. Signal recovery by proximal forward-backward splitting[J]. SIAM Journal on Multiscale Modeling and Simulation., 2005, 4:1168-1200.
[31] Corman E and Yuan X M. A generalized proximal point algorithm and its convergence rate. SIAM Journal on Optimization., 2014, 24(4):1614-1638.
[32] Douglas J and Rachford H H. On the numerical solution of heat conduction problems in two or three space variables[J]. Transactions of the Ameican Mathematical Society., 1956, 82:421-439.
[33] Dykstra R. An algorithm for restricted least squares regression[J]. Publications of the American Statistical Association., 1983, 78(384):837-842.
[34] Eckstein J. Splitting methods for monotone operators with applications to parallel optimization[M]. Ph.D. thesis, MIT, 1989.
[35] Eckstein J and Bertsekas D P. On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators[J]. Mathematical Programming., 1992, 55:293-318.
[36] Eckstein J and Wang Yao. Understanding the convergence of the alternating direction method of multipliers:theoretical and computational perspectives[J]. Pacific Journal of Optimization., 2015, 11(4):619-644.
[37] Elser V, Rankenburg I and Thibault P. Searching with iterated maps[J]. Proceedings of the National Academy of Sciences of the United States of America., 2007, 104(2):418-423.
[38] Esser E, Zhang X Q and Chan T. A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science[J]. SIAM Journal on Imaging Sciences., 2010, 3(4):1015-1046.
[39] Facchinei F and Pang J S. Finite-Dimensional Variational Inequalities and Complementarity Problems[M]. Springer, Berlin (2003).
[40] Fazel M, Pong T K, Sun D F and Tseng P. Hankel matrix rank minimization with applications to system identification and realization[J]. SIAM Journal on Matrix Analalysis and Applications., 2013, 34(3):946-977.
[41] Fortin M and Glowinski. On decomposition-coordination methods using an augmented Lagrangian[M]. In Augmented Lagragian Methods:Applications to the Solutions of Boundary-Value Problems., M. Fortin and R. Glowinski (eds.), North-Holland, Amsterdam, 1983, 97-164.
[42] Gabay D. Applications of the method of multipliers to variational inequalities[M]. In Augmented Lagrangian methods:Applications to the Numerical Solution of Boundary-Value Problems., Fortin M, Glowinski R. (eds), North-Holland, Amsterdam (1983), 299-331.
[43] Glowinski R. On alternating direction methods of multipliers:a historical perspective[M]. In:Fitzgibbon, W., Kuznetsov, Y.A., Neittaanmaki, P., Pironneau, O. (eds.) Modeling, Simulation and Optimization for Science and Technology, 59-82. Springer, Netherlands (2014).
[44] Glowinski R and Marroco A. Sur l'approximation, par elements finis d'ordre un, et la resolution, par penalisation-dualité, d'une classe de problems de Dirichlet non lineares[J]. Rev. Française Informat. Recherche Opérationnelle., 1975, 9:41-76.
[45] Goldburg M and Marks Ⅱ R J. Signal synthesis in the presence of an inconsistent set of constraints[J]. IEEE Transactions on Circuits and Systems., 1985, 32:647-663.
[46] Goldstein A A. Convex programming in Hilbert space[J]. Bulletin of the American Mathematical Society., 1964, 70:709-710.
[47] Golshtein E G and Tretyakov N V. Modified Lagrangians and Monotone Maps in Optimization[M]. John Wiley, New York (1996).[Translation of Modified Lagrangian Functions:Theory and Related Optimization Techniques, Nauka, Moscow (1989).]
[48] Gravel S and Elser V. Divide and concur:a general approach to constraint satisfaction[J]. Phys Rev E Stat Nonlin Soft Matter Phys., 2008, 78(3):036706.
[49] Guo K, Han D R, David Wang Z W and Wu T T. Convergence of ADMM for multi-block nonconvex separable optimization models[J]. Frontier of Mathematics in China., 2017, 12(5):1139-1162.
[50] Guo K, Han D R and Wu T T. Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints[J]. International Journal of Computer Mathematics., 2017, 94:1653-1669.
[51] Guo K, Han D R and Wu T T. Convergence analysis for optimization problems with nonseparable nonconvex objective and linear constraints[J]. Pacific Journal on Optimization., Accepted.
[52] Guo K, Han D R and Yuan X M. Convergenece analysis of Douglas-Rachfod splitting method for "strongly+weakly" convex programming[J]. SIAM Journal on Numerical Analysis., 2017, 55(4):1549-1577.
[53] Guo K and Han D R. A note on the Douglas-Rachford splitting method for optimization problems involving weakly convex functions[J]. Journal of Global optimization. https://doi.org/10.1007/s10898-018-0660-z.
[54] Halperin I. The product of projection operators[J]. Acta Scientiarum Mathematicarum., 1962, 23:96-99.
[55] Han D R, He H J, Yang H and Yuan X M. A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints[J]. Numerische Mathematik., 2014, 127(1):167-200.
[56] Hartman P and Stampacchia G. On some non-linear elliptic differential-functional equations[J]. Acta Mathematica., 1966, 115:271-310.
[57] He B S, Liu H, Wang Z R and Yuan X M. A strictly contractive Peaceman-Rachford splitting method for convex programming[J]. SIAM Journal on Optimization., 2014, 24(3):1101-1140.
[58] Kachurovskii R I. Monotone operators and convex functionals[J]. Uspekhi Mat Nauk., 1960, 15(4):213-215.
[59] Kinderlehrer D and Stampacchia G. An Introduction to Variationa Inequalities and their Applications[M]. Academic Press, New York (1980).
[60] Konnov I V. Combined relaxation methods for finding equilibrium point and solving related problems[J]. Russian Mathematics., 1993, 37:46-53.
[61] Konnov I V. Equilibrium Models and Variational Inequalities[M]. Elsevier, Amsterdam (2007).
[62] Korpelevich G M. The extragradient method for finding saddle points and other problems[J]. Ekonomie i Mathematik Metody., 1976, 12:747-756.
[63] Krasnosel'skii M A. Two remarks on the method of successive approximations[J]. Uspekhi Mat Nauk., 1955, 10:123-127.
[64] Lemaire B. The proximal algorithm[M]. In:Penot J P, (Ed.), New Methods in Optimization and their Industrial Uses, International Series of Numerical Mathematics, 87, 73-87. Birkhauser, Boston, MA.
[65] Levitin E S and Polyak B T. Constrained minimization methods[J]. USSR Computational Mathematics and Mathematical Physics., 1966, 6:1-50.
[66] Li G Y and Pong T K. Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems[J]. Mathematical Programming., 2016, 159:371-401.
[67] Li G Y and Pong T K. Global convergence of splitting methods for nonconvex composite optimization[J]. SIAM Journal on Optimization., 2015, 25:2434-2460.
[68] Lions P L and Mercier B. Splitting algorithms for the sum of two nonlinear operators[J]. SIAM Journal on Numerical Analysis., 1979, 16:964-979.
[69] Martinet B. Determination approchee d'un point fixe d'une application pseudo-constractante[J]. C. R. Acad. Sci. Paris Ser. A., 1972, 274:163-165.
[70] Martinet B. Regularisation d'inequations variationnelles par approximations successives[J]. Rev.francaise Informat.recherche Operationnelle., 1970, 4(3):154-158.
[71] Minty G J. Monotone networks[J]. Proceedings of the Royal Society A., 1960, 257(1289):194-212.
[72] Minty G J. Monotone (nonlinear) operators in Hilbert space[J]. Duke Mathematical Journal., 1962, 29:341-346.
[73] Minty G J. On the maximal domain of a "monotone" function[J]. Michigan Mathematical Journal., 1961, 8(2):135-137.
[74] Minty G J. On the monotonicity of the gradient of a convex functin[J]. Pacific Journal of Mathematics., 1964, 14(1), 243-247.
[75] Nesterov Y E. A method for solving convex programming problem with convergence rate O(1/k2)[J]. Dokl. Akad. Nauk SSSR., 1983, 269:543-547.
[76] Nguyen Q V. Variable quasi-Bregman monotone sequence[J]. Numerical Algorithms., 2016, 73:1107-1130.
[77] O'Connor D and Vandenberghe L. On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting[J]. Mathematical Programming., (2018). https://doi.org/10.1007/s10107-018-1321-1.
[78] Opial Z. Weak convergence of the sequence of successive approximations for nonexpansive mappings[J]. Bulletin of the American Mathematical Society., 1967, 73:591-597.
[79] Passty G B. Ergodic convergence to a zero of the sum of monotone operators in Hilbert space[J]. Journal of Mathematical Analysis and Applications., 1979, 72:383-390.
[80] Peaceman D W and Rachford H H. The numerical solution of parabolic and elliptic differential equations[J]. Journal of the Society for Industrial and Applied Mathematics., 1955, 3:28-41.
[81] Pennanen T. A splitting method for composite mappings[J]. Numerical Functional Analysis and Optimization, 23:875-890.
[82] Rockafellar R T. Characterization of the subdifferentials of convex functions[J]. Pacific Journal of Mathematics., 1966, 17(3):497-510.
[83] Rockafellar R T. Lagrange multipliers and optimality[J]. SIAM Review., (1993), 35(2):183-238.
[84] Rockafellar R T. Monotone operators and the proximal point algorithm[J]. SIAM Journal on Control optimization., 1976, 14(5):877-898.
[85] Rockafellar R T and Wets R J-B. Variational Analysis[M]. Springer-Verlag, Berlin (1998).
[86] Sibony M. Méthodes itératives pour les équations et inéquations aux dérivés partielles nonlinéares de type monotone[J]. Calcolo., 1970, 7:65-183.
[87] Spingarn J E. Applications of the method of parital inverses to convex programming:decomposition[J]. Mathematical Programming., 1985, 32:199-223.
[88] Tseng P. A modified forward-backward splitting method for maximal monotone mappings[J]. SIAM Journal on Control optimization., 2000, 38:431-446.
[89] Tseng P. Applications of a splitting algorithm to decomposition in convex programming and vaiational inequalities[J]. SIAM Journal on Control and optimization., 1991, 29:119-138.
[90] Tseng P. Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming[J]. Mathematical Programming., 1990, 48:249-263.
[91] Tian W Y and Yuan X M. Faster alternating direction method of multipliers with O(1/n2) convergence rates[J]. Mathematics of Computation., In revision.
[92] Varga R S. Matrix Iterative Analysis[M]. 2nd Edn. Springer-Verlas, New York.
[93] Von Neumann J. Functional Operators, vol. Ⅱ. The Geometry of Orthogonal Spaces[M]. Princeton University Press, Princeton (1950).
[94] Wang F H, Xu Z B and Xu H K. Convergence of alternating direction method with multipliers for non-convex composite problems[J]. arXiv preprint arXiv:1410.8625., (2014).
[1] 陈圣杰, 戴彧虹, 徐凤敏. 稀疏线性规划研究[J]. 计算数学, 2018, 40(4): 339-353.
[2] 姜帆, 刘雅梅, 蔡邢菊. 一类自适应广义交替方向乘子法[J]. 计算数学, 2018, 40(4): 367-386.
[3] 蔡文银, 徐玲玲. 核范数和谱范数下广义Sylvester方程最小二乘问题的一类改进算法[J]. 计算数学, 2018, 40(4): 387-401.
[4] 孙聿童, 赵金玲. 求解结构型分裂可行问题的一种交替方向法[J]. 计算数学, 2018, 39(1): 20-27.
[5] 徐海文, 孙黎明. 一类凸优化的加速混合下降算法[J]. 计算数学, 2017, 39(2): 200-212.
[6] 李姣芬, 宋丹丹, 李涛, 黎稳. 核范数和谱范数下广义Sylvester方程最小二乘问题的有效算法[J]. 计算数学, 2017, 39(2): 129-150.
[7] 庄杰鹏, 彭拯. —种修正的Cauchy-Barzilai-Borwein算法[J]. 计算数学, 2016, 37(3): 186-198.
[8] 张艳君, 赵金玲, 徐尔. 求解多集分裂可行问题的一种共轭梯度法[J]. 计算数学, 2013, 34(4): 249-256.
[9] 徐海文. 一类凸优化的混合下降算法[J]. 计算数学, 2012, 34(1): 93-102.
[10] 张阳,. 线性对流占优扩散问题的交替方向差分流线扩散法[J]. 计算数学, 2007, 29(1): 49-66.
[11] 李冲,王兴华,张文红. 复合凸优化问题的Gauss-Newton法的收敛性[J]. 计算数学, 2002, 24(4): 469-478.

Copyright 2008 计算数学 版权所有
中国科学院数学与系统科学研究院 《计算数学》编辑部
北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发
技术支持: 010-62662699 E-mail:support@magtech.com.cn
京ICP备05002806号-10