nach oben

vorheriger Artikel A new algorithm that generates the image of the...

nächster Artikel A coercive heterogeneous media Helmholtz model:...

Tipp

Convergence analysis of positive-indefinite proximal ADMM with a Glowinski’s relaxation factor

Zeitschrift:: Numerical Algorithms > Ausgabe 4/2020

Autoren:: Jiawei Chen, Yiyun Wang, Hongjin He, Yibing Lv

» Jetzt Zugang zum Volltext erhalten

Wichtige Hinweise

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

In this paper, we propose a modified positive-indefinite proximal linearized ADMM (PIPL-ADMM) with a larger Glowinski’s relaxation factor for solving two-block linearly constrained separable convex programming by variational inequality technique. We investigate the internal relationships between the step size coefficient and the penalty coefficient to identify the convergence of PIPL-ADMM. The convergence of PIPL-ADMM and its convergence rate measured by the iteration complexity are established in the ergodic case. Numerical experiments are reported to illustrate the efficiency of the proposed methods.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Jetzt einloggen Kostenlos registrieren

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3, 1–122 (2011) MATHCrossRef

Chan, R.H., Yang, J.F., Yuan, X.M.: Alternating direction method for image inpainting in wavelet domains. SIAM J. Imag. Sci. 4(3), 807–826 (2011) MathSciNetMATHCrossRef

Chang, T.H., Liao, W.C., Hong, M.Y., Wang, X.F.: Asynchronous distributed ADMM for large-scale optimization-Part II: Linear convergence analysis and numerical performance. IEEE Trans. Signal Process. 64(12), 3131–3144 (2016) MathSciNetMATHCrossRef

Donoho, D.L., Tsaig, Y.: Fast solution of l1-norm minimization problems when the solution may be sparse. IEEE Trans. Inform. Theory 54, 4789–4812 (2008) MathSciNetMATHCrossRef

Fortin, M., Glowinski, R.: Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, Sole distributors for the U.S.A. and Canada, Elsevier Science Pub. Co (1983)

Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2, 17–40 (1976) MATHCrossRef

Glowinski, R., Marrocco, A.: Sur l’approximation, paréléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet nonlinéaires, Revue fancaise d’atomatique, Informatique Recherche opérationelle. Anal. Numŕ. 9(2), 41–76 (1975)

Han, D., Yuan, X.M.: A note on the alternating direction method of multipliers. J. Optim. Theory Appl. 155(1), 227–238 (2012) MathSciNetMATHCrossRef

Han, D., Yuan, X.M., Zhang, W., Cai, X.: An ADM-based splitting method for separable convex programming. Comput. Optim. Appl. 54(2), 343–369 (2013) MathSciNetMATHCrossRef

10.

He, B.S., Liao, L.Z., Han, D., Yang, H.: A new inexact alternating directions method for monotone variational inequalities. Math. Program. 92, 103–118 (2002) MathSciNetMATHCrossRef

11.

He, B.S., Yuan, X.M.: On the O(1/ n) convergence rate of the Douglas-Rachford alternating direction method. SIAM J. Numer. Anal. 50(2), 700–709 (2012) MathSciNetMATHCrossRef

12.

He, B.S., Liu, H., Wang, Z.R., Yuan, X.M.: A strictly contractive Peaceman-Rachford splitting method for convex programming. SIAM J. Optim. 24 (3), 1011–1040 (2014) MathSciNetMATHCrossRef

13.

He, B.S., Ma, F., Yuan, X.M.: Linearized alternating direction method of multipliers via positive-indefinite proximal regularization for convex programming, Optimization-online, http://www.optimization-online.org/DB_HTML/2016/07/5569.html (2016)

14.

He, B.S., Ma, F., Yuan, X.M.: Positive-indefinite proximal augmented Lagrangian method and its application to full Jacobian splitting for multi-block separable convex minimization problems, Optimization-online, http://www.optimization-online.org/DB_HTML/2016/09/5631.html (2016)

15.

