Non-Convex Split Feasibility Problems: Models, Algorithms and Theory
Open Journal of Mathematical Optimization, Volume 1 (2020) , article no. 1, 15 p.

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: https://doi.org/10.5802/ojmo.1
Keywords: Split feasibility problems, non-convex minimization, convergence analysis, constrained minimization, CQ algorithm
@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},
     publisher = {Universit\'e de Montpellier},
     volume = {1},
     year = {2020},
     doi = {10.5802/ojmo.1},
     language = {en},
     url = {ojmo.centre-mersenne.org/item/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/item/OJMO_2020__1__A1_0/

[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 2421270 | Zbl 1165.90018

[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 1214.65036

[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 | Article | MR 3010421 | Zbl 1260.49048

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

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

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

[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 1211.90290

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

[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 | Article | Zbl 1129.26012

[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 | Article | Zbl 1202.26026

[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 | Article | MR 3232623 | Zbl 1297.90125

[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 1440.90072

[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 3832977 | Zbl 1402.90118

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

[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 | Article | MR 2044608 | Zbl 1051.65067

[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 | Article

[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 | Article | MR 1309222 | Zbl 0828.65065

[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 3184327 | Zbl 1291.90171

[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 | Article | MR 3804024 | Zbl 1423.90179

[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 3928117 | Zbl 1438.65124

[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 0368.65053

[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 | Article | MR 2914282 | Zbl 1245.90084

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

[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 | Article | MR 3960813 | Zbl 1415.90121

[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 0234.57007

[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 3884565 | Zbl 1434.49012

[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 2377859 | Zbl 1171.90009

[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 | Article | MR 3572363 | Zbl 1358.90109

[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 | Article | MR 3764824 | Zbl 06865936

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

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

[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 3904099

[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 | Article | MR 3166972 | Zbl 1291.90176

[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 | Article | MR 2802990 | Zbl 1308.47079

[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 | Article | MR 3877606 | Zbl 1416.90048