Skip to main content
Erschienen in: Journal of Scientific Computing 3/2018

02.03.2018

A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator

verfasst von: Ming Yan

Erschienen in: Journal of Scientific Computing | Ausgabe 3/2018

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper, we propose a new primal–dual algorithm for minimizing \(f({\mathbf {x}})+g({\mathbf {x}})+h({\mathbf {A}}{\mathbf {x}})\), where f, g, and h are proper lower semi-continuous convex functions, f is differentiable with a Lipschitz continuous gradient, and \({\mathbf {A}}\) is a bounded linear operator. The proposed algorithm has some famous primal–dual algorithms for minimizing the sum of two functions as special cases. E.g., it reduces to the Chambolle–Pock algorithm when \(f=0\) and the proximal alternating predictor–corrector when \(g=0\). For the general convex case, we prove the convergence of this new algorithm in terms of the distance to a fixed point by showing that the iteration is a nonexpansive operator. In addition, we prove the O(1 / k) ergodic convergence rate in the primal–dual gap. With additional assumptions, we derive the linear convergence rate in terms of the distance to the fixed point. Comparing to other primal–dual algorithms for solving the same problem, this algorithm extends the range of acceptable parameters to ensure its convergence and has a smaller per-iteration cost. The numerical experiments show the efficiency of this algorithm.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

Fußnoten
1
The conjugate function \(l^*\) of l is defined as \(l^*({\mathbf {s}})=\sup _{{\mathbf {t}}}\langle {\mathbf {s}},{\mathbf {t}}\rangle -l({\mathbf {t}})\). When \(l({\mathbf {s}})=\iota _{\{\mathbf {0}\}}({\mathbf {s}})\), we have \(l^*({\mathbf {s}})=0\). The conjugate function of \(h\square l\) is \((h\square l)^*=h^*+l^*\).
 
2
The adjoint operator \({\mathbf {A}}^\top \) is defined by \(\langle {\mathbf {s}},{\mathbf {A}}{\mathbf {x}}\rangle _{\mathcal {S}}= \langle {\mathbf {A}}^\top {\mathbf {s}},{\mathbf {x}}\rangle _{\mathcal {X}}\).
 
