nach oben

Erschienen in:

2012 | OriginalPaper | Buchkapitel

9. Invariant Semidefinite Programs

verfasst von : Christine Bachoc, Dion C. Gijswijt, Alexander Schrijver, Frank Vallentin

Erschienen in: Handbook on Semidefinite, Conic and Polynomial Optimization

Verlag: Springer US

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This chapter provides the reader with the necessary background for dealing with semidefinite programs which have symmetry. The basic theory is given and it is illustrated in applications from coding theory, combinatorics, geometry, and polynomial optimization.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Copositive Programming

Nächstes Kapitel A “Joint+Marginal” Approach in Optimization

Andrews, G.E., Askey, R., Roy, R.: Special functions. Cambridge University Press, Cambridge (1999)

Astola, J.: The Lee-scheme and bounds for Lee-codes. Cybernet. Systems 13, 331–343 (1982)

Bachoc, C.: Linear programming bounds for codes in Grassmannian spaces. IEEE Trans. Inf. Th. 52, 2111–2125 (2006)

Bachoc, C.: Semidefinite programming, harmonic analysis and coding theory. arXiv:0909.4767 [cs.IT] (2009)

Bachoc, C., Vallentin, F.: New upper bounds for kissing numbers from semidefinite programming. J. Amer. Math. Soc. 21, 909–924 (2008)

Bachoc, C., Vallentin, F.: Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps, special issue in the honor of Eichii Bannai, Europ. J. Comb. 30 625–637 (2009)

Bachoc, C., Vallentin, F.: More semidefinite programming bounds (extended abstract). pages 129–132 in Proceedings “DMHF 2007: COE Conference on the Development of Dynamic Mathematics with High Functionality”, October 2007, Fukuoka, Japan. (2007)

Bachoc, C., Vallentin, F.: Optimality and uniqueness of the (4,10,1/6) spherical code. J. Comb. Theory Ser. A 116, 195–204 (2009)

Bachoc, C., Zémor, G.: Bounds for binary codes relative to pseudo-distances of k points. Adv. Math. Commun. 4, 547–565 (2010)

10.

Bachoc, C., Nebe G., de Oliveira Filho, F.M., Vallentin, F.: Lower bounds for measurable chromatic numbers. Geom. Funct. Anal. 19,645–661 (2009)

11.

Bai, Y., de Klerk, E., Pasechnik, D.V., Sotirov, R.: Exploiting group symmetry in truss topology optimization. Optimization and Engineering 10, 331–349 (2009)

12.

Bannai, E., Ito, T.: Algebraic combinatorics. I.. The Benjamin/Cummings Publishing Co. Inc., Menlo Park, CA (1984)

13.

Barg, A., Purkayastha, P.: Bounds on ordered codes and orthogonal arrays. Moscow Math. Journal 9, 211–243 (2009)

14.

Barvinok, A.: A course in convexity. Graduate Studies in Mathematics 54, American Mathematical Society (2002)

15.

Berger, M.: A Panoramic View of Riemannian Geometry. Springer-Verlag (2003)

16.

Bochner, S.: Hilbert distances and positive definite functions. Ann. of Math. 42, 647–656 (1941)

17.

Bosse, H.: Symmetric, positive polynomials, which are not sums of squares. Series: CWI. Probability, Networks and Algorithms [PNA], Nr. E0706 (2007)

18.

Boyd, S., Diaconis, P., Parrilo, P.A., Xiao, L.: Symmetry analysis of reversible Markov chains. Internet Mathematics 2, (2005)

19.

Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-regular graphs. Springer-Verlag, Berlin (1989)

20.

Bump, D.: Lie Groups. Graduate Text in Mathematics 225, Springer-Verlag (2004)

21.

Cameron, P. J.: Coherent configurations, association schemes and permutation groups. pages 55–71 in Groups, combinatorics & geometry (Durham, 2001), World Sci. Publishing, River Edge, NJ (2003)

22.

Cimpric̆, J.: A method for computing lowest eigenvalues of symmetric polynomial differential operators by semidefinite programming. J. Math. Anal. Appl. 369, 443–452 (2010)

23.

Cimpric̆, J., Kuhlmann, S., Scheiderer, C.: Sums of squares and moment problems in equivariant situations. Trans. Amer. Math. Soc. 361, 735–765 (2009).

24.

Conway, J.B.: A course in functional analysis. Graduate Text in Mathematics 96, Springer-Verlag (2007)

25.

Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups. third edition, Springer-Verlag, New York (1999)

26.

Creignou, J., Diet, H.: Linear programming bounds for unitary codes. Adv. Math. Commun. 4, 323–344 (2010)

27.

Davidson, K.R.: C*-Algebras by Example. Fields Institute Monographs 6, American Mathematical Society (1996)

28.

Delsarte, P.: An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl. (1973)

29.

Delsarte, P., Goethals, J. M.: Alternating bilinear forms over GF(q). J. Comb. Th. A 19, 26–50 (1975)

30.

Delsarte, P.: Hahn polynomials, discrete harmonics and t-designs. SIAM J. Appl. Math. 34, 157–166 (1978)

31.

Delsarte, P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Th. A 25, 226–241 (1978)

32.

Delsarte, P., Goethals, J.M., Seidel, J.J.: Spherical codes and designs. Geom. Dedicata 6, 363–388 (1977)

33.

de Klerk, E., Dobre, C., Pasechnik, D.V.: Numerical block diagonalization of matrix *-algebras with application to semidefinite programming. To appear in Math. Program., Ser. B. (2009)

34.

Duffin, R.J.: Infinite Programs. In: H.W. Kuhn, A.W. Tucker (eds.) Linear inequalities and related systems, Princeton Univ. Press, 157–170 (1956)

35.

Dunkl, C.F.: A Krawtchouk polynomial addition theorem and wreath product of symmetric groups. Indiana Univ. Math. J. 25, 335–358 (1976)

36.

Ericson, T., Zinoviev, V.: Codes on Euclidean spheres. North-Holland (2001)

37.

Gatermann, K., Parrilo, P.A.: Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Alg. 192, 95–128 (2004)

38.

Gijswijt, D.C.: Matrix Algebras and Semidefinite Programming Techniques for Codes. Dissertation, University of Amsterdam (2005)

39.

Gijswijt, D.C.: Block diagonalization for algebra’s associated with block codes. arXiv:0910.4515 [math.OC] (2009)

40.

Gijswijt, D.C., Mittelmann, H.D., Schrijver, A.: Semidefinite code bounds based on quadruple distances. arXiv.math:1005.4959 [math.CO] (2010)

41.

Gijswijt, D.C., Schrijver, A., Tanaka, H.: New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming. J. Comb. Theory Ser. A 113, 1719–1731 (2006)

42.

Goemans, M.X., Williamson, D.P.: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. J. Comput. System Sci. 68, 442–470 (2004)

43.

Gvozdenović, N.: Approximating the stability number and the chromatic number of a graph via semidefinite programming. Dissertation, University of Amsterdam (2008)

44.

Gvozdenović, N., Laurent, M.: The operator Ψ for the chromatic number of a graph. SIAM J. Optim. 19, 572–591 (2008)

45.

Gvozdenović, N., Laurent, M.: Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization. SIAM J. Optim. 19, 592–615 (2008)

46.

Gvozdenović, N., Laurent, M., Vallentin, F.: Block-diagonal semidefinite programming hierarchies for 0/1 programming. Oper. Res. Lett. 37, 27–31 (2009)

47.

Horn, R.A., Johnson, C.R.: Matrix analysis. Cambridge University Press, Cambridge (1990)

48.

James, A.T., Constantine, A.G.: Generalized Jacobi polynomials as spherical functions of the Grassmann manifold. Proc. London Math. Soc. 29, 174–192 (1974)

49.

Jansson, L., Lasserre, J.B., Riener, C., Theobald, T.: Exploiting symmetries in SDP-relaxations for polynomial optimization. Optimization Online, September 2006, (2006)

50.

Kabatiansky, G.A., Levenshtein, V.I.: Bounds for packings on a sphere and in space. Problems of Information Transmission 14, 1–17 (1978)

51.

Kanno, Y., Ohsaki, M., Murota, K., Katoh, N.: Group symmetry in interior-point methods for semidefinite program. Optimization and Engineering 2, 293–320 (2001)

52.

Kleitman, D.J.: The crossing number of K_5, n. J. Comb. Theory Ser. B 9, 315–323 (1970)

