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