Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Về điều kiện Slater và sự hội tụ hữu hạn của thuật toán Douglas–Rachford trong việc giải quyết các vấn đề khả thi lồi trong không gian Euclid
Tóm tắt
Thuật toán Douglas–Rachford là một phương pháp cổ điển và rất thành công trong việc giải quyết các vấn đề tối ưu hóa và khả thi. Trong bài báo này, chúng tôi cung cấp các điều kiện mới đủ để đảm bảo hội tụ hữu hạn trong bối cảnh các vấn đề khả thi lồi. Phân tích của chúng tôi dựa trên và mở rộng đáng kể công trình tiên phong của Spingarn. Cụ thể, chúng tôi đạt được sự hội tụ hữu hạn khi tồn tại điều kiện Slater trong trường hợp đa diện affine và trong trường hợp siêu phẳng-đỉnh. Nhiều ví dụ minh họa cho kết quả của chúng tôi. Các thí nghiệm số cho thấy sự cạnh tranh của thuật toán Douglas–Rachford trong việc giải các hệ phương trình tuyến tính với điều kiện dương khi so với phương pháp chiếu xen kẽ và phương pháp phản chiếu-chiếu.
Từ khóa
#thuật toán Douglas–Rachford #hội tụ hữu hạn #điều kiện Slater #bài toán khả thi lồi #không gian EuclidTài liệu tham khảo
Bauschke, H.H., Bello Cruz, J.Y., Nghia, T.T.A., Phan, H.M., Wang, X.: The rate of linear convergence of the Douglas–Rachford algorithm for subspaces is the cosine of the Friedrichs angle. J. Approx. Theory 185, 63–79 (2014)
Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011)
Bauschke, H.H., Combettes, P.L., Luke, D.R.: Finding best approximation pairs relative to two closed convex sets in Hilbert spaces. J. Approx. Theory 127, 178–192 (2004)
Bauschke, H.H., Dao, M.N., Noll, D., Phan, H.M.: Proximal point algorithm, Douglas–Rachford algorithm and alternating projections: a case study. J. Convex Anal. 23 (2016)
Bauschke, H.H., Kruk, S.G.: Reflection–projection method for convex feasibility problems with an obtuse cone. J. Optim. Theory Appl. 120, 503–531 (2004)
Bauschke, H.H., Noll, D., Phan, H.M.: Linear and strong convergence of algorithms involving averaged nonexpansive operators. J. Math. Anal. Appl. 421, 1–20 (2015)
Borwein, J.M., Moors, W.B.: Stability of closedness of convex cones under linear mappings. J. Convex Anal. 16, 699–705 (2009)
Cegielski, A.: Iterative Methods for Fixed Point Problems in Hilbert Spaces. Springer, Berlin (2012)
Censor, Y., Zenios, S.A.: Parallel Optimization. Oxford University Press, Oxford (1997)
Combettes, P.L.: Iterative construction of the resolvent of a sum of maximal monotone operators. J. Convex Anal. 16, 727–748 (2009)
Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two and three space variables. Trans. AMS 82, 421–439 (1956)
Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293–318 (1992)
GeoGebra software. http://www.geogebra.org
Hesse, R., Luke, D.R.: Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems. SIAM J. Optim. 23, 2397–2419 (2013)
Lawrence, J., Spingarn, J.E.: On fixed points of nonexpansive piecewise isometric mappings. Proc. Lond. Math. Soc. Third Ser. 55, 605–624 (1987)
Lions, P.-L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)
Luque, F.J.: Asymptotic convergence analysis of the proximal point algorithm. SIAM J. Control Optim. 22, 277–293 (1984)
MATLAB software. http://www.mathworks.com/products/matlab/
Mahey, P., Oualibouch, S., Tao, P.D.: Proximal decomposition on the graph of a maximal monotone operator. SIAM J. Optim. 5, 454–466 (1995)
Mordukhovich, B.S., Nam, N.M.: An easy path to convex analysis and applications. Morgan & Claypool Publishers, San Rafael (2014)
Phan, H.M.: Linear convergence of the Douglas–Rachford method for two closed sets. Optimization (2015). doi:10.1080/02331934.2015.1051532
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877–898 (1976)
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)
Spingarn, J.E.: Partial inverse of a monotone operator. Appl. Math. Optim. 10, 247–265 (1983)
Spingarn, J.E.: A primal–dual projection method for solving systems of linear inequalities. Linear Algebra Appl. 65, 45–62 (1985)