zbMATH — the first resource for mathematics

Sparsity in sums of squares of polynomials. (English) Zbl 1079.90092
Summary: Representation of a given nonnegative multivariate polynomial in terms of a sum of squares of polynomials has become an essential subject in recent developments of sums of squares optimization and semidefinite programming (SDP) relaxation of polynomial optimization problems. We discuss effective methods to obtain a simpler representation of a “sparse” polynomial as a sum of squares of sparse polynomials by eliminating redundancy.

90C22 Semidefinite programming
Full Text: DOI
[1] Barvinok, A., Pommersheim, J.E.: ?An algorithmic theory of lattice points in polyhedra,? New perspectives in algebraic combinatorics (Berkeley, CA, 1996-97), 91-147, Math. Sci. Res. Inst. Publ., 38, Cambridge Univ. Press, Cambridge, 1999 · Zbl 0940.05004
[2] Boyd, S., Ghaoui, L.E., Feron, E., Balakrishnan, V.: Linear Matrix Inequalities in System and Control Theory, (SIAM, Philadelphia, 1994) · Zbl 0816.93004
[3] Choi, M.D., Lam, T.Y., Reznick, B.: Sums of squares of real polynomials. Proc. Symposia Pure Math. 58 (2), 103-126 (1995) · Zbl 0821.11028
[4] Fukuda, K.: ?cdd and cddplus homepage?, http://www.cs.mcgill.ca/\(\sim\)fukuda/soft/cdd_home/cdd.html, Computer Science, McGill University, 3480 University, Montreal , Quebec, Canada H3A 2A7
[5] Gatermann, K., Parrilo, P.A.: ?Symmetry groups, semidefinite programs and sums of squares?. Working paper, Konrad-Zuse-Zentrum fur Informationstechnik, Takustr. 7, D-14195, Berlin, Germany, 2003
[6] Kojima, M., Kim, S., Waki, H.: ?A general framework for convex relaxation of polynomial optimization problems over cones?. J. Operat. Res. Soc. Japan, 46(2), 125-144 (2003) · Zbl 1049.90052
[7] Lasserre, J.B.: ?Global optimization with polynomials and the problems of moments?. SIAM J. Optimization 11, 796-817 (2001) · Zbl 1010.90061
[8] Lasserre, J.B.: ?An Explicit Equivalent Positive Semidefinite Program for 0-1 Nonlinear Programs?, 2002. To appear in SIAM Journal on Optimization · Zbl 1007.90046
[9] De Loera, J.A., Hemmecke, R., Tauzer, J., Yoshida, R.: LattE, http://www.math.ucdavis.edu/\(\sim\)latte, University of California at San Diago
[10] Parrilo, P.A.: ?Semidefinite programming relaxations for semialgebraic problems?. Math. Programming 96, 293-320 (2003) · Zbl 1043.14018
[11] Prajna, S., Papachristodoulou, A., Parrilo, P.A.: ?SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB ? User?s Guide?. Control and Dynamical Systems, California Institute of Technology, Pasadena, CA 91125 USA, 2002
[12] Putinar, M.: ?Positive polynomials on compact semi-algebraic sets?. Indiana Univ. Math. J. 42, 969-984 (1993) · Zbl 0796.12002
[13] 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
[14] Reznick, B.: ?Extremal psd forms with few terms?. Duke Math. J. 45, 363-374 (1978) · Zbl 0395.10037
[15] Reznick, B.: ?Some concrete aspects of Hilbert?s 17th problem?. In Contemp. Math. 253, 251-272 (2000) · Zbl 0972.11021
[16] Shor, N.Z.: ? Class of global minimization bounds of polynomial functions?. Cybernetics 23, 731-734 (1987) · Zbl 0648.90058
[17] Strum, J.F.: ?SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones?. Optimization Meth. Software 11 & 12, 625-653 (1999)
[18] Todd, M.J., Toh, K.C., Tütüncü, R. H.: ?SDPT3 ? a MATLAB software package for semidefinite programming, version 1.3?. Optimization Meth. Software 11 & 12, 545-581 (1999) · Zbl 0997.90060
[19] Yamashita, M., Fujisawa , K., Kojima, M.: ?Implementation and Evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0)?, September 2002. Optimization Meth. Software 18, 491-505 (2003). · Zbl 1106.90366
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.