Hestenes, M.: Multilplier and gradient methods. J. Optim. Theory Appl. 4(5), 303–320 (1969) MathSciNetMATHCrossRef

16.

Huai, K., Ni, M., Yu, Z., Zheng, X., Ma, F.: A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints. Numer. Algorith. 77(3), 653–674 (2018) MathSciNetMATHCrossRef

17.

Lin, Z., Liu, R., Li, H.: Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning. Mach. Learn. 99(2), 287–325 (2015) MathSciNetMATHCrossRef

18.

Monteiro, R.D.C., Svaiter, B.F.: Iteration-complexity of block-decomposition algorithms and the alternatinng direction method of multipliers. SIAM. J. Optim. 23(1), 475–507 (2013) MathSciNetMATHCrossRef

19.

Ng, M.K., Weiss, P., Yuan, X.M.: Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods. SIAM. J. Sci. Comput. 32(5), 2710–2736 (2010) MathSciNetMATHCrossRef

20.

Nesterov, Y.: Gradient methods for minimizing composite functions. Math. Program., Ser. B 140, 125–161 (2013) MathSciNetMATHCrossRef

21.

Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization, pp 283–298. Academic Press (1969)

22.

Rockfellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper Res. 1(2), 97–116 (1976) MathSciNetCrossRef

23.

Rudin, L., Osher, S.J., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Phys. D 60, 259–268 (1992) MathSciNetMATHCrossRef

24.

Wang, Y., Yang, J.F., Yin, W., Zhang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imag. Sci. 1(3), 248–272 (2008) MathSciNetMATHCrossRef

25.

Xia, F.Q., Huang, N.J.: A projection-proximal point algorithm for solving generalized variational inequalities. J. Optim. Theory Appl. 150, 98–117 (2011) MathSciNetMATHCrossRef

26.

Xie, W.S., Yang, Y.F., Zhou, B.: An ADMM algorithm for second-order TV-based MR image reconstruction. Numer. Algorith. 67(4), 827–843 (2014) MathSciNetMATHCrossRef

27.

Yang, J.F., Yuan, X.M.: Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization. Math. Comp. 82, 301–329 (2013) MathSciNetMATHCrossRef

28.

Yang, J.F., Zhang, Y., Yin, W.: A fast alternating direction method for TVL1-l2 signal reconstruction from partial Fourier data. IEEE J. Sel. Top. Signal Process. 4(2), 288–297 (2010) CrossRef

29.

Zhang, L., Fang, C., Chen, S.: An inertial subgradient-type method for solving single-valued variational inequalities and fixed point problems. Numer. Algorith. 79 (3), 941–956 (2018) MathSciNetMATHCrossRef

30.

Zhang, X.Q., Burger, M., Osher, S.: A unified primal-dual algorithm framework based on Bergman iteration. J. Sci. Comput. 46, 20–46 (2010) MATHCrossRef

Titel: Convergence analysis of positive-indefinite proximal ADMM with a Glowinski’s relaxation factor
Autoren:: Jiawei Chen
Yiyun Wang
Hongjin He
Yibing Lv
Publikationsdatum: 22.05.2019
DOI: https://doi.org/10.1007/s11075-019-00731-9
Verlag: Springer US
Zeitschrift: Numerical Algorithms
Ausgabe 4/2020
Print ISSN: 1017-1398
Elektronische ISSN: 1572-9265

Premium Partner

Bildnachweise

Springer Professional

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Publisher’s note

Abstract

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 4/2020

Symbolic-numeric integration of rational functions

A coercive heterogeneous media Helmholtz model: formulation, wavenumber-explicit analysis, and preconditioned high-order FEM

Computing the roots of sparse high–degree polynomials that arise from the study of random simplicial complexes

Convergence of a hybrid viscosity approximation method for finding zeros of m-accretive operators

Computational science in the eighteenth century. Test cases for the methods of Newton, Raphson, and Halley: 1685 to 1745

Efficient preconditioners for Radau-IIA time discretization of space fractional diffusion equations

Premium Partner