A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 11 Issue 8
Aug.  2024

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2024  >  11(8): 1849-1864
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
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
shu

Fixed-Time Gradient Flows for Solving Constrained Optimization: A Unified Approach

doi: 10.1109/JAS.2023.124089
Funds:  This work was supported by the National Key Research and Development Program of China (2020YFA0714300), the National Natural Science Foundation of China (62003084, 62203108, 62073079), the Natural Science Foundation of Jiangsu Province of China (BK20200355), the General Joint Fund of the Equipment Advance Research Program of Ministry of Education (8091B022114), Jiangsu Province Excellent Postdoctoral Program (2022ZB131), and China Postdoctoral Science Foundation (2022M720720, 2023T160105)
More Information
    Abstract

  • 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.

     

    • FullText(HTML)
  • loading
    • References(53)
  • [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
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(7)  / Tables(4)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (150) PDF downloads(41) Cited by()

    Highlights

    • We design several fixed-time gradient flows (FxTGFs) under the Polyak-Lojasiewicz condition
    • A specific class of nonsmooth robust FxTGFs with disturbance rejection is presented
    • An FxTGF with relaxed parameters is provided for nonsmooth composite optimization
    • We conduct a static regret analysis for various typical FxTGFs to show their performance
    • We apply FxTGFs to solve distributed consensus problems and linear equations within a fixed time

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return