Non-Convex Split Feasibility Problems: Models, Algorithms and Theory

Aviv Gibali; Shoham Sabach; Sergey Voldman

doi:10.5802/ojmo.1

Aviv Gibali ^1,²; Shoham Sabach ³; Sergey Voldman ³

¹ Department of Mathematics, ORT Braude College, Karmiel 2161002, Israel
² The Center for Mathematics and Scientific Computation, University of Haifa, Mt. Carmel, Haifa 3498838, Israel
³ Faculty of Industrial Engineering and Management, The Technion, Haifa, 3200003, Israel

Open Journal of Mathematical Optimization, Volume 1 (2020), article no. 1, 15 p.

Abstract

In this paper, we propose a catalog of iterative methods for solving the Split Feasibility Problem in the non-convex setting. We study four different optimization formulations of the problem, where each model has advantages in different settings of the problem. For each model, we study relevant iterative algorithms, some of which are well-known in this area and some are new. All the studied methods, including the well-known CQ Algorithm, are proven to have global convergence guarantees in the non-convex setting under mild conditions on the problem’s data.

Received: 2020-02-06
Revised: 2020-06-25
Accepted: 2020-10-07
Published online: 2020-10-22

DOI: 10.5802/ojmo.1

Keywords: Split feasibility problems, non-convex minimization, convergence analysis, constrained minimization, CQ algorithm

Author's affiliations:

