×

zbMATH — the first resource for mathematics

An elementary proof for the exact relaxation for rank one moment matrices in multi-polynomial SOS relaxation. (English) Zbl 1450.49004
Author’s abstract: We present an elementary proof for the fact that an optimal rank one moment matrix in the multi-polynomial SOS relaxation gives an exact relaxation. This fact is a fundamental result in multi-polynomial SOS relaxation method for the class of multi-polynomial optimization problems. The multi-polynomial SOS relaxation method is designed by exploring the special structures of the class of multi-polynomial optimization problems, which has the advantage for giving an SDP with size about half of that for the classical SOS relaxation in the general formulation.
MSC:
49J45 Methods involving semicontinuity and convergence; relaxation
Software:
SDPT3; SeDuMi
PDF BibTeX Cite
Full Text: Link
References:
[1] L. De Lathauwer, B. De Moor, J. Vandewalle: On the best rank-1 and rank- (R1, R2, . . . , RN) approximation of higher-order tensors, SIAM J. Matrix Anal. Appl. 21 (2000) 1324-1342. · Zbl 0958.15026
[2] K. Fujisawa, Y. Futakata, M. Kojima, S. Matsuyama, S. Nakamura, K. Nakata, M. Yamashita: SDPA-M (SemiDefinite Programming Algorithm in MATLAB), http://homepage.mac.com/klabtitech/sdpa-homepage/download.html.
[3] R. Hartshorne: Algebraic Geometry, Springer, New York (1977).
[4] T. G. Kolda, B. W. Bader: Tensor decompositions and applications, SIAM Review 51(3) (2009) 455-500. · Zbl 1173.65029
[5] J. Lasserre: Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2001) 796-817. · Zbl 1010.90061
[6] M. Laurent: Sums of squares, moment matrices and optimization over polynomi- als, in: Emerging Applications of Algebraic Geometry, M. Putinar and S. Sullivant (eds.), IMA Vol. Math. Appl. 149, Springer, New York (2009) 157-270.
[7] C. Ling, J. Nie, L. Qi, Y. Ye: Biquadratic optimization over unit spheres and semidefinite programming relaxations, SIAM J. Optim. 20 (2009) 1286-1310. · Zbl 1221.90074
[8] J. Nie: Sums of squares methods for minimizing polynomial forms over spheres and hypersurfaces, Front. Math. China 7 (2012) 321-346. · Zbl 1277.65046
[9] J. Nie, L. Wang: Semidefinite relaxations for best rank-1 tensor approximations, SIAM J. Matrix Analysis Appl. 35 (2014) 1155-1179. · Zbl 1305.65134
[10] P. Parrilo: Semidefinite programming relaxations for semialgebraic problems, Math. Program, Ser. B 96 (2003) 293-320. · Zbl 1043.14018
[11] P. Parrilo, B. Sturmfels: Minimizing polynomial functions, in: Proc. DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, S. Basu and L. Gonzalez-Vega (eds.), American Mathematical Society, Providence (2003) 83-100.
[12] J. F. Sturm: SeDuMi 1.02: A Matlab toolbox for optimization over symmetric cones, Optim. Methods Software 11&12 (1999) 625-653.
[13] K. C. Toh, M. J. Todd, R. H. Tutuncu: SDPT3: A Matlab software package for semidefinite programming, Optim. Methods Software 11 (1999) 545-581. · Zbl 0997.90060
[14] X. Y. Zhao, D. F. Sun, K. C. Toh: A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM J. Optimization 20 (2010) 1737-1765. · Zbl 1213.90175
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.