Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

A DC programming approach for solving multicast network design problems via the Nesterov smoothing technique

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

This paper continues our recent effort in applying continuous optimization techniques to study optimalmulticast communication networks modeled as bilevel hierarchical clustering problems. Given a finite number of nodes, we consider two different models of multicast networks by identifying a certain number of nodes as cluster centers, and at the same time, locating a particular node that serves as a total center so as to minimize the total transportation cost throughout the network. The fact that the cluster centers and the total center have to be among the given nodes makes these problems discrete optimization problems. Our approach is to reformulate the discrete problems as continuous ones and to apply Nesterov’s smoothing approximation techniques on the Minkowski gauges that are used as distance measures. This approach enables us to propose two implementable DCA-based algorithms for solving the problems. Numerical results and practical applications are provided to illustrate our approach.

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.

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. An, L.T.H., Belghiti, M.T., Tao, P.D.: A new efficient algorithm based on DC programming and DCA for clustering. J. Glob. Optim.27, 503–608 (2007)

    MathSciNet MATH  Google Scholar 

  2. An, L.T.H., Minh, L.H., Tao, P.D.: New and efficient DCA based algorithms for minimum sum-of-squares clustering. Pattern Recognit.47, 388–401 (2014)

    Article  Google Scholar 

  3. An, L.T.H., Minh, L.H.: Optimization based DC programming and DCA for hierarchical clustering. Eur. J. Oper. Res.183, 1067–1085 (2007)

    Article MathSciNet  Google Scholar 

  4. An, L.T.H., Tao, P.D.: Convex analysis approach to D.C. programming: theory, algorithms and applications. Acta Math. Vietnam22, 289–355 (1997)

    MathSciNet MATH  Google Scholar 

  5. Bagirov, A.: Derivative-free methods for unconstrained nonsmooth optimization and its numerical analysis. Investig. Oper.19, 75–93 (1999)

    Google Scholar 

  6. Bagirov, A., Jia, L., Ouveysi, I., Rubinov, A.M.: Optimization based clustering algorithms in Multicast group hierarchies. In: Proceedings of the Australian Telecommunications, Networks and Applications Conference (ATNAC), Melbourne Australia (published on CD, ISNB 0-646-42229-4) (2003)

  7. Bagirov, A., Taheri, S., Ugon, J.: Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems. Pattern Recognit.53, 12–24 (2016)

    Article  Google Scholar 

  8. Barbosa, G. V., Villas-Boas, S. B., Xavier, A. E.: Solving the two-level clustering problem by hyperbolic smoothing approach, and design of multicast networks. In: Selected Proceedings, WCTR RIO (2013)

  9. Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I, II. Springer, Berlin (1993)

    Book  Google Scholar 

  10. Mordukhovich, B.S., Nam, N.M.: An Easy Path to Convex Analysis and Applications. Morgan & Claypool Publishers, San Rafael, CA (2014)

    MATH  Google Scholar 

  11. Nam, N.M., Rector, R.B., Giles, D.: Minimizing differences of convex functions with applications to facility location and clustering. J. Optim. Theory Appl.173, 255–278 (2017)

    Article MathSciNet  Google Scholar 

  12. Nam, N.M., Geremew, W., Reynolds, S., Tran, T.: The Nesterov smoothing technique and minimizing differences of convex functions for hierarchical clustering. Optim. Lett.12, 455–473 (2018)

    Article MathSciNet  Google Scholar 

  13. Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program.103, 127–152 (2005)

    Article MathSciNet  Google Scholar 

  14. Reinelt, G.: TSPLIB: a traveling salesman problem library. ORSA J. Comput.3, 376–384 (1991)

    Article  Google Scholar 

  15. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton, NJ (1970)

    Book  Google Scholar 

  16. Tao, P.D., An, L.T.H.: A d.c. optimization algorithm for solving the trust-region subproblem. SIAM J. Optim.8, 476–505 (1998)

    Article MathSciNet  Google Scholar 

Download references

Acknowledgements

This material is based upon work supported by the AFRL Mathematical Modeling and Optimization Institute. The authors are grateful to both anonymous referees for their helpful comments that allowed us to improve the original presentation.

Author information

Authors and Affiliations

  1. School of General Studies, Stockton University, Galloway, NJ, 08205, USA

    W. Geremew

  2. Fariborz Maseeh Department of Mathematics and Statistics, Portland State University, Portland, OR, 97207, USA

    N. M. Nam

  3. Faculty of Information Technology, University of Jyväskylä, P.O. Box 35, 40014, Jyväskylä, Finland

    A. Semenov

  4. Industrial Engineering & Management Systems, University of Central Florida, Orlando, FL, 32816, USA

    V. Boginski

  5. Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611, USA

    V. Boginski

  6. Munitions Directorate, Air Force Research Laboratory, Building 13, Eglin AFB, FL, 32542, USA

    E. Pasiliao

Authors
  1. W. Geremew

    You can also search for this author inPubMed Google Scholar

  2. N. M. Nam

    You can also search for this author inPubMed Google Scholar

  3. A. Semenov

    You can also search for this author inPubMed Google Scholar

  4. V. Boginski

    You can also search for this author inPubMed Google Scholar

  5. E. Pasiliao

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toN. M. Nam.

Additional information

Geremew’s research was partly supported by the AFRL Mathematical Modeling and Optimization Institute. Nam’s research was partly supported by the National Science Foundation under Grant DMS-1716057. Semenov’s research was partly supported by the European Office of Aerospace Research and Development under Grant FA9550-17-1-0030.

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Geremew, W., Nam, N.M., Semenov, A.et al. A DC programming approach for solving multicast network design problems via the Nesterov smoothing technique.J Glob Optim72, 705–729 (2018). https://doi.org/10.1007/s10898-018-0671-9

Download citation

Keywords

Mathematics Subject Classification

Access this article

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.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp