Skip to main content
Springer Nature Link
Log in

Douglas–Rachford splitting and ADMM for pathological convex optimization

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

Despite the vast literature on DRS and ADMM, there has been very little work analyzing their behavior under pathologies. Most analyses assume a primal solution exists, a dual solution exists, and strong duality holds. When these assumptions are not met, i.e., under pathologies, the theory often breaks down and the empirical performance may degrade significantly. In this paper, we establish that DRS only requires strong duality to work, in the sense that asymptotically iterates are approximately feasible and approximately optimal.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Artacho, F.J.A., Borwein, J.M., Tam, M.K.: Douglas–Rachford feasibility methods for matrix completion problems. The ANZIAM J. 55(4), 299–326 (2014)

    MathSciNet  MATH  Google Scholar 

  2. Artacho, F.J.A., Borwein, J.M., Tam, M.K.: Global behavior of the Douglas–Rachford method for a nonconvex feasibility problem. J. Global Optim. 65(2), 309–327 (2016)

    MathSciNet  MATH  Google Scholar 

  3. Attouch, H., Baillon, J.B., Théra, M.: Variational sum of monotone operators. J. Convex Anal. 1(11), 001–030 (1994)

    MathSciNet  MATH  Google Scholar 

  4. Attouch, H., Théra, M.: A general duality principle for the sum of two operators. J. Convex Anal. 3(1), 1–24 (1996)

    MathSciNet  MATH  Google Scholar 

  5. Baillon, J.B., Bruck, R.E., Reich, S.: On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces. Houston J. Math. 4(1), 1–9 (1978)

    MathSciNet  MATH  Google Scholar 

  6. Banjac, G., Goulart, P., Stellato, B., Boyd, S.: Infeasibility detection in the alternating direction method of multipliers for convex optimization. Optimization-online.org (2017)

  7. Bauschke, H.H., Boţ, R.I., Hare, W.L., Moursi, W.M.: Attouch-Théra duality revisited: paramonotonicity and operator splitting. J. Approx. Theory 164(8), 1065–1084 (2012)

    MathSciNet  MATH  Google Scholar 

  8. Bauschke, H.H., Borwein, J.M., Lewis, A.S.: The method of cyclic projections for closed convex sets in Hilbert space. Contemp. Math. 204, 1–38 (1997)

    MathSciNet  MATH  Google Scholar 

  9. Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd edn. Springer, New York (2017)

    MATH  Google Scholar 

  10. Bauschke, H.H., Combettes, P.L., Luke, D.: Finding best approximation pairs relative to two closed convex sets in Hilbert spaces. J. Approx. Theory 127(2), 178–192 (2004)

    MathSciNet  MATH  Google Scholar 

  11. Bauschke, H.H., Douglas, G.R., Moursi, W.M.: On a result of Pazy concerning the asymptotic behaviour of nonexpansive mappings. J. Fixed Point Theory Appl. 18(2), 297–307 (2016)

    MathSciNet  MATH  Google Scholar 

  12. Bauschke, H.H., Hare, W.L., Moursi, W.M.: Generalized solutions for the sum of two maximally monotone operators. SIAM J. Control Optim. 52(2), 1034–1047 (2014)

    MathSciNet  MATH  Google Scholar 

  13. Bauschke, H.H., Hare, W.L., Moursi, W.M.: On the range of the Douglas–Rachford operator. Math. Oper. Res. 41(3), 884–897 (2016)

    MathSciNet  MATH  Google Scholar 

  14. Bauschke, H.H., Lukens, B., Moursi, W.M.: Affine nonexpansive operators, attouch-théra duality and the Douglas–Rachford algorithm. Set-Valued Var. Anal. 25(3), 481–505 (2017)

    MathSciNet  MATH  Google Scholar 

  15. Bauschke, H.H., Moursi, W.M.: The Douglas–Rachford algorithm for two (not necessarily intersecting) affine subspaces. SIAM J. Optim. 26(2), 968–985 (2016)

    MathSciNet  MATH  Google Scholar 

  16. Bauschke, H.H., Moursi, W.M.: On the Douglas–Rachford algorithm. Math. Program. 164(1–2), 263–284 (2017)

    MathSciNet  MATH  Google Scholar 

  17. Bertsekas, D.: Convex Optimization Theory. Athena Scientific, Nashua (2009)

    MATH  Google Scholar 

  18. Bertsekas, D., Tsitsiklis, J.: Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Englewood Cliffs (1989)

    MATH  Google Scholar 

  19. Borwein, J., Wolkowicz, H.: Regularizing the abstract convex program. J. Math. Anal. Appl. 83(2), 495–530 (1981)

    MathSciNet  MATH  Google Scholar 

  20. Borwein, J.M., Tam, M.K.: The cyclic Douglas–Rachford method for inconsistent feasibility problems. J. Nonlinear Convex Anal. 16(4), 537–584 (2015)

    MathSciNet  MATH  Google Scholar 

  21. Borwein, J.M., Wolkowicz, H.: Facial reduction for a cone-convex programming problem. J. Aust. Math. Soc. 30(3), 369–380 (1981)

    MathSciNet  MATH  Google Scholar 

  22. Borwein, J.M., Wolkowicz, H.: Characterizations of optimality without constraint qualification for the abstract convex program. In: Guignard, M. (ed.) Optimality and Stability in Mathematical Programming, pp. 77–100. Springer, Berlin (1982)

    MATH  Google Scholar 

  23. 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), 1–122 (2011)

    MATH  Google Scholar 

  24. Chen, L., Li, X., Sun, D., Toh, K.C.: On the equivalence of inexact proximal alm and admm for a class of convex composite programming (2018)

  25. Chen, L., Sun, D., Toh, K.C.: A note on the convergence of ADMM for linearly constrained convex optimization problems. Comput. Optim. Appl. 66(2), 327–343 (2017)

    MathSciNet  MATH  Google Scholar 

  26. Cheung, Y.L., Schurr, S., Wolkowicz, H.: Preprocessing and regularization for degenerate semidefinite programs. In: Bailey, D.H., Bauschke, H.H., Borwein, P., Garvan, F., Théra, M., Vanderwerff, J.D., Wolkowicz, H. (eds.) Comput. Anal. Math., pp. 251–303. Springer, New York (2013)

    Google Scholar 

  27. Combettes, P.L.: Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53(5–6), 475–504 (2004)

    MathSciNet  MATH  Google Scholar 

  28. Combettes, P.L.: Monotone operator theory in convex optimization. Math. Program. 170(1), 177–206 (2018)

    MathSciNet  MATH  Google Scholar 

  29. Combettes, P.L., Pesquet, J.C.: Proximal splitting methods in signal processing. In: Bauschke, H.H., Burachik, R.S., Combettes, P.L., Elser, V., Luke, D.R., Wolkowicz, H. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 185–212. Springer, New York (2011)

    MATH  Google Scholar 

  30. Davis, D.: Convergence rate analysis of primal-dual splitting schemes. SIAM J. Optim. 25(3), 1912–1943 (2015)

    MathSciNet  MATH  Google Scholar 

  31. 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, Berlin (2016)

    Google Scholar 

  32. Davis, D., Yin, W.: Faster convergence rates of relaxed Peaceman–Rachford and ADMM under regularity assumptions. Math. Oper. Res. 42(3), 783–805 (2017)

    MathSciNet  MATH  Google Scholar 

  33. De Loera, J.A., Malkin, P.N., Parrilo, P.A.: Computation with polynomial equations and inequalities arising in combinatorial optimization. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming, pp. 447–481. Springer, New York (2012)

    Google Scholar 

  34. Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889–916 (2016)

    MathSciNet  MATH  Google Scholar 

  35. 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–439 (1956)

    MathSciNet  MATH  Google Scholar 

  36. Drusvyatskiy, D., Wolkowicz, H.: The many faces of degeneracy in conic optimization. Found. Trends Optim. 3(2), 77–170 (2017)

    Google Scholar 

  37. Eckstein, J.: Splitting methods for monotone operators with applications to parallel optimization. Ph.D. thesis, MIT (1989)

  38. Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1–3), 293–318 (1992)

    MathSciNet  MATH  Google Scholar 

  39. Eckstein, J., Yao, W.: Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives. Pac. J. Optim. 11(4), 619–644 (2015)

    MathSciNet  MATH  Google Scholar 

  40. Fazel, M., Pong, T., Sun, D., Tseng, P.: Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. Appl. 34(3), 946–977 (2013)

    MathSciNet  MATH  Google Scholar 

  41. Fenchel, W.: Convex cones, sets, and functions (1953). Mimeographed lecture notes

  42. Fortin, M., Glowinski, R.: On decomposition-coordination methods using an augmented lagrangian. In: M. Fortin, R. Glowinski (eds.) Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, pp. 97–146 (1983)

  43. Gabay, D.: Applications of the method of multipliers to variational inequalities. In: M. Fortin, R. Glowinski (eds.) Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems (1983)

  44. 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)

    MATH  Google Scholar 

  45. Glowinski, R.: Numerical Methods for Nonlinear Variational Problems. Springer, Berlin (1984)

    MATH  Google Scholar 

  46. 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)

    MathSciNet  MATH  Google Scholar 

  47. Kellogg, R.B.: A nonlinear alternating direction method. Math. Comput. 23(105), 23–27 (1969)

    MathSciNet  MATH  Google Scholar 

  48. Kretschmer, K.S.: Programmes in paired spaces. Canad. J. Math. 13, 221–238 (1961)

    MathSciNet  MATH  Google Scholar 

  49. Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979)

    MathSciNet  MATH  Google Scholar 

  50. Liu, Y., Ryu, E.K., Yin, W.: A new use of Douglas–Rachford splittingfor identifying infeasible, unbounded, and pathological conic programs. Math. Program. 177, 225–253 (2018)

    MATH  Google Scholar 

  51. Lofberg, J.: Pre- and post-processing sum-of-squares programs in practice. IEEE Trans. Autom. Control 54(5), 1007–1011 (2009)

    MathSciNet  MATH  Google Scholar 

  52. Lourenço, B.F., Muramatsu, M., Tsuchiya, T.: Solving SDP completely with an interior point oracle (2015). arXiv preprint arXiv:1507.08065

  53. Luo, Z.Q., Sturm, J.F., Zhang, S.: Duality results for conic convex programming. Technical report, Erasmus University Rotterdam, Econometric Institute (1997)

  54. Luo, Z.Q., Sturm, J.F., Zhang, S.: Conic convex programming and self-dual embedding. Optim. Methods Softw. 14(3), 169–218 (2000)

    MathSciNet  MATH  Google Scholar 

  55. Mercier, B.: Inéquations Variationnelles de la Mécanique (Publications Mathématiques d’Orsay, no. 80.01). Orsay, France: Université de Paris-XI (1980)

  56. Moursi, W.M.: The forward-backward algorithm and the normal problem. J. Optim. Theory Appl. 176(3), 605–624 (2018)

    MathSciNet  MATH  Google Scholar 

  57. Nesterov, Y., Todd, M.J., Ye, Y.: Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems. Math. Program. 84(2), 227–267 (1999)

    MathSciNet  MATH  Google Scholar 

  58. Pataki, G.: A simple derivation of a facial reduction algorithm and extended dual systems. Technical report, Columbia University (2000)

  59. Pataki, G., Tran-Dinh, Q., et al.: Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs. Math. Program. Comput. (2019)

  60. Pazy, A.: Asymptotic behavior of contractions in Hilbert space. Israel J. Math. 9(2), 235–240 (1971)

    MathSciNet  MATH  Google Scholar 

  61. 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)

    MathSciNet  MATH  Google Scholar 

  62. Permenter, F., Friberg, H.A., Andersen, E.D.: Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach. SIAM J. Optim. 27(3), 1257–1282 (2017)

    MathSciNet  MATH  Google Scholar 

  63. Permenter, F., Parrilo, P.: Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone. Math. Program. (2017)

  64. Permenter, F., Parrilo, P.A.: Basis selection for SOS programs via facial reduction and polyhedral approximations. In: 53rd IEEE Conference on Decision and Control, CDC 2014, pp. 6615–6620 (2014)

  65. Raghunathan, A.U., Cairano, S.D.: Infeasibility detection in alternating direction method of multipliers for convex quadratic programs. In: 2014 IEEE 53rd Annual Conference on Decision and Control (CDC), pp. 5819–5824 (2014)

  66. Ramana, M.V., Tunçel, L., Wolkowicz, H.: Strong duality for semidefinite programming. SIAM J. Optim. 7(3), 641–662 (1997)

    MathSciNet  MATH  Google Scholar 

  67. Revalski, J.P., Théra, M.: Generalized sums of monotone operators. Comptes Rendus de l’Académie des Sciences - Series I - Mathematics 329(11), 979–984 (1999)

    MathSciNet  MATH  Google Scholar 

  68. Revalski, J.P., Théra, M.: Enlargements and sums of monotone operators. Nonlinear Anal. Theory Methods Appl. 48(4), 505–519 (2002)

    MathSciNet  MATH  Google Scholar 

  69. Rockafellar, R.: Conjugate Duality and Optimization. Soc. Ind. Appl. Math. (1974)

  70. Rockafellar, R.T.: Convex Analysis (1970)

  71. Ryu, E.K.: Cosmic divergence, weak cosmic convergence, and fixed points at infinity. J. Fixed Point Theory Appl. 20, 109 (2018)

    MathSciNet  MATH  Google Scholar 

  72. Stellato, B., Banjac, G., Goulart, P., Bemporad, A., Boyd, S.: OSQP: An operator splitting solver for quadratic programs (2017). arXiv preprint arXiv:1711.08013

  73. Tunçel, L., Wolkowicz, H.: Strong duality and minimal representations for cone optimization. Comput. Optim. Appl. 53(2), 619–648 (2012)

    MathSciNet  MATH  Google Scholar 

  74. Waki, H.: How to generate weakly infeasible semidefinite programs via Lasserre’s relaxations for polynomial optimization. Optim. Lett. 6(8), 1883–1896 (2012)

    MathSciNet  MATH  Google Scholar 

  75. Waki, H., Muramatsu, M.: A facial reduction algorithm for finding sparse sos representations. Oper. Res. Lett. 38(5), 361–365 (2010)

    MathSciNet  MATH  Google Scholar 

  76. Waki, H., Muramatsu, M.: Facial reduction algorithms for conic optimization problems. J. Optim. Theory Appl. 158(1), 188–215 (2013)

    MathSciNet  MATH  Google Scholar 

  77. Waki, H., Nakata, M., Muramatsu, M.: Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization. Comput. Optim. Appl. 53(3), 823–844 (2012)

    MathSciNet  MATH  Google Scholar 

  78. Yamasaki, M.: Some generalizations of duality theorems in math. program. problems. Math. J. Okayama Univ. 14, 69–81 (1969)

    MathSciNet  MATH  Google Scholar 

  79. 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, Berlin (2016)

    Google Scholar 

  80. Ye, Y.: Linear conic programming. Manuscript. Stanford University, Stanford, CA (2004)

    Google Scholar 

Download references

Acknowledgements

Funding was provided by Division of Mathematical Sciences (DMS-1720237), Office of Naval Research Global (N000141712162).

Author information

Authors and Affiliations

  1. UCLA, Los Angeles, USA

    Ernest K. Ryu, Yanli Liu & Wotao Yin

Authors
  1. Ernest K. Ryu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yanli Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wotao Yin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ernest K. Ryu.

Additional information

Publisher's Note

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ryu, E.K., Liu, Y. & Yin, W. Douglas–Rachford splitting and ADMM for pathological convex optimization. Comput Optim Appl 74, 747–778 (2019). https://doi.org/10.1007/s10589-019-00130-9

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-019-00130-9

Keywords

Mathematics Subject Classification

Search

Navigation