IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v90y2025i2d10.1007_s10589-024-00643-y.html
   My bibliography  Save this article

An inexact ADMM for separable nonconvex and nonsmooth optimization

Author

Listed:
  • Jianchao Bai

    (Research and Development Institute of Northwestern Polytechnical University in Shenzhen
    Northwestern Polytechnical University)

  • Miao Zhang

    (Louisiana State University)

  • Hongchao Zhang

    (Louisiana State University)

Abstract

An inexact alternating direction method of multiplies (I-ADMM) with an expansion linesearch step was developed for solving a family of separable minimization problems subject to linear constraints, where the objective function is the sum of a smooth but possibly nonconvex function and a possibly nonsmooth nonconvex function. Global convergence and linear convergence rate of the I-ADMM were established under proper conditions while inexact relative error criterion was used for solving the subproblems. In addition, a unified proximal gradient (UPG) method with momentum acceleration was proposed for solving the smooth but possibly nonconvex subproblem. This UPG method guarantees global convergence and will automatically reduce to an optimal accelerated gradient method when the smooth function in the objective is convex. Our numerical experiments on solving nonconvex quadratic programming problems and sparse optimization problems from statistical learning show that the proposed I-ADMM is very effective compared with other state-of-the-art algorithms in the literature.

Suggested Citation

  • Jianchao Bai & Miao Zhang & Hongchao Zhang, 2025. "An inexact ADMM for separable nonconvex and nonsmooth optimization," Computational Optimization and Applications, Springer, vol. 90(2), pages 445-479, March.
    • Handle: RePEc:spr:coopap:v:90:y:2025:i:2:d:10.1007_s10589-024-00643-y
    DOI: 10.1007/s10589-024-00643-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-024-00643-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10589-024-00643-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Zehui Jia & Xue Gao & Xingju Cai & Deren Han, 2021. "Local Linear Convergence of the Alternating Direction Method of Multipliers for Nonconvex Separable Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 188(1), pages 1-25, January.
    2. Radu Ioan Bot & Dang-Khoa Nguyen, 2020. "The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates," Mathematics of Operations Research, INFORMS, vol. 45(2), pages 682-712, May.
    3. William W. Hager & Hongchao Zhang, 2019. "Inexact alternating direction methods of multipliers for separable convex optimization," Computational Optimization and Applications, Springer, vol. 73(1), pages 201-235, May.
    4. Bingsheng He & Xiaoming Yuan & Wenxing Zhang, 2013. "A customized proximal point algorithm for convex minimization with linear constraints," Computational Optimization and Applications, Springer, vol. 56(3), pages 559-572, December.
    5. Xingju Cai & Deren Han & Xiaoming Yuan, 2017. "On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function," Computational Optimization and Applications, Springer, vol. 66(1), pages 39-73, January.
    6. Fan J. & Li R., 2001. "Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties," Journal of the American Statistical Association, American Statistical Association, vol. 96, pages 1348-1360, December.
    7. Maryam Yashtini, 2022. "Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization," Journal of Global Optimization, Springer, vol. 84(4), pages 913-939, December.
    8. Jianchao Bai & Jicheng Li & Fengmin Xu & Hongchao Zhang, 2018. "Generalized symmetric ADMM for separable convex optimization," Computational Optimization and Applications, Springer, vol. 70(1), pages 129-170, May.
    9. Paul Tseng & Sangwoon Yun, 2010. "A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training," Computational Optimization and Applications, Springer, vol. 47(2), pages 179-206, October.
    10. P. Tseng & S. Yun, 2009. "Block-Coordinate Gradient Descent Method for Linearly Constrained Nonsmooth Separable Optimization," Journal of Optimization Theory and Applications, Springer, vol. 140(3), pages 513-535, March.
    11. VIAL, Jean-Philippe, 1983. "Strong and weak convexity of sets and functions," LIDAM Reprints CORE 529, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. M. V. Solodov & B. F. Svaiter, 2000. "An Inexact Hybrid Generalized Proximal Point Algorithm and Some New Results on the Theory of Bregman Functions," Mathematics of Operations Research, INFORMS, vol. 25(2), pages 214-230, May.
    13. Deren Han & Xiaoming Yuan, 2012. "A Note on the Alternating Direction Method of Multipliers," Journal of Optimization Theory and Applications, Springer, vol. 155(1), pages 227-238, October.
    14. Zhongming Wu & Min Li & David Z. W. Wang & Deren Han, 2017. "A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(06), pages 1-27, December.
    15. William W. Hager & Hongchao Zhang, 2020. "Convergence rates for an inexact ADMM applied to separable convex optimization," Computational Optimization and Applications, Springer, vol. 77(3), pages 729-754, December.
    16. Amir Beck & Marc Teboulle, 2006. "A Linearly Convergent Dual-Based Gradient Projection Algorithm for Quadratically Constrained Convex Minimization," Mathematics of Operations Research, INFORMS, vol. 31(2), pages 398-417, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. William W. Hager & Hongchao Zhang, 2020. "Convergence rates for an inexact ADMM applied to separable convex optimization," Computational Optimization and Applications, Springer, vol. 77(3), pages 729-754, December.
    2. Jianchao Bai & William W. Hager & Hongchao Zhang, 2022. "An inexact accelerated stochastic ADMM for separable convex optimization," Computational Optimization and Applications, Springer, vol. 81(2), pages 479-518, March.
    3. Jianghua Yin & Chunming Tang & Jinbao Jian & Qiongxuan Huang, 2024. "A partial Bregman ADMM with a general relaxation factor for structured nonconvex and nonsmooth optimization," Journal of Global Optimization, Springer, vol. 89(4), pages 899-926, August.
    4. Yangyang Xu, 2019. "Asynchronous parallel primal–dual block coordinate update methods for affinely constrained convex programs," Computational Optimization and Applications, Springer, vol. 72(1), pages 87-113, January.
    5. Le Thi Khanh Hien & Dimitri Papadimitriou, 2024. "An inertial ADMM for a class of nonconvex composite optimization with nonlinear coupling constraints," Journal of Global Optimization, Springer, vol. 89(4), pages 927-948, August.
    6. Maryam Yashtini, 2022. "Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization," Journal of Global Optimization, Springer, vol. 84(4), pages 913-939, December.
    7. William W. Hager & Hongchao Zhang, 2019. "Inexact alternating direction methods of multipliers for separable convex optimization," Computational Optimization and Applications, Springer, vol. 73(1), pages 201-235, May.
    8. Wei Peng & Hui Zhang & Xiaoya Zhang, 2019. "Nonconvex Proximal Incremental Aggregated Gradient Method with Linear Convergence," Journal of Optimization Theory and Applications, Springer, vol. 183(1), pages 230-245, October.
    9. Yaning Jiang & Deren Han & Xingju Cai, 2022. "An efficient partial parallel method with scaling step size strategy for three-block convex optimization problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 96(3), pages 383-419, December.
    10. Le Thi Khanh Hien & Duy Nhat Phan & Nicolas Gillis, 2022. "Inertial alternating direction method of multipliers for non-convex non-smooth optimization," Computational Optimization and Applications, Springer, vol. 83(1), pages 247-285, September.
    11. Peixuan Li & Yuan Shen & Suhong Jiang & Zehua Liu & Caihua Chen, 2021. "Convergence study on strictly contractive Peaceman–Rachford splitting method for nonseparable convex minimization models with quadratic coupling terms," Computational Optimization and Applications, Springer, vol. 78(1), pages 87-124, January.
    12. Pei Wang & Shunjie Chen & Sijia Yang, 2022. "Recent Advances on Penalized Regression Models for Biological Data," Mathematics, MDPI, vol. 10(19), pages 1-24, October.
    13. Masoud Ahookhosh & Le Thi Khanh Hien & Nicolas Gillis & Panagiotis Patrinos, 2021. "A Block Inertial Bregman Proximal Algorithm for Nonsmooth Nonconvex Problems with Application to Symmetric Nonnegative Matrix Tri-Factorization," Journal of Optimization Theory and Applications, Springer, vol. 190(1), pages 234-258, July.
    14. Luoying Yang & Tong Tong Wu, 2023. "Model‐based clustering of high‐dimensional longitudinal data via regularization," Biometrics, The International Biometric Society, vol. 79(2), pages 761-774, June.
    15. Eyal Cohen & Nadav Hallak & Marc Teboulle, 2022. "A Dynamic Alternating Direction of Multipliers for Nonconvex Minimization with Nonlinear Functional Equality Constraints," Journal of Optimization Theory and Applications, Springer, vol. 193(1), pages 324-353, June.
    16. Min Li & Zhongming Wu, 2019. "Convergence Analysis of the Generalized Splitting Methods for a Class of Nonconvex Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 183(2), pages 535-565, November.
    17. Zhongming Wu & Min Li, 2019. "General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems," Computational Optimization and Applications, Springer, vol. 73(1), pages 129-158, May.
    18. Masoud Ahookhosh & Le Thi Khanh Hien & Nicolas Gillis & Panagiotis Patrinos, 2021. "Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization," Computational Optimization and Applications, Springer, vol. 79(3), pages 681-715, July.
    19. Nanshan, Muye & Zhang, Nan & Xun, Xiaolei & Cao, Jiguo, 2022. "Dynamical modeling for non-Gaussian data with high-dimensional sparse ordinary differential equations," Computational Statistics & Data Analysis, Elsevier, vol. 173(C).
    20. Min Tao & Jiang-Ning Li, 2023. "Error Bound and Isocost Imply Linear Convergence of DCA-Based Algorithms to D-Stationarity," Journal of Optimization Theory and Applications, Springer, vol. 197(1), pages 205-232, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:90:y:2025:i:2:d:10.1007_s10589-024-00643-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.