53.

de Klerk, E.: Exploiting special structure in semidefinite programming: A survey of theory and applications. European Journal of Operational Research 201, 1–10 (2010)

54.

de Klerk, E., Maharry, J., Pasechnik, D.V., Richter, R.B., Salazar, G.: Improved bounds for the crossing numbers of K_m, n and K_n. SIAM J. Disc. Math. 20, 189–202 (2006)

55.

de Klerk, E., Newman, M.W., Pasechnik, D.V., Sotirov R.: On the Lovasz θ-number of almost regular graphs with application to Erdős-Rényi graphs. European J. Combin. 31, 879–888 (2009)

56.

de Klerk, E., Pasechnik, D.V.: Solving SDP’s in non-commutative algebras part I: the dual-scaling algorithm. Discussion paper from Tilburg University, Center for economic research (2005)

57.

de Klerk, E., Pasechnik, D.V.: A note on the stability number of an orthogonality graph. European J. Combin. 28, 1971–1979 (2007)

58.

de Klerk, E., Pasechnik, D.V., Schrijver, A.: Reduction of symmetric semidefinite programs using the regular ∗ -representation. Math. Program., Ser. B 109, 613–624 (2007)

59.

de Klerk, E., Pasechnik, D.V., Sotirov, R.: On Semidefinite Programming Relaxations of the Travelling Salesman Problem. Discussion paper from Tilburg University, Center for economic research (2007)

60.

de Klerk, E., Sotirov, R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Program. Ser. A 122, 225–246 (2010)

61.

Knuth, D.E.: The sandwich theorem. Electron. J. Combin. 1, (1994)

62.

Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0/1 programs. In: K. Aardal and A.M.H. Gerards (eds.) Lecture Notes in Computer Science 2081 (2001)

63.

Laurent, M.: Strengthened semidefinite programming bounds for codes. Math. Program. Ser. B 109, 239–261 (2007)

64.

Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: M. Putinar, S. Sullivant (eds.) Emerging Applications of Algebraic Geometry, Vol. 149 of IMA Volumes in Mathematics and its Applications, Springer-Verlag (2009)

65.

Levenshtein, V.I.: Universal bounds for codes and designs. In: V. Pless, W. C. Huffmann (eds.) Handbook of Coding Theory, Elsevier, Amsterdam (1998)

66.

Linial, N., Magen, A., Naor, A.: Girth and Euclidean Distortion. Geom. Funct. Anal. 12 380–394 (2002)

67.

Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25, 1–5 (1979)

68.

MacWilliams, F.J., Sloane, N.J.A.: The theory of error-correcting codes. North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford (1977)

69.

Martin, W.J., Stinson, D.R.: Association schemes for ordered orthogonal arrays and (T, M, S)-nets. Canad. J. Math. 51, 326–346 (1999)

70.

McEliece, R.J., Rodemich, E.R., Rumsey, Jr, H.C.: The Lovász bound and some generalizations. J. Combinatorics, Inform. Syst. Sci. 3, 134–152 (1978)

71.

Mittelmann, H.D., Vallentin, F.: High accuracy semidefinite programming bounds for kissing numbers. Experiment. Math. 19, 174–178 (2010)

72.

Murota, K., Kanno, Y., Kojima, M., Kojima, S.: A numerical algorithm for block-diagonal decomposition of matrix *-algebras, Part I: proposed approach and application to semidefinite programming. Jpn. J. Ind. Appl. Math. 27, 125–160 (2010)

73.

Musin, O.R.: Multivariate positive definite functions on spheres. arXiv:math/0701083 [math.MG] (2007)

74.

Nemirovski, A.: Advances in convex optimization: Conic programming. In: M. Sanz-Sol, J. Soria, J.L. Varona, J. Verdera, (eds.) Proceedings of International Congress of Mathematicians, Madrid, August 22-30, 2006, Volume 1, European Mathematical Society Publishing House (2007)

75.

Odlyzko, A.M., Sloane, N.J.A.: New bounds on the number of unit spheres that can touch a unit sphere in n dimensions. J. Comb. Theory Ser. A 26, 210–214 (1979)

76.

de Oliveira Filho, F.M.: New Bounds for Geometric Packing and Coloring via Harmonic Analysis and Optimization. Dissertation, University of Amsterdam (2009)

