An acceleration scheme for Dykstra's algorithm

详细信息    查看全文

• 作者：Williams López ; Marcos Raydan
• 关键词：Dykstra’s algorithm ; Alternating projection methods ; Orthogonal projections ; Acceleration schemes
• 刊名：Computational Optimization and Applications
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：63
• 期：1
• 页码：29-44
• 全文大小：767 KB
• 参考文献：1.Abdalla, M.O., Grigoriadis, K.M., Zimmerman, D.C.: Enhanced structural damage detection using alternating projection methods. AIAA J. 36, 1305–1311 (1998)CrossRef
  2.Appleby, G., Smolarski, D.: A linear acceleration row action method for projecting onto subspaces. Electron. Trans. Numer. Anal. 20, 253–275 (2005)MATH MathSciNet
  3.Bauschke, H.H., Borwein, J.M.: Dykstra’s alternating projection algorithm for two sets. J. Approx. Theory 79, 418–443 (1994)MATH MathSciNet CrossRef
  4.Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367–426 (1996)MATH MathSciNet CrossRef
  5.Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)MATH CrossRef
  6.Bauschke, H.H., Combettes, P.L., Kruk, S.G.: Extrapolation algorithm for affine-convex feasibility problems. Numer. Algorithms 41, 239–274 (2006)MATH MathSciNet CrossRef
  7.Bauschke, H.H., Deutsch, F., Hundal, H., Park, S.H.: Accelerating the convergence of the method of alternating projections. Trans. Am. Math. Soc. 355, 3433–3461 (2003)MATH MathSciNet CrossRef
  8.Birgin, E.G., Raydan, M.: Robust stopping criteria for Dykstra’s algorithm, SIAM. J. Sci. Comput. 26, 1405–1414 (2005)MATH MathSciNet
  9.Boyle, J.P., Dykstra, L.: A method for finding projections onto the intersections of convex sets in Hilbert spaces. In: Advances in Order Restricted Statistical Inference. Lecture Notes in Statistics, vol. 37, pp. 28–47. Springer, Berlin (1985)
  10.Borwein, J.M., Tam, M.K.: A cyclic Douglas–Rachford iteration scheme. J. Optim. Theory Appl. 160, 1–29 (2014)MATH MathSciNet CrossRef
  11.Bregman, L.M., Censor, Y., Reich, S.: Dykstra’s algorithm as the nonlinear extension of Bregman’s optimization method. J. Convex Anal. 6, 319–333 (1999)MATH MathSciNet
  12.Bregman, L.M., Censor, Y., Reich, S., Zepkowitz-Malachi, Y.: Finding the projection of a point onto the intersection of convex sets via the projection onto halfspaces. J. Approx. Theory 124, 194–218 (2003)MATH MathSciNet CrossRef
  13.Cegielski, A.: Iterative Methods for Fixed Point Problems in Hilbert Spaces. Lecture Notes in Mathematics vol. 2057. Springer, Heidelberg (2012)
  14.Cegielski, A., Censor, Y.: Extrapolation and local acceleration of an iterative process for common fixed point problems. J. Math. Anal. Appl. 394, 809–818 (2012)MATH MathSciNet CrossRef
  15.Cegielski, A., Dylewski, R.: Variable target value relaxed alternating projection method. Comput. Optim. Appl. 47, 455–476 (2010)MATH MathSciNet CrossRef
  16.Cegielski, A., Suchocka, A.: Relaxed alternating projection methods, SIAM. J. Optim. 19, 1093–1106 (2008)MATH MathSciNet
  17.Censor, Y.: Computational acceleration of projection algorithms for the linear best approximation problem. Linear Algebra Appl. 416, 111–123 (2006)MATH MathSciNet CrossRef
  18.Censor, Y., Herman, G.T.: On some optimization techniques in image reconstruction from projections. Appl. Numer. Math. 3, 365–391 (1987)MATH MathSciNet CrossRef
  19.Censor, Y., Reich, S.: The Dykstra’s algorithm with Bregman projections. Commun. Appl. Anal. 2, 407–419 (1998)MATH MathSciNet
  20.Censor, Y., Zenios, S.A.: Parallel Optimization: Theory, Algorithms, and Applications. Oxford University Press, New York (1997)MATH
  21.De Pierro, A., Iusem, A.N.: A parallel projection method for finding a common point of a family of convex sets. Pesqui. Oper. 5, 1–20 (1985)
  22.Deutsch, F.: Accelerating the convergence of the method of alternating projections via a line search: a brief survey. In: Butnariu, D., Censor, Y., Reich, S. (eds.) Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, pp. 203–217. Elsevier, Amsterdam (2001)CrossRef
  23.Deutsch, F.: Best Approximation in Inner Product Spaces. Springer, New York (2001)MATH CrossRef
  24.Deutsch, F., Hundal, H.: The rate of convergence of Dykstra’s cyclic projections algorithm: the polyhedral case. Numer. Funct. Anal. Optim. 15, 537–565 (1994)MATH MathSciNet CrossRef
  25.Dos Santos, L.T.: A parallel subgradient projections method for the convex feasibility problem. J. Comput. Appl. Math. 18, 307–320 (1987)MATH MathSciNet CrossRef
  26.Dykstra, R.L.: An algorithm for restricted least-squares regression. J. Am. Stat. Assoc. 78, 837–842 (1983)MATH MathSciNet CrossRef
  27.Eberle, M.G., Maciel, M.C.: Finding the closest Toeplitz matrix. Comput. Appl. Math. 22, 1–18 (2003)MATH MathSciNet CrossRef
  28.Echebest, N., Guardarucci, M.T., Scolnik, H., Vacchino, M.C.: An accelerated iterative method with diagonally scaled oblique projections for solving linear feasibility problems. Ann. Oper. Res. 138, 235–257 (2005)MATH MathSciNet CrossRef
  29.Escalante, R., Raydan, M.: Dykstra’s algorithm for a constrained least-squares matrix problem. Numer. Linear Algebra Appl. 3, 459–471 (1996)MATH MathSciNet CrossRef
  30.Escalante, R., Raydan, M.: On Dykstra’s algorithm for constrained least-squares rectangular matrix problems. Comput. Math. Appl. 35, 73–79 (1998)MATH MathSciNet CrossRef
  31.Escalante, R., Raydan, M.: Alternating Projection Methods. SIAM, Philadelphia (2011)CrossRef
  32.Galántai, A.: Projectors and Projection Methods. Kluwer Academic Publishers, Dordrecht (2004)MATH CrossRef
  33.García-Palomares, U.M.: Preconditioning projection methods for solving algebraic linear systems. Numer. Algorithms 21, 157–164 (1999)MATH MathSciNet CrossRef
  34.Gearhart, W., Koshy, M.: Acceleration schemes for the method of alternating projection. J. Comput. Appl. Math. 26, 235–249 (1989)MATH MathSciNet CrossRef
  35.Glunt, W., Hayden, T.L., Hong, S., Wells, J.: An alternating projection algorithm for computing the nearest Euclidean distance matrix. SIAM J. Matrix Anal. Appl. 11, 589–600 (1990)MATH MathSciNet CrossRef
  36.Grigoriadis, K.M., Skelton, R.: Low order control design for LMI problems using alternating projection methods. Automatica 32, 1117–1125 (1996)MATH MathSciNet CrossRef
  37.Gubin, L.G., Polyak, B.T., Raik, E.V.: The method of projections for finding the common point of convex sets. USSR Comput. Math. Math. Phys. 7(6), 1–24 (1967)CrossRef
  38.Higham, N.: Computing the nearest correlation matrix - a problem from finance, IMA. J. Numer. Anal. 22, 329–343 (2002)MATH MathSciNet CrossRef
  39.Hundal, H., Deutsch, F.: Two generalizations of Dykstra’s cyclic projections algorithm. Math. Program. 77, 335–355 (1997)MATH MathSciNet
  40.Hernández-Ramos, L.M.: Alternating oblique projections for coupled linear systems. Numer. Algorithms 38, 285–303 (2005)MATH MathSciNet CrossRef
  41.Hernández-Ramos, L.M., Escalante, R., Raydan, M.: Unconstrained optimization techniques for the acceleration of alternating projection methods. Numer. Funct. Anal. Optim. 32, 1041–1066 (2011)MATH MathSciNet CrossRef
  42.Iusem, A.N., De Pierro, A.: Convergence results for an accelerated nonlinear Cimmino algorithm. Numer. Math. 49, 367–378 (1986)MATH MathSciNet CrossRef
  43.López, G., Martín-Márquez, V., Wang, F., Xu, H.-K.: Solving the split feasibility problem without prior knowledge of matrix norms. Inverse Probl. 28(8), 1–18 (2012). doi:10.​1088/​0266-5611/​28/​8/​085004 CrossRef
  44.Luenberger, D.G.: Optimization by Vector Space Methods. Wiley, New York (1969)MATH
  45.Martínez, J.M.: An accelerated successive orthogonal projection method for solving large-scale linear feasibility problems. Comput. Math. Appl. 15, 367–373 (1988)MATH MathSciNet CrossRef
  46.Mendoza, M., Raydan, M., Tarazaga, P.: Computing the nearest diagonally dominant matrix. Numer. Linear Algebra Appl. 5, 461–474 (1998)MATH MathSciNet CrossRef
  47.Moreno, J., Datta, B., Raydan, M.: A symmetry preserving alternating projection method for matrix model updating. Mech. Syst. Signal Process. 23, 1784–1791 (2009)CrossRef
  48.Morillas, P.M.: Dykstra’s algorithm with strategies for projecting onto certain polyhedral cones. Appl. Math. Comp. 167, 635–649 (2005)MATH MathSciNet CrossRef
  49.Pang, C.H.J.: Set intersection problems: supporting hyperplanes and quadratic programming. Math. Program., Ser. A, (2014). doi:10.​1007/​s10107-014-0759-z
  50.Perkins, C.: A convergence analysis of Dykstra’s algorithm for polyhedral sets. SIAM J. Numer. Anal. 40, 792–804 (2002)MATH MathSciNet CrossRef
  51.Pierra, G.: Decomposition through formalization in a product space. Math. Prog. 28, 96–118 (1984)MATH MathSciNet CrossRef
  52.Raydan, M., Tarazaga, P.: Primal and polar approach for computing the symmetric diagonally dominant projection. Numer. Linear Algebra Appl. 9, 333–345 (2002)MATH MathSciNet CrossRef
  53.Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262–278 (2009)MATH MathSciNet CrossRef
  
• 作者单位：Williams López (1)
  Marcos Raydan (2)
  
  1. Departamento de Física y Matemáticas, Universidad de Los Andes, Trujillo, Venezuela
  2. Departamento de Cómputo Científico y Estadística, Universidad Simón Bolívar, Ap. 89000, Caracas, 1080-A, Venezuela
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operations Research and Mathematical Programming
  Operation Research and Decision Theory
  Statistics
  Convex and Discrete Geometry
  
• 出版者：Springer Netherlands
• ISSN：1573-2894

文摘

Dykstra’s algorithm is an iterative alternating projection procedure for solving the best approximation problem: find the closest point, to a given one, in the intersection of a finite number of closed and convex sets. The main drawback of Dykstra’s algorithm is its frequent slow convergence. In this work we develop an acceleration scheme with a strong geometrical flavor, which guarantees termination at the solution in two cycles of projections in the case of two closed subspaces. The proposed scheme can also be applied to any other alternating projection algorithm that solves the best approximation problem.