IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v191y2021i1d10.1007_s10957-021-01933-9.html
   My bibliography  Save this article

Sparse Network Optimization for Synchronization

Author

Listed:
  • Regina S. Burachik

    (University of South Australia)

  • Alexander C. Kalloniatis

    (Defence Science and Technology Group)

  • C. Yalçın Kaya

    (University of South Australia)

Abstract

We propose new mathematical optimization models for generating sparse dynamical graphs, or networks, that can achieve synchronization. The synchronization phenomenon is studied using the Kuramoto model, defined in terms of the adjacency matrix of the graph and the coupling strength of the network, modelling the so-called coupled oscillators. Besides sparsity, we aim to obtain graphs which have good connectivity properties, resulting in small coupling strength for synchronization. We formulate three mathematical optimization models for this purpose. Our first model is a mixed integer optimization problem, subject to ODE constraints, reminiscent of an optimal control problem. As expected, this problem is computationally very challenging, if not impossible, to solve, not only because it involves binary variables but also some of its variables are functions. The second model is a continuous relaxation of the first one, and the third is a discretization of the second, which is computationally tractable by employing standard optimization software. We design dynamical graphs that synchronize, by solving the relaxed problem and applying a practical algorithm for various graph sizes, with randomly generated intrinsic natural frequencies and initial phase variables. We test robustness of these graphs by carrying out numerical simulations with random data and constructing the expected value of the network’s order parameter and its variance under this random data, as a guide for assessment.

Suggested Citation

  • Regina S. Burachik & Alexander C. Kalloniatis & C. Yalçın Kaya, 2021. "Sparse Network Optimization for Synchronization," Journal of Optimization Theory and Applications, Springer, vol. 191(1), pages 229-251, October.
  • Handle: RePEc:spr:joptap:v:191:y:2021:i:1:d:10.1007_s10957-021-01933-9
    DOI: 10.1007/s10957-021-01933-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-021-01933-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10957-021-01933-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kalloniatis, Alexander C. & McLennan-Smith, Timothy A. & Roberts, Dale O., 2020. "Modelling distributed decision-making in Command and Control using stochastic network synchronisation," European Journal of Operational Research, Elsevier, vol. 284(2), pages 588-603.
    2. Nahid Banihashemi & C. Yalçın Kaya, 2013. "Inexact Restoration for Euler Discretization of Box-Constrained Optimal Control Problems," Journal of Optimization Theory and Applications, Springer, vol. 156(3), pages 726-760, March.
    3. C. Kaya & Helmut Maurer, 2014. "A numerical method for nonconvex multi-objective optimal control problems," Computational Optimization and Applications, Springer, vol. 57(3), pages 685-702, April.
    4. C. Y. Kaya & J. M. Martínez, 2007. "Euler Discretization and Inexact Restoration for Optimal Control," Journal of Optimization Theory and Applications, Springer, vol. 134(2), pages 191-206, August.
    5. Anthony Dekker, 2007. "Studying Organisational Topology with Simple Computational Models," Journal of Artificial Societies and Social Simulation, Journal of Artificial Societies and Social Simulation, vol. 10(4), pages 1-6.
    6. Walter Alt & C. Yalçın Kaya & Christopher Schneider, 2016. "Dualization and discretization of linear-quadratic control problems with bang–bang solutions," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(1), pages 47-77, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. C. Yalçın Kaya, 2017. "Markov–Dubins path via optimal control theory," Computational Optimization and Applications, Springer, vol. 68(3), pages 719-747, December.
    2. C. Yalçın Kaya, 2019. "Markov–Dubins interpolating curves," Computational Optimization and Applications, Springer, vol. 73(2), pages 647-677, June.
    3. L. F. Bueno & G. Haeser & J. M. Martínez, 2015. "A Flexible Inexact-Restoration Method for Constrained Optimization," Journal of Optimization Theory and Applications, Springer, vol. 165(1), pages 188-208, April.
    4. Cui, Yunfei & Geng, Zhiqiang & Zhu, Qunxiong & Han, Yongming, 2017. "Review: Multi-objective optimization methods and application in energy saving," Energy, Elsevier, vol. 125(C), pages 681-704.
    5. Antoine Nongaillard & Philippe Mathieu, 2011. "Reallocation Problems in Agent Societies: A Local Mechanism to Maximize Social Welfare," Journal of Artificial Societies and Social Simulation, Journal of Artificial Societies and Social Simulation, vol. 14(3), pages 1-5.
    6. Kalloniatis, Alexander C. & McLennan-Smith, Timothy A. & Roberts, Dale O., 2020. "Modelling distributed decision-making in Command and Control using stochastic network synchronisation," European Journal of Operational Research, Elsevier, vol. 284(2), pages 588-603.
    7. Elijah Polak & Seungho Lee & Ismail Bustany & Akshay Madhan, 2016. "Method of Outer Approximations and Adaptive Approximations for a Class of Matrix Games," Journal of Optimization Theory and Applications, Springer, vol. 170(3), pages 876-899, September.
    8. Cullen, Andrew C. & Alpcan, Tansu & Kalloniatis, Alexander C., 2022. "Adversarial decisions on complex dynamical systems using game theory," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 594(C).
    9. Nguyen Thi Toan & Le Quang Thuy, 2023. "S-Derivative of the Extremum Multifunction to a Multi-objective Parametric Discrete Optimal Control Problem," Journal of Optimization Theory and Applications, Springer, vol. 196(1), pages 240-265, January.
    10. Alt, Walter & Schneider, Christopher & Seydenschwanz, Martin, 2016. "Regularization and implicit Euler discretization of linear-quadratic optimal control problems with bang-bang solutions," Applied Mathematics and Computation, Elsevier, vol. 287, pages 104-124.
    11. Bui Trong Kien & Trinh Duy Binh, 2023. "On the second-order optimality conditions for multi-objective optimal control problems with mixed pointwise constraints," Journal of Global Optimization, Springer, vol. 85(1), pages 155-183, January.
    12. C. Kaya & Helmut Maurer, 2014. "A numerical method for nonconvex multi-objective optimal control problems," Computational Optimization and Applications, Springer, vol. 57(3), pages 685-702, April.
    13. Owen Davis & Siavash Radpour, 2022. "Older Workers’ Wages Are Growing—But Not Fast Enough," SCEPA publication series. 2022-02, Schwartz Center for Economic Policy Analysis (SCEPA), The New School.
    14. Andreas Lichtenberger & Joao Paulo Braga & Willi Semmler, 2022. "Green Bonds for the Transition to a Low-Carbon Economy," Econometrics, MDPI, vol. 10(1), pages 1-31, March.
    15. Andreas Lichtenberger & Joao Paulo Braga & Willi Semmler, 2022. "Green Bonds for the Transition to a Low-Carbon Economy," SCEPA working paper series. 2022-02, Schwartz Center for Economic Policy Analysis (SCEPA), The New School.
    16. E. G. Birgin & L. F. Bueno & J. M. Martínez, 2016. "Sequential equality-constrained optimization for nonlinear programming," Computational Optimization and Applications, Springer, vol. 65(3), pages 699-721, December.
    17. Qun Lin & Ryan Loxton & Kok Teo & Yong Wu, 2015. "Optimal control problems with stopping constraints," Journal of Global Optimization, Springer, vol. 63(4), pages 835-861, December.
    18. Stephan Dempe & Gabriele Eichfelder & Jörg Fliege, 2015. "On the effects of combining objectives in multi-objective optimization," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(1), pages 1-18, August.
    19. C. Yalçın Kaya, 2020. "Optimal Control of the Double Integrator with Minimum Total Variation," Journal of Optimization Theory and Applications, Springer, vol. 185(3), pages 966-981, June.
    20. Nguyen Thi Toan & Le Quang Thuy & Nguyen Tuyen & Yi-Bin Xiao, 2021. "Second-order KKT optimality conditions for multiobjective discrete optimal control problems," Journal of Global Optimization, Springer, vol. 79(1), pages 203-231, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:191:y:2021:i:1:d:10.1007_s10957-021-01933-9. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.