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

Gibali, Aviv; Sabach, Shoham; Voldman, Sergey

Open Journal of Mathematical Optimization, Tome 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.

Mots clés : Split feasibility problems, non-convex minimization, convergence analysis, constrained minimization, CQ algorithm

[1] Attouch, H.; Bolte, J. 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] Attouch, H.; Bolte, J.; Redont, P.; Soubeyran, A. 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] Attouch, H.; Bolte, J.; Svaiter, B. F. 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] Bauschke, H. H.; Combettes, P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 408, Springer, 2011 | Zbl

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

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

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

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

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

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

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

[13] Bolte, J.; Sabach, S.; Teboulle, M.; Vaisbourd, Y. 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] Byrne, C. 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] Byrne, C. 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] Censor, Y.; Bortfeld, T.; Martin, B.; Trofimov, A. A unified approach for inversion problems in intensity-modulated radiation therapy, Phys. Med. Biol., Volume 51 (2006) no. 10, pp. 2353-2365 | DOI

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

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

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

[20] Gibali, A.; Küfer, K. H.; Süss, P. 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] Gibali, A.; Liu, L.-W.; Tang, Y.-C. 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] Gibali, A.; Mai, D. T.; Vinh, N. T. 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] Glowinski, R.; Marroco, A. 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] He, B.; Yuan, X. 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] Kurdyka, K. 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] Liu, T.; Pong, T. K.; Takeda, A. 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] Łojasiewicz, S. 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] Luke, D. R.; Thao, N. H.; Tam, M. K. Quantitative convergence analysis of iterated expansive, set-valued mappings, Math. Oper. Res., Volume 43 (2018) no. 4, pp. 1143-1176 | MR | Zbl

[29] Masad, E.; Reich, S. 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] Pock, T.; Sabach, S. 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] Raeisi, M.; Eskandani, G. Z.; Eslamian, M. 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] Rockafellar, R. T.; Wets, Roger J-B. Variational analysis, 317, Springer, 2009

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

[34] Sabach, S.; Teboulle, M.; Voldman, S. 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] Shefi, R.; Teboulle, M. 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] Wang, F.; Xu, H.-K. Cyclic algorithms for split feasibility problems in Hilbert spaces, Nonlinear Anal.-Theor., Volume 74 (2011) no. 12, pp. 4105-4111 | DOI | MR | Zbl

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