More Web Proxy on the site http://driver.im/

research-article

An alternating structure-adapted Bregman proximal gradient descent algorithm for constrained nonconvex nonsmooth optimization problems and its inertial variant

Authors:

Xiangfeng Wang,

Deren HanAuthors Info & Claims

Journal of Global Optimization, Volume 87, Issue 1

Pages 277 - 300

https://doi.org/10.1007/s10898-023-01300-0

Published: 24 June 2023 Publication History

Abstract

We consider the nonconvex nonsmooth minimization problem over abstract sets, whose objective function is the sum of a proper lower semicontinuous biconvex function of the entire variables and two smooth nonconvex functions of their private variables. Fully exploiting the problem structure, we propose an alternating structure-adapted Bregman proximal (ASABP for short) gradient descent algorithm, where the geometry of the abstract set and the function is captured by employing generalized Bregman function. Under the assumption that the underlying function satisfies the Kurdyka–Łojasiewicz property, we prove that each bounded sequence generated by ASABP globally converges to a critical point. We then adopt an inertial strategy to accelerate the ASABP algorithm (IASABP), and utilize a backtracking line search scheme to find “suitable” step sizes, making the algorithm efficient and robust. The global O(1/K) sublinear convergence rate measured by Bregman distance is also established. Furthermore, to illustrate the potential of ASABP and its inertial version (IASABP), we apply them to solving the Poisson linear inverse problem, and the results are promising.

References

[1]

Ahookhosh M, Hien L, Gillis N, and Patrinos P A block inertial Bregman proximal algorithm for nonsmooth nonconvex problems with application to symmetric nonnegative matrix tri-factorization J. Optim. Theory Appl. 2021 190 234-258

[2]

Ahookhosh M, Hien L, Gillis N, and Patrinos P Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization Comput. Optim. Appl. 2021 79 681-775

[3]

Attouch H, Bolte J, Redont P, and Soubeyran A Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality Math. Oper. Res. 2010 35 438-457

[4]

Attouch H, Bolte J, and Svaiter B Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods Math. Program. 2013 137 91-129

[5]

Bauschke H, Bolte J, Chen J, Teboulle M, and Wang X On linear convergence of non-Euclidean gradient methods without strong convexity and Lipschitz gradient continuity J. Optim. Theory Appl. 2019 182 1068-1087

[6]

Bauschke H, Bolte J, and Teboulle M A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications Math. Oper. Res. 2016 42 330-348

[7]

Benning M, Betcke M, Ehrhardt M, and Schonlieb C Choose your path wisely: gradient descent in a Bregman distance framework SIAM J. Imaging Sci. 2021 14 814-843

[8]

Bertero M, Boccacci P, Desiderà G, and Vicidomini G Image deblurring with Poisson data: from cells to galaxies Inverse Probl 2009 25 123006

[9]

Bertsekas D Nonlinear programming J. Oper. Res. Soc. 1997 48 334-334

[10]

Bertsekas, D., Tsitsiklis, J.: Parallel and Distributed Computation: Numerical Methods. Athena Scientific (2015)

[11]

Bolte J, Sabach S, and Teboulle M Proximal alternating linearized minimization for nonconvex and nonsmooth problems Math. Program. 2014 146 459-494

[12]

Bolte J, Sabach S, Teboulle M, and Vaisbourd Y First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems SIAM J. Optim. 2018 28 2131-2151

[13]

Censor Y, Iusem A, and Zenios S An interior point method with Bregman functions for the variational inequality problem with paramonotone operators Math. Program. 1998 81 373-400

[14]

Gao X, Cai X, and Han D A Gauss-Seidel type inertial proximal alternating linearized minimization for a class of nonconvex optimization problems J. Global Optim. 2020 76 863-887

[15]

Han D A new hybrid generalized proximal point algorithm for variational inequality problems J. Global Optim. 2003 26 125-140

[16]

Hohage T and Werner F Inverse problems with Poisson data: statistical regularization theory, applications and algorithms Inverse Probl 2016 32 093001

[17]

Lu H, Freund R, and Nesterov Y Relatively smooth convex optimization by first-order methods, and applications SIAM J. Optim. 2018 28 333-354

