IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v64y2016i3d10.1007_s10589-016-9826-0.html
   My bibliography  Save this article

A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints

Author

Listed:
  • Jueyou Li

    (Chongqing Normal University
    University of Sydney)

  • Guo Chen

    (University of Sydney)

  • Zhaoyang Dong

    (University of Sydney)

  • Zhiyou Wu

    (Chongqing Normal University)

Abstract

In this paper we consider a class of separable convex optimization problems with linear coupled constraints arising in many applications. Based on Nesterov’s smoothing technique and a fast gradient scheme, we present a fast dual proximal-gradient method to solve this class of problems. Under some conditions, we then give the convergence analysis of the proposed method and show that the computational complexity bound of the method for achieving an $$\varepsilon $$ ε -optimal feasible solution is $$\mathscr {O}(1/\varepsilon )$$ O ( 1 / ε ) . To further accelerate the proposed algorithm, we utilize a restart technique by successively decreasing the smoothing parameter. The advantage of our algorithms allows us to obtain the dual and primal approximate solutions simultaneously, which is fast and can be implemented in a parallel fashion. Several numerical experiments are presented to illustrate the effectiveness of the proposed algorithms. The numerical results validate the efficiency of our methods.

Suggested Citation

  • Jueyou Li & Guo Chen & Zhaoyang Dong & Zhiyou Wu, 2016. "A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints," Computational Optimization and Applications, Springer, vol. 64(3), pages 671-697, July.
    • Handle: RePEc:spr:coopap:v:64:y:2016:i:3:d:10.1007_s10589-016-9826-0
    DOI: 10.1007/s10589-016-9826-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-016-9826-0
    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-016-9826-0?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. Quoc Tran Dinh & Carlo Savorgnan & Moritz Diehl, 2013. "Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems," Computational Optimization and Applications, Springer, vol. 55(1), pages 75-111, May.
    2. Xingju Cai & Guoyong Gu & Bingsheng He, 2014. "On the O(1/t) convergence rate of the projection and contraction methods for variational inequalities with Lipschitz continuous monotone operators," Computational Optimization and Applications, Springer, vol. 57(2), pages 339-363, March.
    3. Niao He & Anatoli Juditsky & Arkadi Nemirovski, 2015. "Mirror Prox algorithm for multi-term composite minimization and semi-separable problems," Computational Optimization and Applications, Springer, vol. 61(2), pages 275-319, June.
    4. I. Necoara & J. A. K. Suykens, 2009. "Interior-Point Lagrangian Decomposition Method for Separable Convex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 143(3), pages 567-588, December.
    5. DEVOLDER, Olivier & GLINEUR, François & NESTEROV, Yurii, 2012. "Double smoothing technique for large-scale linearly constrained convex optimization," LIDAM Reprints CORE 2423, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. NESTEROV, Yu., 2005. "Smooth minimization of non-smooth functions," LIDAM Reprints CORE 1819, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.
    2. E. M. Bednarczuk & A. Jezierska & K. E. Rutkowski, 2018. "Proximal primal–dual best approximation algorithm with memory," Computational Optimization and Applications, Springer, vol. 71(3), pages 767-794, December.

    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. Quoc Tran-Dinh, 2017. "Adaptive smoothing algorithms for nonsmooth composite convex minimization," Computational Optimization and Applications, Springer, vol. 66(3), pages 425-451, April.
    2. Jueyou Li & Zhiyou Wu & Changzhi Wu & Qiang Long & Xiangyu Wang, 2016. "An Inexact Dual Fast Gradient-Projection Method for Separable Convex Optimization with Linear Coupled Constraints," Journal of Optimization Theory and Applications, Springer, vol. 168(1), pages 153-171, January.
    3. TAYLOR, Adrien B. & HENDRICKX, Julien M. & François GLINEUR, 2016. "Exact worst-case performance of first-order methods for composite convex optimization," LIDAM Discussion Papers CORE 2016052, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Nima Rabiei & Jose Muñoz, 2015. "AAR-based decomposition algorithm for non-linear convex optimisation," Computational Optimization and Applications, Springer, vol. 62(3), pages 761-786, December.
    5. Radu Boţ & Christopher Hendrich, 2013. "A double smoothing technique for solving unconstrained nondifferentiable convex optimization problems," Computational Optimization and Applications, Springer, vol. 54(2), pages 239-262, March.
    6. Frank E. Curtis & Arvind U. Raghunathan, 2017. "Solving nearly-separable quadratic optimization problems as nonsmooth equations," Computational Optimization and Applications, Springer, vol. 67(2), pages 317-360, June.
    7. Masoud Ahookhosh & Arnold Neumaier, 2018. "Solving structured nonsmooth convex optimization with complexity $$\mathcal {O}(\varepsilon ^{-1/2})$$ O ( ε - 1 / 2 )," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(1), pages 110-145, April.
    8. Radu Boţ & Christopher Hendrich, 2015. "A variable smoothing algorithm for solving convex optimization problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(1), pages 124-150, April.
    9. Dirk Lorenz & Marc Pfetsch & Andreas Tillmann, 2014. "An infeasible-point subgradient method using adaptive approximate projections," Computational Optimization and Applications, Springer, vol. 57(2), pages 271-306, March.
    10. Guoyin Li & Alfred Ma & Ting Pong, 2014. "Robust least square semidefinite programming with applications," Computational Optimization and Applications, Springer, vol. 58(2), pages 347-379, June.
    11. Masaru Ito, 2016. "New results on subgradient methods for strongly convex optimization problems with a unified analysis," Computational Optimization and Applications, Springer, vol. 65(1), pages 127-172, September.
    12. Zhong-bao Wang & Xue Chen & Jiang Yi & Zhang-you Chen, 2022. "Inertial projection and contraction algorithms with larger step sizes for solving quasimonotone variational inequalities," Journal of Global Optimization, Springer, vol. 82(3), pages 499-522, March.
    13. Dimitris Bertsimas & Nishanth Mundru, 2021. "Sparse Convex Regression," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 262-279, January.
    14. Amir Beck & Shoham Sabach, 2015. "Weiszfeld’s Method: Old and New Results," Journal of Optimization Theory and Applications, Springer, vol. 164(1), pages 1-40, January.
    15. Donghwan Kim & Jeffrey A. Fessler, 2021. "Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions," Journal of Optimization Theory and Applications, Springer, vol. 188(1), pages 192-219, January.
    16. Dang Hieu & Pham Ky Anh & Nguyen Hai Ha, 2021. "Regularization Proximal Method for Monotone Variational Inclusions," Networks and Spatial Economics, Springer, vol. 21(4), pages 905-932, December.
    17. Nguyen Thai An & Nguyen Mau Nam & Xiaolong Qin, 2020. "Solving k-center problems involving sets based on optimization techniques," Journal of Global Optimization, Springer, vol. 76(1), pages 189-209, January.
    18. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2020. "Essentials of numerical nonsmooth optimization," 4OR, Springer, vol. 18(1), pages 1-47, March.
    19. Masoud Ahookhosh, 2019. "Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 89(3), pages 319-353, June.
    20. Alexandre Belloni & Victor Chernozhukov & Lie Wang, 2013. "Pivotal estimation via square-root lasso in nonparametric regression," CeMMAP working papers CWP62/13, Centre for Microdata Methods and Practice, Institute for Fiscal Studies.

    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:64:y:2016:i:3:d:10.1007_s10589-016-9826-0. 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.