IEEE/CAA Journal of Automatica Sinica
Citation: | X. Shi, X. Xu, G. Wen, and J. Cao, “Fixed-time gradient flows for solving constrained optimization: A unified approach,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 8, pp. 1849–1864, Aug. 2024. doi: 10.1109/JAS.2023.124089 |
The accelerated method in solving optimization problems has always been an absorbing topic. Based on the fixed-time (FxT) stability of nonlinear dynamical systems, we provide a unified approach for designing FxT gradient flows (FxTGFs). First, a general class of nonlinear functions in designing FxTGFs is provided. A unified method for designing first-order FxTGFs is shown under Polyak-Łjasiewicz inequality assumption, a weaker condition than strong convexity. When there exist both bounded and vanishing disturbances in the gradient flow, a specific class of nonsmooth robust FxTGFs with disturbance rejection is presented. Under the strict convexity assumption, Newton-based FxTGFs is given and further extended to solve time-varying optimization. Besides, the proposed FxTGFs are further used for solving equation-constrained optimization. Moreover, an FxT proximal gradient flow with a wide range of parameters is provided for solving nonsmooth composite optimization. To show the effectiveness of various FxTGFs, the static regret analyses for several typical FxTGFs are also provided in detail. Finally, the proposed FxTGFs are applied to solve two network problems, i.e., the network consensus problem and solving a system linear equations, respectively, from the perspective of optimization. Particularly, by choosing component-wisely sign-preserving functions, these problems can be solved in a distributed way, which extends the existing results. The accelerated convergence and robustness of the proposed FxTGFs are validated in several numerical examples stemming from practical applications.
[1] |
J. Wang and N. Elia, “A control perspective for centralized and distributed convex optimization,” in Proc. IEEE Decision Control and Eur. Control Conf., Orlando, FL, Dec. 2011, pp. 3800–3805.
|
[2] |
Q. Liu, S. Yang, and J. Wang, “A collective neurodynamic approach to distributed constrained optimization,” IEEE Trans. Neural Netw., vol. 28, no. 8, pp. 1747–1758, 2017.
|
[3] |
J. Cortés, “Finite-time convergent gradient flows with applications to network consensus,” Automatica, vol. 42, no. 11, pp. 1993–2000, 2006. doi: 10.1016/j.automatica.2006.06.015
|
[4] |
C. Xu and J. Prince, “Snakes, shapes, and gradient vector flow,” IEEE Trans. Image Process., vol. 359, no. 7, pp. 3–369, Mar. 1998.
|
[5] |
W. Su, S. Boyd, and E. Candes, “A differential equation for modeling nesterov’s accelerated gradient method: Theory and insights,” in Proc. Adv. Neural Inf. Process. Syst., 2014, pp. 2510–2518.
|
[6] |
A. Wibisono, A. C. Wilson, and M. I. Jordan, “A variational perspective on accelerated methods in optimization,” Nat. Acad. Sci., vol. 113, no. 47, pp. E7351–E7358, 2016.
|
[7] |
H. Attouch, Z. Chbani, J. Peypouquet, and P. Redont, “Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity,” Math. Program., vol. 168, no. 1–2, pp. 123–175, 2018. doi: 10.1007/s10107-016-0992-8
|
[8] |
A. Vassilis, A. Jean-François, and D. Charles, “The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b ≤ 3,” SIAM J. Optim., vol. 28, pp. 551–574, 2018. doi: 10.1137/17M1128642
|
[9] |
O. Sebbouh, C. Dossal, and A. Rondepierre, “Convergence rates of damped inertial dynamics under geometric conditions and perturbations,” SIAM J. Optim., vol. 30, pp. 1850–1877, 2020. doi: 10.1137/19M1272767
|
[10] |
J. M. Sanz Serna, and K. C. Zygalakis, “The connections between Lyapunov functions for some optimization algorithms and differential equations,” SIAM. J. Numer. Anal., vol. 59, no. 3, pp. 1542–1565, 2021. doi: 10.1137/20M1364138
|
[11] |
S. P. Bhat and D. S. Bernstein, “Finite-time stability of continuous autonomous systems,” SIAM J. Control Optim., vol. 38, no. 3, pp. 751–766, 2000. doi: 10.1137/S0363012997321358
|
[12] |
S. Yu, X. Yu, B. Shirinzadeh, and Z. Man, “Continuous finite-time control for robotic manipulators with terminal sliding mode,” Automatica, vol. 41, no. 11, pp. 1957–1964, 2005. doi: 10.1016/j.automatica.2005.07.001
|
[13] |
Y. Shen and Y. Huang, “Global finite-time stabilisation for a class of nonlinear systems,” Int. J. Syst. Sci., vol. 43, no. 1, pp. 73–78, 2012. doi: 10.1080/00207721003770569
|
[14] |
C. Aouiti and M. Bessifi, “Periodically intermittent control for finite-time synchronization of delayed quaternion-valued neural networks,” Neural. Comput. Appl., vol. 33, pp. 6527–6547, 2021. doi: 10.1007/s00521-020-05417-1
|
[15] |
O. Romero and M. Benosman, “Finite-time convergence in continuous-time optimization,” in Proc. 37th Int. Conf. Machine Learning, PMLR, 2020, pp. 8200–8209.
|
[16] |
F. Chen and W. Ren, “Sign projected gradient flow: A continuous time approach to convex optimization with linear equality constraints,” Automatica, vol. 120, p. 109156, 2020. doi: 10.1016/j.automatica.2020.109156
|
[17] |
Y. Wei, Y. Chen, X. Zhao, and J. Cao, “Analysis and synthesis of gradient algorithms based on fractional-order system theory,” IEEE Trans. Syst.,Man,Cybern.,Syst., vol. 53, pp. 3–1906, 1895.
|
[18] |
J. Zhou, X. Wang, S. Mou, and B. D. Anderson, “Finite-time distributed linear equation solver for solutions with minimum l1-norm,” IEEE Trans. Autom. Control, vol. 65, no. 4, pp. 1691–1696, 2020. doi: 10.1109/TAC.2019.2932031
|
[19] |
X. Shi, X. Xu, X. Yu, and J. Cao, “Finite-time convergent primal-dual gradient dynamics with applications to distributed optimization,” IEEE Trans. Cybern., vol. 53, no. 5, pp. 3240–3252, 2023. doi: 10.1109/TCYB.2022.3179519
|
[20] |
X. Shi, G. Wen, J. Cao, and X. Yu, “Finite-time distributed average tracking for multi-agent optimization with bounded inputs,” IEEE Trans. Autom. Control, vol. 68, no. 8, pp. 4948–4955, 2023. doi: 10.1109/TAC.2022.3209406
|
[21] |
X. Shi, G. Wen and X. Yu, “Finite-time convergent algorithms for time-varying distributed optimization,” IEEE Control Syst. Lett., vol. 7, pp. 3223–3228, 2023. doi: 10.1109/LCSYS.2023.3312297
|
[22] |
A. Polyakov, “Nonlinear feedback design for fixed-time stabilization of linear control systems,” IEEE Trans. Autom. Control, vol. 57, pp. 2106–2110, 2012. doi: 10.1109/TAC.2011.2179869
|
[23] |
Y. Liu, H. Li, Z. Zuo, X. Li, and R. Lu, “An overview of finite/fixed-time control and its application in engineering systems,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 12, pp. 2106–2120, 2022.
|
[24] |
C. Aouiti, E. A. Assali, and Y. E. Foutayeni, “Finite-time and fixed-time synchronization of inertial Cohen-Grossberg-type neural networks with time varying delays,” Neural Processing Letters, vol. 50, pp. 2407–2436, 2019. doi: 10.1007/s11063-019-10018-8
|
[25] |
A. M. Alimi, C. Aouiti, and E. A. Assali, “Finite-time and fixed-time synchronization of a class of inertial neural networks with multi-proportional delays and its application to secure communication,” Neurocomputing, vol. 332, pp. 29–43, 2019. doi: 10.1016/j.neucom.2018.11.020
|
[26] |
J. Cao and R. Li, “Fixed-time synchronization of delayed memristor-based recurrent neural networks,” Sci. China Inf. Sci., vol. 60, no. 3, p. 032201, 2017.
|
[27] |
C. Aouiti and F. Miaadi, “A new fixed-time stabilization approach for neural networks with time-varying delays,” Neural. Comput. Appl., vol. 32, pp. 3295–3309, 2020. doi: 10.1007/s00521-019-04586-y
|
[28] |
C. Aouiti, M. Bessifi, and X. Li, “Finite-time and fixed-time synchronization of complex-valued recurrent neural networks with discontinuous activations and time-varying delays,” Circuits,Syst.,Signal Process., vol. 39, no. 11, pp. 5406–5428, 5406.
|
[29] |
C. Aouiti, Q. Hui, H. Jallouli, and E. Moulay, “Sliding mode control-based fixed-time stabilization and synchronization of inertial neural networks with time-varying delays,” Neural. Comput. Appl., vol. 33, pp. 11555–11572, 2021. doi: 10.1007/s00521-021-05833-x
|
[30] |
K. Garg and D. Panagou, “Fixed-time stable gradient flows: Applications to continuous-time optimization,” IEEE Trans. Autom. Control, vol. 66, no. 5, pp. 2002–2015, 2020.
|
[31] |
P. Budhraja, M. Baranwal, K. Garg, and A. Hota, “Breaking the convergence barrier: Optimization via fixed-time convergent flows,” in Proc. AAAI Conf. Artificial Intelligence, vol. 36, no. 6, 2022.
|
[32] |
K. Garg, M. Baranwal, R. Gupta, and M. Benosman, “Fixed-time stable proximal dynamical system for solving MVIPs,” IEEE Trans. Autom. Control, vol. 68, no. 8, pp. 5029–5036, 2023. doi: 10.1109/TAC.2022.3214795
|
[33] |
X. Ju, D. Hu, C. Li, X. He, and G. Feng, “A novel fixed-time converging neurodynamic approach to mixed variational inequalities and applications,” IEEE Trans. Cybern., vol. 52, no. 12, pp. 12942–12953, 2022. doi: 10.1109/TCYB.2021.3093076
|
[34] |
X. He, H. Wen, and T. Huang, “A fixed-time projection neural network for solving L1-minimization problem,” IEEE Trans. Neural Netw., vol. 33, no. 12, pp. 7818–7828, Dec. 2022.
|
[35] |
Z. Wu, Z. Li and J. Yu, “Designing zero-gradient-sum protocols for finite-time distributed optimization problem,” IEEE Trans. Syst.,Man,Cybern.,Syst., vol. 52, no. 7, pp. 4569–4577, Jul. 2022. doi: 10.1109/TSMC.2021.3098641
|
[36] |
X. Shi, X. Yu, J. Cao, and G. Wen, “Continuous distributed algorithms for solving linear equations in finite time,” Automatica, vol. 113, p. 108755, 2020. doi: 10.1016/j.automatica.2019.108755
|
[37] |
L. Guo, X. Shi, and J. Cao, “Exponential convergence of primal-dual dynamical system for linear constrained optimization,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 4, pp. 745–748, 2022. doi: 10.1109/JAS.2022.105485
|
[38] |
H. Karimi, J. Nutini, and M. Schmidt, “Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition,” in Proc. Eur. Conf. Mach. Learn., Sept. 2016, pp. 795–811.
|
[39] |
X. Yi, S. Zhang, T. Yang, T. Chai, and K. H. Johansson, “A primal-dual SGD algorithm for distributed nonconvex optimization,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 5, pp. 812–833, 2022.
|
[40] |
X. Shi, J. Cao, X. Yu, and G. Wen, “Finite-time stability for network systems with discontinuous dynamics over signed digraphs,” IEEE Trans. Autom. Control, vol. 65, no. 11, pp. 4874–4881, 2020. doi: 10.1109/TAC.2019.2960000
|
[41] |
F. Xiao, L. Wang, J. Chen, and Y. Gao, “Finite-time formation control for multi-agent systems,” Automatica, vol. 45, no. 11, pp. 2605–2611, 2009. doi: 10.1016/j.automatica.2009.07.012
|
[42] |
X. Shi, J. Cao, G. Wen, and X. Yu, “Finite-time stability for network systems with nonlinear protocols over signed digraphs,” IEEE Trans. Netw. Sci. Eng., vol. 7, no. 3, pp. 1557–1569, 2020. doi: 10.1109/TNSE.2019.2941553
|
[43] |
Z. Zuo and L. Tie, “A new class of finite-time nonlinear consensus protocols for multi-agent systems,” Int. J. Control, vol. 87, no. 2, pp. 363–370, 2014. doi: 10.1080/00207179.2013.834484
|
[44] |
J. Cortés, “Discontinuous dynamical systems: A tutorial on solutions, nonsmooth analysis, and stability,” IEEE Control Syst. Mag., vol. 28, no. 3, pp. 36–73, 2008. doi: 10.1109/MCS.2008.919306
|
[45] |
M. Goldberg, “Equivalence constants for l p norms of matrices,” Lin. Multilin. Algebra, vol. 21, no. 2, pp. 173–179, 1987. doi: 10.1080/03081088708817789
|
[46] |
X. Yu, Y. Feng and Z. Man, “Terminal sliding mode control — An overview,” IEEE Open J. Ind. Electron. Soc., vol. 2, pp. 36–52, 2021. doi: 10.1109/OJIES.2020.3040412
|
[47] |
N. Parikh and S. Boyd, “Proximal algorithms,” Found. Trends Optim., vol. 123, no. 1, pp. 3–231, 2014.
|
[48] |
A. Themelis, L. Stella, and P. Patrinos, “Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms,” SIAM J. Optim., vol. 28, no. 3, pp. 2274–2303, 2018. doi: 10.1137/16M1080240
|
[49] |
S. Hassan-Moghaddam and M. R. Jovanović, “Proximal gradient flow and Douglas-Rachford splitting dynamics: Global exponential stability via integral quadratic constraints,” Automatica, vol. 123, p. 109311, 2021. doi: 10.1016/j.automatica.2020.109311
|
[50] |
P. Wang, S. Mou, J. Lian, and W. Ren, “Solving a system of linear equations: From centralized to distributed algorithms,” Annu. Rev. Control, vol. 47, pp. 306–322, 2019. doi: 10.1016/j.arcontrol.2019.04.008
|
[51] |
M. Yang and C. Y. Tang, “A distributed algorithm for solving general linear equations over networks,” in Proc. IEEE Conf. Decis. Control, pp. 3580–3585, Dec. 2015.
|
[52] |
A. J. Wood, B. F. Wollenberg, and G. B. Sheble, Power Generation, Operation, and Control, New York, NY: Wiley, 2013.
|
[53] |
A. Cherukuri and J. Cortés, “Distributed generator coordination for initialization and anytime optimization in economic dispatch,” IEEE Trans. Control Netw. Syst., vol. 2, no. 3, pp. 226–237, 2015. doi: 10.1109/TCNS.2015.2399191
|