[18]

Mukkamala M, Ochs P, Pock T, and Sabach S Convex-concave backtracking for inertial Bregman proximal gradient algorithms in nonconvex optimization SIAM J. Math. Data Sci. 2020 2 658-682

[19]

Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Springer (2003)

[20]

Nikolova M and Tan P Alternating structure-adapted proximal gradient descent for nonconvex nonsmooth block-regularized problems SIAM J. Optim. 2019 29 2053-2078

[21]

Pock T and Sabach S Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems SIAM J. Imaging Sci. 2016 9 1756-1787

[22]

Polyak B Some methods of speeding up the convergence of iteration methods USSR Comput. Maths. Math. Phys. 1964 4 1-17

[23]

Rockafellar R Convex Analysis 1970 Princeton Princeton University Press

[24]

Rockafellar, R., Wets, R.: Variational Analysis. Springer (2009)

[25]

Teboulle M A simplified view of first order methods for optimization Math. Program. 2018 170 67-96

[26]

Wu Z, Li C, Li M, and Lim A Inertial proximal gradient methods with bregman regularization for a class of nonconvex optimization problems J. Global Optim. 2021 79 617-644

[27]

Xu Y and Yin W A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion SIAM J. Imaging Sci. 2013 6 1758-1789

[28]

Zhang H, Dai Y, Guo L, and Peng W Proximal-like incremental aggregated gradient method with linear convergence under Bregman distance growth conditions Math. Oper. Res. 2021 46 61-81

[29]

Zhang X, Zhang X, Li X, Li Z, and Wang S Classify social image by integrating multi-modal content Multimed. Tools. Appl. 2018 77 7469-7485

Cited By

Takahashi STakeda A(2025)Approximate bregman proximal gradient algorithm for relatively smooth nonconvex optimizationComputational Optimization and Applications10.1007/s10589-024-00618-z90:1(227-256)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s10589-024-00618-z
Liu BZhao ZLi SWang K(2024)Semi-Adaptive Synergetic Two-Way Pseudoinverse Learning SystemPattern Recognition and Computer Vision10.1007/978-981-97-8505-6_9(121-134)Online publication date: 18-Oct-2024
https://dl.acm.org/doi/10.1007/978-981-97-8505-6_9

Recommendations

Alternating Structure-Adapted Proximal Gradient Descent for Nonconvex Nonsmooth Block-Regularized Problems

There has been increasing interest in constrained nonconvex regularized block optimization problems. We introduce an approach that enables complex application-dependent regularization terms to be used. The proposed alternating structure-adapted proximal ...
Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems
Abstract
This paper proposes an inertial Bregman proximal gradient method for minimizing the sum of two possibly nonconvex functions. This method includes two different inertial steps and adopts the Bregman regularization in solving the subproblem. Under ...
Two-step inertial Bregman alternating minimization algorithm for nonconvex and nonsmooth problems
Abstract
In this paper, we propose an algorithm combining Bregman alternating minimization algorithm with two-step inertial force for solving a minimization problem composed of two nonsmooth functions with a smooth one in the absence of convexity. For ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Global Optimization

Journal of Global Optimization Volume 87, Issue 1

Sep 2023

318 pages

ISSN:0925-5001

Issue’s Table of Contents

© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 24 June 2023

Accepted: 26 May 2023

Received: 08 October 2022

Author Tags

Author Tags

Qualifiers

Research-article

Funding Sources

Natural Science Foundation of China
National Natural Science Foundation of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Takahashi STakeda A(2025)Approximate bregman proximal gradient algorithm for relatively smooth nonconvex optimizationComputational Optimization and Applications10.1007/s10589-024-00618-z90:1(227-256)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s10589-024-00618-z
Liu BZhao ZLi SWang K(2024)Semi-Adaptive Synergetic Two-Way Pseudoinverse Learning SystemPattern Recognition and Computer Vision10.1007/978-981-97-8505-6_9(121-134)Online publication date: 18-Oct-2024
https://dl.acm.org/doi/10.1007/978-981-97-8505-6_9

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents