Approximation algorithms for nonnegative polynomial optimization problems over unit spheres

Abstract

We consider approximation algorithms for nonnegative polynomial optimization problems over unit spheres. These optimization problems have wide applications e.g., in signal and image processing, high order statistics, and computer vision. Since these problems are NP-hard, we are interested in studying on approximation algorithms. In particular, we propose some polynomial-time approximation algorithms with new approximation bounds. In addition, based on these approximation algorithms, some efficient algorithms are presented and numerical results are reported to show the efficiency of our proposed algorithms.

Keywords

Approximation algorithm / polynomial optimization / approximation bound

References

[1] ChenB, HeS, LiZ, ZhangS. Maximum block improvement and polynomial optimization.SIAM J Optim, 2012, 22: 87–107

[2] HeS, LiZ, ZhangS. Approximation algorithms for homogeneous polynomial optimization with quadratic constraints.Math Program, 2010, 125: 353–383

[3] HeS, LuoZ, NieJ, ZhangS. Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization.SIAM J Optim, 2008, 19: 503–523

[4] HenrionD, LasserreJ B, LoefbergJ. GloptiPoly 3: Moments, optimization and semidefinite programming.Optim Methods Softw, 2009, 24: 761–779

[5] HuS, LiG, QiL. A tensor analogy of Yuan’s alternative theorem and polynomial optimization with sign structure.J Optim Theory Appl, 2016, 168: 446–474

[6] HuS, LiG, QiL, SongY. Finding the maximum eigenvalue of essentially nonnegative symmetric tensors via sum of squares programming.J Optim Theory Appl, 2013, 158: 717–738

[7] JiangB, MaS, ZhangS. Alternating direction method of multipliers for real and complex polynomial optimization models.Optimization, 2014, 63: 883–898

[8] KoldaT G, MayoJ R. Shifted power method for computing tensor eigenvalues.SIAM J Matrix Anal Appl, 2012, 32: 1095–1124

[9] LasserreJ B. Global optimization with polynomials and the problem of moments.SIAM J Optim, 2001, 11: 796–817

[10] LaurentM. Sum of squares, moment matrices and optimization over polynomials. In: Putinar M, Sullivant S, eds. Emerging Applications of Algebra Geometry. IMA Volumes in Mathematics and its Applications, Vol 149.Berlin: Springer, 2009, 157–270

[11] LingC, NieJ, QiL, YeY. Bi-quadratic optimization over unit spheres and semidefinite programming relaxations.SIAM J Optim, 2009, 20: 1286–1310

[12] NieJ. Sum of squares methods for minimizing polynomial functions over spheres and hypersurfaces.Front Math China, 2012, 7: 321–346

[13] QiL. Eigenvalues of a real supersymmetric tensor.J Symbolic Comput, 2005, 40: 1302–1324

[14] QiL, TeoK L. Multivariate polynomial minimization and its applications in signal processing.J Global Optim, 2003, 26: 419–433

[15] SoA M-C. Deterministic approximation algorithms for sphere contained homogeneous polynomial optimization problems.Mathe Program, 2011, 129: 357–382

[16] WangY, CaccettaL, ZhouG. Convergence analysis of a block improvement method for polynomial optimization over unit spheres.Numer Linear Algebra Appl, 2015, 22: 1059–1076

[17] ZhangL, QiL. Linear convergence of an algorithm for computing the largest eigenvalue of a nonnegative tensor.Numer Linear Algebra Appl, 2012, 19: 830–841

[18] ZhangL, QiL, XuY. Finding the largest eigenvalue of an irreducible nonnegative tensor and linear convergence for weakly positive tensors.J Comput Math, 2012, 30: 24–33

[19] ZhangX, LingC, QiL. Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints.J Global Optim, 2010, 49: 293–311

[20] ZhangX, LingC, QiL. The best rank-1 approximation of a symmetric tensor and related spherical optimization problems.SIAM J Matrix Anal Appl, 2012, 33: 806–821

[21] ZhangX, LingC, QiL, WuE X. The measure of diffusion skewness and kurtosis in magnetic resonance imaging.Pac J Optim, 2010, 6: 391–404

[22] ZhangX, QiL, YeY. The cubic spherical optimization problems.Math Comp, 2012, 81: 1513–1525

[23] ZhouG, CaccettaL, TeoK, WuS-Y. Nonnegative polynomial optimization over unit spheres and convex programming relaxations.SIAM J Optim, 2012, 22: 987–1008

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany