Certifying the Global Optimality of Quartic Minimization over the Sphere

doi:10.1007/s40305-021-00347-8

Abstract

Abstract: The quartic minimization over the sphere is an NP-hard problem in the general case. There exist various methods for computing an approximate solution for any given instance. In practice, it is quite often that a global optimal solution was found but without a certification. We will present in this article two classes of methods which are able to certify the global optimality, i.e., algebraic methods and semidefinite program (SDP) relaxation methods. Several advances on these topics are summarized, accompanied with some emerged new results. We want to emphasize that for mediumor large-scaled instances, the problem is still a challenging one, due to an apparent limitation on the current force for solving SDP problems and the intrinsic one on the approximation techniques for the problem.

Key words: Quartic minimization, Tensor, Sphere, Global optimality, Elimination method, Critical points, Eigenvectors, Determinant, Nondegenerate, Characteristic polynomial, SDP relaxations, Moment matrix, Flatness, Positivstellensatz, Nonnegative polynomial, Sums of squares, Duality

CLC Number:

Sheng-Long Hu. Certifying the Global Optimality of Quartic Minimization over the Sphere[J]. Journal of the Operations Research Society of China, 2022, 10(2): 241-287.

TrendMD

References

[1] Comon, P., Golub, G., Lim, L.-H., Mourrain, B.:Symmetric tensors and symmetric tensor rank. SIAM J. Matrix Anal. Appl. 30, 1254-1279(2008)
[2] Qi, L.:Eigenvalues of a real supersymmetric tensor. J. Symb. Comput. 40, 1302-1324(2005)
[3] Bollobás, B.:Modern Graph Theory. GTM Vol. 184, Springer, Berlin (1998)
[4] Motzkin, T.S., Straus, E.G.:Maxima for graphs and a new proof of a theorem of Túran. Can. J. Math. 17, 533-540(1965)
[5] Garey, M.R., Johnson, D.S.:Computers and Intractability:A Guide to the Theory of NPCompleteness. W.H. Freeman & Company, Publishers, San Francisco (1979)
[6] Nesterov, Y.:Random walk in a simplex and quadratic optimization over convex polytopes. CORE Discussion Papers, 2003/71, https://ideas.repec.org/p/cor/louvco/2003071.html
[7] Hu, S., Sun, D., Toh, K.-C.:Best nonnegative rank-one approximations of tensors. SIAM J. Matrix Anal. Appl. 40, 1527-1554(2019)
[8] Marshall, M.:Optimization of polynomial functions. Can. Math. Bull. 46, 575-587(2003)
[9] Lombardi, H., Perrucci, D., Roy, M.-F.:An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert's 17th Problem. Memoirs of the American Mathematical Society, Vol. 263, No. 1277(2020)
[10] Golub, G.H., Van Loan, C.F.:Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore, MD (2013)
[11] Bertsekas, D.P.:Nonlinear Programming, 2nd edn. Athena Scientific, Belmont, USA (1999)
[12] Li, Y., Hu, S., Wang, J., Huang, Z.H.:An introduction to the computational complexity of matrix multiplication. J. Oper. Res. Soc. China 8, 29-43(2020)
[13] Hartshorne, R.:Algebraic Geometry. Graduate Texts in Mathematics, Vol. 52. Springer, New York (1977)
[14] Shafarevich, I.R.:Basic Algebraic Geometry, Vol I and Vol II. Springer, New York (1977)
[15] Griffiths, P., Harris, J.:Priniciples of Algebraic Geometry. Wiley (1978)
[16] Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V.:Discriminants. Resultants and Multidimensional Determinants. Birkhäuser, Boston (1994)
[17] Hu, S., Huang, Z.H., Ling, C., Qi, L.:On determinants and eigenvalue theory of tensors. J. Symb. Comput. 50, 508-531(2013)
[18] Eisenbud, D.:Commutative Algebra with a View Toward Algebraic Geometry. Graduate Tests in Mathematics, Vol. 150, Springer, New York (2004)
[19] Cayley, A.:On the theory of linear transformations. Cambridge Math. J. 4, 1-16(1845)
[20] Hu, S., Qi, L.:The E-eigenvectors of tensors. Linear Multilinear A. 62, 1388-1402(2014)
[21] Chow, W.-L.:On compact complex analytic varieties. Am. J. Math. 71, 893-914(1949)
[22] Okonek, C., Schneider, M., Spindler, H.:Vector Bundles on Complex Projective Spaces. Progress in Mathematics, Vol. 3, Birkhäuser, Boston (1980)
[23] Fornaess, J.E., Sibony, N.:Complex dynamics in higher dimension. I, Astérisque 222, 201-231(1994)
[24] Cartwright, D., Sturmfels, B.:The number of eigenvalues of a tensor. Linear Algebra Appl. 438, 942-952(2013)
[25] Friedland, S., Ottaviani, G.:The number of singular vector tuples and uniqueness of best rank-one approximation of tensors. Found. Comput. Math. 14, 1209-1242(2014)
[26] Oeding, L., Ottaviani, G.:Eigenvectors of tensors and algorithms for Waring decomposition. J. Symbolic Comput. 54, 9-35(2013)
[27] Abo, H., Seigal, A., Sturmfels, B.:Eigenconfigurations of tensors, in Algebraic and Geometric Methods in Discrete Mathematics, Contemp. Math., 685, American Mathematical Society, Providence, RI, pp. 1-25(2017)
[28] Ni, G., Qi, L., Wang, F., Wang, Y.:The degree of the E-characteristic polynomial of an even order tensor. J. Math. Anal. Appl. 329, 1218-1229(2007)
[29] Graf von Bothmer, H.-C., Ranestad, K.:A general formula for the algebraic degree in semidefinite programming. Bull. Lond. Math. Soc. 41, 193-197(2009)
[30] Nie, J., Ranestad, K.:Algebraic degree of polynomial optimization. SIAM J. Optim. 20, 485-502(2009)
[31] Nie, J., Ranestad, K., Sturmfels, B.:The algebraic degree of semidefinite programming. Math. Program. 122, 379-405(2010)
[32] Kozhasov, K.:On fully real eigenconfigurations of tensors. SIAM J. Appl. Algebra Geometry 2, 339-347(2018)
[33] Breiding, P.:How many eigenvalues of a random symmetric tensor are real. Trans. AMS 372, 7857-7887(2019)
[34] Draisma, J., Horobet, E.:The average number of critical rank-one approximations to a tensor. Linear & Multilinear Algebra 64, 2498-2518(2016)
[35] Breiding, P.:The expected number of eigenvalues of a real Gaussian tensor. SIAM J. Appl. Algebra Geom. 1, 254-271(2017)
[36] Bott, R., Tu, L.W.:Differential Forms in Algebraic Topology. Springer (1982)
[37] do Carmo, M.P.:Riemannian Geometry. Springer, Berlin (1992)
[38] Hu, S., Li, G.:Convergence rate analysis for the higher order power method in best rank one approximations of tensors. Numer. Math. 140, 993-1031(2018)
[39] Hu, S.:Nondegeneracy of eigenvectors and singular vector tuples of tensors. arXiv:2104.05900(2021)
[40] Hu, S., Ye, K.:Linear convergence of an alternating polar decomposition method for low rank orthogonal tensor approximations. arXiv:1912.04085(2019)
[41] Schmüdgen, K.:The K-moment problem for compact semi-algebraic sets. Mathematische Annalen 289, 203-206(1991)
[42] Bhatia, R.:Matrix Analysis. Springer, New York (1997)
[43] Stewart, G.W., Sun, J.-G.:Matrix Perturbation Theory. Academic Press, New York (1990)
[44] Wilkinson, J.H.:The Algebraic Eigenvalue Problem. Clarendon Press, Oxford (1965)
[45] Lewis, A.S.:The convex analysis of unitarily invariant matrix functions. Arch. Math. 2, 173-183(1995)
[46] Lancaster, P.:On eigenvalues of matrices dependent on a parameter. Numerische Mathematik 6, 377-387(1964)
[47] Sun, J.-G.:Eigenvalues and eigenvectors of a matrix dependent on several parameters. J. Comput. Math. 3, 351-364(1985)
[48] Torki, M.:Second-order directional derivatives of all eigenvalues of a symmetric matrix. Nonlinear Anal. 46, 1133-1150(2001)
[49] Watson, G.A.:Characterization of the subdifferent of some matrix norms. Linear Algebra Appl. 170, 33-45(1988)
[50] Ding, C., Sun, D.F., Sun, J., Toh, K.C.:Spectral operators of matrices. Math. Program. 168, 509-531(2018)
[51] Ding, C., Sun, D.F., Sun, J., Toh, K.C.:Spectral operators of matrices:semismoothness and characterizations of the generalized Jacobian. SIAM J. Optim. 30, 630-659(2020)
[52] Sun, D.F., Sun, J.:Semismooth matrix valued functions. Math. Oper. Res. 27, 150-169(2002)
[53] Zhao, X.Y., Sun, D.F., Toh, K.-C.:A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737-1765(2010)
[54] Bonnans, J.F., Shapiro, A.:Perturbation Analysis of Optimization Problems. Springer, New York (2000)
[55] Cox, D., Little, J., Ó Shea, D.:Ideals, Varieties, and Algorithms:An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, New York (2006)
[56] Cox, D., Little, J., Ó Shea, D.:Using Algebraic Geometry. Springer, New York (1998)
[57] Sturmfels, B.:Solving Systems of Polynomial Equations. American Mathematical Society, Providence (2002)
[58] Macaulay, F.:Some formulae in elimination. Proc. London Math. Soc. 33, 3-27(1902)
[59] Sylvester, J.J.:On a theory of syzygetic relations of two rational integral functions, comprising an application to the theory of sturm's functions, and that of the greatest algebraical common measure. Philosophical Transactions 143, 407-548(1853)
[60] Qi, L.:Eigenvalues and invariants of tensors. J. Math. Anal. Appl. 325, 1363-1377(2007)
[61] Qi, L., Luo, Z.:Tensor Analysis:spectral theory and special tensors. SIAM (2017)
[62] Hu, S., Qi, L.:E-characteristic polynomial of a tensor of dimension two. Appl. Math. Lett. 26, 225-231(2013)
[63] Bochnak, J., Coste, M., Roy, M.-F.:Real Algebraic Geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete, Vol. 36, Springer, Berlin (1998)
[64] Marshall, M.:Positive Polynomials and Sums of Squares. Mathematical Surveys and Monographs, Vol. 146, AMS (2008)
[65] Prestel, A., Delzell, C.N.:Positive Polynomials-From Hilberts 17th Problem to Real Algebra. Springer, Berlin (2001)
[66] Hilbert,D.:Überdie Darstellungdefiniter Formenals Summevon Formenquadraten.Mathematische Annalen 32, 342-350(1888)
[67] Reznick, B.:Some concrete aspects of Hilberts 17th problem, in Real Algebraic Geometry and Ordered Structures, C.N. Delzell and J.J. Madden (eds.), Contemporary Mathematics, 253:251-272(2000)
[68] Eisenbud, D., Green, M., Harris, J.:Cayley-Bacharach theorems and conjectures. Bull. Am. Math. Soc. 33, 295-324(1996)
[69] Blekherman, G.:Nonnegative polynomials and sums of squares. J. Am. Math. Soc. 25, 617-635(2012)
[70] Choi, M.-D., Lam, T.-Y.:Extremal positive semidefinite forms. Math. Ann. 231, 1-18(1977)
[71] Artin, E.:Über die Zerlegung definiter Funnktionen in Quadrate. Hamb. Abh. 5, 100-115(1927)
[72] Krivine, J.L.:Anneaux préordonn'es. J. Analyse Math. 12, 307-326(1964)
[73] Stengle, G.:A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Math. Ann. 207, 87-97(1974)
[74] Schweighofer, M.:On the complexity of Schmüdgen's Positivstellensatz. J. Complexity 20, 529-543(2004)
[75] Putinar, M.:Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42, 969-984(1993)
[76] Schweighofer, M.:Optimization of polynomials on compact semialgebraic sets. SIAM J. Optim. 15(3), 805-825(2005)
[77] de Klerk, E., Laurent, M., Parrilo, P.:On the equivalence of algebraic approaches to the minimization offormsonthesimplex,inPositivePolynomialsinControl,D.HenrionandA.Garulli(eds.),Lecture Notes on Control and Information Sciences 312:pp. 121-133, Springer, Berlin (2005)
[78] Nie, J., Schweighofer, M.:On the complexity of Putinar's Positivstellensatz. J. Complexity 23(1), 135-150(2007)
[79] Reznick, B.:Uniform denominators in Hilbert's seventeenth problem. Math. Z. 220, 75-97(1995)
[80] Powers, V., Reznick, B.:A new bound for Pólya's theorem with applications to polynomials positive on polyhedra. J. Pure Appl. Algebra 164, 221-229(2001)
[81] Handelman,D.:Representingpolynomialsbypositivelinearfunctionsoncompactconvexpolyhedra. Pac. J. Math. 132(1), 35-62(1988)
[82] Krivine, J.L.:Quelques propriétés des préordres dans les anneaux commutatifs unitaires. C.R. Académie des Sciences de Paris 258, 3417-3418(1964)
[83] Blekherman, G.:There are significantly more nonnegative polynomials than sums of squares. Isreal J. Math. 153, 355-380(2006)
[84] Wolkowicz, H., Saigal, R., Vandenberghe, L.:Handbook of Semidefinite Programming:Theory, Algorithms and Applications. Kluwer Academic Publishers, Boston (2000)
[85] Nestrov, Y., Nemirovski, A.:Interior Point Polynomial Time Methods in Convex Programming. Society for Industrial and Applied Mathematics, Philadelphia (1994)
[86] Sturm,J.F.:SeDuMi1.02:AMatlabtoolboxforoptimizationoversymmetriccones.Optim.Methods Softw., 11& 12:625-653(1999)
[87] Fujisawa, K., Futakata, Y., Kojima, M., Matsuyama, S., Nakamura, S., Nakata, K., Yamashita, M.:SDPA-M (semidefinite programming algorithm in Matlab), http://homepage.mac.com/klabtitech/sdpa-homepage/download.html
[88] Toh, K.C., Todd, M.J., Tutuncu, R.H.:SDPT3:A Matlab software package for semidefinite programming. Optim. Methods Softw. 11, 545-581(1999)
[89] Yang, L.Q., Sun, D.F., Toh, K.-C.:SDPNAL+:a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7, 331-366(2015)
[90] Shor, N.Z.:Quadratic optimization problems. Soviet J. Comput. Syst. Sci. 25, 1-11(1987)
[91] Shor, N.Z.:Class of global minimum bounds of polynomial functions. Cybernetics, 23(6):731-734. Russian orig.:Kibernetika, 6:9-11(1987)
[92] Shor, N.Z.:An approach to obtaining global extremums in polynomial mathematical programming problems. Kibernetika 5, 102-106(1987)
[93] Shor, N.Z.:Nondifferentiable Optimization and Polynomial Problems. Kluwer, Dordrecht (1998)
[94] Nesterov, Y.:Squared functional systems and optimization problems, in High Performance Optimization, J. B. G. Frenk, C. Roos, T. Terlaky, and S. Zhang, eds., Kluwer Academic Publishers, Dordrecht, The Netherlands, pp. 405-440(2000)
[95] Nesterov, Y.:Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Softw. 9, 141-160(1998)
[96] Parrilo, P.A.:Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD Thesis, Calif. Inst. Tech, Pasadena (2000)
[97] Parrilo, P.A.:Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2), 293-320(2003)
[98] Parrilo, P.A., Sturmfels, B.:Minimizing polynomial functions, in Algorithmic and Quantitative Real Algebraic geometry, S. Basu and L. Gonzáles-Vega, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 60, pp. 83-99(2003)
[99] Lasserre, J.B.:Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796-817(2001)
[100] Laurent, M.:Sums of squares, moment matrices and optimization over polynomials, in Emerging Applications of Algebraic Geometry, IMA Vol. Math. Appl., 149, M. Putinar and S. Sullivant, eds., pp. 157-270, Springer, New York (2009)
[101] Ben-Tal, A., Nemirovskii, A.:Lectures on Modern Convex Optimization:Analysis, Algorithms, and Engineering Applications. SIAM, Philadelphia (2001)
[102] de Klerk, E., Pasechnik, D.V.:Approximating the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875-892(2002)
[103] Nie, J.:Sums of squares methods for minimizing polynomial forms over spheres and hypersurfaces. Front. Math. China 7, 321-346(2012)
[104] Nie, J., Wang, L.:Semidefinite relaxations for best rank-1 tensor approximations. SIAM J. Matrix Anal. Appl. 35, 1155-1179(2014)
[105] Akhiezer, N.I.:The Classical Moment Problem. Hafner, New York (1965)
[106] Curto, R.E., Fialkow, L.A.:Recursiveness, positivity, and truncated moment problems. Houston J. Math. 17, 603-635(1991)
[107] Curto, R.E., Fialkow, L.A.:Solution of the Truncated Complex Moment Problem for Flat Data. Memoirs of the American Mathematical Society 119(568), (1996)
[108] Curto, R.E., Fialkow, L.A.:Flat Extensions of Positive Moment Matrices:recursively generated relations. Memoirs of the American Mathematical Society 136(648), (1998)
[109] Tchakaloff, V.:Formules de cubature mécanique à coefficients non négatifs. Bull. Sci. Math. 81, 123-134(1957)
[110] Bayer, C., Teichmann, J.:The proof of Tchakaloff's theorem. Proc. Am. Math. Soc. 134, 3035-3040(2006)
[111] Laurent, M., Mourrain, B.:A generalized flat extension theorem for moment matrices. Archiv der Mathematik 93(1), 87-98(2009)
[112] Nie, J.:The A-truncated K-moment problem. Found. Comput. Math. 14, 1243-1276(2014)
[113] Nie, J.:Certifying convergence of Lasserre's hierarchy via flat truncation. Math. Program. 142, 485-510(2013)
[114] Laurent, M.:Semidefinite representations for finite varieties. Math. Program. 109, 1-26(2007)
[115] Nie, J.:Optimality conditions and finite convergence of Lasserre's hierarchy. Math. Program. 146, 97-121(2014)
[116] Nie, J., Demmel, J., Sturmfels, B.:Minimizing polynomials via sums of squares over the gradient ideal. Math. Program. 106, 587-606(2006)
[117] Lasserre, J.B., Laurent, M., Rostalski, P.:Semidefinite characterization and computation of real radical ideals. Found. Comput. Math. 8, 607-647(2008)
[118] Henrion, D., Lasserre, J.-B.:Detecting global optimality and extracting solutions in GloptiPoly, in Positive Polynomials in Control, D. Henrion and A. Garulli (eds.), Lecture Notes on Control and Information Sciences, 312:pp. 293-310, Springer, Berlin (2005)
[119] Henrion, D., Lasserre, J.-B.:GloptiPoly:Global optimization over polynomials with Matlab and SeDuMi. ACM Trans. Math. Soft. 29, 165-194(2003)
[120] Corless, R.M., Gianni, P.M., Trager, B.M.:A reordered Schur factorization method for zerodimensional polynomial systems with multiple roots. Proc. ACM Int. Symp. Symbolic and Algebraic Computation, pp. 133-140, Maui, Hawaii (1997)
[121] Sun, D.F., Toh, K.-C., Yuan, Y.C., Zhao, X.Y.:SDPNAL+:A Matlab software for semidefinite programming with bound constraints (version 1.0). Optim. Methods Softw. 35, 87-115(2020)
[122] Helton, J.W., McCullough, S., Vinnikov, V.:Noncommutative convexity arises from linear matrix inequalities. J. Funct. Anal. 240, 105-191(2006)
[123] Blekherman, G., Parrilo, P.A., Thomas, R.R.:Semidefinite Optimization and Convex Algebraic Geometry. SIAM, Philadelphia (2013)
[124] Pang, J.S., Qi, L.:Nonsmooth equations:motivation and algorithms. SIAM. J. Optim. 3, 443-465(1993)
[125] Facchinei, F., Pang, J.S.:Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol 1 and Vol 2. Springer, New York (2003)
[126] Clarke, F.H.:Optimization and Nonsmooth Analysis. Wiley, New York (1983)
[127] Qi, L., Sun, J.:A nonsmooth version of Newton's method. Math. Program. 58, 353-367(1993)
[128] Sun, D.F.:The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications. Math. Oper. Res. 31, 761-776(2006)
[129] Sun, D.F., Sun, J., Zhang, L.W.:The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming. Math. Program. 114, 349-391(2008)
[130] Faraut, U., Korányi, A.:Analysis on Symmetric Cones (Oxford Mathematical Monographs). Oxford University Press, New York (1994)
[131] Kummer, B.:Newton's method for non-differentiable functions. In:Guddat, J., Bank, B., Hollatz, H., Kall, P., Karte, D., Kummer, B., Lommatzsch, K., Tammer, L., Vlach, M., Zimmermann, K. (eds.) Advances in Mathematical Optimization, pp. 114-125. Akademi-Verlag, Berlin (1988)
[132] Rockafellar, R.T., Wets, R.:Variational Analysis. Grundlehren der Mathematischen Wissenschaften, Vol. 317. Springer, Berlin (1998)
[133] Alizadeh, F., Haeberly, J.P.A., Overton, O.L.:Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77, 111-128(1997)
[134] Chan, Z.X., Sun, D.:Constraint nondegeneracy, strong regularity, and nonsingularity in semidefinite programming. SIAM J. Optim. 19, 370-396(2008)
[135] Rockafellar, R.T.:Convex Analysis. Princeton University Press, New Jersey (1970)
[136] Iarrobino, A., Kanev, V.:Power Sums, Gorenstein Algebras, and Determinantal Varieties. Lecture Notes in Mathematics, No. 1721, Springer (1999)
[137] Landsberg, J.M.:Tensors:geometry and applications. Graduate Studies in Mathematics, 128, AMS, Providence, RI, (2012)
[138] Sturmfels, B.:Gröbner Bases and Convex Polytopes. University Lecture Series 8, Amer. Math. Soc., Providence, RI (1996)
[139] Cox, D., Little, J., Schenck, H.:Toric Varieties. Graduate Studies in Mathematics, Volume 124, AMS (2011)
[140] Sanyal, R., Sottile, F., Sturmfels, B.:Orbitopes. Mathematika 57, 275-314(2011)
[141] Gouveia, J., Parrilo, P.A., Thomas, R.R.:Theta bodies for polynomial ideals. SIAM J. Optim. 20, 2097-2118(2010)
[142] Draisma, J., Horobet, E., Ottaviani, G., Sturmfels, B., Thomas, R.R.:The Euclidean distance degree of an algebraic variety. Found. Comput. Math. 16, 99-149(2016)
[143] Nie, J.:An exact Jacobian SDP relaxation for polynomial optimization. Math. Program. 137, 225-255(2013)
[144] Reznick, B.:Extremal PSD forms with few terms. Duke Math. J. 45, 363-374(1978)
[145] Nie, J., Demmel, J.:Sparse SOS relaxations for minimizing functions that are summation of small polynomial. SIAM J. Optim. 19, 1534-1558(2009)
[146] Waki, H., Kim, S., Kojima, M., Muramatsu, M.:Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17(1), 218-242(2006)
[147] Gaterman, K., Parrilo, P.:Symmetry groups, semidefinite programs and sums of squares. J. Pure Appl. Algebra 192, 95-128(2004)
[148] Parrilo, P.A.:Exploiting algebraic structure in sum of squares programs, in Positive Polynomials in Control, D. Henrion and A. Garulli, eds., LNCIS 312, pp. 181-194(2005)
[149] Vallentin, F.:Symmetry in semidefinite programs. Linear Algebra Appl. 430, 360-369(2009)
[150] Lasserre, J.B.:Convergent semidefinite relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17, 822-843(2006)