Approximation algorith ms for nonnegative polynomial optimization problems over unit spheres

doi:10.1007/s11464-017-0644-1

Front. Math. China

2017, Vol. 12

Issue (6) : 1409-1426 https://doi.org/10.1007/s11464-017-0644-1

RESEARCH ARTICLE

Approximation algorith ms for nonnegative polynomial optimization problems over unit spheres

Xinzhen ZHANG¹, Guanglu ZHOU²(

), Louis CACCETTA², Mohammed ALQAHTANI²

¹. School of Mathematics, Tianjin University, Tianjin 300072, China
². Department of Mathematics and Statistics, Curtin University, Perth, Australia

Download: PDF(198 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Guanglu ZHOU

Issue Date: 27 November 2017

Cite this article:

Xinzhen ZHANG,Guanglu ZHOU,Louis CACCETTA, et al. Approximation algorith ms for nonnegative polynomial optimization problems over unit spheres[J]. Front. Math. China, 2017, 12(6): 1409-1426.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-017-0644-1
https://academic.hep.com.cn/fmc/EN/Y2017/V12/I6/1409

1	ChenB, HeS, LiZ, ZhangS. Maximum block improvement and polynomial optimization.SIAM J Optim, 2012, 22: 87–107 https://doi.org/10.1137/110834524
2	HeS, LiZ, ZhangS. Approximation algorithms for homogeneous polynomial optimization with quadratic constraints.Math Program, 2010, 125: 353–383 https://doi.org/10.1007/s10107-010-0409-z
3	HeS, LuoZ, NieJ, ZhangS. Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization.SIAM J Optim, 2008, 19: 503–523 https://doi.org/10.1137/070679041
4	HenrionD, LasserreJ B, LoefbergJ. GloptiPoly 3: Moments, optimization and semidefinite programming.Optim Methods Softw, 2009, 24: 761–779 https://doi.org/10.1080/10556780802699201
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 https://doi.org/10.1007/s10957-014-0652-1
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 https://doi.org/10.1007/s10957-013-0293-9
7	JiangB, MaS, ZhangS. Alternating direction method of multipliers for real and complex polynomial optimization models.Optimization, 2014, 63: 883–898 https://doi.org/10.1080/02331934.2014.895901
8	KoldaT G, MayoJ R. Shifted power method for computing tensor eigenvalues.SIAM J Matrix Anal Appl, 2012, 32: 1095–1124 https://doi.org/10.1137/100801482
9	LasserreJ B. Global optimization with polynomials and the problem of moments.SIAM J Optim, 2001, 11: 796–817 https://doi.org/10.1137/S1052623400366802
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 https://doi.org/10.1007/978-0-387-09686-5_7
11	LingC, NieJ, QiL, YeY. Bi-quadratic optimization over unit spheres and semidefinite programming relaxations.SIAM J Optim, 2009, 20: 1286–1310 https://doi.org/10.1137/080729104
12	NieJ. Sum of squares methods for minimizing polynomial functions over spheres and hypersurfaces.Front Math China, 2012, 7: 321–346 https://doi.org/10.1007/s11464-012-0187-4
13	QiL. Eigenvalues of a real supersymmetric tensor.J Symbolic Comput, 2005, 40: 1302–1324 https://doi.org/10.1016/j.jsc.2005.05.007
14	QiL, TeoK L. Multivariate polynomial minimization and its applications in signal processing.J Global Optim, 2003, 26: 419–433 https://doi.org/10.1023/A:1024778309049
15	SoA M-C. Deterministic approximation algorithms for sphere contained homogeneous polynomial optimization problems.Mathe Program, 2011, 129: 357–382 https://doi.org/10.1007/s10107-011-0464-0
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 https://doi.org/10.1002/nla.1996
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 https://doi.org/10.1002/nla.822
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 https://doi.org/10.4208/jcm.1110-m11si09
19	ZhangX, LingC, QiL. Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints.J Global Optim, 2010, 49: 293–311 https://doi.org/10.1007/s10898-010-9545-5
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 https://doi.org/10.1137/110835335
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 https://doi.org/10.1090/S0025-5718-2012-02577-4
23	ZhouG, CaccettaL, TeoK, WuS-Y. Nonnegative polynomial optimization over unit spheres and convex programming relaxations.SIAM J Optim, 2012, 22: 987–1008 https://doi.org/10.1137/110827910

[1]	Jiawang NIE. Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces[J]. Front Math Chin, 2012, 7(2): 321-346.
[2]	Xing WANG, Dachuan XU, Xinyuan ZHAO. A primal-dual approximation algorithm for stochastic facility location problem with service installation costs[J]. Front Math Chin, 2011, 6(5): 957-964.
[3]	Weiping SHANG, Pengjun WAN, Xiaodong HU, . Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks[J]. Front. Math. China, 2010, 5(1): 75-87.

Viewed

Full text

Abstract

Cited

Shared

Discussed