Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The cubic spherical optimization problems

Authors: Xinzhen Zhang, Liqun Qi and Yinyu Ye
Journal: Math. Comp. 81 (2012), 1513-1525
MSC (2010): Primary 15A18, 15A69, 90C60
Published electronically: February 3, 2012
MathSciNet review: 2904588
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. I.M. Bomze and E. de Klerk, Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. Journal of Global Optimization, 24 (2002), 163-185. MR 1934026 (2003i:90048)
  • 2. J.F. Cardoso, High-order contrasts for independent component analysis. Neural Computation, 11 (1999), 157-192.
  • 3. P. Comon, Independent component analysis, a new concept? Signal Processing, 36 (1994), 287-314.
  • 4. S. He, Z. Li and S. Zhang, Approximation algorithms for homogeneous polynomial optimization with quadratic constraints. Mathematical Programming, 125 (2011), 353-383. MR 2733568
  • 5. E. Kofidis and P.A. Regalia, On the best rank-1 approximation of higher-order supersymmetric tensors. SIAM Journal on Matrix Analysis and Applications, 23 (2002), 863-884. MR 1896822 (2003a:15029)
  • 6. 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.
  • 7. L. De Lathauwer, B. De Moor, J. Vandewalle, On the best rank-1 and rank-( $ R_1,R_2,\dots , R_N$) approximation of higher-order tensor. SIAM Journal on Matrix Analysis and Applications, 21 (2000), 1324-1342. MR 1780276 (2001i:15034)
  • 8. C. Ling, J. Nie, L. Qi and Y. Ye, Bi-quadratic optimization over unit spheres and semidefinite programming relaxations. SIAM Journal on Optimization, 20 (2009), 1286-1310. MR 2546345 (2010h:90087)
  • 9. 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.
  • 10. 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.
  • 11. J. Nie, Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces. preprint, 2009.
  • 12. L. Qi, Eigenvalues of a real supersymmetric tensor. Journal of Symbolic Computation, 40 (2005), 1302-1324. MR 2178089 (2006j:15031)
  • 13. L. Qi, F. Wang and Y. Wang, Z-Eigenvalue methods for a global optimization polynomial optimization problem. Mathematical Programming, 118 (2009), 301-316. MR 2470793 (2009m:90111)
  • 14. T. Zhang and G.H. Golub, Rank-1 approximation of higher-order tensors. SIAM Journal on Matrix Analysis and Applications, 23 (2001), 534-550. MR 1871328 (2002j:15039)
  • 15. X. Zhang, C. Ling, L. Qi and E.X. Wu, The measure of diffusion skewness and kurtosis in magnetic resonance imaging. Pacific Journal of Optimization, 6 (2010), 391-404. MR 2668347

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 15A18, 15A69, 90C60

Retrieve articles in all journals with MSC (2010): 15A18, 15A69, 90C60

Additional Information

Xinzhen Zhang
Affiliation: Department of Mathematics, School of Science, Tianjin University, Tianjin, 300072, China.

Liqun Qi
Affiliation: Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong.

Yinyu Ye
Affiliation: Department of Management Science and Engineering, Stanford University, Stanford, CA94305 and The Hong Kong Polytechnic University, Hong Kong.

Keywords: Cubic spherical optimization, approximation solution, polynomial time approximation scheme (PTAS)
Received by editor(s): June 4, 2009
Received by editor(s) in revised form: June 2, 2011
Published electronically: February 3, 2012
Additional Notes: The first author is supported by the National Natural Science Foundation of China (Grant Nos. 11101303 and 11171180), and Independent Innovation Fund of Tianjin University
The second author is supported by the Hong Kong Research Grant Council
Article copyright: © Copyright 2012 American Mathematical Society

American Mathematical Society