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

Adaptive smoothing algorithms for nonsmooth composite convex minimization

Author

Listed:
  • Quoc Tran-Dinh

    (University of North Carolina at Chapel Hill (UNC))

Abstract

We propose an adaptive smoothing algorithm based on Nesterov’s smoothing technique in Nesterov (Math Prog 103(1):127–152, 2005) for solving “fully” nonsmooth composite convex optimization problems. Our method combines both Nesterov’s accelerated proximal gradient scheme and a new homotopy strategy for smoothness parameter. By an appropriate choice of smoothing functions, we develop a new algorithm that has the $$\mathcal {O}\left( \frac{1}{\varepsilon }\right) $$ O 1 ε -worst-case iteration-complexity while preserves the same complexity-per-iteration as in Nesterov’s method and allows one to automatically update the smoothness parameter at each iteration. Then, we customize our algorithm to solve four special cases that cover various applications. We also specify our algorithm to solve constrained convex optimization problems and show its convergence guarantee on a primal sequence of iterates. We demonstrate our algorithm through three numerical examples and compare it with other related algorithms.

Suggested Citation

  • Quoc Tran-Dinh, 2017. "Adaptive smoothing algorithms for nonsmooth composite convex minimization," Computational Optimization and Applications, Springer, vol. 66(3), pages 425-451, April.
    • Handle: RePEc:spr:coopap:v:66:y:2017:i:3:d:10.1007_s10589-016-9873-6
    DOI: 10.1007/s10589-016-9873-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-016-9873-6
    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-9873-6?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. NESTEROV, Yurii, 2007. "Smoothing technique and its applications in semidefinite optimization," LIDAM Reprints CORE 1951, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. A. Belloni & V. Chernozhukov & L. Wang, 2011. "Square-root lasso: pivotal recovery of sparse signals via conic programming," Biometrika, Biometrika Trust, vol. 98(4), pages 791-806.
    4. Patrick L. Combettes & Jean-Christophe Pesquet, 2011. "Proximal Splitting Methods in Signal Processing," Springer Optimization and Its Applications, in: Heinz H. Bauschke & Regina S. Burachik & Patrick L. Combettes & Veit Elser & D. Russell Luke & Henry (ed.), Fixed-Point Algorithms for Inverse Problems in Science and Engineering, chapter 0, pages 185-212, Springer.
    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. NESTEROV, Yu., 2005. "Excessive gap technique in nonsmooth convex minimization," LIDAM Reprints CORE 1818, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. 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).
    8. 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. Fan Wu & Wei Bian, 2023. "Smoothing Accelerated Proximal Gradient Method with Fast Convergence Rate for Nonsmooth Convex Optimization Beyond Differentiability," Journal of Optimization Theory and Applications, Springer, vol. 197(2), pages 539-572, May.

    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. 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.
    2. 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.
    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. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. David Degras, 2021. "Sparse group fused lasso for model segmentation: a hybrid approach," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 15(3), pages 625-671, September.
    12. Daskalakis, Constantinos & Deckelbaum, Alan & Kim, Anthony, 2015. "Near-optimal no-regret algorithms for zero-sum games," Games and Economic Behavior, Elsevier, vol. 92(C), pages 327-348.
    13. A. Chambolle & Ch. Dossal, 2015. "On the Convergence of the Iterates of the “Fast Iterative Shrinkage/Thresholding Algorithm”," Journal of Optimization Theory and Applications, Springer, vol. 166(3), pages 968-982, September.
    14. 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.
    15. 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.
    16. Yurii Nesterov, 2009. "Unconstrained Convex Minimization in Relative Scale," Mathematics of Operations Research, INFORMS, vol. 34(1), pages 180-193, February.
    17. Pi, J. & Wang, Honggang & Pardalos, Panos M., 2021. "A dual reformulation and solution framework for regularized convex clustering problems," European Journal of Operational Research, Elsevier, vol. 290(3), pages 844-856.
    18. Samid Hoda & Andrew Gilpin & Javier Peña & Tuomas Sandholm, 2010. "Smoothing Techniques for Computing Nash Equilibria of Sequential Games," Mathematics of Operations Research, INFORMS, vol. 35(2), pages 494-512, May.
    19. Xiangfeng Wang & Junping Zhang & Wenxing Zhang, 2020. "The distance between convex sets with Minkowski sum structure: application to collision detection," Computational Optimization and Applications, Springer, vol. 77(2), pages 465-490, November.
    20. DEVOLDER, Olivier & GLINEUR, François & NESTEROV, Yurii, 2013. "Intermediate gradient methods for smooth convex problems with inexact oracle," LIDAM Discussion Papers CORE 2013017, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).

    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:66:y:2017:i:3:d:10.1007_s10589-016-9873-6. 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.