Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An Inexact Spingarn’s Partial Inverse Method with Applications to Operator Splitting and Composite Optimization

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

We propose and study the iteration-complexity of an inexact version of the Spingarn’s partial inverse method. Its complexity analysis is performed by viewing it in the framework of the hybrid proximal extragradient method, for which pointwise and ergodic iteration-complexity has been established recently by Monteiro and Svaiter. As applications, we propose and analyze the iteration-complexity of an inexact operator splitting algorithm—which generalizes the original Spingarn’s splitting method—and of a parallel forward–backward algorithm for multi-term composite convex optimization.

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

Notes

  1. see, e.g., [32, Corollary 16.39]

References

  1. Spingarn, J.E.: Partial inverse of a monotone operator. Appl. Math. Optim. 10(3), 247–265 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  2. Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877–898 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  3. Solodov, M.V., Svaiter, B.F.: A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Anal. 7(4), 323–345 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  4. Boţ, R.I., Csetnek, E.R.: A hybrid proximal-extragradient algorithm with inertial effects. Numer. Funct. Anal. Optim. 36(8), 951–963 (2015)

    Article  MATH  MathSciNet  Google Scholar 

  5. Ceng, L.C., Mordukhovich, B.S., Yao, J.C.: Hybrid approximate proximal method with auxiliary variational inequality for vector optimization. J. Optim. Theory Appl. 146(2), 267–303 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  6. Eckstein, J., Silva, P.J.S.: A practical relative error criterion for augmented Lagrangians. Math. Program. 141(1–2, Ser. A), 319–348 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  7. He, Y., Monteiro, R.D.C.: An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems. SIAM J. Optim. 26(1), 29–56 (2016)

    Article  MATH  MathSciNet  Google Scholar 

  8. Iusem, A.N., Sosa, W.: On the proximal point method for equilibrium problems in Hilbert spaces. Optimization 59(8), 1259–1274 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  9. Lotito, P.A., Parente, L.A., Solodov, M.V.: A class of variable metric decomposition methods for monotone variational inclusions. J. Convex Anal. 16(3–4), 857–880 (2009)

    MATH  MathSciNet  Google Scholar 

  10. Monteiro, R.D.C., Ortiz, C., Svaiter, B.F.: Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems. Comput. Optim. Appl. 57(1), 45–69 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  11. Monteiro, R.D.C., Ortiz, C., Svaiter, B.F.: An adaptive accelerated first-order method for convex optimization. Comput. Optim. Appl. 64(1), 31–73 (2016)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  13. Solodov, M.V., Svaiter, B.F.: An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions. Math. Oper. Res. 25(2), 214–230 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  14. Solodov, M.V., Svaiter, B.F.: A unified framework for some inexact proximal point algorithms. Numer. Funct. Anal. Optim. 22(7–8), 1013–1035 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  15. Monteiro, R.D.C., Svaiter, B.F.: On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM J. Optim. 20, 2755–2787 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  16. Gonçalves, M.L.N., Melo, J.G., Monteiro, R.D.C.: Improved Pointwise Iteration-Complexity of a Regularized ADMM and of a Regularized Non-euclidean HPE Framework, pp. 30332–0205. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta (2016)

    MATH  Google Scholar 

  17. Burachik, R.S., Sagastizábal, C.A., Scheimberg, S.: An inexact method of partial inverses and a parallel bundle method. Optim. Methods Softw. 21(3), 385–400 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  18. Burachik, R.S., Iusem, A.N., Svaiter, B.F.: Enlargement of monotone operators with applications to variational inequalities. Set-Valued Anal. 5(2), 159–180 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  19. Martinez-Legaz, J.-E., Théra, M.: \(\epsilon \)-subdifferentials in terms of subdifferentials. Set-Valued Anal. 4(4), 327–332 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  20. Burachik, R.S., Sagastizábal, C.A., Svaiter, B.F.: \(\epsilon \)-enlargements of maximal monotone operators: theory and applications. In: Fukushima, M., Qi, L. (eds.) Reformulation: nonsmooth, piecewise smooth, semismooth and smoothing methods (Lausanne, 1997) vol. 22 of Appl. Optim., pp. 25–43. Kluwer Acad. Publ., Dordrecht (1999)

  21. Monteiro, R. D. C., Svaiter, B. F.: Convergence rate of inexact proximal point methods with relative error criteria for convex optimization. http://www.optimization-online.org/DB_HTML/2010/08/2714.html (2010)

  22. Nesterov, Y.: Introductory Lectures on Convex Optimization. A Basic Course. Kluwer Academic Publishers, Boston (2004)

    Book  MATH  Google Scholar 

  23. Monteiro, R.D.C., Svaiter, B.F.: Complexity of variants of Tseng’s modified F-B splitting and Korpelevich’s methods for hemivariational inequalities with applications to saddle point and convex optimization problems. SIAM J. Optim. 21, 1688–1720 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  24. Solodov, M.V., Svaiter, B.F.: A hybrid projection-proximal point algorithm. J. Convex Anal. 6(1), 59–70 (1999)

    MATH  MathSciNet  Google Scholar 

  25. Alghamdi, M.A., Alotaibi, A., Combettes, P.L., Shahzad, N.: A primal-dual method of partial inverses for composite inclusions. Optim. Lett. 8(8), 2271–2284 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  26. Ouorou, A.: Epsilon-proximal decomposition method. Math. Program. 99(1, Ser. A), 89–108 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  27. Combettes, P.L.: Iterative construction of the resolvent of a sum of maximal monotone operators. J. Convex Anal. 16(3–4), 727–748 (2009)

    MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  29. Briceño-Arias, L.M., Combettes, P.L.: A monotone + skew splitting model for composite monotone inclusions in duality. SIAM J. Optim. 21(4), 1230–1250 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  30. Eckstein, J., Svaiter, B.F.: A family of projective splitting methods for the sum of two maximal monotone operators. Math. Program. 111(1–2, Ser. B), 173–199 (2008)

    MATH  MathSciNet  Google Scholar 

  31. Eckstein, J., Svaiter, B.F.: General projective splitting methods for sums of maximal monotone operators. SIAM J. Control Optim. 48(2), 787–811 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  32. Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)

    Book  MATH  Google Scholar 

  33. Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I. Springer, New York (2003)

    MATH  Google Scholar 

  34. Briceño-Arias, Luis M.: Forward-Douglas-Rachford splitting and forward-partial inverse method for solving monotone inclusions. Optimization 64(5), 1239–1261 (2015)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgements

The work of S. C. L. was partially supported by CAPES Scholarship No. 201302186. The work of the first author was partially supported by CNPq Grants Nos. 406250/2013-8, 405214/2016-2 and 306317/2014-1. We are thankful to the two anonymous referees for their constructive suggestions which have improved the first version of this paper and for bringing to our attention the references [27] and [34].

Author information

Authors and Affiliations

  1. Departamento de Matemática, Universidade Federal de Santa Catarina, Florianópolis, 88040-900, Brazil

    Maicon Marques Alves & Samara Costa Lima

Authors
  1. Maicon Marques Alves
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Samara Costa Lima
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Maicon Marques Alves.

Additional information

Communicated by Marc Bonnet.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Alves, M.M., Lima, S.C. An Inexact Spingarn’s Partial Inverse Method with Applications to Operator Splitting and Composite Optimization. J Optim Theory Appl 175, 818–847 (2017). https://doi.org/10.1007/s10957-017-1188-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-017-1188-y

Keywords

Mathematics Subject Classification

Search

Navigation