The cubic spherical optimization problems

Zhang, Xinzhen; Qi, Liqun; Ye, Yinyu

doi:10.1090/S0025-5718-2012-02577-4

The cubic spherical optimization problems
HTML articles powered by AMS MathViewer

by Xinzhen Zhang, Liqun Qi and Yinyu Ye PDF

Math. Comp. 81 (2012), 1513-1525 Request permission

Abstract:

In this paper, the cubic spherical optimization problems, including the cubic one-spherical/two-spherical/three-spherical optimization problems, are discussed. We first show that the two-spherical optimization problem is a special case of the three-spherical optimization problem. Then we show that the one-spherical optimization problem and the two-spherical optimization problem have the same optimal value when the tensor is symmetric. In addition, NP-hardness of them are established. For the cubic three-spherical optimization problem, we discuss the conditions under which the problem is polynomial time solvable and if the polynomial time approximation scheme (PTAS) exists. Then we present a relative quality bound by finding the largest singular values of matrices. Finally, a practical method for solving the cubic three-spherical optimization problem is proposed and preliminary numerical results are reported.

References

Immanuel M. Bomze and Etienne De Klerk, Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, J. Global Optim. 24 (2002), no. 2, 163–185. Dedicated to Professor Naum Z. Shor on his 65th birthday. MR 1934026, DOI 10.1023/A:1020209017701
J.F. Cardoso, High-order contrasts for independent component analysis. Neural Computation, 11 (1999), 157–192.
P. Comon, Independent component analysis, a new concept? Signal Processing, 36 (1994), 287–314.
Simai He, Zhening Li, and Shuzhong Zhang, Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, Math. Program. 125 (2010), no. 2, Ser. B, 353–383. MR 2733568, DOI 10.1007/s10107-010-0409-z
Eleftherios Kofidis and Phillip A. Regalia, On the best rank-1 approximation of higher-order supersymmetric tensors, SIAM J. Matrix Anal. Appl. 23 (2001/02), no. 3, 863–884. MR 1896822, DOI 10.1137/S0895479801387413
L. De Lathauwer, First-order perturbation analysis of the best rank-$(R_1, R_2, R_3)$ approximation in multilinear algebra. Journal of Chemometrics, 18 (2004), 2–11.
Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle, On the best rank-1 and rank-$(R_1,R_2,\cdots ,R_N)$ approximation of higher-order tensors, SIAM J. Matrix Anal. Appl. 21 (2000), no. 4, 1324–1342. MR 1780276, DOI 10.1137/S0895479898346995
Chen Ling, Jiawang Nie, Liqun Qi, and Yinyu Ye, Biquadratic optimization over unit spheres and semidefinite programming relaxations, SIAM J. Optim. 20 (2009), no. 3, 1286–1310. MR 2546345, DOI 10.1137/080729104
W.S. Lu and S.C. Pei, On optimal low-rank approximation of multidimensional discrete signals. IEEE Transacations on Circuits and Systems II, 45 (1998), 417–422.
Yu. Nesterov, Random walk in a simplex and quadratic optimization over convex polytopes. CORE Discussion Paper 2003/71, CORE, Catholic University of Louvain, Louvain-la-Neuve, Belgium, 2003.
J. Nie, Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces. preprint, 2009.
Liqun Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput. 40 (2005), no. 6, 1302–1324. MR 2178089, DOI 10.1016/j.jsc.2005.05.007
Liqun Qi, Fei Wang, and Yiju Wang, $Z$-eigenvalue methods for a global polynomial optimization problem, Math. Program. 118 (2009), no. 2, Ser. A, 301–316. MR 2470793, DOI 10.1007/s10107-007-0193-6
Tong Zhang and Gene H. Golub, Rank-one approximation to high order tensors, SIAM J. Matrix Anal. Appl. 23 (2001), no. 2, 534–550. MR 1871328, DOI 10.1137/S0895479899352045
Xinzhen Zhang, Chen Ling, Liqun Qi, and Ed Xuekui Wu, The measure of diffusion skewness and kurtosis in magnetic resonance imaging, Pac. J. Optim. 6 (2010), no. 2, 391–404. MR 2668347