Skip to main content
SpringerLink
Log in

On Nesterov's Approach to Semi-infinite Programming

  • Published:
Acta Applicandae Mathematica Aims and scope Submit manuscript

Abstract

We generalize Nesterov's construction for the reduction of various classes of semi-infinite programming problems to the semidefinite programming form. In this way, we are able to consider ‘cones of squares’ of real-valued and matrix-valued functions as rather particular cases of a unifying abstract scheme. We also interpret from this viewpoint some results of M. Krein and A. Nudelman. This provides (in a way which probably has not been anticipated by these authors) a very powerful tool for solving various optimization problems.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Biggs, N. L.: Graphs with large girth, Ars Combin. C 25(1988), 73-80.

    Google Scholar 

  2. Biggs, N. L. and Boshier, A. G.: Note on the girth of Ramanujan graphs, J. Combin. Theory B 49(1990), 190-194.

    Google Scholar 

  3. Biggs, N. L. and Hoare, M. J.: The sextet construction for cubic graphs, Combinatorica 3(1983), 153-165.

    Google Scholar 

  4. Bollobás, B.: Extremal Graph Theory, Academic Press, London, 1978.

    Google Scholar 

  5. Bondy, J. A. and Simonovits, M.: Cycles of even length in graphs, J. Combin. Theory B 16(1974), 97-105.

    Google Scholar 

  6. Brower, A., Cohen, A. and Nuemaier, A.: Distance Regular Graphs, Springer, Berlin, 1989.

    Google Scholar 

  7. Brower, A. E.: The complement of a geometric hyperplane in a generalized polygon is usually connected, In: F. De Clerk et al.(eds), Finite Geometry and Combinatorics, London Math. Soc. Lecture Notes Ser. 191, Cambridge Univ. Press, 1993, pp. 53-57.

  8. Carter, R.W.:Simple Groups of Lie Type, Wiley, New York, 1972.

    Google Scholar 

  9. Coblitz, N.: A Course in Number Theory and Cryptography, 2nd edn, Springer, Berlin, 1994.

    Google Scholar 

  10. Coblitz, N.: Algebraic Aspects of Cryptography, Springer, Berlin, 1998.

    Google Scholar 

  11. Imrich, W.: Explicit construction of graphs without small cycles, Combinatorica 2(1984), 53-59.

    Google Scholar 

  12. Landau, S.: Standing the test of time: The data encryption standard, Notices Amer. Math. Soc., March 2000, pp. 341-349.

  13. Lazebnik, F. and Ustimenko, V.: Some Algebraic Constructions of Dense Graphs of Large Girth and of Large Size, Discrete Math. Theor. Comput. Sci. 10, Chapman and Hall, London, 1993, pp. 75-93.

    Google Scholar 

  14. Lazebnik, F. and Ustimenko, V.: Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Appl. Math. 60(1995), 275-284.

    Google Scholar 

  15. Lazebnik, F., Ustimenko, V. A. and Woldar, A. J.: A new series of dense graphs of high girth, Bull. Amer. Math. Soc. (NS) 32(1) (1995), 73-79.

    Google Scholar 

  16. Lazebnik, F., Ustimenko, V. A. and Woldar, A. J.: A characterization of the components of the graphs D(k,q), Discrete Math. 157(1996), 271-283.

    Google Scholar 

  17. Lubotzky, A.: Discrete Groups, Expanding Graphs and Invariant Measures, Progr. in Math. 125, Birkhäuser, Basel, 1994.

    Google Scholar 

  18. Lubotzky, A.: Cayley graphs, eigenvalues, expanders and random walks, In: Surveys in Combinatorics, London Math. Soc. Lecture Notes Ser. 218, Cambridge Univ. Press, 1995, pp. 155-190.

  19. Lubotsky, A., Philips, R. and Sarnak, P.: Ramanujan graphs, J. Combin. Theory 115(2) (1989), 62-89.

    Google Scholar 

  20. Magnus, W., Karrass, A. and Solitar, D.: Combinatorial Group Theory, Interscience Publ., New York, 1966.

    Google Scholar 

  21. Margulis, G. A.: Explicit construction of graphs without short cycles and low density codes, Combinatorica 2(1982), 71-78.

    Google Scholar 

  22. Margulis, G.: Explicit constructions of concentrators, Problems Inform. Transmissions 10(1975), 325-332.

    Google Scholar 

  23. Morgenstern, M.: Existence and explicit construction of q +1-regular Ramanujan graphs for every prime power q, J. Combin. Theory B 62(1994), 44-62.

    Google Scholar 

  24. Shannon, C.: Communication theory of secrecy systems, Bell. Syst. Tech. J. 28(1949), 656-715.

    Google Scholar 

  25. Stanton, D.: Generalized polygons and Chebychev polynomials, J. Combin. Theory A 34(1983), 15-27.

    Google Scholar 

  26. Serre, J.P.: Lie Algebras and Lie Groups, Lecture Notes in Math., Springer, Berlin, 1974.

    Google Scholar 

  27. Simonovitz, M.: Extremal graph theory, In: L. W. Beineke and R. J. Wilson (eds), Selected Topics in Graph Theory2, Academic Press, London, 1983, pp. 161-200.

    Google Scholar 

  28. Thas, J. A.: Generalized polygons, In: F. Buekenhout (ed.), Handbook on Incidence Geometry, North-Holland, Amsterdam, 1995, Ch. 9.

    Google Scholar 

  29. Tits, J.: Sur la trialité et certains groupes qui s'en déduisent, Publ. Math. IHES 2(1959), 15-20.

    Google Scholar 

  30. Tits, J.: Les groupes simples de Suzuki et de Ree, Seminaire Bourbaki 13(210) (1960/1961), 1-18.

    Google Scholar 

  31. Ustimenko, V.: On some properties of geometries Chevalley groups and their generalizations, In: Investigation in Algebraic Theory of Combinatorial Objects, Kluwer, Dordrecht, 1992, pp. 134-148.

    Google Scholar 

  32. Ustimenko, V. A.: Coordinatization of regular tree and its quotients, In: Voronoi's Impact in Modern Science(Proc. Memorial Voronoi Conference, Kiev, 1998), IM AN Ukraine, Kiev, 1998, pp. 125-152.

  33. Ustimenko, V. A.: Linear interpretation of Chevalley group flag geometries, Ukraine Math. J. 43(7, 8) (1991), 1055-1060 (in Russian).

    Google Scholar 

  34. Ustimenko, V. A.: Geometries of twisted simple groups of Lie type as objects of linear algebra, In: Questions of Group Theory and Homological Algebra, University of Jaroslavl, Jaroslavl, 1990, pp. 33-56 (in Russian).

    Google Scholar 

  35. Ustimenko, V. A.: On the varieties of parabolic subgroups, their generalizations and combina-torial applications, Acta Appl. Math. 52(1998), 223-238.

    Google Scholar 

  36. Ustimenko, V. and Sharma, D.: Special graphs in cryptography, In: Proc. 2000Internat. Workshop on Practice and Theory in Public Key Cryptography (PKC 2000), Melbourne, December 1.

  37. Ustimenko, V. and Sharma, D.: CRYPTIM: The system to encrypt text and image data, In: Proc. Internat. ICSC Congress on Intelligent Systems and Applications, December 2000, University of Wollongong.

  38. Ustimenko, V.: CRYPTIM: Graphs as tools for symmetric encryption, In: Lecture Notes in Comput. Sci. 2227, Springer, New York, pp. 278-287.

  39. Ustimenko, V.: On a group theoretical construction of expanding graphs, J. Group Theory(to appear).

  40. Ustimenko, V. and Woldar, A.: Extremal properties of regular and affine generalized m-gons as tactical configurations, Europ. J. Combin.(to appear).

  41. Valette, A.: Graphes de Ramanujan et applications, Seminaire BourbakiNo. 829, 1996-1997, pp. 1-23.

    Google Scholar 

  42. Weiss, A. L.: Girth of bipartite sextet graphs, Combinatorica4(2-3) (1984), 241-245.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556-4618, U.S.A, 255 Hurley Building

    Leonid Faybusovich

Authors
  1. Leonid Faybusovich
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Faybusovich, L. On Nesterov's Approach to Semi-infinite Programming. Acta Applicandae Mathematicae 74, 195–215 (2002). https://doi.org/10.1023/A:1020643711475

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1020643711475

Search

Navigation