Tiếp cận các bài toán tối ưu phi mượt phi lồi qua hệ động lực bậc nhất với các yếu tố làm chậm bị ẩn và tán xạ điều khiển bởi Hessian

Springer Science and Business Media LLC - Tập 26 - Trang 227-245 - 2017
Radu Ioan Boţ1, Ernö Robert Csetnek1
1Faculty of Mathematics, University of Vienna, Vienna, Austria

Tóm tắt

Trong bài báo này, chúng tôi thực hiện phân tích tiệm cận của hệ thống động lực gần kề-građient $$\left\{ \begin{array}{ll} \dot x(t) +x(t) = \text{prox}_{\gamma f}\left[x(t)-\gamma\nabla{\Phi}(x(t))-ax(t)-by(t)\right],\\ \dot y(t)+ax(t)+by(t)=0 \end{array}\right. $$ trong đó f là một hàm hợp lệ, lồi và bán liên tục theo phía dưới, Φ là một hàm mượt mà có thể không lồi và γ, a, b là các số thực dương. Chúng tôi chỉ ra rằng các quỹ đạo sinh ra tiến gần đến tập hợp các điểm cực trị của f + Φ, ở đây hiểu là các điểm nút của vi phân phụ giới hạn của nó, dưới điều kiện rằng một sự điều chỉnh của hàm tổng này thỏa mãn tính chất Kurdyka-Łojasiewicz. Chúng tôi cũng thiết lập các tốc độ hội tụ cho các quỹ đạo, được cấu trúc dưới dạng chỉ số Łojasiewicz của hàm điều chỉnh được xem xét.

Từ khóa

#tối ưu hóa phi lồi #hệ động lực gần kề-građient #phân tích tiệm cận #vi phân phụ #tốc độ hội tụ #tính chất Kurdyka-Łojasiewicz

Tài liệu tham khảo

Abbas, B., Attouch, H.: Dynamical systems and forward-backward algorithms associated with the sum of a convex subdifferential and a monotone cocoercive operator. Optimization 64(10), 2223–2252 (2015) Abbas, B., Attouch, H., Svaiter, B.F.: Newton-like dynamics and forward-backward methods for structured monotone inclusions in Hilbert spaces. J. Optim. Theory Appl. 161(2), 331–360 (2014) Alvarez, F., Attouch, H., Bolte, J., Redont, P.: A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics. J. Math. Pures Appl. (9) 81(8), 747–779 (2002) Alvarez, F., Pérez, J. M.: A dynamical system associated with Newton’s method for parametric approximations of convex minimization problems. Appl. Math. Optim. 38(2), 193–217 (1998) Attouch, H., Alvarez, F. : The heavy ball with friction dynamical system for convex constrained minimization problems. In: Optimization (Namur, 1998). Lecture Notes in Economics and Mathematical Systems 481, pp. 25–35. Springer, Berlin (2000) Antipin, A.S.: Minimization of convex functions on convex sets by means of differential equations. Russian Differentsial’nye Uravneniya 30(9), 1475–1486 (1994). translation in Differential Equations 30(9), 13651375, 1994 Attouch, H., Marques Alves, M., Svaiter, B.F.: A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity O(1/n 2). J. Convex Anal. 23(1), 139–180 (2016) Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Programm. 116(1-2), Series B, 5–16 (2009) Attouch, H., Bolte, J., Redont, P.: Optimizing properties of an inertial dynamical system with geometric damping. Link with proximal methods. Control Cybern. 31(3), 643–657 (2002) Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35(2), 438–457 (2010) 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. Programm. 137(1-2), Series A, 91–129 (2013) Attouch, H., Czarnecki, M.-O.: Asymptotic behavior of coupled dynamical systems with multiscale aspects. J. Differ. Equ. 248(6), 1315–1344 (2010) Attouch, H., Goudou, X., Redont, P.: The heavy ball with friction method. I. The continuous dynamical system: global exploration of the local minima of a real-valued function by asymptotic analysis of a dissipative dynamical system. Commun. Contemp. Math. 2(1), 1–34 (2000) Attouch, H., Maingé, P.-E., Redont, P.: A second-order differential system with Hessian-driven damping; application to non-elastic shock laws. Differ. Equ. Appl. 4(1), 27–65 (2012) Attouch, H., Peypouquet, J., Redont, P.: A dynamical approach to an inertial forward-backward algorithm for convex minimization. SIAM J. Optim. 24(1), 232–256 (2014) Attouch, H., Peypouquet, J., Redont, P.: Fast convex optimization via inertial dynamics with Hessian driven damping. J. Differ. Equ. 261, 5734–5783 (2016) Attouch, H., Redont, P.: The second-order in time continuous Newton method. In: Approximation, Optimization and Mathematical Economics (Pointe–Pitre, 1999), p. 2536. Physica, Heidelberg (2001) Attouch, H., Svaiter, B.F.: A continuous dynamical Newton-like approach to solving monotone inclusions. SIAM J. Control Optim. 49(2), 574–598 (2011) Banert, S., Boţ, R.I.: A forward-backward-forward differential equation and its asymptotic properties. J. Convex Anal. 25(2) (2018) Bauschke, H.H., Combettes, P.L.: Convex analysis and monotone operator theory in hilbert spaces. CMS Books in Mathematics, Springer, New York (2011) Bolte, J.: Continuous gradient projection method in Hilbert spaces. J. Optim. Theory Appl. 119(2), 235–259 (2003) Bolte, J., Daniilidis, A., Lewis, A.: The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4), 1205–1223 (2006) Bolte, J., Daniilidis, A., Lewis, A., Shota, M.: Clarke subgradients of stratifiable functions. SIAM J. Optim. 18(2), 556–572 (2007) Bolte, J., Daniilidis, A., Ley, O., Mazet, L.: Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity. Trans. Amer. Math. Soc. 362(6), 3319–3363 (2010) Bolte, J., Nguyen, T.P., Peypouquet, J., Suter, B.W.: From error bounds to the complexity of first-order descent methods for convex functions, Mathematical Programming, doi:10.1007/s10107-016-1091-6 Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Programm. Ser. A 146(1–2), 459–494 (2014) Borwein, J.M., Zhu, Q.J.: Techniques of variational analysis. Springer, New York (2005) Boţ, R.I., Csetnek, E.R.: An inertial Tseng’s type proximal algorithm for nonsmooth and nonconvex optimization problems. J. Optim. Theory Appl. 171(2), 600–616 (2016) Boţ, R.I., Csetnek, E.R.: A dynamical system associated with the fixed points set of a nonexpansive operator, Journal of Dynamics and Differential Equations, doi:10.1007/s10884-015-9438-x (2015) Boţ, R.I., Csetnek, E.R.: Approaching the solving of constrained variational inequalities via penalty term-based dynamical systems. J. Math. Anal. Appl. 435(2), 1688–1700 (2016) Boţ, R.I., Csetnek, E.R.: Second order forward-backward dynamical systems for monotone inclusion problems. SIAM J. Control Optim. 54(3), 1423–1443 (2016) Boţ, R.I., Csetnek, E.R.: Convergence rates for forward-backward dynamical systems associated with strongly monotone inclusions, Journal of Mathematical Analysis and Applications, doi:10.1016/j.jmaa.2016.07.007 (2016) Boţ, R.I., Csetnek, E.R., László, S.: An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions. EURO J. Comput. Optim. 4, 3–25 (2016) Brézis, H.: Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert, North-Holland Mathematics Studies No. 5, Notas de Matemática (50). North-Holland/Elsevier, New York (1973) Chouzenoux, E., Pesquet, J.-C., Repetti, A.: Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function. J. Optim. Theory Appl. 162(1), 107–132 (2014) Frankel, P., Garrigos, G., Peypouquet, J.: Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates. J. Optim. Theory Appl. 165(3), 874–900 (2015) Haraux, A.: Systèmes Dynamiques dissipatifs et applications. Recherches en Mathé- matiques Appliquéées 17, Masson, Paris (1991) Hesse, R., Luke, D.R., Sabach, S., Tam, M.K.: Proximal heterogeneous block input-output method and application to blind ptychographic diffraction imaging. SIAM J. Imaging Sci. 8(1), 426–457 (2015) Kurdyka, K.: On gradients of functions definable in o-minimal structures. Ann. l’inst. Fourier (Grenoble) 48(3), 769–783 (1998) Li, G., Pong, T.K.: Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods arXiv:1602.02915v2 (2016) Łojasiewicz, S.: Une propriéte ́topologique des sous-ensembles analytiques réels, pp. 87–89. Les Équations aux Dérivées Partielles, Éditions du Centre National de la Recherche Scientifique , Paris (1963) Mordukhovich, B.: Variational Analysis and Generalized Differentiation I: Basic Theory, II: Applications. Springer-Verlag, Berlin (2006) Ochs, P., Chen, Y., Brox, T., Pock, T.: iPiano: Inertial proximal algorithm for non-convex optimization. SIAM J. Imaging Sci. 7(2), 1388–1419 (2014) Rockafellar, R.T., Wets, R. J.-B.: Variational analysis fundamental principles of mathematical sciences 317. Springer-Verlag, Berlin (1998)