Decentralized Conditional Gradient Method on Time-Varying Graphs | Programming and Computer Software Skip to main content
Springer Nature Link
Log in

Decentralized Conditional Gradient Method on Time-Varying Graphs

  • Published:
Programming and Computer Software Aims and scope Submit manuscript

Abstract

In this paper, we consider a generalization of the decentralized Frank–Wolfe algorithm to time-varying networks, investigate the convergence properties of the algorithm, and carry out the corresponding numerical experiments. The time-varying network is modeled as a deterministic or stochastic sequence of graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1.
Fig. 2.

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

REFERENCES

  1. Braun, G., Carderera, A., Combettes, C.W., Hassani, H., Karbasi, A., Mokhtari, A., and Pokutta, S., Conditional Gradient Methods, 2022. https://arxiv.org/pdf/2211.14103.pdf.

  2. Levitin, E.S. and Polyak, B.T., Constrained minimization methods, Zh. Vychisl. Mat. Mat. Fiz., 1966, pp. 787–823.

  3. Nedic, A., Distributed gradient methods for convex machine learning problems in networks: Distributed optimization, IEEE Signal Process. Mag., 2020, pp. 92–101.

  4. Forero, P.A., Cano, F., and Giannakis, G.B., Consensus-based distributed linear support vector machines, Proc. 9th ACM/IEEE Int. Conf. Information Processing in Sensor Networks, 2010.

  5. Gan, L., Topcu, U., and Low, S.H., Optimal decentralized protocol for electric vehicle charging, IEEE Trans. Power Syst., 2012, pp. 940–951.

  6. Ram, S.S., Veeravalli, V.V., and Nedic, A., Distributed non-autonomous power control through distributed convex optimization, Proc. IEEE INFOCOM, 2009.

  7. Ren, W. and Beard, R.W., Distributed consensus in multi-vehicle cooperative control, 2008, vol. 27, no. 2.

  8. Rogozin, A., Gasnikov, A., Beznosikov, A., and Kovalev, D., Decentralized convex optimization over time-varying graphs: A survey, 2022. https://arxiv.org/pdf/2210.09719.pdf.

  9. Wai, Hoi-To, et al., Decentralized Frank–Wolfe algorithm for convex and nonconvex problems, IEEE Trans. Autom. Control, 2017, pp. 5522–5537.

  10. Raigorodskii, A.M., Models of random graphs and their applications, Tr. Mosk. Fiz.-Tekh. Inst., 2010.

    Google Scholar 

Download references

Funding

This work was supported by the Russian Science Foundation, project no. 23-11-00229 (https://rscf.ru/en/project/23-11-00229).

Author information

Authors and Affiliations

  1. Moscow Institute of Physics and Technology, Institutskii per. 9, 141701, Dolgoprudny, Russia

    R. A. Vedernikov & A. V. Rogozin

  2. Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Bol’shoi Karetnyi per. 19/1, 127051, Moscow, Russia

    A. V. Gasnikov

  3. Caucasian Mathematical Center of the Adyghe State University, ul. Pervomaiskaya 208, 385016, Maykop, Russia

    A. V. Gasnikov

Authors
  1. R. A. Vedernikov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. V. Rogozin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. A. V. Gasnikov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to R. A. Vedernikov, A. V. Rogozin or A. V. Gasnikov.

Ethics declarations

The authors declare that they have no conflicts of interest.

Additional information

Translated by Yu. Kornienko

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Vedernikov, R.A., Rogozin, A.V. & Gasnikov, A.V. Decentralized Conditional Gradient Method on Time-Varying Graphs. Program Comput Soft 49, 505–512 (2023). https://doi.org/10.1134/S0361768823060075

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0361768823060075

Search

Navigation