×

zbMATH — the first resource for mathematics

Symmetry groups, semidefinite programs, and sums of squares. (English) Zbl 1108.13021
Summary: We investigate the representation of multivariate symmetric polynomials as sum of squares, as well as the effective computation of this decomposition. Since this task is solved using semidefinite programming tools we explore the geometric, algebraic, and computational implications of the presence of discrete symmetries in semidefinite programs. It is shown that symmetry exploitation allows a significant reduction in both matrix size and number of decision variables. The results, reinterpreted from an invariant-theoretic viewpoint, provide a novel representation of a class of nonnegative symmetric polynomials. For this, we introduce a common generalization of sum of squares polynomials and positive semidefinite matrices, termed “sum of squares matrices.” The main theorem states that an invariant sum of squares polynomial is a sum of inner products of pairs of matrices, whose entries are invariant polynomials. In these pairs, one of the matrices is computed based on the real irreducible representations of the group, and the other is a sum of squares matrix. The reduction techniques enable the numerical solution of large-scale instances, otherwise computationally infeasible to solve.

MSC:
13J30 Real algebra
68W30 Symbolic computation and algebraic computation
90C22 Semidefinite programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Choi, M.D., Positive semidefinite biquadratic forms, Linear algebra appl., 12, 95-100, (1975) · Zbl 0336.15014
[2] Choi, M.D.; Lam, T.Y., Extremal positive semidefinite forms, Math. ann., 231, 1-18, (1977) · Zbl 0347.15009
[3] Choi, M.D.; Lam, T.Y.; Reznick, B., Real zeros of positive semidefinite forms I, Math. Z., 171, 1, 1-26, (1980) · Zbl 0415.10018
[4] Choi, M.D.; Lam, T.Y.; Reznick, B., Even symmetric sextics, Math. Z., 195, 4, 559-580, (1987) · Zbl 0654.10024
[5] C.F. Cid, W. Plesken, Invariants of finite groups and involutive division, in: V.G. Ganzha (Ed.), Computer Algebra in Scientific Computing, CASC 2001. Proceedings of the Fourth International Workshop, Springer, Berlin, 2001, pp. 123-135. · Zbl 1002.13002
[6] H. Derksen, G. Kemper, Computational Invariant Theory, Encyclopaedia of Mathematical Sciences, Vol. 130, Springer, Berlin, 2002. · Zbl 1011.13003
[7] Fässler, A.; Stiefel, E., Group theoretical methods and their applications, (1992), Birkhäuser Basel · Zbl 0769.20002
[8] The GAP Group, GAP—Groups, Algorithms, and Programming, Version 4.2, 2000, available at .
[9] Gatermann, K., Semi-invariants, equivariants and algorithms, Appl. algebra engrg. comm. comput., 7, 105-124, (1996) · Zbl 0845.13009
[10] K. Gatermann, Computer Algebra Methods for Equivariant Dynamical Systems, Lecture Notes in Mathematics, Vol. 1728, Springer, Berlin, 2000. · Zbl 0944.65131
[11] K. Gatermann, F. Guyard, The symmetry package in Maple, 1998-2000, available at .
[12] M. Golubitsky, I. Stewart, D.G. Schaeffer, Singularities and Groups in Bifurcation Theory II, Applied Mathematical Sciences, Vol. 69, Springer, New York, 1988. · Zbl 0691.58003
[13] D.R. Grayson, M.E. Stillman, Macaulay 2, a software system for research in algebraic geometry, available at .
[14] G.D. James, The Representation Theory of the Symmetric Groups, Lecture Notes in Mathematics, Vol. 682, Springer, Berlin, 1978. · Zbl 0393.20009
[15] Kanno, Y.; Ohsaki, M.; Murota, K.; Katoh, N., Group symmetry in interior-point methods for semidefinite programming, Optim. engrg., 2, 293-320, (2001) · Zbl 1035.90056
[16] G. Kemper, Invar, a maple package for invariant theory of finite groups, see .
[17] Lasserre, J.B., Global optimization with polynomials and the problem of moments, SIAM J. optim., 11, 3, 796-817, (2001) · Zbl 1010.90061
[18] J.E. Marsden, T. Ratiu, Introduction to Mechanics and Symmetry, Texts in Applied Mathematics, Vol. 17, 2nd Edition, Springer, Berlin, 1999. · Zbl 0933.70003
[19] Nesterov, Y., Squared functional systems and optimization problems, (), 405-440 · Zbl 0958.90090
[20] P.A. Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization, Ph.D. Thesis, California Institute of Technology, May 2000, available at .
[21] Parrilo, P.A., Semidefinite programming relaxations for semialgebraic problems, Math. programming, 96, 2, Ser. B, 293-320, (2003) · Zbl 1043.14018
[22] P.A. Parrilo, B. Sturmfels, Minimizing polynomial functions, in: S. Basu, L. González-Vega (Eds.), Algorithmic and Quantitative Real Algebraic Geometry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 60, American Mathematical Society, Providence, RI, 2003, available from . · Zbl 1099.13516
[23] Powers, V.; Wörmann, T., An algorithm for sums of squares of real polynomials, J. pure appl. algebra, 127, 99-104, (1998) · Zbl 0936.11023
[24] S. Prajna, A. Papachristodoulou, P.A. Parrilo, SOSTOOLS: Sum of squares optimization toolbox for MATLAB, 2002, available from and http://control.ee.ethz.ch/ parrilo/sostools.
[25] Procesi, C., Positive symmetric functions, Adv. math., 29, 219-225, (1978) · Zbl 0383.12013
[26] B. Reznick, Some concrete aspects of Hilbert’s 17th problem, Contemporary Mathematics, Vol. 253, American Mathematical Society, Providence, RI, 2000, pp. 251-272. · Zbl 0972.11021
[27] Serre, J.-P., Linear representations of finite groups, (1977), Springer Berlin
[28] Shor, N.Z., Class of global minimum bounds of polynomial functions, Cybernetics, 23, 6, 731-734, (1987), (Russian orig.: Kibernetika 6 (1987) (9-11) · Zbl 0648.90058
[29] Sottile, F., Real Schubert calculuspolynomial systems and a conjecture of Shapiro and Shapiro, Exp. math., 9, 2, 161-182, (2000) · Zbl 0997.14016
[30] Stanley, R.P., Invariants of finite groups and their applications to combinatorics, Bull. amer. math. soc., 1, 475-511, (1979) · Zbl 0497.20002
[31] B. Sturmfels, Algorithms in Invariant Theory, Texts and Monographs in Symbolic Computation, Vol. 1, Springer, Wien, 1993.
[32] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lectures, Vol. 8, American Mathematical Society, Providence, RI, 1995.
[33] Sturmfels, B., Solving systems of polynomial equations, (2002), American Mathematical Society Providence, RI · Zbl 1101.13040
[34] H. Wolkowicz, R. Saigal, L. Vandenberghe (Eds.), Handbook of Semidefinite Programming, Kluwer, Dordrecht, 2000. · Zbl 0962.90001
[35] Worfolk, P., Zeros of equivariant vector fieldsalgorithms for an invariant approach, J. symbolic comput., 17, 487-511, (1994) · Zbl 0819.13013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.