77.

de Oliveira Filho, F.M., Vallentin, F.: Fourier analysis, linear programming, and densities of distance avoiding sets in \({\mathbb{R}}^{n}\). J. Eur. Math. Soc. (JEMS) 12, 1417–1428 (2010)

78.

Pasechnik, D.V., Kini, K.: A GAP package for computation with coherent configurations. In: K. Fukuda, J. van der Hoeven, M. Joswig, N. Takayama (eds.) Mathematical Software — ICMS 2010 LNCS 6327, Springer (2010)

79.

Roy, A., Scott, A. J.: Unitary designs and codes. Des. Codes Cryptogr. 53, 13–31 (2009)

80.

Roy, A.: Bounds for codes and designs in complex subspaces. arXiv:0806.2317 [math.CO] (2008)

81.

Rudin, W.: Real and Complex Analysis. McGraw-Hill International Editions (1987)

82.

Schoenberg, I.J.: Positive definite functions on spheres. Duke Math. J. 9, 96–108 (1942)

83.

Schrijver, A.: Association schemes and the Shannon capacity: Eberlein polynomials and the Erdős-Ko-Rado theorem. Algebraic methods in graph theory Vol. I, II (Szeged, 1978), pp. 671–688, Colloq. Math. Soc. János Bolyai 25, North-Holland, Amsterdam-New York (1981)

84.

Schrijver, A.: New code upper bounds from the Terwilliger algebra and semidefinite programming. IEEE Trans. Inform. Theory 51, 2859–2866 (2005)

85.

Soifer, A.: The mathematical coloring book. Springer-Verlag (2008)

86.

Stanton, D.: Orthogonal polynomials and Chevalley groups. In: R.A. Askey, T.H. Koornwinder, W. Schempp (eds.) Special functions: group theoretical aspects and applications, Reidel Publishing Compagny (1984)

87.

Sturm, J.F.: Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones. Optimization Methods and Software 11, 625–653 (1999)

88.

Sturmfels, B.: Algorithms in Invariant Theory. Springer-Verlag (1993)

89.

Szegö, G.: Orthogonal polynomials. American Mathematical Society (1939)

90.

Takesaki, M.: Theory of Operator Algebras I. Encyclopaedia of Mathematical Sciences, 124. Operator Algebras and Non-commutative Geometry, 5. Springer-Verlag, Berlin, (2002)

91.

Tarnanen, H., Aaltonen, M., Goethals J.M.: On the nonbinary Johnson scheme. European J. Combin. 6, 279–285 (1985)

92.

Tarnanen, H.: Upper bounds on permutation codes via linear programming. European J. Combin. 20, 101–114 (1999)

93.

Vallentin, F.: Optimal embeddings of distance transitive graphs into Euclidean spaces. J. Comb. Theory Ser. B 98, 95–104 (2008)

94.

Vallentin, F.: Symmetry in semidefinite programs. Linear Algebra and Appl. 430, 360–369 (2009)

95.

Vallentin, F.: Lecture notes: Semidefinite programs and harmonic analysis. arXiv:0809.2017 [math.OC] (2008)

96.

Vilenkin, N.Ja., Klimyk, A.U.: Representation of Lie Groups and Special Functions, Volume 2. Kluwer Academic Publishers (1993)

97.

Wang, H.G.: Two-point homogeneous spaces. Ann. of Math. 55, 177–191 (1952)

98.

Woodall, D.R.: Cyclic-order graphs and Zarankiewicz’s crossing-number conjecture. J. Graph Theory 17, 657–671 (1993)

99.

Zarankiewicz, K.: On a problem of P. Turán concerning graphs. Fundamenta Mathematicae 41, 137–145 (1954)

Titel: Invariant Semidefinite Programs
verfasst von: Christine Bachoc
Dion C. Gijswijt
Alexander Schrijver
Frank Vallentin
Verlag: Springer US
Buch: Handbook on Semidefinite, Conic and Polynomial Optimization
Print ISBN: 978-1-4614-0768-3

Electronic ISBN: 978-1-4614-0769-0

Copyright-Jahr: 2012
DOI: https://doi.org/10.1007/978-1-4614-0769-0_9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Premium Partner