A Perturbed Primal-Dual Dynamical System for Solving Convex-Concave Bilinear Saddle Point Problems
-
摘要: 该文旨在研究求解凸凹双线性鞍点问题的一类带有外源扰动的二阶惯性原始对偶动力系统. 首先, 建立了该系统全局强解的存在性和唯一性定理; 随后, 当扰动参数满足一定的可积条件时, 证明了原始对偶间隙函数和速度向量范数沿动力系统所产生解轨道的快速收敛速率. 数值实验结果表明在不同的扰动情况下, 该动力系统均保持较快的收敛速率.Abstract: A 2nd-order inertial primal-dual dynamical system with external perturbations for solving convex-concave bilinear saddle point problems was investigated. Firstly, the existence and uniqueness of the global strong solution of the dynamical system was established. Then, with integrable assumption on perturbation parameters, the fast convergence rates of the primal-dual gap function and the norms of velocity vectors along the trajectories generated by the dynamical system were obtained. Numerical experiments show that, the dynamical system has fast convergence rates under different kinds of perturbations.
-
图 1 不同的外源扰动函数ϵ选择下的收敛速率比较
注 为了解释图中的颜色，读者可以参考本文的电子网页版本，后同.
Figure 1. Comparison of convergence rates with different exogenous disturbance functions ϵ
-
[1] POLYAK B T. Some methods of speeding up the convergence of iteration methods[J]. USSR Computational Mathematics and Mathematical Physics, 1964, 4(5): 1-17. doi: 10.1016/0041-5553(64)90137-5 [2] SU W, BOYD S, CANDÈS E J. A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[J]. Journal of Machine Learning Research, 2016, 17(153): 1-43. [3] ATTOUCH H, CHBANI Z, PEYPOUQUET J, et al. Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[J]. Mathematical Programming, 2018, 168(1): 123-175. [4] XU B, WEN B. On the convergence of a class of inertial dynamical systems with Tikhonov regularization[J]. Optimization Letters, 2021, 15(6): 2025-2052. doi: 10.1007/s11590-020-01663-3 [5] SHI B, DU S S, JORDAN M I, et al. Understanding the acceleration phenomenon via high-resolution differential equations[J]. Mathematical Programming, 2022, 195(1): 79-148. [6] LUO H, CHEN L. From differential equation solvers to accelerated first-order methods for convex optimization[J]. Mathematical Programming, 2022, 195(1): 735-781. [7] ATTOUCH H, BOŢ R I, CSETNEK E R. Fast optimization via inertial dynamics with closed-loop damping[J]. Journal of the European Mathematical Society, 2023, 25(5): 1985-2056. [8] ZENG X, LEI J, CHEN J. Dynamical primal-dual Nesterov accelerated method and its application to network optimization[J]. IEEE Transactions on Automatic Control, 2023, 68(3): 1760-1767. doi: 10.1109/TAC.2022.3152720 [9] BO R I, NGUYEN D K. Improved convergence rates and trajectory convergence for primal-dual dynamical systems with vanishing damping[J]. Journal of Differential Equations, 2021, 303: 369-406. doi: 10.1016/j.jde.2021.09.021 [10] HE X, HU R, FANG Y P. "Second-order primal" + "first-order dual" dynamical systems with time scaling for linear equality constrained convex optimization problems[J]. IEEE Transactions on Automatic Control, 2022, 67(8): 4377-4383. doi: 10.1109/TAC.2022.3176527 [11] HULETT D A, NGUYEN D K. Time rescaling of a primal-dual dynamical system with asymptotically vanishing damping[J]. Applied Mathematics and Optimization, 2023, 88(2): 27. doi: 10.1007/s00245-023-09999-9 [12] HE X, TIAN F, LI A Q, et al. Convergence rates of mixed primal-dual dynamical systems with Hessian driven damping[J]. Optimization, 2025, 74(2): 365-390. doi: 10.1080/02331934.2023.2253813 [13] ATTOUCH H, CHBANI Z, FADILI J, et al. Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics[J]. Journal of Optimization Theory and Applications, 2022, 193(1): 704-736. [14] HARAUX A. Systèmes Dynamiques Dissipatifs et Applications[M]. Paris: Elsevier Masson, 1991. [15] BRÉZIS H. Opérateurs Maximaux Monotones et Semi-Groupes de Contractions Dans Les Espaces de Hilbert[M]. Amsterdam: North Holland Publishing Company, 1973. [16] HE X, HU R, FANG Y P. Inertial primal-dual dynamics with damping and scaling for linearly constrained convex optimization problems[J]. Applicable Analysis, 2023, 102(15): 4114-4139. [17] ATTOUCH H, PEYPOUQUET J, REDONT P. Fast convex optimization via inertial dynamics with Hessian driven damping[J]. Journal of Differential Equations, 2016, 261(10): 5734-5783. -
下载:
图(2)
计量
- 文章访问数: 45
- HTML全文浏览量: 12
- PDF下载量: 7
- 被引次数: 0
渝公网安备50010802005915号