Research article Special Issues

Linear convergence of a primal-dual algorithm for distributed interval optimization

  • Received: 09 October 2023 Revised: 18 December 2023 Accepted: 27 December 2023 Published: 12 January 2024
  • In this paper, we investigate a distributed interval optimization problem whose local functions are interval functions rather than scalar functions. Focusing on distributed interval optimization, this paper presents a distributed primal-dual algorithm. A criterion is introduced under which linear convergence to the Pareto solution of distributed interval optimization problems can be achieved without strong convexity. Lastly, a numerical simulation is presented to illustrate the linear convergence of the algorithm that has been proposed.

    Citation: Yinghui Wang, Jiuwei Wang, Xiaobo Song, Yanpeng Hu. Linear convergence of a primal-dual algorithm for distributed interval optimization[J]. Electronic Research Archive, 2024, 32(2): 857-873. doi: 10.3934/era.2024041

    Related Papers:

  • In this paper, we investigate a distributed interval optimization problem whose local functions are interval functions rather than scalar functions. Focusing on distributed interval optimization, this paper presents a distributed primal-dual algorithm. A criterion is introduced under which linear convergence to the Pareto solution of distributed interval optimization problems can be achieved without strong convexity. Lastly, a numerical simulation is presented to illustrate the linear convergence of the algorithm that has been proposed.



    加载中


    [1] I. Necoara, Y. Nesterov, F. Glineur, Linear convergence of first order methods for non-strongly convex optimization, Math. Program., 175 (2019), 69–107. https://doi.org/10.1007/s10107-018-1232-1 doi: 10.1007/s10107-018-1232-1
    [2] A. Makhdoumi, A. Ozdaglar, Convergence rate of distributed admm over networks, IEEE Trans. Autom. Control, 62 (2017), 5082–5095. https://doi.org/10.1109/TAC.2017.2677879 doi: 10.1109/TAC.2017.2677879
    [3] X. He, T. Huang, J. Yu, C. Li, Y. Zhang, A continuous-time algorithm for distributed optimization based on multiagent networks, IEEE Trans. Syst. Man Cybern.: Syst., 49 (2017), 2700–2709. https://doi.org/10.1109/TSMC.2017.2780194 doi: 10.1109/TSMC.2017.2780194
    [4] H. Li, Q. Lü, X. Liao, T. Huang, Accelerated convergence algorithm for distributed constrained optimization under time-varying general directed graphs, IEEE Trans. Syst. Man Cybern.: Syst., 50 (2018), 2612–2622. https://doi.org/10.1109/TSMC.2018.2823901 doi: 10.1109/TSMC.2018.2823901
    [5] Q. Wang, J. Chen, B. Xin, X. Zeng, Distributed optimal consensus for euler-lagrange systems based on event-triggered control, IEEE Trans. Syst. Man Cybern.: Syst., 51 (2021), 4588–4598. https://doi.org/10.1109/TSMC.2019.2944857 doi: 10.1109/TSMC.2019.2944857
    [6] J. Guo, R. Jia, R. Su, Y. Zhao, Identification of fir systems with binary-valued observations against data tampering attacks, IEEE Trans. Syst. Man Cybern.: Syst., 53 (2023), 5861–5873. https://doi.org/10.1109/TSMC.2023.3276352 doi: 10.1109/TSMC.2023.3276352
    [7] J. Guo, X. Wang, W. Xue, Y. Zhao, System identification with binary-valued observations under data tampering attacks, IEEE Trans. Autom. Control, 66 (2020), 3825–3832. https://doi.org/10.1109/TAC.2020.3029325 doi: 10.1109/TAC.2020.3029325
    [8] X. Zeng, Y. Peng, Y. Hong, Distributed algorithm for robust resource allocation with polyhedral uncertain allocation parameters, J. Syst. Sci. Complexity, 31 (2018), 103–119. https://doi.org/10.1007/s11424-018-7145-5 doi: 10.1007/s11424-018-7145-5
    [9] V. Kekatos, G. B. Giannakis, Distributed robust power system state estimation, IEEE Trans. Power Syst., 28 (2013), 1617–1626. https://doi.org/10.1109/TPWRS.2012.2219629 doi: 10.1109/TPWRS.2012.2219629
    [10] S. Sra, S. Nowozin, S. J. Wright, Optimization for Machine Learning, Mit Press, 2012.
    [11] B. Q. Hu, S. Wang, A novel approach in uncertain programming part Ⅰ: new arithmetic and order relation for interval numbers, J. Ind. Manage. Optim., 2 (2006), 351–371. https://doi.org/10.3934/jimo.2006.2.351 doi: 10.3934/jimo.2006.2.351
    [12] L. Wu, M. Shahidehpour, Z. Li, Comparison of scenario-based and interval optimization approaches to stochastic SCUC, IEEE Trans. Power Syst., 27 (2012), 913–921. https://doi.org/10.1109/TPWRS.2011.2164947 doi: 10.1109/TPWRS.2011.2164947
    [13] A. Neumaier, Interval Methods for Systems of Equations, Cambridge University Press, 1990.
    [14] J. Rohn, Positive definiteness and stability of interval matrices, SIAM J. Matrix Anal. Appl., 15 (1994), 175–184. https://doi.org/10.1137/S0895479891219216 doi: 10.1137/S0895479891219216
    [15] V. I. Levin, Nonlinear optimization under interval uncertainty, Cybern. Syst. Anal., 35 (1999), 297–306. https://doi.org/10.1007/BF02733477 doi: 10.1007/BF02733477
    [16] T. Saeed, S. Treană, New classes of interval-valued variational problems and inequalities, Results Control Optim., 13 (2023), 100324. https://doi.org/10.1016/j.rico.2023.100324 doi: 10.1016/j.rico.2023.100324
    [17] M. Ciontescu, S. Treană, On some connections between interval-valued variational control problems and the associated inequalities, Results Control Optim., 12 (2023), 100300. https://doi.org/10.1016/j.rico.2023.100300 doi: 10.1016/j.rico.2023.100300
    [18] Y. Guo, G. Ye, W. Liu, D. Zhao, S. Treanţǎ, Solving nonsmooth interval optimization problems based on interval-valued symmetric invexity, Chaos, Solitons Fractals, 174 (2023), 113834. https://doi.org/10.1016/j.chaos.2023.113834 doi: 10.1016/j.chaos.2023.113834
    [19] S. Treană, T. Saeed, On weak variational control inequalities via interval analysis, Mathematics, 11 (2023), 2177. https://doi.org/10.3390/math11092177 doi: 10.3390/math11092177
    [20] I. Hisao, T. Hideo, Multiobjective programming in optimization of the interval objective function, Eur. J. Oper. Res., 48 (1990), 219–225. https://doi.org/10.1016/0377-2217(90)90375-L doi: 10.1016/0377-2217(90)90375-L
    [21] S. T. Liu, R. T. Wang, A numerical solution method to interval quadratic programming, Appl. Math. Comput., 189 (2007), 1274–1281. https://doi.org/10.1016/j.amc.2006.12.007 doi: 10.1016/j.amc.2006.12.007
    [22] C. Jiang, X. Han, G. Liu, G. Liu, A nonlinear interval number programming method for uncertain optimization problems, Eur. J. Oper. Res., 188 (2008), 1–13. https://doi.org/10.1016/j.ejor.2007.03.031 doi: 10.1016/j.ejor.2007.03.031
    [23] A. Jayswal, I. Stancu-Minasian, I. Ahmad, On sufficiency and duality for a class of interval-valued programming problems, Appl. Math. Comput., 218 (2011), 4119–4127. https://doi.org/10.1016/j.amc.2011.09.041 doi: 10.1016/j.amc.2011.09.041
    [24] M. Hladık, Interval linear programming: a survey, in Linear Programming-New Frontiers in Theory and Applications, (2012), 85–120.
    [25] A. Bellet, Y. Liang, A. B. Garakani, M. F. Balcan, F. Sha, A distributed Frank-Wolfe algorithm for communication-efficient sparse learning, in Proceedings of the 2015 SIAM International Conference on Data Mining (SDM), (2015), 478–486. https://doi.org/10.1137/1.9781611974010.54
    [26] G. Qu, N. Li, Accelerated distributed Nesterov gradient descent, IEEE Trans. Autom. Control, 65 (2020), 2566–2581. https://doi.org/10.1109/TAC.2019.2937496 doi: 10.1109/TAC.2019.2937496
    [27] A. Nedic, A. Olshevsky, W. Shi, Achieving geometric convergence for distributed optimization over time-varying graphs, SIAM J. Optim., 27 (2017), 2597–2633. https://doi.org/10.1137/16M1084316 doi: 10.1137/16M1084316
    [28] S. Liang, L. Y. Wang, G. Yin, Exponential convergence of distributed primal–dual convex optimization algorithm without strong convexity, Automatica, 105 (2019), 298–306. https://doi.org/10.1016/j.automatica.2019.04.004 doi: 10.1016/j.automatica.2019.04.004
    [29] X. Yi, S. Zhang, T. Yang, K. H. Johansson, T. Chai, Exponential convergence for distributed optimization under the restricted secant inequality condition, IFAC-PapersOnLine, 53 (2020), 2672–2677. https://doi.org/10.1016/j.ifacol.2020.12.383 doi: 10.1016/j.ifacol.2020.12.383
    [30] S. Treană, Lu-optimality conditions in optimization problems with mechanical work objective functionals, IEEE Trans. Neural Networks Learn. Syst., 33 (2021), 4971–4978. https://doi.org/10.1109/TNNLS.2021.3066196 doi: 10.1109/TNNLS.2021.3066196
    [31] H. C. Wu, On interval-valued nonlinear programming problems, J. Math. Anal. Appl., 338 (2008), 299–316. https://doi.org/10.1016/j.jmaa.2007.05.023 doi: 10.1016/j.jmaa.2007.05.023
    [32] B. T. Polyak, Introduction to Optimization, Chapman and Hall, 1987.
    [33] R. Durrett, Probability: Theory and Examples, Cambridge University Press, 2010. https://doi.org/10.1017/CBO9780511779398
    [34] T. Maeda, On optimization problems with set-valued objective maps: existence and optimality, J. Optim. Theory Appl., 153 (2012), 263–279. https://doi.org/10.1007/s10957-011-9952-x doi: 10.1007/s10957-011-9952-x
    [35] A. K. Bhurjee, G. Panda, Efficient solution of interval optimization problem, Math. Methods Oper. Res., 76 (2012), 273–288. https://doi.org/10.1007/s00186-012-0399-0 doi: 10.1007/s00186-012-0399-0
    [36] S. S. Ram, A. Nedić, V. V. Veeravalli, Distributed stochastic subgradient projection algorithms for convex optimization, J. Optim. Theory Appl., 147 (2010), 516–545. https://doi.org/10.1007/s10957-010-9737-7 doi: 10.1007/s10957-010-9737-7
    [37] A. Nedic, A. Ozdaglar, Distributed subgradient methods for multi-agent optimization, IEEE Trans. Autom. Control, 54 (2009), 48–61. https://doi.org/10.1109/TAC.2008.2009515 doi: 10.1109/TAC.2008.2009515
    [38] A. P. Ruszczyński, A. Ruszczynski, Nonlinear Optimization, Princeton University Press, 2006. https://doi.org/10.1515/9781400841059
    [39] A. Nedic, A. Ozdaglar, P. A. Parrilo, Constrained consensus and optimization in multi-agent networks, IEEE Trans. Autom. Control, 55 (2010), 922–938. https://doi.org/10.1109/TAC.2010.2041686 doi: 10.1109/TAC.2010.2041686
    [40] A. Nedić, A. Olshevsky, Stochastic gradient-push for strongly convex functions on time-varying directed graphs, IEEE Trans. Autom. Control, 61 (2016), 3936–3947. https://doi.org/10.1109/TAC.2016.2529285 doi: 10.1109/TAC.2016.2529285
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

Metrics

Article views(850) PDF downloads(51) Cited by(0)

Article outline

Figures and Tables

Figures(6)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog