Skip to main content

Advertisement

Springer Nature Link
Log in

Approximate Customized Proximal Point Algorithms for Separable Convex Optimization

  • Published:
Journal of the Operations Research Society of China Aims and scope Submit manuscript

Abstract

Proximal point algorithm (PPA) is a useful algorithm framework and has good convergence properties. The main difficulty is that the subproblems usually only have iterative solutions. In this paper, we propose an inexact customized PPA framework for two-block separable convex optimization problem with linear constraint. We design two types of inexact error criteria for the subproblems. The first one is absolutely summable error criterion, under which both subproblems can be solved inexactly. When one of the two subproblems is easily solved, we propose another novel error criterion which is easier to implement, namely relative error criterion. The relative error criterion only involves one parameter, which is more implementable. We establish the global convergence and sub-linear convergence rate in ergodic sense for the proposed algorithms. The numerical experiments on LASSO regression problems and total variation-based image denoising problem illustrate that our new algorithms outperform the corresponding exact algorithms.

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

Fig. 1

Similar content being viewed by others

References

  1. Tibshirani, R.: Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B 58, 267–288 (1996)

    MathSciNet  MATH  Google Scholar 

  2. Chambolle, A., Lions, P.L.: Image recovery via total variation minimization and related problems. Numer. Math. 76, 167–188 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  3. Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithm. Phys. D. 60, 259–268 (1992). (Experimental Mathematics: Computational Issues in Nonlinear Science (Los Alamos, NM, 1991))

  4. Cai, J.F., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 1956–1982 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chen, C.H., He, B.S., Yuan, X.M.: Matrix completion via an alternating direction method. IMA J. Numer. Anal. 32, 227–245 (2012)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

  8. 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. ESAIM Math. Model. Numer. Anal. 9, 41–76 (1975)

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  11. Cai, X., Gu, G., He, B., Yuan, X.: A proximal point algorithm revisit on the alternating direction method of multipliers. Sci. China Math. 56, 2179–2186 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bai, J., Zhang, H., Li, J.: A parameterized proximal point algorithm for separable convex optimization. Optim. Lett. 12, 1589–1608 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gu, G., He, B., Yuan, X.: Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems: a unified approach. Comput. Optim. Appl. 59, 135–161 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  14. He, B., Yuan, X., Zhang, W.: A customized proximal point algorithm for convex minimization with linear constraints. Comput. Optim. Appl. 56, 559–572 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Ma, F., Ni, M.: A class of customized proximal point algorithms for linearly constrained convex optimization. Comput. Appl. Math. 37, 896–911 (2018)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  17. 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, 323–345 (1999)

    Article  MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  19. Rasch, J., Chambolle, A.: Inexact first-order primal-dual algorithms. Comput. Optim. Appl. 76, 381–430 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  20. Alves, M.M., Eckstein, J., Geremia, M., Melo, J.G.: Relative-error inertial-relaxed inexact versions of Douglas-Rachford and ADMM splitting algorithms. Comput. Optim. Appl. 75, 389–422 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  21. Eckstein, J., Yao, W.: Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM. Math. Program. 170, 417–444 (2018)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  23. Eckstein, J., Yao, W.: Approximate ADMM algorithms derived from Lagrangian splitting. Comput. Optim. Appl. 68, 363–405 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  24. Xie, J.: On inexact ADMMs with relative error criteria. Comput. Optim. Appl. 71, 743–765 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  25. Xie, J., Liao, A., Yang, X.: An inexact alternating direction method of multipliers with relative error criteria. Optim. Lett. 11, 583–596 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  26. Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  27. Cai, X., Han, D.: \(O(1/t)\) complexity analysis of the generalized alternating direction method of multipliers. Sci. China Math. 62, 795–808 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  28. Nocedal, J., Wright, S.J.: Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006)

    Google Scholar 

  29. 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 (2010)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Nanjing Normal University, Nanjing, 210023, Jiangsu, China

    Hong-Mei Chen, Xing-Ju Cai & Ling-Ling Xu

  2. Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing, 210023, Jiangsu, China

    Hong-Mei Chen, Xing-Ju Cai & Ling-Ling Xu

Authors
  1. Hong-Mei Chen
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Xing-Ju Cai
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Ling-Ling Xu
    View author publications

    You can also search for this author inPubMed Google Scholar

Contributions

Xing-Ju Cai and Ling-Ling Xu contributed to the conception of the study. Hong-Mei Chen performed the experiment and wrote the manuscript. Ling-Ling Xu helped perform the analysis with constructive discussions.

Corresponding author

Correspondence to Ling-Ling Xu.

Ethics declarations

Conflicts of interest

The authors declare that they have no conflict of interest.

Additional information

The work is supported by the National Natural Science Foundation of China (Nos. 11971238 and 11871279)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, HM., Cai, XJ. & Xu, LL. Approximate Customized Proximal Point Algorithms for Separable Convex Optimization. J. Oper. Res. Soc. China 11, 383–408 (2023). https://doi.org/10.1007/s40305-022-00412-w

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40305-022-00412-w

Keywords

Mathematics Subject Classification