Circumcentering approximate reflections for solving the convex feasibility problem
Tóm tắt
The circumcentered-reflection method (CRM) has been applied for solving convex feasibility problems. CRM iterates by computing a circumcenter upon a composition of reflections with respect to convex sets. Since reflections are based on exact projections, their computation might be costly. In this regard, we introduce the circumcentered approximate-reflection method (CARM), whose reflections rely on outer-approximate projections. The appeal of CARM is that, in rather general situations, the approximate projections we employ are available under low computational cost. We derive convergence of CARM and linear convergence under an error bound condition. We also present successful theoretical and numerical comparisons of CARM to the original CRM, to the classical method of alternating projections (MAP), and to a correspondent outer-approximate version of MAP, referred to as MAAP. Along with our results and numerical experiments, we present a couple of illustrative examples.
Tài liệu tham khảo
Pierra, G.: Decomposition through formalization in a product space. Math. Program. 28(1), 96–115 (1984). https://doi.org/10.1007/BF02612715
Kaczmarz, S.: Angenäherte Auflösung von Systemen linearer Gleichungen. Bull. Int. Acad. Pol. Sci. Lett. Class. Sci. Math. Nat. A 35, 355–357 (1937)
Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38(3), 367–426 (1996). https://doi.org/10.1137/S0036144593251710
Douglas, J., Rachford, H.H. Jr.: On the numerical solution of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 82(2), 421–421 (1956). https://doi.org/10.1090/S0002-9947-1956-0084194-4
Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979). https://doi.org/10.1137/0716071
Cimmino, G.: Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. Ric. Sci. 9(II), 326–333 (1938)
Behling, R., Bello-Cruz, J.-Y., Santos, L.-R.: Circumcentering the Douglas–Rachford method. Numer. Algorithms 78(3), 759–776 (2018). https://doi.org/10.1007/s11075-017-0399-5
Behling, R., Bello-Cruz, J.-Y., Santos, L.-R.: On the linear convergence of the circumcentered-reflection method. Oper. Res. Lett. 46(2), 159–162 (2018). https://doi.org/10.1016/j.orl.2017.11.018
Arefidamghani, R., Behling, R., Bello-Cruz, J.-Y., Iusem, A.N., Santos, L.-R.: The circumcentered-reflection method achieves better rates than alternating projections. Comput. Optim. Appl. 79(2), 507–530 (2021). https://doi.org/10.1007/s10589-021-00275-6
Bauschke, H.H., Ouyang, H., Wang, X.: On circumcenters of finite sets in Hilbert spaces. Linear Nonlinear Anal. 4(2), 271–295 (2018)
Bauschke, H.H., Ouyang, H., Wang, X.: Best approximation mappings in Hilbert spaces. Math. Program. (2021). https://doi.org/10.1007/s10107-021-01718-y
Bauschke, H.H., Ouyang, H., Wang, X.: Circumcentered methods induced by isometries. Vietnam J. Math. 48, 471–508 (2020). https://doi.org/10.1007/s10013-020-00417-z
Bauschke, H.H., Ouyang, H., Wang, X.: On circumcenter mappings induced by nonexpansive operators. Pure Appl. Funct. Anal. 6(2), 257–288 (2021)
Bauschke, H.H., Ouyang, H., Wang, X.: On the linear convergence of circumcentered isometry methods. Numer. Algorithms 87, 263–297 (2021). https://doi.org/10.1007/s11075-020-00966-x
Behling, R., Bello-Cruz, Y., Santos, L.-R.: On the circumcentered-reflection method for the convex feasibility problem. Numer. Algorithms 86, 1475–1494 (2021). https://doi.org/10.1007/s11075-020-00941-6
Dizon, N., Hogan, J., Lindstrom, S.B.: Circumcentering Reflection Methods for Nonconvex Feasibility Problems (2019). 1910.04384
Dizon, N., Hogan, J., Lindstrom, S.B.: Centering Projection Methods for Wavelet Feasibility Problems (2020). 2005.05687
Ouyang, H.: Finite convergence of locally proper circumcentered methods (2020). 2011.13512 [math]
Fukushima, M.: An outer approximation algorithm for solving general convex programs. Oper. Res. 31(1), 101–113 (1983). https://doi.org/10.1287/opre.31.1.101
Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables, 1st edn. Classics in Applied Mathematics. SIAM, Philadelphia (2000)
Cegielski, A.: Iterative Methods for Fixed Point Problems in Hilbert Spaces. Lecture Notes in Mathematics, vol. 2057. Springer, New York (2012)
Cegielski, A.: Generalized relaxations of nonexpansive operators and convex feasibility problems. In: Leizarowitz, A., Mordukhovich, B.S., Shafrir, I., Zaslavski, A.J. (eds.) Nonlinear Analysis and Optimization: A Conference in Celebration of Alex Ioffe’s 70th and Simeon Reich’s 60th Birthdays, Haïfa, Israël, June 18–24, 2008. Contemporary Mathematics, pp. 111–123. Am. Math. Soc., Providence (2010)
Cheney, W., Goldstein, A.A.: Proximity maps for convex sets. Proc. Am. Math. Soc. 10(3), 448–450 (1959). https://doi.org/10.2307/2032864
Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd edn. CMS Books in Mathematics. Springer, Berlin (2017). https://doi.org/10.1007/978-3-319-48311-5
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis, 2nd edn. Grundlehren Der Mathematischen Wissenschaften, vol. 317. Springer, Berlin (2004)
Robinson, S.M.: Generalized equations and their solutions, part II: applications to nonlinear programming. In: Guignard, M. (ed.) Optimality and Stability in Mathematical Programming. Mathematical Programming Studies, pp. 200–221. Springer, Berlin (1982). https://doi.org/10.1007/BFb0120989
Hoffman, A.J.: On approximate solutions of systems of linear inequalities. J. Res. Natl. Bur. Stand. 49(4), 263–265 (1952)
Behling, R., Iusem, A.: The effect of calmness on the solution set of systems of nonlinear equations. Math. Program. 137(1), 155–165 (2013). https://doi.org/10.1007/s10107-011-0486-7
Kanzow, C., Yamashita, N., Fukushima, M.: Levenberg–Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints. J. Comput. Appl. Math. 172(2), 375–397 (2004). https://doi.org/10.1016/j.cam.2004.02.013
Bauschke, H.H., Borwein, J.M.: On the convergence of von Neumann’s alternating projection algorithm for two sets. Set-Valued Anal. 1(2), 185–212 (1993). https://doi.org/10.1007/BF01027691
Bauschke, H.H.: Projection Algorithms and Monotone Operators. PhD thesis, Simon Fraser University, Burnaby (August 1996)
Drusvyatskiy, D., Ioffe, A.D., Lewis, A.S.: Transversality and alternating projections for nonconvex sets. Found. Comput. Math. 15(6), 1637–1651 (2015). https://doi.org/10.1007/s10208-015-9279-3
Kruger, A.Y.: About intrinsic transversality of pairs of sets. Set-Valued Var. Anal. 26(1), 111–142 (2018). https://doi.org/10.1007/s11228-017-0446-3
Lin, A., Han, S.-P.: A class of methods for projection on the intersection of several ellipsoids. SIAM J. Optim. 15(1), 129–138 (2004). https://doi.org/10.1137/S1052623403422297
Jia, Z., Cai, X., Han, D.: Comparison of several fast algorithms for projection onto an ellipsoid. J. Comput. Appl. Math. 319, 320–337 (2017). https://doi.org/10.1016/j.cam.2017.01.008
Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Rev. 59(1), 65–98 (2017). https://doi.org/10.1137/141000671
Birgin, E.G., Martínez, J.M.: Practical Augmented Lagrangian Methods for Constrained Optimization, 1st edn. SIAM, Philadelphia (2014). https://doi.org/10.1137/1.9781611973365
Siqueira, A.S., Orban, D.: NLPModels.Jl. Zenodo (2019). https://doi.org/10.5281/ZENODO.2558627
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002). https://doi.org/10.1007/s101070100263