Literatur
1.
Zurück zum Zitat Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011)CrossRefMATH Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011)CrossRefMATH
2.
Zurück zum Zitat Baytas, I.M., Yan, M., Jain, A.K., Zhou, J.: Asynchronous multi-task learning. In: IEEE International Conference on Data Mining (ICDM), pp. 11–20. IEEE (2016) Baytas, I.M., Yan, M., Jain, A.K., Zhou, J.: Asynchronous multi-task learning. In: IEEE International Conference on Data Mining (ICDM), pp. 11–20. IEEE (2016)
3.
Zurück zum Zitat Briceno-Arias, L.M.: Forward-Douglas–Rachford splitting and forward-partial inverse method for solving monotone inclusions. Optimization 64(5), 1239–1261 (2015)MathSciNetCrossRefMATH Briceno-Arias, L.M.: Forward-Douglas–Rachford splitting and forward-partial inverse method for solving monotone inclusions. Optimization 64(5), 1239–1261 (2015)MathSciNetCrossRefMATH
4.
Zurück zum Zitat Chambolle, A., Pock, T.: A first-order primal–dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120–145 (2011)MathSciNetCrossRefMATH Chambolle, A., Pock, T.: A first-order primal–dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120–145 (2011)MathSciNetCrossRefMATH
6.
Zurück zum Zitat Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal–dual algorithm. Math. Program. 159(1–2), 253–287 (2016)MathSciNetCrossRefMATH Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal–dual algorithm. Math. Program. 159(1–2), 253–287 (2016)MathSciNetCrossRefMATH
7.
Zurück zum Zitat Chen, P., Huang, J., Zhang, X.: A primal–dual fixed point algorithm for convex separable minimization with applications to image restoration. Inverse Probl. 29(2), 025011 (2013)MathSciNetCrossRefMATH Chen, P., Huang, J., Zhang, X.: A primal–dual fixed point algorithm for convex separable minimization with applications to image restoration. Inverse Probl. 29(2), 025011 (2013)MathSciNetCrossRefMATH
8.
Zurück zum Zitat Chen, P., Huang, J., Zhang, X.: A primal–dual fixed point algorithm for minimization of the sum of three convex separable functions. Fixed Point Theory Appl. 2016(1), 1–18 (2016)MathSciNetCrossRefMATH Chen, P., Huang, J., Zhang, X.: A primal–dual fixed point algorithm for minimization of the sum of three convex separable functions. Fixed Point Theory Appl. 2016(1), 1–18 (2016)MathSciNetCrossRefMATH
9.
Zurück zum Zitat Combettes, P.L., Condat, L., Pesquet, J.C., Vu, B.C.: A forward–backward view of some primal–dual optimization methods in image recovery. In: 2014 IEEE International Conference on Image Processing (ICIP), pp. 4141–4145 (2014) Combettes, P.L., Condat, L., Pesquet, J.C., Vu, B.C.: A forward–backward view of some primal–dual optimization methods in image recovery. In: 2014 IEEE International Conference on Image Processing (ICIP), pp. 4141–4145 (2014)
10.
Zurück zum Zitat Combettes, P.L., Pesquet, J.C.: Primal–dual splitting algorithm for solving inclusions with mixtures of composite, lipschitzian, and parallel-sum type monotone operators. Set Valued Var. Anal. 20(2), 307–330 (2012)MathSciNetCrossRefMATH Combettes, P.L., Pesquet, J.C.: Primal–dual splitting algorithm for solving inclusions with mixtures of composite, lipschitzian, and parallel-sum type monotone operators. Set Valued Var. Anal. 20(2), 307–330 (2012)MathSciNetCrossRefMATH
11.
Zurück zum Zitat Condat, L.: A direct algorithm for 1-d total variation denoising. IEEE Signal Process. Lett. 20(11), 1054–1057 (2013)CrossRef Condat, L.: A direct algorithm for 1-d total variation denoising. IEEE Signal Process. Lett. 20(11), 1054–1057 (2013)CrossRef
12.
Zurück zum Zitat Condat, L.: A primal–dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl. 158(2), 460–479 (2013)MathSciNetCrossRefMATH Condat, L.: A primal–dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl. 158(2), 460–479 (2013)MathSciNetCrossRefMATH
13.
14.
Zurück zum Zitat Davis, D., Yin, W.: Convergence rate analysis of several splitting schemes. In: Glowinski, R., Osher, S.J., Yin, W. (eds.) Splitting Methods in Communication, Imaging, Science, and Engineering, pp. 115–163. Springer, Cham (2016)CrossRef Davis, D., Yin, W.: Convergence rate analysis of several splitting schemes. In: Glowinski, R., Osher, S.J., Yin, W. (eds.) Splitting Methods in Communication, Imaging, Science, and Engineering, pp. 115–163. Springer, Cham (2016)CrossRef
15.
Zurück zum Zitat Davis, D., Yin, W.: A three-operator splitting scheme and its optimization applications. Set Valued Var. Anal. 25(4), 829–858 (2017)MathSciNetCrossRefMATH Davis, D., Yin, W.: A three-operator splitting scheme and its optimization applications. Set Valued Var. Anal. 25(4), 829–858 (2017)MathSciNetCrossRefMATH
16.
Zurück zum Zitat Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 82, 421–489 (1956)MathSciNetCrossRefMATH Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 82, 421–489 (1956)MathSciNetCrossRefMATH
17.
Zurück zum Zitat Drori, Y., Sabach, S., Teboulle, M.: A simple algorithm for a class of nonsmooth convexconcave saddle-point problems. Oper. Res. Lett. 43(2), 209–214 (2015)MathSciNetCrossRef Drori, Y., Sabach, S., Teboulle, M.: A simple algorithm for a class of nonsmooth convexconcave saddle-point problems. Oper. Res. Lett. 43(2), 209–214 (2015)MathSciNetCrossRef
18.
Zurück zum Zitat Esser, E., Zhang, X., Chan, T.F.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015–1046 (2010)MathSciNetCrossRefMATH Esser, E., Zhang, X., Chan, T.F.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015–1046 (2010)MathSciNetCrossRefMATH
19.
Zurück zum Zitat Gabay, D.: Applications of the method of multipliers to variational inequalities. Stud. Math. Appl. 15, 299–331 (1983) Gabay, D.: Applications of the method of multipliers to variational inequalities. Stud. Math. Appl. 15, 299–331 (1983)
20.
Zurück zum Zitat Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1), 17–40 (1976)CrossRefMATH Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1), 17–40 (1976)CrossRefMATH
21.
Zurück zum Zitat Glowinski, R., Marroco, 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 non linéaires. Revue française d’automatique, informatique, recherche opérationnelle. Analyse numérique 9(2), 41–76 (1975) Glowinski, R., Marroco, 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 non linéaires. Revue française d’automatique, informatique, recherche opérationnelle. Analyse numérique 9(2), 41–76 (1975)
22.
Zurück zum Zitat He, B., You, Y., Yuan, X.: On the convergence of primal–dual hybrid gradient algorithm. SIAM J. Imaging Sci. 7(4), 2526–2537 (2014)MathSciNetCrossRefMATH He, B., You, Y., Yuan, X.: On the convergence of primal–dual hybrid gradient algorithm. SIAM J. Imaging Sci. 7(4), 2526–2537 (2014)MathSciNetCrossRefMATH
23.
Zurück zum Zitat Komodakis, N., Pesquet, J.C.: Playing with duality: an overview of recent primal-dual approaches for solving large-scale optimization problems. IEEE Signal Process. Mag. 32(6), 31–54 (2015)CrossRef Komodakis, N., Pesquet, J.C.: Playing with duality: an overview of recent primal-dual approaches for solving large-scale optimization problems. IEEE Signal Process. Mag. 32(6), 31–54 (2015)CrossRef
24.
Zurück zum Zitat Krol, A., Li, S., Shen, L., Xu, Y.: Preconditioned alternating projection algorithms for maximum a posteriori ECT reconstruction. Inverse Probl. 28(11), 115005 (2012)MathSciNetCrossRefMATH Krol, A., Li, S., Shen, L., Xu, Y.: Preconditioned alternating projection algorithms for maximum a posteriori ECT reconstruction. Inverse Probl. 28(11), 115005 (2012)MathSciNetCrossRefMATH
25.
Zurück zum Zitat Latafat, P., Patrinos, P.: Asymmetric forward–backward-adjoint splitting for solving monotone inclusions involving three operators. Comput. Optim. Appl. 68(1), 57–93 (2017)MathSciNetCrossRefMATH Latafat, P., Patrinos, P.: Asymmetric forward–backward-adjoint splitting for solving monotone inclusions involving three operators. Comput. Optim. Appl. 68(1), 57–93 (2017)MathSciNetCrossRefMATH
26.
Zurück zum Zitat Lorenz, D.A., Pock, T.: An inertial forward–backward algorithm for monotone inclusions. J. Math. Imaging Vis. 51(2), 311–325 (2015)MathSciNetCrossRefMATH Lorenz, D.A., Pock, T.: An inertial forward–backward algorithm for monotone inclusions. J. Math. Imaging Vis. 51(2), 311–325 (2015)MathSciNetCrossRefMATH
27.
Zurück zum Zitat Loris, I., Verhoeven, C.: On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty. Inverse Probl. 27(12), 125007 (2011)MathSciNetCrossRefMATH Loris, I., Verhoeven, C.: On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty. Inverse Probl. 27(12), 125007 (2011)MathSciNetCrossRefMATH
28.
Zurück zum Zitat O’Connor, D., Vandenberghe, L.: On the equivalence of the primal-dual hybrid gradient method and Douglas–Rachford splitting. optimization-online.org (2017) O’Connor, D., Vandenberghe, L.: On the equivalence of the primal-dual hybrid gradient method and Douglas–Rachford splitting. optimization-online.org (2017)
29.
Zurück zum Zitat Passty, G.B.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. J. Math. Anal. Appl. 72(2), 383–390 (1979)MathSciNetCrossRefMATH Passty, G.B.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. J. Math. Anal. Appl. 72(2), 383–390 (1979)MathSciNetCrossRefMATH
30.
Zurück zum Zitat Peaceman, D.W., Rachford, H.H.: The numerical solution of parabolic and elliptic differential equations. J. Soc. Ind. Appl. Math. 3(1), 28–41 (1955)MathSciNetCrossRefMATH Peaceman, D.W., Rachford, H.H.: The numerical solution of parabolic and elliptic differential equations. J. Soc. Ind. Appl. Math. 3(1), 28–41 (1955)MathSciNetCrossRefMATH
31.
Zurück zum Zitat Peng, Z., Wu, T., Xu, Y., Yan, M., Yin, W.: Coordinate friendly structures, algorithms and applications. Ann. Math. Sci. Appl. 1(1), 57–119 (2016)MATH Peng, Z., Wu, T., Xu, Y., Yan, M., Yin, W.: Coordinate friendly structures, algorithms and applications. Ann. Math. Sci. Appl. 1(1), 57–119 (2016)MATH
32.
Zurück zum Zitat Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the Mumford–Shah functional. In: 2009 IEEE 12th International Conference on Computer Vision, pp. 1133–1140. IEEE (2009) Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the Mumford–Shah functional. In: 2009 IEEE 12th International Conference on Computer Vision, pp. 1133–1140. IEEE (2009)
33.
Zurück zum Zitat Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., Knight, K.: Sparsity and smoothness via the fused lasso. J. R. Stat. Soc. Ser. B (Stat. Methodol.) 67(1), 91–108 (2005)MathSciNetCrossRefMATH Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., Knight, K.: Sparsity and smoothness via the fused lasso. J. R. Stat. Soc. Ser. B (Stat. Methodol.) 67(1), 91–108 (2005)MathSciNetCrossRefMATH
34.
Zurück zum Zitat Vũ, B.C.: A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math. 38(3), 667–681 (2013)MathSciNetCrossRefMATH Vũ, B.C.: A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math. 38(3), 667–681 (2013)MathSciNetCrossRefMATH
35.
Zurück zum Zitat Yan, M., Yin, W.: Self equivalence of the alternating direction method of multipliers. In: Glowinski, R., Osher, S.J., Yin, W. (eds.) Splitting Methods in Communication, Imaging, Science, and Engineering, pp. 165–194. Springer, Cham (2016)CrossRef Yan, M., Yin, W.: Self equivalence of the alternating direction method of multipliers. In: Glowinski, R., Osher, S.J., Yin, W. (eds.) Splitting Methods in Communication, Imaging, Science, and Engineering, pp. 165–194. Springer, Cham (2016)CrossRef
36.
Zurück zum Zitat Zou, H., Hastie, T.: Regularization and variable selection via the elastic net. J. R. Stat. Soc. Ser. B (Stat. Methodol.) 67(2), 301–320 (2005)MathSciNetCrossRefMATH Zou, H., Hastie, T.: Regularization and variable selection via the elastic net. J. R. Stat. Soc. Ser. B (Stat. Methodol.) 67(2), 301–320 (2005)MathSciNetCrossRefMATH
Metadaten
Titel
A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator
verfasst von
Ming Yan
Publikationsdatum
02.03.2018
Verlag
Springer US
Erschienen in
Journal of Scientific Computing / Ausgabe 3/2018
Print ISSN: 0885-7474
Elektronische ISSN: 1573-7691
DOI
https://doi.org/10.1007/s10915-018-0680-3

Weitere Artikel der Ausgabe 3/2018

Journal of Scientific Computing 3/2018 Zur Ausgabe