Semidefinite representations for finite varieties. (English) Zbl 1152.90007

This paper studies the following problem: \[ \text{inf\,}f(x)\text{ such that }h_1(x)= 0,\dots, h_n(x)= 0,\;h_{n+1}(x)\geq 0,\dots, h_{n+k}(x)\geq 0, \] where \(f,h_1,\dots, h_{n+k}\in R[x_1,x_2,\dots, x_n]\). That is the problem of minimizing a polynomial over a set defined by polynomial equations and inequalities. It is a central problem in combinational optimization and optimization of a linear or polynomial function over a basic closed semi-algebraic set. When the polynomial equations have a finite set of complex solutions, this problem can be reformulated as a semidefinite problem.
In this paper, the semidefinite represent action involve combinational moment matrix, which are matrix induced by a basic of quotient vector space \(R[x_1,x_2,\dots, x_n]/I\), where \(I\) is the ideal generated by polynomial equations in the problem. This paper proves the finite convergence of a hierarchy of semidefinite relaxation introduced by Lasserre. Semidefinite approximation can be constructed by considering truncated combinatorial, moment, matrices, rank conditions are given in a grid case that ensures the approximation solve the original problem is optimality.


90C30 Nonlinear programming
90C22 Semidefinite programming


Full Text: DOI Link


[1] Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming 58, 295–324 (1993) · Zbl 0796.90041 · doi:10.1007/BF01581273
[2] Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Springer, 2003 · Zbl 1031.14028
[3] Burer, S., Monteiro, R.D.C., Zhang, Y.: Rank-two heuristics for max-cut and other binary quadratic programs. SIAM Journal on Optimization 12, 503–521 (2002) · Zbl 1152.90532 · doi:10.1137/S1052623400382467
[4] Burer, S., Monteiro, R.D.C., Zhang, Y.: Maximum stable set formulations and heuristics based on continuous optimization. Mathematical Programming 94, 137–166 (2002) · Zbl 1023.90071 · doi:10.1007/s10107-002-0356-4
[5] Cox, D.A., Little, J.B., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, 1997
[6] Cox, D.A., Little, J.B., O’Shea, D.: Using Algebraic Geometry. Graduate Texts in Mathematics, Number 185, Springer, New York, 1998 · Zbl 0920.13026
[7] Curto, R.E., Fialkow, L.A.: Solution of the truncated complex moment problem for flat data. Memoirs of the American Mathematical Society vol. 119, n. 568 (1996) · Zbl 0876.30033
[8] Fuglede, B.: The multidimensional moment problem. Expositiones Mathematicae 1, 47–65 (1983) · Zbl 0514.44006
[9] Jibetean, D., Laurent, M.: Semidefinite approximations for global unconstrained polynomial optimization. SIAM Journal on Optimization 16, 490–514 (2005) · Zbl 1103.90073 · doi:10.1137/04060562X
[10] Landau, H.: Classic background of the moment problem. In Moments in Mathematics, Proceedings of Symposia in Applied Mathematics, vol. 37, AMS, Providence, 1987, pp. 1–15
[11] Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization 11, 796–817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802
[12] Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0–1 programs. In: K. Aardal, A.M.H. Gerards, (eds.), Lecture Notes in Computer Science 2081, 293–303 (2001) · Zbl 1010.90515 · doi:10.1007/3-540-45535-3_23
[13] Lasserre, J.B.: Polynomials nonnegative on a grid and discrete representations. Transactions of the American Mathematical Society 354, 631–649 (2001) · Zbl 1052.90064 · doi:10.1090/S0002-9947-01-02898-7
[14] Laurent, M.: A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0-1 programming. Mathematics of Operations Research 28, 470–496 (2003) · Zbl 1082.90084 · doi:10.1287/moor.28.3.470.16391
[15] Laurent, M.: Semidefinite relaxations for Max-Cut. In: The Sharpest Cut: The Impact of Manfred Padberg and His Work. M. Grötschel, ed. MPS-SIAM Series in Optimization 4, 257–290 (2004)
[16] Laurent, M.: Lower bound for the number of iterations in semidefinite relaxations for the cut polytope. Mathematics of Operations Research 28, 871–883 (2003) · Zbl 1082.90085 · doi:10.1287/moor.28.4.871.20508
[17] Laurent, M.: Revisiting two theorems of Curto and Fialkow on moment matrices. Preprint, 2004. To appear in Proceedings of the American Mathematical Society 133, 2965–2976 (2005) · Zbl 1078.14085
[18] Lovász, L.: On the Shannon capacity of a graph. IEEE Transactions on Information Theory IT-25, 1–7 (1979) · Zbl 0395.94021
[19] Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization 1, 166–190 (1991) · Zbl 0754.90039 · doi:10.1137/0801013
[20] Marshall, M.: Optimization of polynomial functions. Canad. Math. Bull. 46, 575–587 (2003) · Zbl 1063.14071 · doi:10.4153/CMB-2003-054-7
[21] Nesterov, Y.: Squared functional systems and optimization problems. In: J.B.G. Frenk, C. Roos, T. Terlaky, S. Zhang, (eds.), High Performance Optimization, Kluwer Academic Publishers, 2000, pp. 405–440 · Zbl 0958.90090
[22] Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, May, 2000
[23] Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming B 96, 293–320 (2003) · Zbl 1043.14018 · doi:10.1007/s10107-003-0387-5
[24] Parrilo, P.A.: An explicit construction of distinguished representations of polynomials nonnegative over finite sets. Preprint, ETH, Zürich, 2002
[25] Parrilo, P., Sturmfels, B.: Minimizing polynomial functions. In: Algorithmic and quantitative real algebraic geometry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 60, AMS, 2003, pp. 83–99 · Zbl 1099.13516
[26] Powers, V., Wörmann, T.: An algorithm for sums of squares of real polynomials. Journal of Pure and Applied Algebra 127, 99–104 (1998) · Zbl 0936.11023 · doi:10.1016/S0022-4049(97)83827-3
[27] Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal 42, 969–984 (1993) · Zbl 0796.12002 · doi:10.1512/iumj.1993.42.42045
[28] Schweighofer, M.: Optimization of polynomials on compact semialgebraic sets. SIAM Journal on Optimization 15, 805–825 (2005) · Zbl 1114.90098 · doi:10.1137/S1052623403431779
[29] Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3, 411–430 (1990) · Zbl 0712.90050 · doi:10.1137/0403036
[30] Shor, N.Z.: An approach to obtaining global extremums in polynomial mathematical programming problems. Kibernetika 5, 102–106 (1987)
[31] Sturmfels, B.: Solving Systems of Polynomial Equations. CBMS, Regional Conference Series in Mathematics, Number 97, AMS, Providence, 2002 · Zbl 1101.13040
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.