Aviv Gibali ^{1, 2}; Shoham Sabach ³; Sergey Voldman ³

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{OJMO_2020__1__A1_0,
     author = {Aviv Gibali and Shoham Sabach and Sergey Voldman},
     title = {Non-Convex {Split} {Feasibility} {Problems:} {Models,} {Algorithms} and {Theory}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {1},
     pages = {1--15},
     publisher = {Universit\'e de Montpellier},
     volume = {1},
     year = {2020},
     doi = {10.5802/ojmo.1},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.1/}
}

TY  - JOUR
AU  - Aviv Gibali
AU  - Shoham Sabach
AU  - Sergey Voldman
TI  - Non-Convex Split Feasibility Problems: Models, Algorithms and Theory
JO  - Open Journal of Mathematical Optimization
PY  - 2020
SP  - 1
EP  - 15
VL  - 1
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.1/
DO  - 10.5802/ojmo.1
LA  - en
ID  - OJMO_2020__1__A1_0
ER  -

%0 Journal Article
%A Aviv Gibali
%A Shoham Sabach
%A Sergey Voldman
%T Non-Convex Split Feasibility Problems: Models, Algorithms and Theory
%J Open Journal of Mathematical Optimization
%D 2020
%P 1-15
%V 1
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.1/
%R 10.5802/ojmo.1
%G en
%F OJMO_2020__1__A1_0

Aviv Gibali; Shoham Sabach; Sergey Voldman. Non-Convex Split Feasibility Problems: Models, Algorithms and Theory. Open Journal of Mathematical Optimization, Volume 1 (2020), article  no. 1, 15 p. doi : 10.5802/ojmo.1. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.1/

References
Cited by

[1] H. Attouch; J. Bolte On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., Volume 116 (2009) no. 1-2, pp. 5-16 | MR | Zbl

[2] H. Attouch; J. Bolte; P. Redont; A. Soubeyran Proximal alternating minimization and projection methods for non-convex problems: an approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., Volume 35 (2010) no. 2, pp. 438-457 | Zbl

[3] H. Attouch; J. Bolte; B. F. Svaiter Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., Volume 137 (2013) no. 1-2, pp. 91-129 | DOI | MR | Zbl

[4] H. H. Bauschke; P. L. Combettes Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 408, Springer, 2011 | Zbl

[5] M. S. Bazaraa; H. D. Sherali; C. M. Shetty Nonlinear Programming: Theory and Algorithms, Wiley, 2013 | Zbl

[6] A. Beck First-Order Methods in Optimization, Society for Industrial and Applied Mathematics, 2017 | DOI | Zbl

[7] A. Beck; M. Teboulle Gradient-based algorithms with applications to signal-recovery problems, Convex optimization in signal processing and communications (2010), pp. 42-88 | Zbl

[8] D. P. Bertsekas Nonlinear Programming: Theory and Algorithms, Athena Scientific, Belmont, MA, USA, 1995 | Zbl

[9] J. Bolte; A. Daniilidis; A. Lewis The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optimiz., Volume 17 (2006) no. 4, pp. 1205-1223 | DOI | Zbl

[10] J. Bolte; A. Daniilidis; O. Ley; L. Mazet Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity, T. Am. Math. Soc., Volume 362 (2010) no. 6, pp. 3319-3363 | DOI | Zbl

[11] J. Bolte; S. Sabach; M. Teboulle Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., Volume 146 (2014) no. 1-2, pp. 459-494 | DOI | MR | Zbl

[12] J. Bolte; S. Sabach; M. Teboulle Non-convex Lagrangian-based optimization: monitoring schemes and global convergence, Math. Oper. Res., Volume 43 (2018) no. 4, pp. 1210-1232 | Zbl

[13] J. Bolte; S. Sabach; M. Teboulle; Y. Vaisbourd First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems, SIAM J. Optimiz., Volume 28 (2018) no. 3, pp. 2131-2151 | MR | Zbl

[14] C. Byrne Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Probl., Volume 18 (2002) no. 2, pp. 441-453 | DOI | MR | Zbl

[15] C. Byrne A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Probl., Volume 20 (2004) no. 1, pp. 103-120 | DOI | MR | Zbl

[16] Y. Censor; T. Bortfeld; B. Martin; A. Trofimov A unified approach for inversion problems in intensity-modulated radiation therapy, Phys. Med. Biol., Volume 51 (2006) no. 10, pp. 2353-2365 | DOI

[17] Y. Censor; T. Elfving A multiprojection algorithm using Bregman projections in a product space, Numer. Algorithms, Volume 8 (1994) no. 2, pp. 221-239 | DOI | MR | Zbl

[18] C. Chen; T. K. Pong; L. Tan A difference-of-convex approach for split feasibility with applications to matrix factorizations and outlier detection (2019) (https://arxiv.org/abs/1903.01101)

[19] D. Gabay; B. Mercier A multiprojection algorithm using Bregman projections in a product space, Comput. and Math. Appl., Volume 2 (1976), pp. 221-239

[20] A. Gibali; K. H. Küfer; P. Süss Successive linear programing approach for solving the nonlinear split feasibility problem, J. Nonlinear Convex A., Volume 15 (2014) no. 2, pp. 345-353 | MR | Zbl

[21] A. Gibali; L.-W. Liu; Y.-C. Tang Note on the modified relaxation CQ algorithm for the split feasibility problem, Optim. Lett., Volume 12 (2018) no. 4, pp. 817-830 | DOI | MR | Zbl

[22] A. Gibali; D. T. Mai; N. T. Vinh A new relaxed CQ algorithm for solving split feasibility problems in Hilbert spaces and its applications, J. Ind. Manag. Optim., Volume 15 (2019) no. 2, pp. 963-984 | MR | Zbl

[23] R. Glowinski; A. Marroco 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: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, Volume 9 (1975) no. R2, pp. 41-76 | Zbl

[24] B. He; X. Yuan On the $O (1 / n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Numer. Anal., Volume 50 (2012) no. 2, pp. 700-709 | DOI | MR | Zbl

[25] K. Kurdyka On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier, Volume 48 (1998) no. 3, pp. 769-783 | DOI | Numdam | MR | Zbl

[26] T. Liu; T. K. Pong; A. Takeda A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems, Math. Program., Volume 176 (2019) no. 1-2, pp. 339-367 | DOI | MR | Zbl

[27] S. Łojasiewicz Une propriété topologique des sous-ensembles analytiques réels, Les équations aux dérivées partielles, Volume 117 (1963), pp. 87-89 | Zbl

[28] D. R. Luke; N. H. Thao; M. K. Tam Quantitative convergence analysis of iterated expansive, set-valued mappings, Math. Oper. Res., Volume 43 (2018) no. 4, pp. 1143-1176 | MR | Zbl

[29] E. Masad; S. Reich A note on the multiple-set split convex feasibility problem in Hilbert space, J. Nonlinear Convex A., Volume 8 (2007) no. 3, pp. 367-371 | MR | Zbl

[30] T. Pock; S. Sabach Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems, SIAM J. Imaging Sci., Volume 9 (2016) no. 4, pp. 1756-1787 | DOI | MR | Zbl

[31] M. Raeisi; G. Z. Eskandani; M. Eslamian A general algorithm for multiple-sets split feasibility problem involving resolvents and Bregman mappings, Optimization, Volume 67 (2018) no. 2, pp. 309-327 | DOI | MR | Zbl

[32] R. T. Rockafellar; Roger J-B. Wets Variational analysis, 317, Springer, 2009 | Zbl

[33] S. Sabach; M. Teboulle Lagrangian methods for composite optimization, Handb. Numer. Anal., Volume 20 (2019) | MR | Zbl

[34] S. Sabach; M. Teboulle; S. Voldman A smoothing alternating minimization-based algorithm for clustering with sum-min of Euclidean norms, Pure Appl. Funct. Anal., Volume 3 (2018), pp. 653-679 | MR

[35] R. Shefi; M. Teboulle Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM J. Optimiz., Volume 24 (2014) no. 1, pp. 269-297 | DOI | MR | Zbl

[36] F. Wang; H.-K. Xu Cyclic algorithms for split feasibility problems in Hilbert spaces, Nonlinear Anal.-Theor., Volume 74 (2011) no. 12, pp. 4105-4111 | DOI | MR | Zbl

[37] J. Xu; E. C. Chi; M. Yang; K. Lange A majorization–minimization algorithm for split feasibility problems, Comput. Optim. Appl., Volume 71 (2018) no. 3, pp. 795-828 | DOI | MR | Zbl

Cited by Sources: